When Does Second-Order Optimization Speed Up Training?

Satoki Ishikawa, Rio YokotaICLR 2024 · OpenReview

In the world of deep learning, first-order optimizers like SGD and Adam are the undisputed kings. We’ve all heard the promise of second-order methods: by using curvature information (the Hessian) rather than just the gradient, we should be able to take "smarter" steps and converge much faster. Yet, in practice, they are rarely used.

A new ICLR 2024 Tiny Paper by Satoki Ishikawa and Rio Yokota from the Tokyo Institute of Technology aims to answer the million-dollar question: Under what specific conditions does second-order optimization actually outperform first-order methods?

TL;DR

Second-order optimization (like K-FAC and Shampoo) is a powerhouse for training with large batch sizes on relatively small datasets. However, as dataset sizes scale up to the levels seen in Large Language Models (LLMs), the advantage over standard first-order methods like AdamW diminishes or even disappears.

What Problem Does This Paper Address?

Despite decades of theoretical promise, second-order methods haven't seen widespread adoption. The primary hurdles are computational overhead and a lack of clarity on their "sweet spot." Researchers often find that while a second-order method might converge in fewer iterations, the cost per iteration is so high that first-order methods win on total wall-clock time.

The authors set out to map the territory where second-order methods provide a genuine edge, specifically looking at the interplay between batch size and dataset size.

Methods and Datasets

The researchers conducted a comprehensive empirical study comparing several prominent second-order optimizers against standard baselines:

  • Second-Order Optimizers: K-FAC (Kronecker-factored Approximate Curvature), Shampoo, PSGD, SENG, and FOOF.
  • First-Order Baselines: SGD and AdamW.

They evaluated these across different architectures (MLPs, ResNet18, Vision Transformers, and GPT-style models) to see how performance scales as they manipulated batch sizes and the total number of training samples. The study utilized a variety of standard benchmarks to represent different scales of complexity, including MNIST, CIFAR-10, BookCorpus, and OpenWebText.

Key Insights

  • The Large Batch Savior: First-order methods famously suffer from the "large batch problem," where generalization accuracy drops as you increase the mini-batch size. Second-order methods (specifically K-FAC and Shampoo) are much more robust here, maintaining high accuracy even as batch sizes grow significantly.
  • The Dataset Size Trap: This is the most surprising finding. Second-order methods excel when the dataset is small. As the dataset grows, the mini-batch becomes a smaller and smaller fraction of the total data. Because the curvature information is estimated from these mini-batches, it becomes less representative of the global landscape, causing the second-order advantage to vanish.
  • Curvature Stability: The authors found that the curvature matrix (the "shape" of the loss landscape) stabilizes very quickly in the early stages of training for almost all layers except the final one. This suggests we don't need to compute expensive second-order updates throughout the entire training process.
  • The Damping Connection: In second-order optimization, "damping" is a technique used to keep the updates stable. The authors discovered a proportional relationship: as you increase the batch size, you generally need to increase the damping to maintain optimal performance.

Key Results

Batch Scaling

In tests on CIFAR-10 and MNIST, K-FAC and Shampoo maintained near-peak accuracy at batch sizes where SGD and AdamW performance began to plummet.

Test accuracy across different batch sizes for various optimizers

Convergence Speed and Dataset Size

On a small version of the BookCorpus dataset (1,024 samples), K-FAC reached low training loss significantly faster than AdamW. However, on the full dataset (524,288 samples), AdamW and Shampoo performed almost identically, while K-FAC’s convergence actually worsened.

Training loss over iterations across different dataset sizes

LLM Training

When training GPT-2 on OpenWebText, Shampoo only showed a clear advantage over AdamW at very large batch sizes (1,536 and above). At smaller, more common batch sizes, AdamW was actually more effective at reducing validation loss.

Limitations and Future Work

As a "Tiny Paper," the scope is naturally focused. The authors acknowledge that while they've identified when these methods work, the why behind K-FAC’s deterioration on large datasets remains a point for further investigation.

Furthermore, the study primarily looks at convergence rates and accuracy. Future work could integrate more detailed wall-clock time analysis to provide a definitive guide for practitioners on whether the extra compute of a second-order step is worth the "smarter" update in a production environment.

The takeaway for practitioners? If you are constrained to small datasets but have the hardware to run massive batches, second-order methods are your best friend. If you're training the next massive LLM, AdamW is still the king of the hill—for now.

Summary updated

Abstract

While numerous second-order optimization methods have been proposed to accelerate training in deep learning, they are seldom used in practice. This is partly due to a limited understanding of the conditions under which second-order optimization outperforms first-order optimization. This study aims to identify these conditions, particularly in terms of batch size and dataset size. We find empirically that second-order optimization outperforms first-order optimization when the batch size is large and the data set size is not too large.
BibTeX
@inproceedings{ishikawa2024when,
  author = {Satoki Ishikawa and Rio Yokota},
  title = {{When Does Second-Order Optimization Speed Up Training?}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=NLrfEsSZNb},
}
Figure