Jorge: Approximate Preconditioning for GPU-efficient Second-order Optimization

Siddharth Singh, Zachary Sating, Abhinav Bhatele

Abstract

Despite their better convergence properties compared to first-order optimizers, second-order optimizers for deep learning have been less popular due to their significant computational costs. The primary efficiency bottleneck in such optimizers is matrix inverse calculations in the preconditioning step, which are expensive to compute on GPUs. In this paper, we introduce Jorge, a second-order optimizer that promises the best of both worlds -- rapid convergence benefits of second-order methods, and high computational efficiency typical of first-order methods. We address the primary computational bottleneck of computing matrix inverses by completely eliminating them using an approximation of the preconditioner computation. This makes Jorge extremely efficient on GPUs in terms of wall-clock time. Further, we describe an approach to determine Jorge's hyperparameters directly from a well-tuned SGD baseline, thereby significantly minimizing tuning efforts. Our empirical evaluations demonstrate the distinct advantages of using Jorge, outperforming state-of-the-art optimizers such as SGD, AdamW, and Shampoo across multiple deep learning models, both in terms of sample efficiency and wall-clock time.

Introduction

In deep learning, first-order optimizers like SGD or Adam are the standard due to their computational efficiency on GPUs. However, they often require many iterations to converge. Second-order methods, which utilize the curvature of the loss landscape, can converge in significantly fewer steps but are historically hindered by the "matrix inverse" bottleneck. Calculating matrix inverses is computationally expensive and poorly suited for the parallel architecture of GPUs, often making the total wall-clock training time of second-order methods longer than that of simple SGD. Jorge is designed to bridge this gap, offering second-order convergence without the iterative inversion penalty.

The Jorge Optimizer

Jorge (named after optimization expert Dr. Jorge Nocedal) is built as an enhancement of the Shampoo optimizer. Its primary innovation is Approximate Preconditioning. Instead of calculating the exact inverse fourth root of preconditioner matrices, Jorge utilizes a binomial series expansion. This mathematical shift replaces slow, iterative matrix inversions with a series of matrix multiplications and additions (GEMMs), which are the "sweet spot" for GPU performance.

Comparison of Shampoo and Jorge algorithms, highlighting the replacement of matrix inversion with a binomial series expansion.

To ensure the stability of this approximation, Jorge dynamically adjusts its smoothing parameters ($\beta_2$) in every iteration based on the matrix norm. Furthermore, to simplify adoption, the authors developed a "bootstrapping" method to derive Jorge’s hyperparameters directly from a well-tuned SGD baseline, including a "grafting" technique where Jorge adopts the learning rate magnitude of SGD while maintaining its own second-order update direction.

Empirical Evaluation and Key Results

The researchers evaluated Jorge across standard computer vision benchmarks, including ImageNet (ResNet-50), MS-COCO (Mask-RCNN and DeepLabv3), and CIFAR-10 (ResNet-18).

Key performance metrics include:

  • Wall-Clock Efficiency: On ResNet-50, Jorge’s per-iteration overhead is only 1% slower than SGD, compared to 26% for standard Shampoo.
  • Training Speed: Jorge reached target accuracy on ImageNet 25% faster than SGD in total clock time. For Mask-RCNN, the improvement was 45%.
  • Sample Efficiency: Jorge consistently required 27% to 41% fewer iterations than SGD to reach target validation metrics.
  • Generalization: Jorge successfully matches or exceeds SGD’s final accuracy, avoiding the generalization gap often seen with Adam in computer vision tasks.

Insights on Learning Rate Schedules

An interesting finding during evaluation was Jorge's sensitivity to learning rate schedules. While many modern models use Cosine Decay, Jorge performs best with a step-decay schedule. Smoother schedules like Cosine or Polynomial Decay led to overfitting in some cases. This suggests that Jorge's more accurate updates make it more prone to falling into "sharp" local minima if the learning rate remains high for too long.

Validation performance across different learning rate schedules, showing Jorge's preference for step-decay.

Limitations and Future Work

Despite its speed, Jorge has a higher memory footprint than Adam or SGD, requiring 3 to 4 optimizer states per parameter (approximately 1.5–2x more memory than Adam). Future work aims to extend Jorge to Large Language Models (LLMs), develop distributed versions to mitigate per-GPU memory consumption, and create automated tuning strategies for bootstrapping from AdamW baselines.

Summary updated

Abstract

Despite their better convergence properties compared to first-order optimizers, second-order optimizers for deep learning have been less popular due to their significant computational costs. The primary efficiency bottleneck in such optimizers is matrix inverse calculations in the preconditioning step, which are expensive to compute on GPUs. In this paper, we introduce Jorge, a second-order optimizer that promises the best of both worlds -- rapid convergence benefits of second-order methods, and high computational efficiency typical of first-order methods. We address the primary computational bottleneck of computing matrix inverses by completely eliminating them using an approximation of the preconditioner computation. This makes Jorge extremely efficient on GPUs in terms of wall-clock time. Further, we describe an approach to determine Jorge's hyperparameters directly from a well-tuned SGD baseline, thereby significantly minimizing tuning efforts. Our empirical evaluations demonstrate the distinct advantages of using Jorge, outperforming state-of-the-art optimizers such as SGD, AdamW, and Shampoo across multiple deep learning models, both in terms of sample efficiency and wall-clock time.
BibTeX
@misc{singh2023jorge,
  author = {Siddharth Singh and Zachary Sating and Abhinav Bhatele},
  title = {{Jorge: Approximate Preconditioning for GPU-efficient Second-order Optimization}},
  year = {2023},
  eprint = {2310.12298},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.12298},
}
Figure