Stochastic Gradient Descent with Polyak's Learning Rate

Abstract

Stochastic gradient descent (SGD) for strongly convex functions converges at the rate $\bO(1/k)$. However, achieving good results in practice requires tuning the parameters (for example the learning rate) of the algorithm. In this paper we propose a generalization of the Polyak step size, used for subgradient methods, to Stochastic gradient descent. We prove a non-asymptotic convergence at the rate $\bO(1/k)$ with a rate constant which can be better than the corresponding rate constant for optimally scheduled SGD. We demonstrate that the method is effective in practice, and on convex optimization problems and on training deep neural networks, and compare to the theoretical rate.

References in corpus (7)

• Adam: A Method for Stochastic Optimization
• ADADELTA: An Adaptive Learning Rate Method
• Striving for Simplicity: The All Convolutional Net
• On the Convergence of Adam and Beyond
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Train faster, generalize better: Stability of stochastic gradient descent
• WNGrad: Learn the Learning Rate in Gradient Descent

Cited by in corpus (5)

• Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence
• Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent
• Training Neural Networks for and by Interpolation
• Minimizing Quantum Renyi Divergences via Mirror Descent with Polyak Step Size
• Stochastic Polyak Stepsize with a Moving Target