On the Convergence of Adam under Non-uniform Smoothness: Separability
  from SGDM and Beyond
Bohan Wang Huishuai Zhang Qi Meng Ruoyu Sun Zhi-Ming Ma Wei Chen
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.