Most of our fundamental guarantees in machine learning—the proofs that tell us how many samples we need to reach a certain accuracy—rely on a convenient fiction: that every data point is independent and identically distributed (i.i.d.). In reality, data often arrives in streams where the current state is heavily influenced by the previous one. Whether it is a sequence of fMRI brain scans, a stock market ticker, or a robot’s sensor readings, these data points are "sticky."
Researchers are now quantifying the "tax" we pay for this stickiness. By moving beyond the i.i.d. assumption, they have identified the fundamental limits of learning from Markovian trajectories and time series, showing that the speed of learning is dictated not just by the number of samples, but by how quickly a system "forgets" its past.
The Markovian Tax and Mixing Time
When data points are dependent, each new observation provides less "new" information than an independent one would. Dheeraj Mysore Nagaraj, Prateek Jain, and their colleagues describe this as a fundamental efficiency penalty in Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms.
The core metric here is mixing time: the time it takes for a Markov chain to move far enough from its starting state that it effectively reaches its steady state (stationary distribution). If a system has a long mixing time, it is highly correlated; it stays in similar states for a long time. Zhenyu Sun and Ermin Wei show that in non-convex optimization, the sample complexity scales linearly with this mixing time. Essentially, you have to wait for the chain to "forget" where it was before you can gain a truly fresh perspective on the underlying distribution.
The Concept of Effective Sample Size
To bridge the gap between i.i.d. theory and dependent reality, researchers often calculate an effective sample size. If you have 1,000 samples from a highly correlated process, you might only have the equivalent of 100 independent observations.
This discount factor is often determined by the spectral gap or the pseudo-spectral gap of the transition matrix. Pierre Alquier and Vahe Karagulyan developed empirical PAC-Bayes bounds that use this gap to adjust generalization guarantees. In their framework, the raw sample count is scaled by the estimated spectral gap, ensuring that the risk bounds reflect the actual amount of information present in the time series. Similarly, Tieliang Gong and colleagues found that in modal regression, the spectral gap acts as a multiplicative discount on the learning rate.
Robustness of High-Dimensional Estimators
A major question in this field is whether standard tools like Sparse PCA or Lasso still work when the i.i.d. assumption fails. Work by Yixin Wang, Fang Han, and Han Liu provides a theoretical foundation for Sparse PCA in high-dimensional Vector Autoregressive (VAR) models. They prove that while temporal correlation increases the estimation error, the method remains robust. The difficulty is governed by the spectral norm of the transition matrix—essentially a measure of the data's "auto-correlation."
For the Lasso estimator, Kam Chung Wong and Ambuj Tewari demonstrated that consistency holds even for non-linear or misspecified systems, provided the process is $\beta$-mixing (a condition where dependence decays over time). Their work in Lasso Guarantees for Time Series Estimation Under Subgaussian Tails and β-Mixing shows that while dependence doesn't necessarily ruin the asymptotic convergence rate, it does increase the minimum sample size required for those guarantees to "kick in."
Challenging the Mixing Bottleneck
While most research treats mixing time as a speed limit, some recent findings suggest the relationship might be more nuanced. In Long-Context Linear System Identification, Oguz Kaan Yüksel and Mathieu Even identify a "learning-without-mixing" phenomenon. They argue that for certain long-range dependencies, a long context window doesn't inherently slow down learning. This suggests that in specific structural models, we might be able to bypass the "Markovian tax" that plagues more general settings.
Practical Implications for Distributed Systems
This theoretical shift has immediate consequences for modern paradigms like Federated Learning (FL). In streaming FL, clients process continuous, time-correlated data (like sensor readings). Tan-Khiem HUYNH and Giovanni Neglia show that while these correlations amplify gradient noise, the core benefit of FL remains: adding more clients still provides a linear speedup in convergence. The "Markovian tax" is paid by the individual client, but the collective power of the network helps mitigate the cost.