# Learning with little mixing

arXiv: https://arxiv.org/abs/2206.08269 · HTML: https://mlsanity.com/paper/2206.08269/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 61 references that are in the map.
- First posted on arXiv 16 Jun 2022.

## Builds on (most cited first, 18 of 18)

- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification](https://mlsanity.com/paper/1802.08334/) (2018)
- [Near optimal finite time identification of arbitrary linear dynamical systems](https://mlsanity.com/paper/1812.01251/) (2018)
- [Finite Time Identification in Unstable Linear Systems](https://mlsanity.com/paper/1710.01852/) (2017)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Learning nonlinear dynamical systems from a single trajectory](https://mlsanity.com/paper/2004.14681/) (2020)
- [Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systems](https://mlsanity.com/paper/2002.08538/) (2020)
- [Learning with Square Loss: Localization through Offset Rademacher Complexity](https://mlsanity.com/paper/1502.06134/) (2015)
- [Finite-time Identification of Stable Linear Systems: Optimality of the Least-Squares Estimator](https://mlsanity.com/paper/2003.07937/) (2020)
- [Single Trajectory Nonparametric Learning of Nonlinear Dynamics](https://mlsanity.com/paper/2202.08311/) (2022)
- [Learning from many trajectories](https://mlsanity.com/paper/2203.17193/) (2022)
- [Linear Systems can be Hard to Learn](https://mlsanity.com/paper/2104.01120/) (2021)
- [Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems](https://mlsanity.com/paper/2105.11558/) (2021)
- [On Empirical Risk Minimization with Dependent and Heavy-Tailed Data](https://mlsanity.com/paper/2109.02224/) (2021)
- [Learning from weakly dependent data under Dobrushin's condition](https://mlsanity.com/paper/1906.09247/) (2019)
- [On aggregation for heavy-tailed classes](https://mlsanity.com/paper/1502.07097/) (2015)
- [Improved Prediction and Network Estimation Using the Monotone Single Index Multi-variate Autoregressive Model](https://mlsanity.com/paper/2106.14630/) (2021)

## Built on by (most cited first, 30 of 33)

- [Transformers as Algorithms: Generalization and Stability in In-context Learning](https://mlsanity.com/paper/2301.07067/) (2023)
- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers](https://mlsanity.com/paper/2402.13512/) (2024)
- [Optimistic Active Exploration of Dynamical Systems](https://mlsanity.com/paper/2306.12371/) (2023)
- [A Tutorial on the Non-Asymptotic Theory of System Identification](https://mlsanity.com/paper/2309.03873/) (2023)
- [On the Performance of Empirical Risk Minimization with Smoothed Data](https://mlsanity.com/paper/2402.14987/) (2024)
- [Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss](https://mlsanity.com/paper/2402.05928/) (2024)
- [Streaming PCA for Markovian Data](https://mlsanity.com/paper/2305.02456/) (2023)
- [Active Learning for Control-Oriented Identification of Nonlinear Systems](https://mlsanity.com/paper/2404.09030/) (2024)
- [The noise level in linear regression with dependent data](https://mlsanity.com/paper/2305.11165/) (2023)
- [Non-asymptotic System Identification for Linear Systems with Nonlinear Policies](https://mlsanity.com/paper/2306.10369/) (2023)
- [On the Consistency of Kernel Methods with Dependent Observations](https://mlsanity.com/paper/2406.06101/) (2024)
- [Optimal kernel regression bounds under energy-bounded noise](https://mlsanity.com/paper/2505.22235/) (2025)
- [Rate-Optimal Non-Asymptotics for the Quadratic Prediction Error Method](https://mlsanity.com/paper/2404.07937/) (2024)
- [Long-Context Linear System Identification](https://mlsanity.com/paper/2410.05690/) (2024)
- [Length independent generalization bounds for deep SSM architectures via Rademacher contraction and stability constraints](https://mlsanity.com/paper/2405.20278/) (2024)
- [Nonconvex Linear System Identification with Minimal State Representation](https://mlsanity.com/paper/2504.18791/) (2025)
- [Concentration Phenomenon for Random Dynamical Systems: An Operator Theoretic Approach](https://mlsanity.com/paper/2212.03670/) (2022)
- [A note on the smallest eigenvalue of the empirical covariance of causal Gaussian processes](https://mlsanity.com/paper/2212.09508/) (2022)
- [Finite Sample Frequency Domain Identification](https://mlsanity.com/paper/2404.01100/) (2024)
- [A least-square method for non-asymptotic identification in linear switching control](https://mlsanity.com/paper/2404.08120/) (2024)
- [Single Trajectory Conformal Prediction](https://mlsanity.com/paper/2406.01570/) (2024)
- [Recovery Guarantees for Continual Learning of Dependent Tasks: Memory, Data-Dependent Regularization, and Data-Dependent Weights](https://mlsanity.com/paper/2604.17578/) (2026)
- [Learning Nonlinear Couplings in Network of Agents from a Single Sample Trajectory](https://mlsanity.com/paper/2211.11069/) (2022)
- [Stability properties of gradient flow dynamics for the symmetric low-rank matrix factorization problem](https://mlsanity.com/paper/2411.15972/) (2024)
- [Non-Asymptotic Bounds for Closed-Loop Identification of Sub-Exponentially Growing Nonlinear Stochastic Systems](https://mlsanity.com/paper/2412.04157/) (2024)
- [Logarithmic Regret for Nonlinear Control](https://mlsanity.com/paper/2501.10261/) (2025)
- [Kernel conditional tests from learning-theoretic bounds](https://mlsanity.com/paper/2506.03898/) (2025)
- [Adaptive prediction theory combining offline and online learning](https://mlsanity.com/paper/2512.00342/) (2025)
- [Kernel-Based Learning of Safety Barriers](https://mlsanity.com/paper/2601.12002/) (2026)

## Abstract (arXiv)

We study square loss in a realizable time-series framework with martingale difference noise. Our main result is a fast rate excess risk bound which shows that whenever a trajectory hypercontractivity condition holds, the risk of the least-squares estimator on dependent data matches the iid rate order-wise after a burn-in time. In comparison, many existing results in learning from dependent data have rates where the effective sample size is deflated by a factor of the mixing-time of the underlying process, even after the burn-in time. Furthermore, our results allow the covariate process to exhibit long range correlations which are substantially weaker than geometric ergodicity. We call this phenomenon learning with little mixing, and present several examples for when it occurs: bounded function classes for which the L2 and L2+ε norms are equivalent, ergodic finite state Markov chains, various parametric models, and a broad family of infinite dimensional ℓ2(mathbbN) ellipsoids. By instantiating our main result to system identification of nonlinear dynamics with generalized linear model transitions, we obtain a nearly minimax optimal excess risk bound after only a polynomial burn-in time.