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.

本文证明了自适应随机梯度方法的规范版本（AdaGrad-Norm）在强凸函数或满足 Polyak Lojasiewicz 不等式的非凸函数的子集中，达到的收敛速度是线性的。文中引入了梯度的限制均衡不等式（RUIG）的概念，用来描述函数的景观，并且 RUIG 在证明 AdaGrad-Norm 对超参数调整的鲁棒性中发挥着关键作用。我们开发了一个两阶段的框架来证明 AdaGrad-Norm 的线性收敛，而不知道目标函数的参数。数值实验验证了理论，并提出了未来的改进方向。