Part of Advances in Neural Information Processing Systems 32 (NeurIPS 2019)
PHUONG_HA NGUYEN, Lam Nguyen, Marten van Dijk
We study the convergence of Stochastic Gradient Descent (SGD) for strongly convex objective functions. We prove for all t a lower bound on the expected convergence rate after the t-th SGD iteration; the lower bound is over all possible sequences of diminishing step sizes. It implies that recently proposed sequences of step sizes at ICML 2018 and ICML 2019 are {\em universally} close to optimal in that the expected convergence rate after {\em each} iteration is within a factor 32 of our lower bound. This factor is independent of dimension d. We offer a framework for comparing with lower bounds in state-of-the-art literature and when applied to SGD for strongly convex objective functions our lower bound is a significant factor 775⋅d larger compared to existing work.