mlsanityData to 14 Oct 2026

Learning with little mixing

arXiv 2206.08269 ↗First posted 16 Jun 2022cs.LG stat.MLcited by 33

Not on the map. Why?

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.

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

18 of 61 references.

References · 18

  1. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  2. 2018Learning Without Mixing: Towards A Sharp Analysis of Linear System Identificationcited by 158
  3. 2018Near optimal finite time identification of arbitrary linear dynamical systemscited by 89
  4. 2017Finite Time Identification in Unstable Linear Systemscited by 66
  5. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  6. 2014Learning without Concentrationcited by 50
  7. 2020Learning nonlinear dynamical systems from a single trajectorycited by 46
  8. 2020Non-asymptotic and Accurate Learning of Nonlinear Dynamical Systemscited by 39
  9. 2015Learning with Square Loss: Localization through Offset Rademacher Complexitycited by 38
  10. 2020Finite-time Identification of Stable Linear Systems: Optimality of the Least-Squares Estimatorcited by 26
  11. 2022Single Trajectory Nonparametric Learning of Nonlinear Dynamicscited by 26
  12. 2022Learning from many trajectoriescited by 24
6 more
  1. 2021Linear Systems can be Hard to Learncited by 20
  2. 2021Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systemscited by 17
  3. 2021On Empirical Risk Minimization with Dependent and Heavy-Tailed Datacited by 16
  4. 2019Learning from weakly dependent data under Dobrushin's conditioncited by 13
  5. 2015On aggregation for heavy-tailed classescited by 7
  6. 2021Improved Prediction and Network Estimation Using the Monotone Single Index Multi-variate Autoregressive Modelcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 4; 2023: 6; 2024: 13; 2025: 5; 2026: 5.

33 papers.

Sort:

By area:

  1. 2023Transformers as Algorithms: Generalization and Stability in In-context Learningcited by 222
  2. 2022Statistical Learning Theory for Control: A Finite Sample Perspectivecited by 53
  3. 2024From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformerscited by 34
  4. 2023Optimistic Active Exploration of Dynamical Systemscited by 32
  5. 2023A Tutorial on the Non-Asymptotic Theory of System Identificationcited by 26
  6. 2024On the Performance of Empirical Risk Minimization with Smoothed Datacited by 13
  7. 2024Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Losscited by 10
  8. 2023Streaming PCA for Markovian Datacited by 9
  9. 2024Active Learning for Control-Oriented Identification of Nonlinear Systemscited by 7
  10. 2023The noise level in linear regression with dependent datacited by 6
  11. 2023Non-asymptotic System Identification for Linear Systems with Nonlinear Policiescited by 5
  12. 2024On the Consistency of Kernel Methods with Dependent Observationscited by 4
21 more
  1. 2025Optimal kernel regression bounds under energy-bounded noisecited by 4
  2. 2024Rate-Optimal Non-Asymptotics for the Quadratic Prediction Error Methodcited by 3
  3. 2024Long-Context Linear System Identificationcited by 3
  4. 2024Length independent generalization bounds for deep SSM architectures via Rademacher contraction and stability constraintscited by 2
  5. 2025Nonconvex Linear System Identification with Minimal State Representationcited by 2
  6. 2022Concentration Phenomenon for Random Dynamical Systems: An Operator Theoretic Approachcited by 1
  7. 2022A note on the smallest eigenvalue of the empirical covariance of causal Gaussian processescited by 1
  8. 2024Finite Sample Frequency Domain Identificationcited by 1
  9. 2024A least-square method for non-asymptotic identification in linear switching controlcited by 1
  10. 2024Single Trajectory Conformal Predictioncited by 1
  11. 2026Recovery Guarantees for Continual Learning of Dependent Tasks: Memory, Data-Dependent Regularization, and Data-Dependent Weightscited by 1
  12. 2022Learning Nonlinear Couplings in Network of Agents from a Single Sample Trajectorycited by 0
  13. 2024Stability properties of gradient flow dynamics for the symmetric low-rank matrix factorization problemcited by 0
  14. 2024Non-Asymptotic Bounds for Closed-Loop Identification of Sub-Exponentially Growing Nonlinear Stochastic Systemscited by 0
  15. 2025Logarithmic Regret for Nonlinear Controlcited by 0
  16. 2025Kernel conditional tests from learning-theoretic boundscited by 0
  17. 2025Adaptive prediction theory combining offline and online learningcited by 0
  18. 2026Kernel-Based Learning of Safety Barrierscited by 0
  19. 2026Uniform error bounds for quantized dynamical modelscited by 0
  20. 2026Minimax Optimality and Spectral Routing for Majority-Vote Ensembles under Markov Dependencecited by 0
  21. 2026Two-Layer Linear Auto-Regressive Models Estimate Latent Statescited by 0