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 的收敛速度，并给出了收敛速率的上界和下界。

自适应梯度方法在细化平滑度和噪声假设下的收敛分析

Convergence Analysis of Adaptive Gradient Methods under Refined  Smoothness and Noise Assumptions

We study differentially private (DP) algorithms for stochastic non-convex
optimization. In this problem, the goal is to minimize the population loss over
a $p$-dimensional space given $n$ i.i.d. samples drawn from a distribution. We
improve upon the population gradient bound of ${\sqrt{p}}/{\sqrt{n}}$ from
prior work and obtain a sharper rate of $\sqrt[4]{p}/\sqrt{n}$. We obtain this
rate by providing the first analyses on a collection of private gradient-based
methods, including adaptive algorithms DP RMSProp and DP Adam. Our proof
technique leverages the connection between differential privacy and adaptive
data analysis to bound gradient estimation error at every iterate, which
circumvents the worse generalization bound from the standard uniform
convergence argument. Finally, we evaluate the proposed algorithms on two
popular deep learning tasks and demonstrate the empirical advantages of DP
adaptive gradient methods over standard DP SGD.

研究不同 ially private (DP) 算法在随机非凸优化中的应用，通过提供对私有梯度法的分析，提出了 DP RMSProp 和 DP Adam 等最佳算法来达成更快的收敛速度，在两个流行的深度学习任务中，证明了 DP 自适应梯度法比标准的 DP SGD 更具有优势。

私有随机非凸优化：自适应算法和更紧的泛化界

Private Stochastic Non-Convex Optimization: Adaptive Algorithms and  Tighter Generalization Bounds

In this paper, we study stochastic non-convex optimization with non-convex
random functions. Recent studies on non-convex optimization revolve around
establishing second-order convergence, i.e., converging to a nearly
second-order optimal stationary points. However, existing results on stochastic
non-convex optimization are limited, especially with a high probability
second-order convergence. We propose a novel updating step (named NCG-S) by
leveraging a stochastic gradient and a noisy negative curvature of a stochastic
Hessian, where the stochastic gradient and Hessian are based on a proper
mini-batch of random functions. Building on this step, we develop two
algorithms and establish their high probability second-order convergence. To
the best of our knowledge, the proposed stochastic algorithms are the first
with a second-order convergence in {\it high probability} and a time complexity
that is {\it almost linear} in the problem's dimensionality.

本文研究带有非凸随机函数的随机非凸优化，并提出一种称为 NCG-S 的新型更新步骤，可以在高概率下实现二阶收敛，所提出的随机算法是首个具有高概率二阶收敛和几乎是线性时间复杂度的方法。