Adaptive gradient methods are arguably the most successful optimization
algorithms for neural network training. While it is well-known that adaptive
gradient methods can achieve better dimensional dependence than stochastic
gradient descent (SGD) under favorable geometry for stochastic convex
optimization, the theoretical justification for their success in stochastic
non-convex optimization remains elusive. In this paper, we aim to close this
gap by analyzing the convergence rates of AdaGrad measured by the $\ell_1$-norm
of the gradient. Specifically, when the objective has $L$-Lipschitz gradient
and the stochastic gradient variance is bounded by $\sigma^2$, we prove a
worst-case convergence rate of $\tilde{\mathcal{O}}(\frac{\sqrt{d}L}{\sqrt{T}}
+ \frac{\sqrt{d} \sigma}{T^{1/4}})$, where $d$ is the dimension of the
problem.We also present a lower bound of ${\Omega}(\frac{\sqrt{d}}{\sqrt{T}})$
for minimizing the gradient $\ell_1$-norm in the deterministic setting, showing
the tightness of our upper bound in the noiseless case. Moreover, under more
fine-grained assumptions on the smoothness structure of the objective and the
gradient noise and under favorable gradient $\ell_1/\ell_2$ geometry, we show
that AdaGrad can potentially shave a factor of $\sqrt{d}$ compared to SGD. To
the best of our knowledge, this is the first result for adaptive gradient
methods that demonstrates a provable gain over SGD in the non-convex setting.

分析了 AdaGrad 在随机非凸优化中收敛速率，证明了存在优于 SGD 的收敛速度，并给出了收敛速率的上界和下界。