Reciprocal Learning

Julian Rodemann, Christoph Jansen, Georg Schollmeyer

Presented at NeurIPS 2024, this paper introduces a unifying framework for a wide variety of machine learning paradigms—ranging from active learning to multi-armed bandits—under the banner of Reciprocal Learning.

Reciprocal learning unifies algorithms where models learn from data, and data is iteratively selected by the model. By formalizing this "two-way street," the authors provide the first rigorous convergence guarantees for these methods, demonstrating that stability requires "non-greedy" data updates and probabilistic predictions.

The Challenge of Iterative Learning

We are entering an era of "data scarcity" where simply throwing more parameters at more data is no longer a viable path to progress. This bottleneck has led to a surge in techniques like active learning (choosing which data to label), self-training (using model predictions as labels), and bandits (choosing actions to maximize reward).

While these methods are successful in practice, they are usually studied in silos and lack a unified theoretical foundation for convergence. In a standard supervised learning setup, we know when a model has converged to a minimum. But when the model is constantly changing its own training set, how do we know if the whole system will ever reach a stable point? Most current stopping criteria for these loops are based on heuristics rather than rigorous mathematical proof.

The Reciprocal Learning Framework

The authors propose a decision-theoretic framework that views this process as two interdependent decision problems:

  1. Parameter Selection: Standard Empirical Risk Minimization (ERM) to find the best model for the current data.
  2. Data Selection: Choosing the next set of data points based on the current model’s performance.
Iterative convergence in reciprocal learning, highlighting the importance of the Lipschitz condition on sample adaptation.

The core of their analysis revolves around the Sample Adaption Function, which describes how the training set evolves from one iteration to the next. To prove convergence, they rely on the Banach Fixed-Point Theorem. Essentially, if the change in the data is "small enough" relative to the change in the model (i.e., the function is a contraction), the system will eventually settle into a unique, stable state.

To achieve this necessary "smoothness," the authors identify three critical conditions:

  • Soft Labels: Predictions must be probabilistic (soft) rather than categorical (hard).
  • Regularization/Randomization: Data selection must be either regularized (to prevent jumping to extremes) or randomized (like Thompson sampling).
  • Non-Greedy Updates: The algorithm must be able to both add and remove data points.

Key Insights: Data Regularization and Stability

  • "Lipschitz is All You Need": The paper argues that the key to stability in iterative learning is Lipschitz continuity. If a small change in model parameters leads to a massive, jumpy change in the training data, the system will likely diverge or oscillate forever.
  • The Case for Amending: Most self-training algorithms are "greedy"—they only add new pseudo-labeled data. The authors prove that these greedy versions cannot converge to a fixed point because the sample size grows indefinitely. Instead, they advocate for "amending" strategies that swap out old data for better-informed samples.
Restricted sample and model spaces illustrating the concept of data regularization.
  • Data Regularization as a New Frontier: While we are used to regularizing model weights (like L2 regularization) to prevent overfitting, this paper introduces Data Regularization, which smoothes the data selection criterion itself. Their experiments show this significantly reduces "in-experiment" variance, making the training process much more predictable.
  • Weak Oracles are Better for Stability: In active learning, a "strong oracle" (providing perfect hard labels) can actually prevent convergence. A "weak oracle" (providing noisy or probabilistic labels) provides the mathematical smoothness necessary for the system to reach a stable equilibrium.

Key Results and Limitations

The authors prove that non-greedy reciprocal learning converges at a linear rate to a stable data-parameter combination, provided the sample adaption function is a contraction. Furthermore, they provide a bound showing that the stable point reached by these algorithms is close to the theoretically "optimal" data-parameter fit. Through experiments on the Banknote Authentication dataset (simulating semi-supervised environments with 70-90% unlabeled data), they demonstrated that regularized selection criteria resulted in much more stable parameter trajectories than unregularized versions.

Limitations: The authors acknowledge that their proofs currently require the loss function to be strongly convex and have Lipschitz gradients, which may not cover all complex neural network architectures. Additionally, much of the explicit constructive proof is tailored toward binary classification.

Despite these constraints, this framework paves the way for the "theory-informed" design of future iterative algorithms. It suggests that if we want stable AI that learns on the fly, we need to be as careful about how we select our data as we are about how we tune our weights.

Summary updated

Abstract

We demonstrate that numerous 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 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 converges at linear rates to an approximately optimal model under some 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 active learning, self-training, and bandits.
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