Research map / Learning theory and algorithms / Sample complexity
A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging
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.
Gives a general theorem turning individual high-probability bounds on unaveraged stochastic approximation iterates into sharp concentration bounds for Polyak-Ruppert averaged iterates, with applications to contractive SA, TD-learning, Q-learning, and off-policy TD.
Problem
Finite-time high-probability (concentration) bounds for Polyak-Ruppert averaged stochastic approximation iterates in general settings are underexplored.
Approach
Assume high-probability bounds on the non-averaged SA iterates, and use a local smoothness (pseudo-smoothness) condition plus subgaussian noise and an exponential-moment (MGF) argument to bound the averaged error; step size does not depend on the target probability delta, so the bound holds across the whole distribution.
Key results
- Main theorem gives leading term of order (log(1/delta)+d)/(k+1) times sigma-bar^2 for averaged SA, plus higher-order terms, with the leading term shown tight up to a factor 2*sqrt(6) by a Gaussian construction.
- For contractive SA with additive noise, averaging improves the leading-term constant over non-averaged bounds (24 sigma-bar^2 vs at least 32 sigma^2).
- Under multiplicative noise, the averaged error tail is shown to be heavier than any sub-Weibull distribution (impossibility result).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Polyak–Ruppert averaging instead of the non-averaged SA bound | Contractive SA with additive noise · Contractive SA, additive noise | leading-term squared error bound: 32a\sigma^2 -> 24\bar{\sigma}^2; 32 a^2ec_d (1+\mu)\sigma^2/(a-1) -> 3(d+8\log(2))\bar{\sigma}^2 | Helped |
| Use Polyak–Ruppert averaging | Temporal difference learning · Averaged TD-learning | convergence rate | Helped |
| Use Polyak–Ruppert averaging | Stochastic approximation · General SA | convergence rate in k: O(1/k^\xi) -> O(1/k) | Helped |
| Use Polyak–Ruppert averaging with additive noise | Contractive SA · Additive noise | tail behavior | No clear effect |
| Use Polyak–Ruppert averaging with multiplicative noise | General SA · Multiplicative noise | tail behavior | Hurt |
| Use step-size exponent \xi=1/2 | Linear operator with non-additive noise · Averaged SA | higher-order-term convergence rate: O(1/k^{1+\xi}+1/k^{2-\xi}) | Helped |
| Use step-size exponent \xi=2/3 | Nonlinear operator · Averaged SA | higher-order-term convergence rate: O(1/k^{2\xi}+1/k^{2-\xi}) | Helped |
| Use a smaller \xi | Linear operator with additive noise · Averaged SA | higher-order-term convergence rate: O(1/k^{2-\xi}) | Helped |
| Use Polyak–Ruppert averaging for Q-learning | Asynchronous Q-learning · Q-learning with i.i.d. samples | high-probability error guarantee | Helped |
| Use the proposed framework for off-policy TD(n) | Off-policy TD(n) with linear function approximation · Off-policy TD-learning | high-probability error guarantee | Helped |
Surprising findings
- With multiplicative noise, averaged SA cannot achieve a sub-Weibull tail, unlike non-averaged SA.
- The averaged iterate's squared-error tail bound involves f^2 (heavier) as an artifact of the proof, requiring a separate lemma to recover the original tail.
Limitations
- Leading-order bounds rely on assumption that individual non-averaged high-probability bounds are available and known in form f_xi(delta,k).
- Higher-order terms may be heavier-tailed; tail bound for multiplicative noise is polynomial in delta rather than sub-Weibull.
- Requires subgaussian noise assumptions at fixed point and the Jacobian noise condition.
Experimental setup
Metrics: high-probability error bound tail behavior convergence rate in k
Baselines: non-averaged SA high-probability bounds (Chen et al.) Samsonov et al. averaged LSA bounds
Builds on: Polyak-Ruppert averaging Chen et al. high-probability bounds for contractive SA Moreau envelope smoothing
Closest papers by meaning
- Statistical inference for Linear Stochastic Approximation with Markovian Noise (NeurIPS 2025 · similarity 0.88)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.87)
- Statistical Guarantees for High-Dimensional Stochastic Gradient Descent (NeurIPS 2025 · similarity 0.87)
- How Accurately Can a Gaussian Approximate Stochastic Approximation Iterates? (NeurIPS 2026 · similarity 0.86)
- Generalization Analysis of Stochastic Weight Averaging with General Sampling (ICML 2024 · similarity 0.86)
- Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence (ICML 2025 · similarity 0.86)
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.