Adam-family Methods for Nonsmooth Optimization with Convergence Guarantees

Nachuan Xiao, Xiaoyin Hu, Xin Liu, Kim-Chuan Toh

TL;DR

This paper provides the first comprehensive convergence guarantees for Adam-family optimizers (including Adam, AMSGrad, and AdaBelief) when applied to nonsmooth, non-convex problems like training ReLU-based neural networks. By introducing a novel "two-timescale" framework and leveraging the theory of conservative fields, the authors prove that these popular methods converge even in the presence of heavy-tailed noise and the "pathological" nonsmoothness typical of modern deep learning.

What Problem Does This Paper Address?

Despite the ubiquity of Adam-family optimizers in deep learning, a significant gap exists between theory and practice. Most existing convergence proofs assume that the objective function is "smooth" (differentiable with Lipschitz continuous gradients). However, modern neural networks rely on nonsmooth components like ReLU or Leaky ReLU activation functions. When these are composed, the resulting loss function is not only nonsmooth but often fails to be "Clarke regular"—a standard requirement for traditional nonsmooth analysis.

Furthermore, standard optimization theory usually assumes evaluation noise has a finite variance ($L^2$ integrable). In reality, many machine learning tasks (like language modeling) exhibit "heavy-tailed" noise, where outliers are frequent and variance may be infinite. This paper asks: Can we mathematically guarantee that Adam-family methods will converge under these realistic, messy conditions?

Methods

The authors introduce a Generalized Framework for Adam-family Methods (AFM). The key innovations include:

  • Two-Timescale Updating: The framework decouples the stepsizes for updating the parameters and the evaluation noise. By choosing specific diminishing stepsizes (e.g., in the order of $o(1/\log(k))$), they ensure the algorithm filters out noise effectively while still making progress toward a solution.
  • Conservative Fields: Instead of relying on standard gradients or Clarke subdifferentials, the authors use "conservative fields." This is a relatively new mathematical tool that correctly describes how automatic differentiation (AD) libraries like PyTorch and TensorFlow actually compute "gradients" for nonsmooth functions.
  • Gradient Clipping (ADAM-C & SGD-C): To handle heavy-tailed noise, the authors develop variants that incorporate gradient clipping. They prove convergence even when evaluation noise is only assumed to be integrable ($L^1$), rather than having finite variance.
  • Stationarity Proofs: They prove that their framework converges to "stationary points" in two senses: the conservative field sense and, with random initialization, the more traditional Clarke stationary sense.

Datasets

The authors validated their theoretical findings through extensive numerical experiments on several standard benchmarks:

  • Image Classification: ResNet-50 trained on CIFAR-10 and CIFAR-100.
  • Heavy-Tailed Noise Testing: LeNet trained on MNIST, where the authors manually injected heavy-tailed noise following a Levy stable distribution.
  • Natural Language Processing (NLP): A Seq2Seq Transformer model on the Multi30k dataset and an LSTM model on the Penn Treebank dataset.

Key Insights and Ideas

  • The AD Reality Check: The paper acknowledges that what PyTorch calculates isn't always a "subgradient" in the classical sense. By using conservative fields, the theory finally aligns with how software actually works.
  • Clipping is Theoretically Sound: While practitioners use gradient clipping as a "trick" to stabilize training, this paper provides a rigorous framework showing that clipping is essential for convergence when noise is heavy-tailed.
  • Diminishing Stepsizes for Momentum: A major insight is that by applying diminishing stepsizes to the momentum and variance terms (not just the global learning rate), one can provide convergence guarantees without sacrificing the practical performance that makes Adam popular.
  • Avoiding Spurious Points: The authors show that while nonsmoothness can introduce "spurious" stationary points, Adam-family methods with random initialization can almost surely avoid them and find meaningful solutions.

Key Results

  • Theoretical Coverage: The framework successfully encompasses Adam, AdaBelief, AMSGrad, NAdam, and Yogi, providing them all with nonsmooth convergence guarantees for the first time.
  • Empirical Parity: On CIFAR datasets, the proposed AFM versions of Adam performed identically to or slightly better than the standard PyTorch implementations, proving that theoretical rigor doesn't have to cost performance.
  • Superior Robustness: In the presence of heavy-tailed noise (MNIST tests), the proposed ADAM-C (clipping) method converged successfully and achieved high accuracy, while standard SGD and Adam either failed to converge or were significantly slower.
  • NLP Success: On translation and language modeling tasks, the clipping-based methods (ADAM-C and SGD-C) outperformed their standard counterparts, demonstrating the potential of these methods for large-scale, real-world applications.

Limitations and Future Work

  • Convergence Rates: The paper establishes asymptotic convergence (that the algorithm will eventually get there) but does not provide explicit convergence rates (how fast it gets there) for the nonsmooth case.
  • Complexity Analysis: Establishing the iteration complexity for stochastic subgradient methods when the objective is only a "potential function" remains an open and "extremely challenging" problem.
  • Hyperparameter Sensitivity: While the two-timescale framework is robust, it introduces specific stepsize requirements that may require careful tuning in new domains.

Summary updated

Abstract

In this paper, we present a comprehensive study on the convergence properties of Adam-family methods for nonsmooth optimization, especially in the training of nonsmooth neural networks. We introduce a novel two-timescale framework that adopts a two-timescale updating scheme, and prove its convergence properties under mild assumptions. Our proposed framework encompasses various popular Adam-family methods, providing convergence guarantees for these methods in training nonsmooth neural networks. Furthermore, we develop stochastic subgradient methods that incorporate gradient clipping techniques for training nonsmooth neural networks with heavy-tailed noise. Through our framework, we show that our proposed methods converge even when the evaluation noises are only assumed to be integrable. Extensive numerical experiments demonstrate the high efficiency and robustness of our proposed methods.
BibTeX
@misc{xiao2023adam,
  author = {Nachuan Xiao and Xiaoyin Hu and Xin Liu and Kim-Chuan Toh},
  title = {{Adam-family Methods for Nonsmooth Optimization with Convergence Guarantees}},
  year = {2023},
  eprint = {2305.03938},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.03938},
}
Figure