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.

The 33th Annual Conference on Neural Information Processing Systems (NeurIPS 2019)

References in corpus (5)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• SGD: General Analysis and Improved Rates
• New Convergence Aspects of Stochastic Gradient Algorithms

Cited by in corpus (6)

• Better Theory for SGD in the Nonconvex World
• Random Reshuffling: Simple Analysis with Vast Improvements
• Lower error bounds for the stochastic gradient descent optimization algorithm: Sharp convergence rates for slowly and fast decaying learning rates
• On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Size
• Improving the convergence of SGD through adaptive batch sizes
• Hogwild! over Distributed Local Data Sets with Linearly Increasing Mini-Batch Sizes