Research map / Learning theory and algorithms / Sample complexity
Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that ERM for square loss on beta-mixing data attains a near mixing-free rate governed by a weak-variance critical radius, provided the class is weakly sub-Gaussian in Orlicz norm, via blocking plus mixed-tail generic chaining.
Problem
Sample-size deflation by mixing time (multiplicative) in non-asymptotic rates for learning with dependent beta-mixing data and square loss, without realizability.
Approach
Combines blocking with a Psi_p-Bernstein inequality and mixed-tail generic chaining, under a weakly sub-Gaussian class condition ||f||_{Psi_p} <= L||f||_{L2}^eta, so that mixing only enters through additive higher-order terms and the leading term depends on a weak variance proxy.
Key results
- Main theorem: ERM satisfies ||f_hat - f*||_{L2}^2 <= c(r_star^2 + V_{2q} log(1/delta)/n) with probability 1-4delta, once n exceeds a polynomial burn-in and k >= k_mix, for weakly sub-Gaussian classes.
- For d-dimensional parametric classes, the leading term is weak variance times (d + log(1/delta))/n, recovering the parametric rate after a polynomial burn-in.
- Realizable bounded linear regression: bound c_2 V(W)(d+log(1/delta))/n holds when n/k >= c_1 (...)(kB_W^2/V(W))(d+log(1/delta)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use mixed-tail generic chaining and weakly sub-Gaussian class assumptions with blocking | ERM for dependent square-loss learning · Beta-mixing data; convex or realizable hypothesis classes | L2 estimation error squared | Helped |
Limitations
- Burn-in can be exponentially large in dimension for smoothness classes unless smoothness scales with dimension
- Requires convex or realizable hypothesis class for ERM analysis
- Does not cover the martingale (mixing-free) regime with self-normalized arguments
Experimental setup
Metrics: L2 estimation error bound burn-in sample size
Baselines: Martingale-based analysis of square loss ERM Blocking with Hoeffding/Bernstein bounds
Builds on: Learning without concentration Blocking technique for beta-mixing Mixed-tail generic chaining Fuk-Nagaev inequality based linear regression analysis
Closest papers by meaning
- Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples (ICML 2024 · similarity 0.86)
- Sparse Variational Student-t Processes (AAAI 2024 · similarity 0.85)
- Towards Theoretical Understanding of Learning Large-scale Dependent Data via Random Features (ICML 2024 · similarity 0.85)
- Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD (NeurIPS 2024 · similarity 0.85)
- Stochastic Zeroth-Order Optimization Under Heavy-Tailed Noise (NeurIPS 2026 · similarity 0.84)
- Demystifying SGD with Doubly Stochastic Gradients (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.