Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent
TL;DR
Sharp lower bounds are established for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes for Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes.
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 $\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$.