Linear Convergence of Adaptive Stochastic Gradient Descent
arXiv:1908.10525
Abstract
We prove that the norm version of the adaptive stochastic gradient method (AdaGrad-Norm) achieves a linear convergence rate for a subset of either strongly convex functions or non-convex functions that satisfy the Polyak Lojasiewicz (PL) inequality. The paper introduces the notion of Restricted Uniform Inequality of Gradients (RUIG)---which is a measure of the balanced-ness of the stochastic gradient norms---to depict the landscape of a function. RUIG plays a key role in proving the robustness of AdaGrad-Norm to its hyper-parameter tuning in the stochastic setting. On top of RUIG, we develop a two-stage framework to prove the linear convergence of AdaGrad-Norm without knowing the parameters of the objective functions. This framework can likely be extended to other adaptive stepsize algorithms. The numerical experiments validate the theory and suggest future directions for improvement.
References in corpus (14)
- Adam: A Method for Stochastic Optimization
- On the Convergence of Adam and Beyond
- Understanding deep learning requires rethinking generalization
- A Convergence Theory for Deep Learning via Over-Parameterization
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- Gradient Descent Provably Optimizes Over-parameterized Neural Networks
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
- On exponential convergence of SGD in non-convex over-parametrized learning
- WNGrad: Learn the Learning Rate in Gradient Descent
- Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
- Online Adaptive Methods, Universality and Acceleration
- SGD Converges to Global Minimum in Deep Learning via Star-convex Path
- Minimum weight norm models do not always generalize well for over-parameterized problems
- Diagonal Rescaling For Neural Networks