Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.01155
curl -X POST /api/v1/records/arxiv/2611.01155/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.01155/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'