Research map / Bandits and online learning / Multi-armed bandits
Reciprocal Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Unifies active learning, self-training, and multi-armed bandits as "reciprocal learning" (data depends on the current model fit) and proves linear convergence under Lipschitz sample adaption with regularized or randomized, non-greedy data selection.
Problem
Many ML algorithms (active learning, self-training, bandits) alter training data based on the current model fit, but there is no general theory of whether such iterative parameter-data loops converge or what they converge to.
Approach
Formalize these algorithms as reciprocal learning: iterated ERM where the empirical training distribution is updated by a sample adaption function that depends on the previous fit. Show that if this sample adaption is Lipschitz with a small enough constant (non-greedy, probabilistic predictions, regularized or randomized selection), the iteration is a contraction and the Banach fixed-point theorem
Key results
- Non-greedy reciprocal learning with Lipschitz sample adaption (L <= (1+beta/gamma)^-1) converges at a linear rate to a fixed point (theorem on non-greedy convergence).
- Convergent parameters satisfy ||theta_c - theta*||_2 <= 2 L_loss L / gamma of the optimal data-parameter combination.
- Greedy reciprocal learning (only adding data) does not converge; corollaries state amending self-training and Thompson/epsilon-greedy bandits converge while UCB is not guaranteed, and strong-oracle active learning is not guaranteed to converge.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use non-greedy sample adaption that adds and removes data, with a Lipschitz constant satisfying L ≤ (1 + β/γ)^-1 | Reciprocal learning · Non-greedy reciprocal learning | convergence: L ≤ (1 + \frac{\beta}{\gamma})^{-1} | Helped |
| Make sample adaption non-Lipschitz | Non-greedy reciprocal learning · Non-greedy reciprocal learning | convergence | Hurt |
| Only add data and do not remove any | Reciprocal learning · Greedy reciprocal learning | convergence | Hurt |
| Add soft pseudo-labels and use regularized or randomized data selection | Self-training · Self-training | convergence | Helped |
| Use Thompson sampling or epsilon-greedy in non-greedy bandits | Multi-armed bandits · Multi-armed bandits | convergence | Helped |
| Use deterministic UCB data selection | Multi-armed bandits · Multi-armed bandits | convergence guarantee | Hurt |
| Use hard labels from a strong oracle | Active learning · Active learning | convergence guarantee | Hurt |
| Use soft labels from a weak oracle with regularized or randomized data selection | Active learning · Active learning | convergence | Helped |
| Use regularized data selection and soft predictions | Reciprocal learning · Greedy and non-greedy reciprocal learning | sample-adaption Lipschitz continuity | Helped |
| Use randomized data selection and soft predictions | Reciprocal learning · Greedy and non-greedy reciprocal learning | sample-adaption Lipschitz continuity | Helped |
Surprising findings
- Greedy algorithms that only add data never converge, so amending (add-and-remove) self-training is needed for convergence.
- Standard logistic loss is not strongly convex, so regularization of parameters is needed for convergence guarantees.
Limitations
- Sufficient conditions only; failure of conditions does not imply divergence.
- Requires strong convexity and Lipschitz gradients of the loss, limiting applicability.
- Analysis restricted to binary classification for the explicit Lipschitz proofs and to training data (population fixed); no empirical experiments.
Experimental setup
Builds on: performative prediction Banach fixed-point theorem Wasserstein distance Thompson sampling upper confidence bound
Closest papers by meaning
- On the Stability and Generalization of Meta-Learning (NeurIPS 2024 · similarity 0.86)
- Causal Bandits: The Pareto Optimal Frontier of Adaptivity, a Reduction to Linear Bandits, and Limitations around Unknown Marginals (ICML 2024 · similarity 0.86)
- Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update (NeurIPS 2025 · similarity 0.85)
- A Classification View on Meta Learning Bandits (ICML 2025 · similarity 0.85)
- Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits (NeurIPS 2024 · similarity 0.85)
- Near-Optimal Solutions of Constrained Learning Problems (ICLR 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.