Linear Convergence of Adaptive Stochastic Gradient Descent
[edit]
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:14751485, 2020.
Abstract
We prove that the norm version of the adaptive stochastic gradient method (AdaGradNorm) achieves a linear convergence rate for a subset of either strongly convex functions or nonconvex 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 balancedness of the stochastic gradient norms—to depict the landscape of a function. RUIG plays a key role in proving the robustness of AdaGradNorm to its hyperparameter tuning in the stochastic setting. On top of RUIG, we develop a twostage framework to prove the linear convergence of AdaGradNorm 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.
Related Material


