When optimizing non-convex objectives—such as those found in matrix completion, tensor factorization, or mixture models—practitioners often rely on iterative heuristics like Alternating Minimization (AltMin) or Expectation-Maximization (EM). Empirically, these algorithms are fast and reliable. Theoretically, however, they present a formidable challenge: statistical dependency.
If an algorithm reuses the same dataset at every iteration, the parameter estimates at step $t$ become highly correlated with the data. This correlation breaks standard statistical tools (like Chernoff or Hoeffding concentration bounds), making it incredibly difficult to prove global convergence.
To bypass this theoretical bottleneck, researchers use a powerful mechanism: sample splitting (also known as iterative data resampling). By partitioning the available data into disjoint subsets and using a fresh subset for each iteration, we can guarantee statistical independence throughout the optimization path.
The Statistical Dependency Trap
To understand why sample splitting is necessary, consider a generic iterative algorithm updating a parameter $\theta$:
$$\theta_{t+1} = f(\theta_t, D)$$
where $D$ is our observed dataset. If we reuse the entire dataset $D$ at every step, $\theta_t$ becomes a complex function of $D$. When we try to analyze the next update step, we want to show that the expected update points in the direction of the true solution:
$$\mathbb{E}[f(\theta_t, D) \mid \theta_t]$$
However, because $\theta_t$ and $D$ are statistically dependent, we cannot treat $\theta_t$ as a fixed, independent constant. The data $D$ is no longer a "clean" sample from the underlying population distribution; it has been conditioned on by the trajectory of the optimization itself. This dependency introduces subtle biases that can cause the algorithm to overfit to specific noise patterns or get trapped in local minima.
The Solution: Fresh Samples at Each Step
Sample splitting resolves this by decoupling the model state from the data. The mechanism is straightforward:
- Partition: Divide the observed data $D$ into $T$ disjoint batches: $D_1, D_2, \dots, D_T$.
- Update: At iteration $t$, update the parameters using only the batch $D_t$:
$$\theta_{t+1} = f(\theta_t, D_t)$$
Because $D_t$ is completely disjoint from the data used to compute $\theta_t$, the parameter $\theta_t$ acts as a fixed constant relative to $D_t$. This restores conditional independence, allowing researchers to evaluate expectations and apply concentration inequalities as if each step were the very first iteration of the algorithm.
Full Dataset D ───► Partition ───┬─► Batch D₁ ───► Step 1 (Initializes θ₁)
├─► Batch D₂ ───► Step 2 (Updates θ₁ to θ₂)
└─► Batch Dₜ ───► Step t (Updates θₜ₋₁ to θₜ)
Unlocking Alternating Minimization
The breakthrough application of sample splitting was in proving the convergence of Alternating Minimization for matrix completion (the mathematics underlying the famous Netflix Prize problem).
In Low-rank Matrix Completion using Alternating Minimization, Prateek Jain et al. provided the first proof of global geometric convergence for AltMin. By partitioning the observed entries of a low-rank matrix into independent subsets for each step, they eliminated the feedback loop between the current low-rank factors and the observed entries.
Building on this foundation, other researchers refined the technique to achieve tighter bounds and broader applicability:
- Optimal Complexity: Moritz Hardt in On the Provable Convergence of Alternating Minimization for Matrix Completion utilized a unique independent subset per iteration to significantly tighten the sample complexity bounds, reducing the dependency on the matrix's rank and condition number.
- Noisy Observations: Ayan Acharya et al. extended this to Noisy Matrix Completion Using Alternating Minimization, proving that partitioning data prevents the accumulation of correlated errors, allowing the algorithm to recover matrices up to the noise floor.
- Robust and Inductive Variants: Yeshwanth Cherapanamjeri et al. applied sample splitting to handle corrupted entries in Nearly Optimal Robust Matrix Completion, while Xiao Zhang et al. used it in Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow to ensure gradient estimates remained unbiased when incorporating side features.
- Vector-Valued Outputs: Ambuj Tewari et al. demonstrated in Alternating Minimization for Regression Problems with Vector-valued Outputs that fresh data subsets allow AltMin to match the statistical accuracy of the Maximum Likelihood Estimator even when noise across outputs is highly correlated.
Guarantees for Expectation-Maximization
Another domain plagued by non-convexity is latent variable modeling, typically solved via the Expectation-Maximization (EM) algorithm.
In Alternating Minimization for Mixed Linear Regression, Xinyang Yi et al. focused on Mixed Linear Regression (MLR)—where data points are generated from a mixture of multiple distinct linear models. By feeding a fresh batch of independent samples into each EM update, the authors proved that the algorithm avoids local minima and converges geometrically to the ground truth. They generalized this approach in Regularized EM Algorithms: A Unified Framework and Statistical Guarantees, establishing that data-splitting ensures gradient estimates remain unbiased in high-dimensional regularized settings.
Subsequent work has pushed this mechanism to its limits:
- Many Components: Jeongyeol Kwon et al. used sample splitting in EM Converges for a Mixture of Many Linear Regressions to guarantee exact parameter recovery in noiseless settings for mixtures with more than two components.
- Agnostic Learning: Avishek Ghosh et al. proved in Agnostic Learning of Mixed Linear Regressions with EM and AM Algorithms that sample splitting maintains robustness even when the data does not follow a strict generative model.
- Super-Linear Convergence: Interestingly, Avishek Ghosh et al. showed in Alternating Minimization Converges Super-Linearly for Mixed Linear Regression that sample splitting can be used to prove that AltMin actually accelerates beyond linear convergence, achieving super-linear and even quadratic rates.
A Ubiquitous Theoretical Tool
The utility of sample splitting spans across diverse machine learning paradigms, serving as a foundational proof technique whenever adaptivity or iteration threatens statistical independence.
Higher-Order Tensors and Neural Networks
Beyond matrices, Prateek Jain et al. applied sample splitting to 3D arrays in Provable Tensor Factorization with Missing Data, overcoming the curse of local minima. Similarly, Kai Zhong et al. utilized a resampling strategy in Recovery Guarantees for One-hidden-layer Neural Networks to ensure that the data points used to calculate the gradient at each step were independent of the current weights, guaranteeing global optimum recovery for one-hidden-layer networks.
Graphs and Structured Models
In network analysis, Ping Li demonstrated in Rate optimal Chernoff bound and application to community detection in the stochastic block models that splitting an adjacency matrix into independent sub-blocks allows for multi-stage updates in Stochastic Block Models while maintaining the clean statistical independence required for sharp minimax error rates. For multi-response models, Sheng Chen 0014 et al. leveraged resampling in Alternating Estimation for Structured High-Dimensional Multi-Response Models to decouple parameter updates from correlated noise.
Active Learning, Bandits, and Streaming
When algorithms choose data adaptively, feedback loops are particularly dangerous.
- In active learning, Songbai Yan et al. used data splitting in Active Learning with Logged Data to ensure importance sampling estimators remained theoretically sound despite adaptive query policies.
- In multi-armed bandits, Shubhanshu Shekhar et al. processed queries in discrete batches in Instance Dependent Regret Analysis of Kernelized Bandits to prevent the accumulation of dependencies that typically loosen Gaussian Process confidence intervals.
- In streaming regression, Sepideh Mahabadi et al. partitioned data into distinct buckets in Adaptive Sketches for Robust Regression with Importance Sampling. This prevented a "chicken-and-egg" loop where current model parameters might bias the sketching matrix used for future samples.
The Theory-Practice Divide
There is a fascinating tension at the heart of sample splitting: it is rarely used this way in practice.
Data is expensive. If a practitioner has 10,000 data points and wants to run an algorithm for 10 steps, partitioning the data means using only 1,000 points per step, which throws away valuable statistical power. In reality, practitioners reuse all 10,000 data points at every single iteration, and the algorithms still converge beautifully.
Why, then, do theorists remain obsessed with sample splitting?
Because it serves as an indispensable mathematical stepping stone. Proving convergence with sample splitting establishes that the algorithm's core mechanics are fundamentally sound. It isolates the geometric contraction of the optimization from the statistical behavior of the data.
Once a problem is understood within the clean sandbox of sample splitting, researchers can develop more advanced mathematical machinery—such as "leave-one-out" analysis, as demonstrated by Kabir Aladin Chandrasekher et al. in Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization—to finally prove that the algorithm works even when data is fully reused.
Key Foundational Work
Low-rank Matrix Completion using Alternating Minimization (2012) — contributed 1 concept elements to this direction.
Noisy Matrix Completion Using Alternating Minimization (2013) — contributed 1 concept elements to this direction.
On the Provable Convergence of Alternating Minimization for Matrix Completion (2013) — contributed 1 concept elements to this direction.