Linear Convergence of Adaptive Stochastic Gradient Descent
This work addresses the need for theoretical guarantees in adaptive optimization algorithms for machine learning practitioners, though it is incremental as it builds on existing AdaGrad methods.
The paper tackles the problem of proving linear convergence for the AdaGrad-Norm adaptive stochastic gradient method, showing it achieves this rate for strongly convex functions or those satisfying the Polyak Lojasiewicz inequality, with theoretical robustness to hyper-parameter tuning validated by numerical experiments.
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.