Adaptive Optimization in the $\infty$-Width Limit

Etai Littwin, Greg YangICLR 2023 · OpenReview

Abstract

Recent works have developed a detailed understanding of large neural networks' behaviors via their infinite-width limits, such as the Neural Tangent Kernel (NTK) and the feature learning ($\mu$) limits. However, these theories were primarily developed for Stochastic Gradient Descent (SGD). In practice, nearly all large neural networks are trained using Adam or other Adaptive Gradient Optimizers (AGOs), which are not covered by previous frameworks. This paper closes that gap by extending the Tensor Programs framework to derive the NTK and $\mu$ parametrizations—and their infinite-width limits—for deep MLPs trained with AGOs.

Introduction: The Adaptive Optimizer Gap

In recent years, deep learning theory has made massive strides by studying "infinite-width" limits. Two major regimes have emerged:

  1. The Neural Tangent Kernel (NTK) limit: The network behaves like a linear model, and weights barely move from initialization, resulting in no true "feature learning."
  2. The $\mu$ (Maximal Update Parametrization) limit: Weights move significantly, allowing the network to learn internal representations and features from data.

While these limits provide profound insights, almost all existing theory assumes the use of SGD. In the real world, large-scale models (like Transformers) rely on adaptive optimizers like Adam, which scale updates based on moving averages of past gradients. This paper provides the theoretical foundation for understanding how these adaptive optimizers behave as network width scales to infinity.

Methods: Extending Tensor Programs

To analyze AGOs, the authors utilize and extend the Tensor Programs (TP) framework—a mathematical language used to track the distribution of neural network activations as width goes to infinity.

  • New Instruction Set: Standard TP cannot handle the complex, per-parameter nonlinearities used in AGOs (such as dividing by the square root of the second moment). The authors introduce a new instruction set, denoted as $NE \otimes ORT$, allowing the framework to express these adaptive updates.
  • Master Theorem: They prove a new "Master Theorem" for this expanded language, providing a rigorous $O(n^{-1/2})$ convergence rate guarantee for variables in the program as width ($n$) increases.
  • Parametrization Scaling: The study identifies the specific scaling rules for initialization and learning rates required to achieve stable Adaptive NTK (ANTK) and $\mu$ limits for adaptive optimizers.
Scaling rules for ANTK and $\mu$ parameterizations

Key Insights and Theoretical Findings

The ANTK is Nonlinear

In standard SGD, the NTK is a constant kernel. In the Adaptive NTK (ANTK) limit, the "kernel" actually depends nonlinearly on the loss derivative. This means the training dynamics are more complex than standard NTK. Yet, crucially, they still fail to learn features because the weights stay too close to their starting points.

Feature Learning Requires $\mu$P

Just as with SGD, the authors demonstrate that if you want an adaptive optimizer to actually learn features at infinite width, you must use the $\mu$P (Maximal Update Parametrization) scaling. The $\mu$ limit of AGOs successfully fixes the feature learning failure of the ANTK limit.

Scaling the Epsilon Parameter

A subtle but vital finding is that the $\epsilon$ parameter in Adam (used for numerical stability) must be scaled with the network width ($n$) to prevent the adaptive gradients from collapsing or exploding in the infinite-width limit.

A Universal Tool

The extended Tensor Programs framework is not limited to MLPs. It provides a universal "recipe" to analyze almost any architecture (Transformers, CNNs, etc.) trained with any AGO.

Empirical Validation

While focused on theoretical derivations, the authors validated their findings using synthetic Gaussian inputs and ReLU MLPs.

  • Rigorous Derivation: The paper provides the first formal proof of the infinite-width limits for Adam and other AGOs.
  • Convergence Rate: They established a universal $O(n^{-1/2})$ rate at which finite-width adaptive networks approach their infinite-width counterparts. Numerical experiments confirm that as the width of a ReLU MLP increases (from 64 to 7000), its training trajectory converges perfectly to the theoretical predictions.

Limitations and Future Work

  • Architecture Scope: While the TP framework is architecturally universal, the specific theorems in this paper are demonstrated primarily on Multi-Layer Perceptrons (MLPs). Extending the explicit derivations to Transformers is a logical next step.
  • Implicit Bias: The authors note that while they have derived the dynamics, they haven't yet fully explored the implicit bias of AGOs—i.e., why Adam generalizes differently than SGD. This paper provides the mathematical "microscope" needed to study that question in future work.
  • Constant Time: The analysis assumes training time is constant while width goes to infinity. Exploring "long-time" limits where training time also scales remains an open challenge.

Summary updated

Abstract

Recent works have developed detailed understanding of large neural networks' behaviors via their infinite-width limits, e.g., the neural tangent kernel (NTK) and the feature learning ($\mu$) limits. These theories were developed for stochastic gradient descent. Yet, in practice, all large NN are trained using Adam or other adaptive gradient optimizers (AGO), which are not covered by such previous works. Here, we close this gap via the Tensor Programs framework. Specifically, for deep MLPs, we derive the NTK and $\mu$ parametrizations as well as their infinite-width limits. We find 1) The NTK limit of AGO, in contrast to that of SGD, now depends nonlinearly on the loss derivative but nevertheless still fails to learn features; 2) this is fixed by the $\mu$ limit of AGO (as in the case of SGD). To obtain these results, we extend the Tensor Programs language with a new instruction that allows one to express the gradient processing done by AGOs.
BibTeX
@inproceedings{littwin2023adaptive,
  author = {Etai Littwin and Greg Yang},
  title = {{Adaptive Optimization in the $\textbackslash\{\}infty$-Width Limit}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=zgVDqw9ZUES},
}
Figure