schema_version: 1
title: SGD with Vanishing Correlated Gradient Errors (technique notes)
abstract: For strongly convex smooth objectives and deterministic historical gradient-error
  weights, the notes derive convergence and a PR CLT whose effective covariance depends
  on cumulative weights and innovation cross-covariance. Running averages and fixed
  c/t gains illustrate different single-step and downstream objectives. Within normalized
  deterministic scalar historical linear estimators, a sharp cumulative variance bound
  is attained by a polynomial-gain recursion under the stated exponent conditions.
field: Optimization
license: CC-BY-4.0
type: paper
authors:
- eggtea
keywords:
- SGD
- Polyak–Ruppert averaging
- correlated errors
- variance lower bound
main: SGD with Vanishing Correlated Gradient Errors.pdf
takeaways: takeaways.md
verification:
- type: review
  path: verification/review.md
  status: materials-present-not-independently-verified
  model: GPT-6 (Codex; exact runtime variant not exposed)
  date: '2026-10-17'
  scope: Main statements, convergence and PR proofs, variance bound and attainment;
    experiment implementation inspected; no full experiment rerun.
references:
- title: Efficient estimations from a slowly convergent Robbins--Monro process
  authors: D. Ruppert
  url: https://ecommons.cornell.edu/entities/publication/9a14790e-66a6-4460-9280-e9fb146fd02d
- title: Acceleration of stochastic approximation by averaging
  authors: B. T. Polyak and A. B. Juditsky
  url: https://doi.org/10.1137/0330046
- title: 'Stochastic approximation with averaging of the iterates: Optimal asymptotic
    rate of convergence for general processes'
  authors: H. J. Kushner and J. Yang
  url: https://doi.org/10.1137/0331047
- title: 'On linear stochastic approximation: Fine-grained Polyak--Ruppert and non-asymptotic
    concentration. In'
  authors: W. Mou, C. J. Li, M. J. Wainwright, P. L. Bartlett, and M. I. Jordan
  url: https://proceedings.mlr.press/v125/mou20a.html
- title: Convergence rate of linear two-time-scale stochastic approximation
  authors: V. R. Konda and J. N. Tsitsiklis
  url: https://doi.org/10.1214/105051604000000116
- title: Convergence rate and averaging of nonlinear two-time-scale stochastic approximation
    algorithms
  authors: A. Mokkadem and M. Pelletier
  url: https://doi.org/10.1214/105051606000000448
- title: 'A generalization of the averaging procedure: The use of two-time-scale algorithms'
  authors: A. Mokkadem and M. Pelletier
  url: https://doi.org/10.1137/080718395
- title: On the convergence of SGD with biased gradients
  authors: A. Ajalloeian and S. U. Stich
  url: https://arxiv.org/abs/2008.00051
- title: 'Stochastic compositional gradient descent: Algorithms for minimizing compositions
    of expected-value functions'
  authors: M. Wang, E. X. Fang, and H. Liu
  url: https://doi.org/10.1007/s10107-016-1017-3
- title: Stochastic gradients under nuisances
  authors: F. Yu, R. Mehta, A. Luedtke, and Z. Harchaoui
  url: https://arxiv.org/abs/2508.20326
- title: A convergence theorem for non negative almost supermartingales and some applications.
    In
  authors: H. Robbins and D. Siegmund
  url: https://doi.org/10.1016/B978-0-12-604550-5.50015-8