This paper aims to clearly distinguish between Stochastic Gradient Descent
with Momentum (SGDM) and Adam in terms of their convergence rates. We
demonstrate that Adam achieves a faster convergence compared to SGDM under the
condition of non-uniformly bounded smoothness. Our findings reveal that: (1) in
deterministic environments, Adam can attain the known lower bound for the
convergence rate of deterministic first-order optimizers, whereas the
convergence rate of Gradient Descent with Momentum (GDM) has higher order
dependence on the initial function value; (2) in stochastic setting, Adam's
convergence rate upper bound matches the lower bounds of stochastic first-order
optimizers, considering both the initial function value and the final error,
whereas there are instances where SGDM fails to converge with any learning
rate. These insights distinctly differentiate Adam and SGDM regarding their
convergence rates. Additionally, by introducing a novel stopping-time based
technique, we further prove that if we consider the minimum gradient norm
during iterations, the corresponding convergence rate can match the lower
bounds across all problem hyperparameters. The technique can also help proving
that Adam with a specific hyperparameter scheduler is parameter-agnostic, which
hence can be of independent interest.

本文旨在清楚地区分随机梯度下降法和带动量的 Adam 算法在收敛速度方面的差异。我们证明了在非均匀有界平滑性条件下，Adam 算法相对于随机梯度下降法具有更快的收敛速度。我们的发现表明：（1）在确定性环境中，Adam 算法可以达到确定性一阶优化器收敛速度的已知下界，而具有动量的梯度下降法的收敛速度对初始函数值具有更高的依赖度；（2）在随机设置中，Adam 算法的收敛速度上界与随机一阶优化器的下界相匹配，同时考虑初始函数值和最终误差，而随机梯度下降法的学习率存在无法收敛的情况。这些观点可以明显区分 Adam 算法和随机梯度下降法的收敛速度。此外，通过引入一种新的基于停止时间的技术，我们进一步证明了如果在迭代过程中考虑最小梯度范数，相应的收敛速度可以在所有问题超参数上匹配下界。该技术还可以帮助证明具有特定超参数调度器的 Adam 算法是参数不可知的，这一点可能具有独立的研究意义。

Adam 在非均匀平滑性条件下的收敛性：从 SGDM 到更进一步的分离性

On the Convergence of Adam under Non-uniform Smoothness: Separability  from SGDM and Beyond

Federated Averaging (FedAvg) is known to experience convergence issues when
encountering significant clients system heterogeneity and data heterogeneity.
Server momentum has been proposed as an effective mitigation. However, existing
server momentum works are restrictive in the momentum formulation, do not
properly schedule hyperparameters and focus only on system homogeneous
settings, which leaves the role of server momentum still an under-explored
problem. In this paper, we propose a general framework for server momentum,
that (a) covers a large class of momentum schemes that are unexplored in
federated learning (FL), (b) enables a popular stagewise hyperparameter
scheduler, (c) allows heterogeneous and asynchronous local computing. We
provide rigorous convergence analysis for the proposed framework. To our best
knowledge, this is the first work that thoroughly analyzes the performances of
server momentum with a hyperparameter scheduler and system heterogeneity.
Extensive experiments validate the effectiveness of our proposed framework.

提出了一种服务器动量的通用框架，用来解决联邦学习中由于客户端系统和数据异质性引起的收敛问题，并通过严密的收敛分析和大量实验证实了该框架的有效性。