Metraipolis › archive › dc_045e1c50eeb7
Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent — arXiv:2611.01155
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.01155
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:25:02.619Z
- SHA-256 of the archived text
bd1486471abb08125b0becfc613e1c70931245c739500f6164f0db4ff3f8345b- Stable URL of this page
https://metraipolis.com/documento/dc_045e1c50eeb7
How to cite
Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent — arXiv:2611.01155 — arXiv (en), https://arxiv.org/abs/2611.01155 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_045e1c50eeb7 (Metraipolis archive dc_045e1c50eeb7, sha256 bd1486471abb08125b0becfc613e1c70931245c739500f6164f0db4ff3f8345b)
BibTeX
@misc{dc045e1c50eeb7,
title = {Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent — arXiv:2611.01155},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.01155},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_045e1c50eeb7; sha256 bd1486471abb08125b0becfc613e1c70931245c739500f6164f0db4ff3f8345b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01155. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every fixed exponent $\gamma\in(1/2,1)$, a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order $n^{1/2-\gamma}+n^{\gamma-1}$ in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of $\gamma$. The nonlinear bias contributes $n^{1/2-\gamma}$ even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order $n^{-(1-\gamma)/2}$ for the relative mean error of estimating the limiting variance from one SGD trajectory, uniformly over a scalar quadratic family. With the limiting variance known, achieving approximation error $\varepsilon$ on this example takes order $\varepsilon^{-4}$ iterations for the best choice $\gamma=3/4$. Achieving both Gaussian approximation and relative mean variance-estimation errors at most $\varepsilon$ uniformly over the model class requires at least order $\varepsilon^{-6}$ iterations for every fixed $\gamma$.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG); Optimization and Control (math.OC); Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2611.01155 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:02:37.807Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).