# Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 36 references that are in the map.
- First posted on arXiv 8 Feb 2024.

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

- [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)
- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [Learning with Square Loss: Localization through Offset Rademacher Complexity](https://mlsanity.com/paper/1502.06134/) (2015)
- [Learning with little mixing](https://mlsanity.com/paper/2206.08269/) (2022)
- [A Tutorial on the Non-Asymptotic Theory of System Identification](https://mlsanity.com/paper/2309.03873/) (2023)
- [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)
- [The noise level in linear regression with dependent data](https://mlsanity.com/paper/2305.11165/) (2023)
- [Generalization for slowly mixing processes](https://mlsanity.com/paper/2305.00977/) (2023)

## Built on by (most cited first, 10 of 10)

- [From Self-Attention to Markov Models: Unveiling the Dynamics of Generative Transformers](https://mlsanity.com/paper/2402.13512/) (2024)
- [Active Learning for Control-Oriented Identification of Nonlinear Systems](https://mlsanity.com/paper/2404.09030/) (2024)
- [Rate-Optimal Non-Asymptotics for the Quadratic Prediction Error Method](https://mlsanity.com/paper/2404.07937/) (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)
- [Recovery Guarantees for Continual Learning of Dependent Tasks: Memory, Data-Dependent Regularization, and Data-Dependent Weights](https://mlsanity.com/paper/2604.17578/) (2026)
- [A Short Information-Theoretic Analysis of Linear Auto-Regressive Learning](https://mlsanity.com/paper/2409.06437/) (2024)
- [Smart Predict-then-Optimize Method with Dependent Data: Risk Bounds and Calibration of Autoregression](https://mlsanity.com/paper/2411.12653/) (2024)
- [Stability properties of gradient flow dynamics for the symmetric low-rank matrix factorization problem](https://mlsanity.com/paper/2411.15972/) (2024)
- [Logarithmic Regret for Nonlinear Control](https://mlsanity.com/paper/2501.10261/) (2025)

## Abstract (arXiv)

In this work, we study statistical learning with dependent (β-mixing) data and square loss in a hypothesis class mathscrFsubset LPsip where Psip is the norm |f|Psip triangleq supm≥ 1 m-1/p |f|Lm  for some p∈ [2,∞]. Our inquiry is motivated by the search for a sharp noise interaction term, or variance proxy, in learning with dependent data. Absent any realizability assumption, typical non-asymptotic results exhibit variance proxies that are deflated multiplicatively by the mixing time of the underlying covariates process. We show that whenever the topologies of L2 and Psip are comparable on our hypothesis class mathscrF -- that is, mathscrF is a weakly sub-Gaussian class: |f|Psip lesssim |f|L2η for some η∈ (0,1] -- the empirical risk minimizer achieves a rate that only depends on the complexity of the class and second order statistics in its leading term. Our result holds whether the problem is realizable or not and we refer to this as a near mixing-free rate, since direct dependence on mixing is relegated to an additive higher order term. We arrive at our result by combining the above notion of a weakly sub-Gaussian class with mixed tail generic chaining. This combination allows us to compute sharp, instance-optimal rates for a wide range of problems. Examples that satisfy our framework include sub-Gaussian linear regression, more general smoothly parameterized function classes, finite hypothesis classes, and bounded smoothness classes.