On the Convergence of Stochastic Gradient Descent with Bandwidth-based Step Size
arXiv:2102.09031
Abstract
We investigate the stochastic gradient descent (SGD) method where the step size lies within a banded region instead of being given by a fixed formula. The optimal convergence rate under mild conditions and large initial step size is proved. Our analysis provides comparable theoretical error bounds for SGD associated with a variety of step sizes. In addition, the convergence rates for some existing step size strategies, e.g., triangular policy and cosine-wave, can be revealed by our analytical framework under the boundary constraints. The bandwidth-based step size provides efficient and flexible step size selection in optimization. We also propose a up-down policy and give several non-monotonic step sizes. Numerical experiments demonstrate the efficiency and significant potential of the bandwidth-based step-size in many applications.
References in corpus (11)
- ADADELTA: An Adaptive Learning Rate Method
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Identifying and attacking the saddle point problem in high-dimensional non-convex optimization
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Barzilai-Borwein Step Size for Stochastic Gradient Descent
- Snapshot Ensembles: Train 1, get M for free
- Gradient Descent Can Take Exponential Time to Escape Saddle Points
- How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
- Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
- Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
- A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance