The bedrock of classical statistical learning theory is the assumption that data points are independent and identically distributed (i.i.d.). This assumption makes proving generalization bounds straightforward: if you sample $N$ points from a distribution, each point provides a completely fresh, unbiased glimpse of the underlying truth. Errors across independent samples tend to cancel each other out, allowing concentration inequalities (like Hoeffding's or Bernstein's) to guarantee that a model's training performance will closely match its real-world performance.
But when dealing with time series, robotics trajectories, or dynamical systems, this assumption collapses. If you measure a stock price, a weather pattern, or a robot's position every millisecond, the observation at time $t$ is heavily dictated by the observation at time $t-1$.
If a dataset of 1,000 sequential points is so highly correlated that the state changes only a few times, you do not actually have 1,000 independent pieces of information. You might only have the equivalent of 5 or 10 independent glimpses. If you blindly apply standard i.i.d. bounds to this data, your theoretical guarantees become vacuous, vastly overestimating how well your model will generalize.
To build a rigorous foundation for time-series prediction and system identification, researchers have had to reinvent generalization theory. They do this by answering a fundamental question: How do we quantify the "effective" number of independent samples in a dependent trajectory?
Slicing Time via Mixing Processes
The earliest and most intuitive way to handle temporal dependency is to measure how fast a system "forgets" its past. If a stochastic process eventually forgets where it started, observations taken far apart in time will behave as if they are independent.
This intuition is formalized through mixing processes ($\alpha$-mixing, $\beta$-mixing, and $\phi$-mixing). A mixing coefficient quantifies the maximum possible dependence between two events separated by a time lag $\tau$. As $\tau$ grows to infinity, the mixing coefficient drops to zero.
Highly Dependent Approximately Independent
[ X_1 X_2 X_3 ] --lag τ--> [ X_{1+τ} X_{2+τ} X_{3+τ} ]
In his seminal work, Meir extended the Structural Risk Minimization framework to time series by leveraging these mixing properties in Structural Risk Minimization for Nonparametric Time Series Prediction. The core mechanism relies on a "blocking technique": a single long trajectory of dependent data is sliced into alternating blocks of length $a$ and $b$. If the separation block $b$ is large enough, the blocks of length $a$ become approximately independent of one another.
By treating these blocks as independent data chunks, theorists can repurpose classical proofs. Mohri et al. used this insight in Stability Bound for Stationary Phi-mixing and Beta-mixing Processes to provide the first generalization bounds for stable learning algorithms operating on mixing sequences. Similarly, Steinwart et al. demonstrated in Fast Learning from Non-i.i.d. Observations that regularized algorithms like Support Vector Machines can achieve fast, near-optimal learning rates on $\alpha$-mixing data.
The penalty for this dependency shows up directly in the math: the sample size $N$ in the error bound is effectively replaced by $N / (a+b)$, representing the reduced number of independent blocks. Recent refinements, such as those by Fu et al. in Sharper Bounds for Uniformly Stable Algorithms with Stationary Mixing Process, continue to tighten these bounds, minimizing the residual error terms that internal correlations leave behind.
Algorithmic Stability and Online Proxies
What if you cannot easily prove that your data-generating process is mixing? Another approach shifts the focus from the data distribution to the learning algorithm itself.
An algorithm is considered uniformly stable if changing a single data point in the training set alters the model's predictions by at most a tiny factor, $\epsilon$. In the i.i.d. setting, stability is a powerful tool for proving generalization. In the dependent setting, it becomes a lifeline. Even if your data points are correlated, a stable algorithm prevents any single correlated sequence from swinging the model's parameters too wildly.
However, proving generalization directly from a dependent trajectory remains difficult because standard combinatorial metrics (like the VC dimension) fail. To circumvent this, researchers use an Online-to-Batch conversion.
Instead of analyzing a batch algorithm directly on a time series, you imagine an online learning agent processing the sequence step-by-step, minimizing its "regret" against an adversary. Because online learning frameworks make absolutely no assumptions about how the data is generated—it can be fully dependent or even adversarial—we can derive clean regret bounds. By using a stable online proxy, Chatterjee et al. showed in Generalization Bounds for Dependent Data using Online-to-Batch Conversion that you can port these guarantees back to batch models using a metric called Wasserstein-stability.
This perspective helps explain why highly expressive architectures generalize well on sequential tasks. For instance, Li et al. analyzed In-Context Learning (ICL) in Transformers through the lens of algorithmic stability in Transformers as Algorithms: Generalization and Stability in In-context Learning, proving that the implicit optimization algorithms executed by Transformers are inherently stable enough to maintain accuracy when prompts consist of temporally dependent observations.
Martingales and the Geometry of Markov Chains
For structured dynamical systems—like a linear system or a finite-state Markov chain—we can look under the hood of the transition dynamics rather than treating the process as a generic mixing sequence. Here, the primary mathematical tools are martingales and spectral gaps.
A martingale is a sequence of random variables where the conditional expectation of the next value, given all past values, is equal to the present value. Essentially, it models a fair game where errors do not accumulate systematically. Even though the states of a dynamical system are highly correlated, the innovations (the fresh noise introduced at each time step) form a martingale difference sequence.
By isolating these noise terms, researchers can deploy self-normalized martingale concentration inequalities. As detailed by Matni et al. in A Tutorial on Concentration Bounds for System Identification, these bounds allow control theorists to certify the exact accuracy of parameters learned from a single continuous trajectory of a linear dynamical system, bypassing the need for independent system restarts.
When the system is a Markov chain, its mixing speed is governed by its geometry—specifically, its spectral gap. The spectral gap is the difference between the largest and second-largest eigenvalues of the chain's transition matrix.
Small Spectral Gap --> Slow Mixing --> High Data Dependency --> Weak Bounds
Large Spectral Gap --> Fast Mixing --> Low Data Dependency --> Tight Bounds
A large spectral gap means the Markov chain converges rapidly to its steady state, shedding its historical dependencies. Gong et al. leveraged this in Regularized Modal Regression on Markov-Dependent Observations: A Theoretical Assessment, proving that the learning rate of a regression model on Markovian data is explicitly scaled by this spectral gap. To make these bounds practical, Alquier et al. developed methods in Empirical PAC-Bayesian Bounds for Markov chains to estimate this pseudo-spectral gap directly from a single observed trajectory, eliminating uncomputable theoretical constants and making error guarantees fully empirical.
Why Deep Networks Succeed on Dependent Data
Given how much mathematical machinery is required to fix generalization bounds for simple linear models under temporal dependency, you might expect deep neural networks to fail spectacularly. Yet, empirical evidence shows that deep models excel at time-series forecasting and reinforcement learning.
Theoretical work has begun to close this gap by showing that deep architectures possess inductive biases that naturally mitigate temporal correlations. Ma et al. provided a rigorous proof in Theoretical analysis of deep neural networks for temporally dependent observations, demonstrating that deep neural networks applied to temporally dependent data achieve convergence rates nearly identical to those for independent data, suffering only a minor logarithmic complexity penalty.
Furthermore, the optimization process itself helps. In Stochastic Gradient Descent Learns State Equations with Nonlinear Activations, Oymak proved that despite the presence of severe temporal correlations and nonlinear dynamics, Stochastic Gradient Descent (SGD) efficiently finds the true parameters of recurrent state equations with near-optimal sample complexity. The sequential updates of SGD act as a natural regularizer, preventing the model from over-indexing on the local dependencies of a single trajectory.
By shifting from the rigid assumption of i.i.d. data to frameworks based on mixing blocks, algorithmic stability, and martingale differences, machine learning theory can finally provide ironclad performance guarantees for models operating in our inherently continuous, sequential, and dependent world.