Optimal Learning through Iterative Sample Recycling

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 128 papers36 conceptsfrozen 2026-10-04

In classical statistical theory, a common "trick" used to make proofs work is sample splitting. To analyze an iterative algorithm, researchers often assume that each step uses a fresh, independent batch of data. This keeps the math clean because it prevents the current state of the model from becoming "correlated" with the data used to update it.

However, in the real world, data is expensive. Discarding a batch of samples after a single gradient step is incredibly wasteful. A growing body of research shows that this independence assumption is often a mathematical convenience rather than a physical necessity. By recycling samples across iterations, we can achieve the same statistical accuracy with significantly less data.

The Cost of Fresh Samples

The traditional requirement for fresh samples at every iteration leads to a sample complexity that scales with the number of iterations. If an algorithm needs $T$ steps to converge, and each step requires $n$ samples to maintain a certain precision, the total cost is $O(n \times T)$.

As Udaya Ghai and Karan Singh demonstrate in Sample-Efficient Agnostic Boosting, this overhead is often the primary bottleneck. By blending a subset of previously used data with a smaller batch of fresh samples, they reduced the sample complexity of agnostic boosting from $O(1/\epsilon^4)$ to $O(1/\epsilon^3)$, moving closer to the theoretical limits of empirical risk minimization.

Why Reuse Works: Beyond Independence

If we use the same data twice, don't we risk overfitting? The core insight of this research direction is that uniform concentration and geometric convergence can protect us from the pitfalls of data dependency.

  1. Uniform Concentration: Instead of requiring a sample to be independent of a specific hypothesis, we prove that the sample is "good enough" for all possible hypotheses in a class simultaneously. Wenhao Zhan, Yuxin Chen, and colleagues used this in Optimal Multi-Distribution Learning to maintain unbiased risk estimates while reusing a cumulative dataset across iterations.
  2. Geometric Convergence: In many non-convex problems, like matrix completion or phase retrieval, the algorithm moves toward the solution so quickly that the "error" introduced by data reuse doesn't have time to accumulate. Yudong Chen and Martin J Wainwright showed in Fast low-rank estimation by projected gradient descent that simple projected gradient descent converges at a geometric rate even when reusing the same data at every step.

Squeezing Information in Reinforcement Learning

Reinforcement Learning (RL) is notoriously sample-hungry. Standard off-policy algorithms often draw a fresh batch of experience for every single update. However, Jiafei Lyu and Zongqing Lu argue in Off-Policy RL Algorithms Can be Sample-Efficient for Continuous Control via Sample Multiple Reuse that this is inefficient. By reusing a single batch for multiple consecutive iterations, the agent can perform a deeper local optimization of the value function, extracting more information from each interaction with the environment.

Similarly, in the offline setting—where we cannot collect new data at all—recycling is mandatory. Gen Li, Yuejie Chi, and Yuting Wei proved in Settling the sample complexity of model-based offline reinforcement learning that reusing the same dataset across all iterations of value iteration does not compromise statistical optimality. This effectively eliminates the need for the "burn-in" datasets or sample-splitting often found in earlier theoretical models.

Engineering Independence

When natural convergence isn't enough to justify reuse, we can "force" the math to work by adding a tiny amount of noise. Ishani Karmarkar and Aaron Sidford introduced a framework in Reusing Samples in Variance Reduction that injects noise into sub-problem solutions. This creates a property they call pseudo-independence, which allows optimization algorithms to recycle random samples without breaking the mathematical guarantees of the solver.

The Shift in Perspective

The recurring theme across these works—from Piotr Indyk’s Fourier sampling to Guoqing Liu’s Evolution Strategies—is a move away from "disposable" data.

By treating data as a persistent resource to be refined rather than a one-time fuel to be consumed, these researchers are bridging the gap between theoretical sample complexity and practical performance. The result is a new generation of algorithms that are not just faster, but fundamentally more efficient with the information they are given.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_optimal_learning_through_iterative_sampl_e77b6579,
  title = {Optimal Learning through Iterative Sample Recycling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-learning-through-iterative-sample-recycling/rdr_e77b65798f0a4554ada2e4c9b0ca4190},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimal_learning_through_iterative_sampl_e77b6579_v1,
  title = {Optimal Learning through Iterative Sample Recycling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimal-learning-through-iterative-sample-recycling/rdr_e77b65798f0a4554ada2e4c9b0ca4190/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}