Efficient Full-Matrix Adaptive Regularization

Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, Yi ZhangICML 2019 · OpenReview

This paper introduces GGT, a novel optimization algorithm that brings the theoretical power of full-matrix adaptive regularization to the practical world of large-scale deep learning. By addressing the computational bottlenecks of traditional full-matrix methods, GGT offers a robust alternative to standard optimizers like Adam and SGD, particularly for complex landscapes such as Recurrent Neural Networks (RNNs).

The Curse of Dimensionality in Optimization

Most popular deep learning optimizers, such as Adam, RMSprop, and AdaGrad, are "diagonal" adaptive methods. This means they scale the learning rate for each parameter individually, effectively treating every weight in a neural network as if it were entirely independent.

In reality, parameters are highly correlated. The mathematically "ideal" way to optimize would be to use a full-matrix preconditioner—like the inverse square root of the gradient covariance matrix—to rotate and scale the descent direction. However, for a model with $d$ parameters, this matrix is $d \times d$. If your model has 10 million parameters, storing and inverting a $10^7 \times 10^7$ matrix is computationally impossible, creating a severe "curse of dimensionality."

The authors address this bottleneck by finding a way to capture off-diagonal parameter correlations without incurring the prohibitive $O(d^3)$ computational cost.

The GGT Method

The authors propose the GGT algorithm (named after its $GG^\top$ matrix structure), which relies on a few core innovations to make full-matrix preconditioning viable:

  • Low-Rank Approximation: Instead of looking at the entire history of gradients, GGT maintains a "sliding window" of the last $r$ gradients (where $r$ is a small number, e.g., 200). This makes the second-moment matrix low-rank.
  • The "Matrix Trick": To compute the update, GGT needs the inverse square root of a large $d \times d$ matrix. The authors use a clever linear algebra identity to transform this into an eigendecomposition of a much smaller $r \times r$ matrix. This shifts the heavy computational lifting from the massive parameter dimension to the small window dimension.
The GGT Matrix Trick
  • GPU-Friendliness: The algorithm is designed to use standard, highly optimized matrix-vector operations, making it efficient on modern hardware.
  • Theoretical Convergence: The paper provides the first proof of convergence to first-order critical points for this type of adaptive algorithm in a stochastic, non-convex setting.

Experimental Setup and Key Insights

The authors evaluated GGT across three distinct scales: synthetic ill-conditioned tasks, Computer Vision (CIFAR-10 using a 26-layer Shake-Shake Residual Network), and Language Modeling (Penn Treebank using a 3-layer LSTM).

During these experiments, several key insights emerged:

  • RNNs vs. CNNs: One of the most striking findings is that RNN landscapes are much more "anisotropic" (stretched out and narrow) than CNN landscapes. Visualizing the "spectral decay" of the gradients revealed that RNNs have a condition number roughly 1,000 times larger than CNNs. This explains why GGT provides a massive performance boost to RNNs but only a modest one to CNNs.
  • The Value of Forgetting: Using a sliding window isn't just a computational shortcut; it's a feature. In non-convex optimization, the "curvature" of the landscape changes as the model moves. By "forgetting" old gradients, GGT adapts to the local geometry of the loss surface much more effectively.
  • Wall-Clock Practicality: While GGT involves more complex math than SGD, it only incurs a 1.3x to 2x overhead in running time per iteration. Because it often converges in fewer steps, it can actually be faster in total "wall-clock" time.

Key Results

GGT demonstrated strong empirical performance across the board, particularly shining in environments with ill-conditioned loss surfaces.

  • Superior RNN Performance: On the Penn Treebank (PTB) language modeling task, GGT achieved a validation perplexity of 2.42, significantly outperforming Adam (2.51), AdaGrad (2.65), and SGD (2.76).
  • Faster Convergence on Synthetic Tasks: In synthetic ill-conditioned tests, GGT converged orders of magnitude faster than diagonal methods, which often got "stuck" navigating narrow canyons in the loss landscape.
  • Competitive Generalization: On CNNs (CIFAR-10), GGT dominated the training loss. While it showed a slight "generalization gap" on test accuracy—a phenomenon common in adaptive methods compared to perfectly tuned SGD—it still performed highly competitively alongside Adam.
Performance on CIFAR-10 and PTB

Limitations and Future Work

While powerful, GGT is not without its limitations. It requires storing $r$ copies of the model gradients in memory. For extremely large models (e.g., billions of parameters), even a modest window of $r=200$ might exceed available GPU memory.

Additionally, like all optimizers, GGT introduces new hyperparameters to tune, most notably the window size $r$. While $r=200$ worked well across their tests, finding the optimal window for different architectures remains an open question. Finally, the authors suggest that future work could involve designing neural network architectures specifically intended to be paired with full-matrix optimizers, potentially unlocking even higher performance ceilings.

Summary updated

Abstract

Adaptive regularization methods pre-multiply a descent direction by a preconditioning matrix. Due to the large number of parameters of machine learning problems, full-matrix preconditioning methods...
BibTeX
@inproceedings{agarwal2019efficient,
  author = {Naman Agarwal and Brian Bullins and Xinyi Chen and Elad Hazan and Karan Singh and Cyril Zhang and Yi Zhang},
  title = {{Efficient Full-Matrix Adaptive Regularization}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=ry-l-o-u-r},
}
Figure