Reciprocal Learning

Julian Rodemann, Christoph Jansen, Georg Schollmeyer

TL;DR

This paper introduces Reciprocal Learning, a unifying theoretical framework that encompasses active learning, multi-armed bandits, and self-training. By treating data selection and parameter estimation as interdependent decision problems, the authors provide the first rigorous convergence guarantees for these algorithms, proving they reach stable, near-optimal solutions when data selection is regularized or randomized.

What Problem Does This Paper Address?

In classical machine learning, we typically treat data as a static foundation upon which we build a model. However, many modern techniques—like active learning (where the model asks for specific labels) or multi-armed bandits (where the model chooses which "arm" to pull)—turn this into a two-way street. The model learns from the data, but the model’s current state also dictates what data is collected or used next.

While these "data-adaptive" methods are widely used to improve sample efficiency, their theoretical stability is poorly understood. There is no consensus on when to stop these iterative processes, and rigorous proofs of convergence have been largely missing. As we approach an era where high-quality training data is becoming scarce, understanding how models can reliably "learn which data to learn from" is critical.

Figure 1. (A) Classical machine learning fits a model from the model space (restricted by red curve) to a realized sample from the sample space (blue-grey); figure replicated from The Elements of Statistical Learning [34, Figure 7.2]. (B) In reciprocal learning, the realized sample is no longer static, but changes in response to the fit. Grey ellipse indicates restriction of sample space in 𝑡= 2 through realization in 𝑡= 1. Sample in 𝑡thus depends on model in 𝑡−1 and sample in 𝑡−1.

Methods

The authors formalize this feedback loop using the language of Decision Theory. They define a "sample adaptation function" ($f$) that maps the current model and data to the next iteration's dataset.

To prove that these algorithms actually settle down (converge), the authors rely on the Banach fixed-point theorem. For this theorem to work, the reciprocal learning process must be a "contraction"—meaning that as the model changes slightly, the resulting change in the data selection must be even smaller.

The paper identifies three essential "design principles" to ensure this stability:

  1. Non-greedy Adaptation: The algorithm must be able to both add and remove data points (amending the dataset) rather than just infinitely accumulating them.
  2. Probabilistic Predictions: Using "soft labels" (probabilities) instead of "hard labels" (0 or 1) prevents discrete, jerky jumps in the learning process.
  3. Data Regularization or Randomization: Just as we regularize model parameters to prevent overfitting, the authors show we must regularize the data selection process (or use randomization like Thompson Sampling) to ensure the feedback loop remains smooth and contractive.

Datasets

This is a theoretical paper focused on proving mathematical properties and convergence rates. Consequently, it does not perform empirical benchmarks on standard datasets (like ImageNet or GLUE). Instead, it provides mathematical proofs that apply to any dataset satisfying the stated assumptions (e.g., bounded feature spaces and specific loss function properties).

Key Insights and Ideas

  • The Symmetry of Regularization: One of the most elegant insights is that data selection and parameter learning are symmetrical. We are used to regularizing parameters to keep them stable; the authors demonstrate that data regularization is the necessary counterpart to keep the training set stable.
Figure 2. Data regularization is symmetrical to classical regularization, see illustration in The Elements of Statistical Learning [34, Figure 7.2].
  • Greedy Algorithms Don't "Converge": The paper proves that "greedy" algorithms—those that only add data without ever removing or replacing old points—technically cannot converge to a fixed point in the joint space of models and data. This explains why "amending" strategies in self-training are often more stable in practice.
  • Unification: By showing that bandits, active learning, and self-training are all just different flavors of the same "Reciprocal Learning" equation, the authors allow researchers to apply theoretical breakthroughs in one sub-field to all the others.

Key Results

  • Linear Convergence: The authors prove that if the sample adaptation is sufficiently "smooth" (Lipschitz-continuous), reciprocal learning iterates converge at a linear rate to a stable fixed point.
  • Approximate Optimality: They show that this stable fixed point isn't just arbitrary; it is guaranteed to be close to the globally optimal combination of data and parameters.
  • Algorithm-Specific Corollaries:
    • Multi-armed Bandits: Thompson sampling and epsilon-greedy strategies are guaranteed to converge, whereas deterministic strategies like Upper Confidence Bound (UCB) are not.
  • Active Learning: Learning from a "weak oracle" (which provides soft, probabilistic labels) is theoretically more stable than learning from a "strong oracle" (which provides hard labels).

Limitations and Future Work

  • Strict Assumptions: The proofs require the loss function to be strongly convex and have Lipschitz gradients. While common (e.g., Ridge-regularized Logistic Regression), these conditions don't cover all modern deep learning architectures.
  • In-Sample Focus: The analysis focuses on how parameters alter the training sample at hand. It does not yet account for "Performative Prediction" scenarios where a model's deployment changes the entire underlying population (e.g., a credit scoring model changing how people manage their finances).
  • Future Directions: The authors suggest investigating the generalization performance of these stable solutions and exploring "credal sets" (sets of probability distributions) to better identify optimal training samples.

Summary updated

Abstract

We demonstrate that a wide array of machine learning algorithms are specific instances of one single paradigm: reciprocal learning. These instances range from active learning over multi-armed bandits to self-training. We show that all these algorithms do not only learn parameters from data but also vice versa: They iteratively alter training data in a way that depends on the current model fit. We introduce reciprocal learning as a generalization of these algorithms using the language of decision theory. This allows us to study under what conditions they converge. The key is to guarantee that reciprocal learning contracts such that the Banach fixed-point theorem applies. In this way, we find that reciprocal learning algorithms converge at linear rates to an approximately optimal model under relatively mild assumptions on the loss function, if their predictions are probabilistic and the sample adaption is both non-greedy and either randomized or regularized. We interpret these findings and provide corollaries that relate them to specific active learning, self-training, and bandit algorithms.
BibTeX
@inproceedings{rodemann2024reciprocal,
  author = {Julian Rodemann and Christoph Jansen and Georg Schollmeyer},
  title = {{Reciprocal Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=mhhlZeAr67},
}
Figure