@inproceedings{6d5cd33b373d43389cb5f20cd3cb2839,
title = "Tight dimension independent lower bound on the expected convergence rate for diminishing step sizes in SGD",
abstract = "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 universally close to optimal in that the expected convergence rate after 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.",
author = "P.H. Nguyen and L.M. Nguyen and {van Dijk}, M.",
year = "2019",
language = "English",
series = "NeurIPS Proceedings",
publisher = "Neural information processing systems foundation",
editor = "H. Wallach and H. Larochelle and A. Beygelzimer and F. d'Alch{\'e}-Buc and E. Fox and R. Garnett",
booktitle = "Advances in Neural Information Processing Systems 32 (NeurIPS 2019)",
note = "33rd Annual Conference on Neural Information Processing Systems, NeurIPS 2019 ; Conference date: 08-12-2019 Through 14-12-2019",
}