Proving Convergence Under Iterative Data Reuse

88 concepts59 papers2 proposals

When analyzing statistical algorithms, we often rely on a fundamental assumption: the data used to evaluate a model must be independent of the model itself. For simple, single-step estimators, this assumption is easy to satisfy. However, modern machine learning relies heavily on iterative algorithms—such as the Expectation-Maximization (EM) algorithm, Alternating Minimization (AltMin), and Gradient Descent—which update their parameters step-by-step based on data.

This iterative process introduces a profound theoretical challenge. Once an algorithm uses a dataset to update its parameters, the new parameters become statistically dependent on that exact dataset. If the algorithm reuses the same data in the next iteration, standard independence assumptions break down.

For decades, a massive gap existed between theory and practice. To make mathematical proofs tractable, theorists assumed a technique called sample splitting (or resampling), where an algorithm consumes a completely fresh batch of data at every single iteration. In practice, however, practitioners routinely violate this assumption, successfully reusing the same dataset across hundreds of iterations without experiencing the catastrophic overfitting or instability that naive theory might predict.

Recent breakthroughs in mathematical statistics have begun to bridge this gap, developing sophisticated tools to analyze iterative algorithms under full data reuse.


The Statistical Feedback Loop

To understand why data reuse complicates mathematical analysis, consider a generic iterative optimization loop. We start with an initial parameter estimate $\theta_0$ and a fixed dataset $D$. At iteration $t$, the algorithm computes a new estimate:

$$\theta_{t+1} = f(\theta_t, D)$$

If $D$ consists of independent and identically distributed (i.e., i.i.d.) samples, $\theta_1$ is a function of those samples. When we proceed to compute $\theta_2$, the function $f(\theta_1, D)$ now evaluates the dataset $D$ using a parameter $\theta_1$ that already encodes information about $D$.

As Jain et al. point out in the context of matrix completion, these intricate statistical dependencies invalidate standard concentration inequalities (like Hoeffding's or Bernstein's bounds), which require the data to be independent of the evaluation point. Without independence, the noise in the dataset can couple with the algorithm's state, potentially driving the trajectory toward unrepresentative local minima or creating complex statistical biases (Zhong et al.; Ghosh et al.).

Sample Splitting (Theory):
Iteration 1: Data Batch 1 ──> θ_1
Iteration 2: Data Batch 2 ──> θ_2
Iteration 3: Data Batch 3 ──> θ_3  (Data-inefficient, but mathematically independent)

Iterative Data Reuse (Practice):
Iteration 1: Full Dataset ──> θ_1 ──┐
                                    ▼
Iteration 2: Full Dataset ──> θ_2 ──┤ (Statistical feedback loop)
                                    ▼
Iteration 3: Full Dataset ──> θ_3 ──┘

The Fiction of Sample Splitting

To bypass this feedback loop, early convergence proofs mandated sample splitting. If an algorithm requires $T$ iterations to converge, the dataset is partitioned into $T$ independent blocks, and block $t$ is used exclusively at step $t$ (Kwon et al.).

While sample splitting guarantees statistical independence at each step, it suffers from two fatal flaws:

  1. Data Inefficiency: It multiplies the required sample complexity by the number of iterations $T$, making it highly impractical for data-scarce regimes (Cai et al.).
  2. Algorithmic Mismatch: It fails to explain why standard, "no-split" implementations actually work in the real world (Chen et al.; Wu et al.).

To resolve this, researchers have developed three primary mechanisms to prove that iterative data reuse does not compromise statistical optimality.


Mechanism 1: Leave-One-Out Analysis

One of the most powerful frameworks for decoupling iterative dependencies is leave-one-out analysis. The core intuition is to construct a parallel, hypothetical trajectory of the algorithm that runs on a dataset missing exactly one sample.

Suppose we have a dataset $D = \{x_1, \dots, x_n\}$, and we create a modified dataset $D^{(i)}$ by removing or replacing the $i$-th sample. If we run our iterative algorithm on $D^{(i)}$, it generates a sequence of parameters $\theta_t^{(i)}$. Because $\theta_t^{(i)}$ never saw the $x_i$, it remains completely independent of that specific sample.

True Trajectory (on D):     θ_0 ──> θ_1 ──> θ_2 ──> ... ──> θ_t  (Dependent on x_i)
                                     │       │               │
                                     ▼       ▼               ▼   (Proved to be close)
Auxiliary Trajectory (on D^(i)): θ_0 ──> θ_1^(i) ──> θ_2^(i) ──> ... ──> θ_t^(i) (Independent of x_i)

By leveraging high-dimensional probability tools, authors can prove that the true trajectory $\theta_t$ stays extremely close to the auxiliary trajectory $\theta_t^{(i)}$ for all $t$ (Chandrasekher et al.). This allows researchers to bound the influence of any single data point, effectively showing that the statistical feedback loop is too weak to destabilize the algorithm. Chen et al. successfully used this approach to establish near-optimal speed and accuracy bounds for non-convex phase retrieval without relying on sample splitting.


Mechanism 2: Implicit Regularization

For non-convex optimization problems solved via vanilla Gradient Descent, data reuse is often protected by a phenomenon known as implicit regularization.

When an algorithm reuses a dataset, one might worry that the parameter updates will begin to overfit to the specific noise patterns within that sample set. However, in problems like low-rank matrix factorization and tensor recovery, the geometric landscape of the objective function naturally constrains the optimization path.

As demonstrated by Li et al. and Li et al., the gradient updates naturally steer the parameters through a well-behaved geometric region. The algorithm is implicitly regularized to favor low-rank, incoherent structures, preventing the parameters from aligning with the malicious directional components of the noise. Because the trajectory is trapped in this benign region, the statistical dependencies that develop across iterations remain harmlessly bounded.


Mechanism 3: Uniform Concentration Bounds

A third way to eliminate the sample-splitting requirement is to shift focus from a single trajectory to the entire parameter space via uniform concentration.

Standard concentration bounds state that for a fixed parameter $\theta$, the empirical loss matches the population loss with high probability. If $\theta$ depends on the data, this breaks. However, if we can prove that the empirical loss matches the population loss for all possible parameters $\theta$ simultaneously within a specific region, then the specific path our algorithm takes no longer matters.

Standard Concentration:
For a fixed θ:  |Empirical(θ) - Population(θ)| < ε  (Breaks if θ is chosen based on data)

Uniform Concentration:
For ALL θ ∈ Ω:  |Empirical(θ) - Population(θ)| < ε  (Holds even if θ moves dynamically through Ω)

By establishing uniform concentration bounds over a localized basin of attraction, researchers can guarantee that an iterative algorithm will converge geometrically to the ground truth without needing fresh samples at each step. This strategy has been successfully deployed across several domains:

  • Expectation-Maximization: Kwon et al. utilized uniform concentration to prove the global convergence of EM for mixtures of linear regressions under complete data reuse.
  • Alternating Minimization: Chen et al. eliminated the resampling assumption for multi-response regression, proving that AltMin achieves optimal statistical error even when reusing the same dataset across all iterations.
  • Reinforcement Learning: In offline policy optimization, Li et al. showed that reusing a single offline dataset across all iterations of value iteration maintains statistical optimality, bypassing the need for data-wasting partitions.

Bridging the Theory-Practice Divide

By moving away from the artificial constraint of sample splitting, modern learning theory has achieved a more realistic alignment with practical machine learning. Whether through the lens of leave-one-out sequences, geometric implicit regularization, or uniform empirical processes, proving convergence under iterative data reuse reveals a shared truth: the statistical dependencies generated during optimization are often too weak to overcome the global geometric forces driving the algorithm toward the true solution.

As a result, we can confidently deploy data-efficient, single-dataset iterative solvers, secure in the knowledge that their empirical success is backed by rigorous mathematical guarantees (Hardt).

Key Foundational Work

Learning Mixtures of Gaussians using the k-means Algorithm (2009) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 65 papers
  2. Version 1 · 2026-10-04 · 91 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_iterative_data_reuse_714f1067,
  title = {iterative data reuse},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iterative-data-reuse/rdr_714f1067748542028db384a7302fd65a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_iterative_data_reuse_714f1067_v2,
  title = {iterative data reuse},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/iterative-data-reuse/rdr_714f1067748542028db384a7302fd65a/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake