Most of the foundational theory in machine learning rests on the "i.i.d. assumption"—the idea that data points are independent and identically distributed. In practice, however, data often arrives in sequences where the present is tethered to the past. Whether it is a stock ticker, a weather pattern, or a robot’s sensor stream, observations are inherently dependent.
To bridge this gap, researchers have developed a framework based on mixing processes. The core intuition is that while data points may be correlated in the short term, a "well-behaved" system eventually forgets its initial state. If this decay of memory is fast enough, we can recover the strong statistical guarantees typically reserved for independent data.
Quantifying Memory with Mixing Coefficients
The central challenge in learning from dependent data is quantifying exactly how much "information" is lost to correlation. Researchers use various mixing coefficients—such as $\alpha$, $\beta$, and $\phi$—to measure the rate at which a process approaches independence.
As Mehryar Mohri and Afshin Rostamizadeh established in Stability Bound for Stationary Phi-mixing and Beta-mixing Processes, these coefficients allow us to extend algorithmic stability results to non-i.i.d. settings. Intuitively, if a process is $\beta$-mixing, it means the joint distribution of the past and the future eventually looks like the product of their marginals. This "mixing" allows us to treat a long sequence of dependent data as a collection of nearly independent blocks, a technique used by Yafei Wang and colleagues to prove that stochastic optimization remains efficient even with temporal dependencies.
Theoretical Optimality in the Face of Dependence
A recurring discovery across this research is that many standard algorithms are surprisingly robust to dependence. Aurélie C. Lozano and Robert E. Schapire demonstrated in Convergence and Consistency of Regularized Boosting Algorithms with Stationary B-Mixing Observations that boosting remains consistent on weakly dependent data, requiring only minor adjustments to regularization.
More recently, William Kengne proved that deep neural networks are minimax optimal on dependent data. By applying PAC-Bayes bounds to Markov chains, Kengne showed that DNNs achieve the same fundamental convergence rates for regression and classification on correlated data as they do in the i.i.d. setting, provided the data "mixes" well enough. Similarly, Fang Han and Han Liu extended Principal Component Analysis to non-Gaussian dependent data, showing that rank-based methods can still map complex networks even when observations are stubbornly correlated.
The Estimation Bottleneck
While the theory is robust, a significant practical hurdle remains: mixing coefficients are rarely known. Most theoretical bounds require the researcher to plug in a specific mixing rate or a "spectral gap" (a measure of how fast a Markov chain converges).
Daniel J. McDonald and Cosma Rohilla Shalizi point out in Estimating beta-mixing coefficients that it is notoriously difficult to estimate these rates from a single observed trajectory. Without knowing the mixing rate, a practitioner cannot know how much to "thin" their data to achieve reliable coverage in conformal prediction, as noted by Frédéric Zheng and Alexandre Proutière, or how to set the optimal delay in a bandit algorithm.
Moving Toward Empirical and Additive Bounds
To solve this, recent work has shifted toward making these bounds more practical. Pierre Alquier and Vahe Karagulyan developed the first fully empirical PAC-Bayes bounds for Markov chains, which estimate the necessary spectral constants directly from the data trajectory itself.
Another innovation comes from Andreas Maurer, who introduced bounds where the mixing time enters the equation additively rather than multiplicatively. In Generalization for slowly mixing processes, Maurer shows that this change significantly tightens the error guarantees for systems that are slow to reach independence, reducing the "mixing time tax" that previously made these bounds overly pessimistic.
Finally, researchers like Baptiste Abélès and Gergely Neu are exploring algorithmic ways to "force" independence. In Mixing-LinUCB, they introduce intentional delays in data processing. By waiting for the system to "mix" before using a new observation, they decorrelate the noise and achieve regret bounds that nearly match the optimal i.i.d. setting.