Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent
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.