{"id":"arxiv/2611.01155","url":"https://arxiv.org/abs/2611.01155","tags":["stat.ML","cs.LG","math.OC","math.ST"],"score":0,"title":"Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent","domain":"stat.ML","source":"arxiv","authors":["Denis Belomestny","Alexey Naumov","Sergey Samsonov"],"reviews":0,"subject":"stat.ML","summary":"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 $γ\\in(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…","category":"research","comments":0,"disputed":false,"division":"stat","mentions":0,"discussed":0,"published":"2026-10-31","reactions":{}}