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 {\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\cdot d$ larger compared to existing work.
Cite
Text
Nguyen et al. "Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD." Neural Information Processing Systems, 2019.Markdown
[Nguyen et al. "Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD." Neural Information Processing Systems, 2019.](https://mlanthology.org/neurips/2019/nguyen2019neurips-tight/)BibTeX
@inproceedings{nguyen2019neurips-tight,
title = {{Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD}},
author = {Nguyen, Phuong_Ha and Nguyen, Lam and van Dijk, Marten},
booktitle = {Neural Information Processing Systems},
year = {2019},
pages = {3665-3674},
url = {https://mlanthology.org/neurips/2019/nguyen2019neurips-tight/}
}