Sample Complexity under Temporal Dependence

57 concepts38 papers1 proposal

Imagine flipping a coin 1,000 times. If each flip is independent, you receive 1,000 distinct pieces of information. Now imagine a "sticky" coin that has a 99% chance of repeating its previous outcome. If it lands heads, it will likely stay heads for the next several dozen flips. Even if you observe 1,000 total flips, you have not collected 1,000 independent pieces of evidence; instead, you have collected a few long, redundant blocks of identical outcomes.

This scenario illustrates the core challenge of learning from non-i.i.d. or temporally dependent data. In fields like reinforcement learning, time-series analysis, and streaming optimization, data points arrive in a highly correlated sequence. As noted by Ingo Steinwart et al. in Fast Learning from Non-i.i.d. Observations, this temporal correlation introduces informational redundancy. Consequently, the raw sample size $N$ overstates the true amount of unique information available to a learning algorithm, leading to a phenomenon known as sample size deflation.

Quantifying the Information Tax via Mixing Times

To build rigorous generalization bounds for dependent data, statistical learning theory must mathematically discount the raw sample size. The severity of this discount depends on how fast the data-generating process "forgets" its past states. This forgetting rate is typically formalized using two related concepts: mixing times and spectral gaps.

  • Mixing Time ($\tau$): The time required for a Markov chain or a mixing process to get close to its steady-state (stationary) distribution. If a system has a long mixing time, observations far apart in time remain correlated.
  • Spectral Gap ($\gamma$): The difference between the largest and second-largest eigenvalues of the system's transition operator. A larger spectral gap implies that the system converges rapidly to stationarity (fast mixing), while a tiny spectral gap means the system is highly persistent or "sticky."

Early foundations laid by Mehryar Mohri et al. in Rademacher Complexity Bounds for Non-I.I.D. Processes handled this by breaking dependent sequences into independent blocks. They demonstrated a fundamental trade-off: increasing the number of blocks provides more data points for estimation, but it also increases a penalty term that accounts for the correlation between those blocks.

The Effective Sample Size Mechanism

When analyzing algorithms under temporal dependence, standard statistical guarantees undergo a transformation where the raw sample count $N$ is replaced by an effective sample size $N_{\text{eff}}$.

For instance, in high-dimensional regression, Jianqing Fan et al. demonstrate in Adaptive Huber Regression on Markov-dependent Data that the sample size must be explicitly discounted by the spectral gap of the underlying Markov chain. Similarly, Tieliang Gong et al. show in Regularized Modal Regression on Markov-Dependent Observations: A Theoretical Assessment that a smaller spectral gap acts as a multiplicative discount on the data, meaning significantly more raw observations are required to achieve the same statistical confidence as independent observations.

Raw Data Stream:      [X_1 -> X_2 -> X_3] -> [X_4 -> X_5 -> X_6] -> [X_7 -> X_8 -> X_9]
                      \_________________/    \_________________/    \_________________/
                           Highly                 Highly                 Highly
                         Correlated             Correlated             Correlated
                             |                      |                      |
Effective Information:   [Block 1]              [Block 2]              [Block 3]

To make these bounds practical for real-world time series, researchers have developed ways to estimate these hidden structural properties directly from data. In Empirical PAC-Bayes bounds for Markov chains, Pierre Alquier et al. developed a method to estimate the pseudo-spectral gap from a single observed trajectory. This allows for data-dependent generalization bounds that scale based on the actual amount of independent information present in the stream, a framework that William Kengne extended to prove the minimax optimality of deep neural networks on dependent data in Minimax optimality of deep neural networks on dependent data via PAC-Bayes bounds.

Algorithmic Consequences and the Markovian Tax

When optimization or reinforcement learning algorithms operate on a single continuous trajectory, the mixing time acts as a direct penalty on convergence speed—a "Markovian tax."

In temporal difference (TD) learning and stochastic approximation, gradient noise is amplified by the mixing time because consecutive gradients point in similar, unrepresentative directions. R. Srikant et al. showed in Finite-Time Error Bounds For Linear Stochastic Approximation andTD Learning that environments that take longer to explore require a higher number of samples to reach a steady state.

For non-convex optimization, Zhenyu Sun et al. proved in Improved Lower Bounds for First-order Stochastic Non-convex Optimization under Markov Sampling that the sample complexity scales linearly with the mixing time, establishing a fundamental lower bound on how fast an algorithm can optimize when the sampler is slow to forget its starting position. This tax also appears in distributed settings; Tan-Khiem HUYNH et al. show in Streaming Federated Learning with Markovian Data that while federated learning achieves a linear speedup with more clients, the local gradient noise remains fundamentally scaled by the data source's spectral gap.

To mitigate this penalty, algorithms often use heuristics like Experience Replay. As analyzed by Dheeraj Mysore Nagaraj et al. in Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms, shuffling past observations breaks the temporal correlation between consecutive updates, providing a provable speedup over standard online stochastic gradient descent.

Avoiding Deflation: Learning Without Mixing

Is a mixing time penalty always mandatory when dealing with dependent data? Traditional frameworks suggested that data dependence fundamentally slows down the asymptotic learning rate. However, a recent paradigm shift reveals that for certain loss functions, we can avoid sample size deflation entirely.

In Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss, Ingvar Ziemann et al. demonstrated that for the square loss, the mixing time does not slow down the asymptotic rate of learning. Instead, it only affects the initial burn-in phase—the amount of data required to reach a stable learning regime. Once the algorithm passes this threshold, the error rate scales at a speed comparable to independent data.

Error Rate
   ^
   |   /  Traditional Bound (Asymptotically slowed by mixing time)
   |  /
   | /    Sharp "Learning-Without-Mixing" Bound
   |/____ (Mixing time only prolongs the initial burn-in phase)
   +----------------------------------------------------------> Samples (N)

This "learning-without-mixing" phenomenon is highly relevant when identifying dynamical systems with long-range dependencies. Oguz Kaan Yüksel et al. proved in Long-Context Linear System Identification that as the context window of an autoregressive model grows, the system's mixing time may increase, but this does not inherently slow down the learning process. By moving past pessimistic mixing-time bounds, modern dependent learning theory provides a more precise understanding of why algorithms can successfully extract patterns from highly correlated continuous streams of data.

Key Foundational Work

Fast Learning from Non-i.i.d. Observations (2009) — contributed 2 concept elements to this direction.
Rademacher Complexity Bounds for Non-I.I.D. Processes (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_mixing_time_dependency_temporal_correlat_d3957959,
  title = {mixing time dependency (temporal correlation sample complexity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mixing-time-dependency-temporal-correlation-sample-complexity/rdr_d39579597ce44f5383d64d53b3ecae18},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_mixing_time_dependency_temporal_correlat_d3957959_v1,
  title = {mixing time dependency (temporal correlation sample complexity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mixing-time-dependency-temporal-correlation-sample-complexity/rdr_d39579597ce44f5383d64d53b3ecae18/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake