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:
-
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.
-
Single-Shot Hyperparameter Bootstrapping from SGD: To eliminate hyperparameter sweeps:
-
Learning Rate: Uses grafting, adopting the update magnitude of a baseline SGD step while keeping Jorge's preconditioned direction.
- 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.
- 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