Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization

Anas Barakat, Pascal BianchiarXiv 2019 · arXiv

Introduction

Adaptive gradient methods, most notably ADAM, have become the standard for training deep neural networks due to their empirical efficiency. However, their theoretical properties, particularly in non-convex settings, have historically been less certain. While these methods often outperform standard Stochastic Gradient Descent (SGD), research has shown that ADAM can fail to converge even on simple convex problems under specific conditions. This paper addresses this gap by providing a rigorous theoretical foundation for a generalized momentum algorithm that encompasses popular adaptive methods like AdaGrad, RMSProp, and ADAM.

Methodology

The authors analyze a unified framework for momentum-based adaptive algorithms. To ensure stability and convergence in non-convex landscapes, they introduce a "clipped" version of the adaptive step size.

Comparison of effective step size and momentum parameters across common optimization algorithms.

The core methodological contributions include:

  1. Bounded Adaptive Step Size (Clipping): The proposed algorithm constrains the adaptive step size within a theoretically safe range. This upper bound is derived from the Lipschitz constant of the objective function's gradient, preventing the algorithm from taking destabilizingly large steps.
  2. Lyapunov Analysis: To track the progress of the optimization, the authors construct a custom Lyapunov function $H(x, y) = f(x) + \frac{1}{2b}\|y\|^2$, where $y$ represents a scaled version of the momentum buffer. This allows them to prove that the "energy" of the system decreases over time.
  3. Kurdyka-Lojasiewicz (KL) Framework: Beyond simple gradient convergence, the paper utilizes the KL property—a geometric condition characterizing function "flatness" near critical points—to derive specific convergence rates for the objective function values.

Convergence Analysis

The theoretical analysis yields several key results for both deterministic and stochastic settings:

  • Gradient Convergence: In both settings, the minimum squared gradient norm decreases at a rate of $O(1/n)$. This matches the optimal rate for standard non-adaptive gradient descent in non-convex optimization. In the stochastic case, the rate includes an additional term proportional to the gradient noise variance.
  • Function Value Convergence: By leveraging the KL property, the authors establish that for a KL exponent $\theta \in (0, 1/2)$, the function value $f(x_k)$ converges to the minimum at a sublinear rate of $O(k^{\frac{1}{2\theta-1}})$.
  • Dimension Independence: Notably, these convergence rates are independent of the parameter space dimension $d$, making the results highly relevant for modern high-dimensional deep learning models.

Experimental Insights

The theoretical findings were illustrated using a synthetic toy problem $f(x) = x^p$. By varying $p \in [1, 7]$, the authors demonstrated how the local geometry (captured by the KL exponent) dictates the convergence speed. "Clipped ADAM" was shown to maintain stability and achieve the predicted rates across various levels of function flatness.

Conclusion and Future Work

This work provides a significant step toward bridging the gap between the practice and theory of adaptive optimization. By introducing clipping and utilizing the KL property, it offers the first convergence rate guarantees for objective values in adaptive methods.

However, practical challenges remain. The "safe" clipping bound depends on the Lipschitz constant $L$, which is typically unknown in deep learning. Furthermore, while the analysis covers smooth functions, extending these guarantees to non-smooth objectives (e.g., those using ReLU activations) remains an important avenue for future research.

Summary updated

Abstract

Although ADAM is a very popular algorithm for optimizing the weights of neural networks, it has been recently shown that it can diverge even in simple convex optimization examples. Several variants of ADAM have been proposed to circumvent this convergence issue. In this work, we study the ADAM algorithm for smooth nonconvex optimization under a boundedness assumption on the adaptive learning rate. The bound on the adaptive step size depends on the Lipschitz constant of the gradient of the objective function and provides safe theoretical adaptive step sizes. Under this boundedness assumption, we show a novel first order convergence rate result in both deterministic and stochastic contexts. Furthermore, we establish convergence rates of the function value sequence using the Kurdyka-Lojasiewicz property.
BibTeX
@misc{barakat2019convergence,
  author = {Anas Barakat and Pascal Bianchi},
  title = {{Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization}},
  year = {2019},
  eprint = {1911.07596},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1911.07596},
}
Figure