Implicit Bias of AdamW: $\ell_∞$-Norm Constrained Optimization

ICML 2024

TL;DR

AdamW, a popular optimizer, is known to outperform Adam, but its theoretical underpinnings remain elusive. This paper reveals that AdamW implicitly performs $\ell_\infty$-norm constrained optimization, meaning it steers solutions towards those with small maximum component values. This finding helps explain AdamW's superior generalization and optimization performance.

What Problem Does This Paper Address?

Deep learning models, especially large language models (LLMs), have seen tremendous success with optimizers like Adam and its variant AdamW. While AdamW often achieves better generalization and optimization than Adam (which uses $\ell_2$ regularization for weight decay), the theoretical reasons for this advantage are not well understood. A key question is what objective function AdamW is actually optimizing, especially since its weight decay mechanism differs from Adam's. This paper aims to bridge this theoretical gap by understanding the implicit bias of AdamW, i.e., what kind of solutions it tends to find.

Methods

The authors' core contribution is showing that AdamW implicitly performs $\ell_\infty$-norm constrained optimization. They achieve this by:

  • Connecting AdamW to Normalized Steepest Descent (NSD): They demonstrate that AdamW behaves like a smoothed version of SignGD (normalized steepest descent with respect to the $\ell_\infty$ norm).
  • Analyzing NSD with Weight Decay: They prove that normalized steepest descent with weight decay (NSD-WD) for any norm converges to KKT points of a norm-constrained optimization problem.
  • Deriving a Tight Upper Bound for Adam Updates: A crucial technical contribution is a novel, tight upper bound on the average update size of Adam-like algorithms. This bound is key to extending the analysis from NSD-WD to AdamW.
  • Characterizing KKT Points: They formally define and utilize KKT (Karush-Kuhn-Tucker) conditions to characterize the stationary points of the constrained optimization problem.

Datasets

The paper uses the Penn Treebank (PTB) dataset for language modeling experiments.

Key Insights and Ideas

  • AdamW as $\ell_\infty$-Norm Regularizer: The most significant insight is that AdamW implicitly regularizes the $\ell_\infty$ norm of the learned solution. This means it favors solutions where the largest absolute value of any parameter is minimized, rather than minimizing the sum of squared parameters ($\ell_2$ norm).
  • AdamW vs. SignGD: AdamW is shown to be a "smoothed" version of SignGD, which is the normalized steepest descent with respect to the $\ell_\infty$ norm. This connection helps explain why AdamW might inherit some of SignGD's beneficial properties.
  • Weight Decay and Norm Constraints: The paper establishes a general connection between normalized steepest descent with weight decay and Frank-Wolfe, a method known for constrained optimization. This suggests that weight decay, when combined with normalized descent, inherently leads to constrained optimization.
  • Hyperparameter Sensitivity: The analysis highlights the importance of the relationship between learning rate ($\eta$), weight decay ($\lambda$), and the momentum parameters ($\beta_1, \beta_2$) for controlling the $\ell_\infty$ norm of AdamW iterates. Specifically, certain conditions on these parameters are necessary for the $\ell_\infty$ norm to remain bounded.

Key Results

  • Theoretical Guarantee: In the full-batch setting, if AdamW converges, it converges to a KKT point of the original loss function constrained by an $\ell_\infty$ norm bound related to the weight decay factor. For convex loss functions, it converges to the constrained minimizer.
  • Empirical Validation: Experiments on the PTB dataset show that for specific hyperparameter settings (e.g., $\beta_1 = \beta_2$ or $\lambda\eta \ll 1 - \beta_2$), the $\ell_\infty$ norm of AdamW iterates is indeed bounded, aligning with theoretical predictions. In contrast, Adam's $\ell_\infty$ norm often increases without bound.
  • Synthetic Problem Advantage: For a synthetic quadratic problem designed to have better properties under $\ell_\infty$ geometry, normalized steepest descent with $\ell_\infty$ norm (and weight decay) outperformed its $\ell_2$ norm counterpart, supporting the conjecture that $\ell_\infty$ geometry can be beneficial.

Limitations and Future Work

  • Full-Batch Assumption: The primary theoretical results are derived for the full-batch setting. Extending these to the more common stochastic setting remains an open challenge.
  • Hyperparameter Tuning: While the paper provides theoretical insights into hyperparameter choices, finding optimal settings for practical applications still requires empirical exploration.
  • Understanding $\ell_\infty$ Geometry: The paper suggests that language modeling loss functions might have better properties under $\ell_\infty$ geometry. Further research is needed to understand this phenomenon more deeply and to explore if other adaptive methods can leverage this.
  • Non-asymptotic Convergence Rates: The authors aim to provide non-asymptotic convergence rates for AdamW in both convex and non-convex settings.

Summary updated

BibTeX
@inproceedings{2024implicit,
  title = {{Implicit Bias of AdamW: $\textbackslash\{\}ell\_∞$-Norm Constrained Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
}
Figure