The Implicit Regularization of Momentum Gradient Descent in Overparametrized Models

Li Wang, Zhiguo Fu, Yingcong Zhou, Zili YanAAAI 2023 · DOI

TL;DR

This paper investigates the implicit regularization of Momentum Gradient Descent (MGD) in overparameterized models, particularly linear neural networks. They show that MGD's optimization path closely mimics ridge regression for depth-1 models, but for deeper models, it develops an implicit bias towards sparse solutions, with this bias intensifying with depth.

What Problem Does This Paper Address?

Deep learning models, despite being overparameterized (having more parameters than data points), often generalize well. This phenomenon is partly attributed to the "implicit regularization" of optimization algorithms – the tendency of the optimization process itself to favor certain types of solutions, akin to explicit regularization terms in the loss function. While the implicit regularization of standard Gradient Descent (GD) has been studied, MGD, a widely used optimization algorithm that incorporates momentum, has received less theoretical attention in this regard. This paper aims to bridge this gap by characterizing the implicit regularization of MGD, especially how model depth influences this regularization.

Methods

The authors analyze MGD by first deriving its continuous-time limit, called Momentum Gradient Flow (MGF). For depth-1 linear models with a least squares objective, they derive a closed-form analytical solution for MGF. They then compare the optimization path of MGF to that of ridge regression, establishing a tight coupling. For deeper linear models, they analyze the dynamics of MGF by examining how individual weight components evolve at different rates. This analysis reveals an "evolution gap" that increases with depth, suggesting an implicit bias towards sparsity. They also use numerical experiments to validate their theoretical findings.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic data generated for experiments.

Key Insights and Ideas

  • MGD mimics Ridge for Depth-1: For simple linear regression (depth-1), MGD's optimization path is remarkably similar to ridge regression, suggesting comparable generalization behavior.
  • Depth Induces Sparsity Bias: As the depth of the linear model increases (N ≥ 2), MGD develops a significant "evolution gap" among weight components. Larger weights are learned faster, while smaller weights lag, leading to an implicit bias towards sparse solutions.
  • Early Stopping Amplifies Sparsity: The paper suggests that early stopping, combined with small initializations and step sizes, can further enhance this implicit sparsity-inducing effect in deeper MGD models.
  • MGF as Regularized Least Squares: The paper shows that MGF can be viewed as solving a sequence of L2-regularized least squares problems, providing a theoretical link between optimization dynamics and explicit regularization.

Key Results

  • For depth-1 linear models, the risk of MGF is no more than 1.54 times that of ridge regression under a specific calibration, and their Bayes risks are nearly indistinguishable.
  • For deeper models (N ≥ 2), the evolution gap of weight components increases with depth, indicating a stronger implicit bias towards sparsity.
  • Numerical experiments visually demonstrate the increasing evolution gap and the resulting sparsity bias as model depth increases.

Limitations and Future Work

  • Linear Models: The theoretical analysis is primarily conducted on linear models. Extending these findings to non-linear deep neural networks remains an open challenge.
  • Hyperparameter Sensitivity: The paper notes that further exploration of how hyperparameters (momentum, learning rate) affect MGD's generalization performance is a worthwhile direction.
  • Theoretical Coupling of MGF and Ridge: The paper suggests a tighter theoretical explanation for the coupling between MGF and L2 norms under specific calibrations is needed.
  • Impact of Depth, Early Stopping, and Initialization: While the paper provides insights, a more comprehensive theoretical characterization of these factors' impact on implicit regularization is desired.
  • Matrix Factorization: The paper mentions experiments on matrix factorization, indicating that MGD tends towards low-rank solutions with increasing depth, but theoretical explanations are pending.

Summary updated

BibTeX
@inproceedings{wang2023implicit,
  author = {Li Wang and Zhiguo Fu and Yingcong Zhou and Zili Yan},
  title = {{The Implicit Regularization of Momentum Gradient Descent in Overparametrized Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i8.26209},
}
Figure