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.
- 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.
- 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.