We provide a simple convergence proof for AdaGrad optimizing non-convex
objectives under only affine noise variance and bounded smoothness assumptions.
The proof is essentially based on a novel auxiliary function $\xi$ that helps
eliminate the complexity of handling the correlation between the numerator and
denominator of AdaGrad's update. Leveraging simple proofs, we are able to
obtain tighter results than existing results \citep{faw2022power} and extend
the analysis to several new and important cases. Specifically, for the
over-parameterized regime, we show that AdaGrad needs only
$\mathcal{O}(\frac{1}{\varepsilon^2})$ iterations to ensure the gradient norm
smaller than $\varepsilon$, which matches the rate of SGD and significantly
tighter than existing rates $\mathcal{O}(\frac{1}{\varepsilon^4})$ for AdaGrad.
We then discard the bounded smoothness assumption and consider a realistic
assumption on smoothness called $(L_0,L_1)$-smooth condition, which allows
local smoothness to grow with the gradient norm. Again based on the auxiliary
function $\xi$, we prove that AdaGrad succeeds in converging under
$(L_0,L_1)$-smooth condition as long as the learning rate is lower than a
threshold. Interestingly, we further show that the requirement on learning rate
under the $(L_0,L_1)$-smooth condition is necessary via proof by contradiction,
in contrast with the case of uniform smoothness conditions where convergence is
guaranteed regardless of learning rate choices. Together, our analyses broaden
the understanding of AdaGrad and demonstrate the power of the new auxiliary
function in the investigations of AdaGrad.

本文提供了一种简单的收敛证明方法，证明了当仅有仿射噪声方差和有界光滑性假设时，AdaGrad 优化非凸目标，本文基于一个新的辅助函数 ξ 来消除处理 AdaGrad 更新的分子和分母之间的相关性的复杂性，与现有结果相比得到了更紧的结果，并将分析扩展到了若干个新的重要情况。