Jorge: Approximate Preconditioning for GPU-Efficient Second-Order Optimization

Siddharth Singh, Zachary Sating, Abhinav BhateleSubmission to ICLR 2024 · Rejected

TL;DR

Second-order optimizers converge in fewer steps than standard first-order methods, but computing matrix inverses on GPUs makes them painfully slow per iteration. Jorge bypasses matrix inversions altogether by approximating the inverse preconditioners via a truncated binomial series, achieving iteration times within 5–10% of SGD. Combined with a "single-shot" heuristic that borrows hyperparameters directly from a tuned SGD baseline, Jorge matches or exceeds SGD's generalization while cutting overall training wall-clock time by up to 45%.

What Problem Does This Paper Address?

First-order optimizers like SGD and Adam dominate deep learning due to their minimal per-step compute overhead and predictable behavior on GPUs. In contrast, second-order methods (e.g., K-FAC, Shampoo) capture curvature information to achieve superior sample efficiency (converging in far fewer epochs).

However, second-order optimizers are notoriously bottlenecked by the need to compute matrix inverses (or inverse roots) of preconditioner matrices. These operations rely on iterative linear algebra routines with irregular memory access patterns that run poorly on parallel GPU architectures. Furthermore, second-order methods introduce extra hyperparameters that are difficult and expensive to tune. As a result, second-order methods often take longer in total wall-clock time than first-order baselines unless distributed across massive multi-GPU clusters.

Methods

Jorge builds directly upon Shampoo, which preconditions parameter gradients $G_t$ using left and right Kronecker factors ($L_t$ and $R_t$) via $L_t^{-1/4} G_t R_t^{-1/4}$. The authors introduce two core innovations:

  1. Inversion-Free Preconditioning via Binomial Expansion: Instead of maintaining $L_t$ and computing its inverse fourth root $L_t^{-1/4}$ at step $t$, Jorge directly updates an approximation $\hat{L}_t \approx L_t^{-1/4}$. By expressing the exponential moving average update in terms of $\hat{L}_{t-1}$ and applying a binomial series expansion: $$(I + A)^{-1/4} = I - \frac{1}{4}A + \frac{5}{32}A^2 - \dots$$ Jorge drops cubic and higher-order terms, turning the preconditioner update into purely dense matrix multiplications and additions (GEMM operations highly optimized on GPUs). To guarantee that the series converges ($\|A\| < 1$), Jorge dynamically computes the moving-average coefficient $\beta_2$ at each step based on the Frobenius norm of the update matrix.

  2. Single-Shot Hyperparameter Bootstrapping from SGD: To eliminate hyperparameter sweeps:

  3. Learning Rate: Uses grafting, adopting the update magnitude of a baseline SGD step while keeping Jorge's preconditioned direction.

  4. Weight Decay: Scales decoupled weight decay as $\lambda_{\text{Jorge}} = \frac{1}{1 - \beta_{\text{SGD}}} \lambda_{\text{SGD}}$ (giving $10\times$ SGD's weight decay when $\beta_{\text{SGD}} = 0.9$) to match the effective cumulative decay of momentum-based SGD.
  5. LR Schedule: Replaces continuous cosine/polynomial decays with a step-decay schedule (dropping the learning rate by $10\times$ at $1/3$ and $2/3$ of total epochs).

Datasets

The authors evaluated Jorge across standard computer vision benchmarks from the torchvision suite:

  • ImageNet-1k: Image classification with ResNet-50.
  • MS-COCO 2017: Object detection with Mask-RCNN (and Faster-RCNN in schedule ablations) and semantic image segmentation with DeepLabv3 (both using ResNet-50 backbones).
  • CIFAR-10: Evaluated with ResNet-18 for learning rate schedule ablations.

No new datasets were introduced.

Key Insights and Ideas

  • Matrix multiplications beat matrix inversions on hardware: By truncating the binomial expansion after the quadratic term, the approximation error remains negligible for optimization, but GPU utilization skyrockets because matrix multiplications saturate Tensor Cores.
  • Dynamic damping preserves convergence: Adapting $\beta_2$ per-step according to the matrix norm ensures mathematical validity of the binomial series without manual dampening parameter tuning.
  • Why smooth schedules fail on second-order methods: Second-order updates take larger, more accurate initial steps, making them susceptible to trapping in sharp minima under smooth decay schedules (cosine/polynomial). Standard step decay keeps the early learning rate sufficiently high to escape sharp basins, preventing overfitting.

Key Results

  • Iteration Speed: Jorge's per-iteration time is within 1–10% of SGD and 21–26% faster than Shampoo.
  • Wall-Clock Speedup:
  • On ImageNet (batch size 1024, 16 A100 GPUs), Jorge reaches the target 75.9% accuracy in 25% less time than SGD and beats standard Shampoo (239 min vs. 325 min). It even outperforms Distributed Shampoo by 5% without requiring inter-GPU optimizer parallelization.
  • In small batch regimes (4 A100s), Jorge reduces time-to-convergence over SGD by 23% (ResNet-50), 34% (DeepLabv3), and 45% (Mask-RCNN).
  • Final Generalization: Bootstrapping from SGD parameters yielded comparable or superior final accuracy across tasks:
  • ResNet-50 (BS 1024): 76.70% (Jorge) vs. 76.02% (SGD) vs. 71.85% (AdamW).
  • Mask-RCNN: 38.92 bbox mAP (Jorge) vs. 38.30 (SGD) vs. 36.58 (AdamW).

Limitations and Future Work

  • High Memory Footprint: Jorge requires maintaining left and right preconditioners, momentum buffers, and an extra buffer for SGD grafting, consuming $1.5\times$ to $2\times$ the optimizer memory of Adam.
  • Scope of Evaluation: Testing is currently limited to convolutional vision models; performance on transformer architectures and Large Language Models (LLMs) remains unverified.
  • Dependency on SGD Baselines: The bootstrapping technique relies on a well-tuned SGD configuration, which is uncommon in NLP domains. The authors plan to investigate bootstrapping heuristics derived from AdamW as well as distributed state-sharding implementations in future work.

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},
}

Loading related content...

Figure