Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent

Abstract

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 γ∈(1/2,1), a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order n^1/2−γ+n^γ−1 in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of γ. The nonlinear bias contributes n^1/2−γ even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order n^{−(1−γ)/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 ε on this example takes order ε⁻⁴ iterations for the best choice γ=3/4. Achieving both Gaussian approximation and relative mean variance-estimation errors at most ε uniformly over the model class requires at least order ε⁻⁶ iterations for every fixed γ.

Online Covariance Estimation for Averaged Stochastic Gradient Descent on Riemannian Manifolds
Jingrong Guan, Liwei Jiang, Sen Na
arXiv24 Oct 2026PreprintCC BY 4.0Full textOptimisation & control StatisticsarXiv
Self-Normalized Inference from Riemannian Stochastic Gradient Paths
Xiaotian Chang, Qirui Hu, Yi Liu
arXiv1 Nov 2026PreprintCC BY 4.0Full textStatisticsarXiv
Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions
Weiming Ou, Xiao Wang
arXiv26 Sep 2026PreprintCC BY 4.0Full textProbability StatisticsarXiv
Scalable Statistical Inference in Stochastic Gradient Descent
Rahul Singh, Abhinek Shukla
arXiv31 Aug 2026PreprintarXiv licenceFull textStatisticsarXiv
Averaged proximal reflected gradient method for monotone variational inequalities
Xiaokai Chang, Jialin Li, Jun Yang
arXiv15 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{belomestny2026lower,
  title = {{Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent}},
  author = {Denis Belomestny and Alexey Naumov and Sergey Samsonov},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.01155},
  eprint = {2611.01155},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.01155},
}

RIS

TY  - UNPB
TI  - Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent
AU  - Denis Belomestny
AU  - Alexey Naumov
AU  - Sergey Samsonov
PY  - 2026
DA  - 2026/11/01
PB  - arXiv
DO  - 10.48550/arxiv.2611.01155
UR  - https://arxiv.org/abs/2611.01155
AB  - 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 γ∈(1/2,1), a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order n^1/2−γ+n^γ−1 in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of γ. The nonlinear bias contributes n^1/2−γ even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order n^−(1−γ)/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 ε on this example takes order ε^−4 iterations for the best choice γ=3/4. Achieving both Gaussian approximation and relative mean variance-estimation errors at most ε uniformly over the model class requires at least order ε^−6 iterations for every fixed γ.
ER  -

Abstract

Related

Cite