# Structured Preconditioners in Adaptive Optimization: A Unified Analysis

arXiv: https://arxiv.org/abs/2503.10537 · HTML: https://mlsanity.com/paper/2503.10537/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 37 references that are in the map.
- First posted on arXiv 13 Mar 2025.

## Builds on (most cited first, 23 of 23)

- [Adafactor: Adaptive Learning Rates with Sublinear Memory Cost](https://mlsanity.com/paper/1804.04235/) (2018)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [Large Batch Optimization for Deep Learning: Training BERT in 76 minutes](https://mlsanity.com/paper/1904.00962/) (2019)
- [Large Batch Training of Convolutional Networks](https://mlsanity.com/paper/1708.03888/) (2017)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradients](https://mlsanity.com/paper/2010.07468/) (2020)
- [Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training](https://mlsanity.com/paper/2305.14342/) (2023)
- [ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning](https://mlsanity.com/paper/2006.00719/) (2020)
- [Old Optimizer, New Norm: An Anthology](https://mlsanity.com/paper/2409.20325/) (2024)
- [SOAP: Improving and Stabilizing Shampoo using Adam](https://mlsanity.com/paper/2409.11321/) (2024)
- [AdaGrad stepsizes: Sharp convergence over nonconvex landscapes](https://mlsanity.com/paper/1806.01811/) (2018)
- [Revisiting Natural Gradient for Deep Networks](https://mlsanity.com/paper/1301.3584/) (2013)
- [Fast Approximate Natural Gradient Descent in a Kronecker-factored Eigenbasis](https://mlsanity.com/paper/1806.03884/) (2018)
- [Modular Duality in Deep Learning](https://mlsanity.com/paper/2410.21265/) (2024)
- [MARS: Unleashing the Power of Variance Reduction for Training Large Models](https://mlsanity.com/paper/2411.10438/) (2024)
- [A New Perspective on Shampoo's Preconditioner](https://mlsanity.com/paper/2406.17748/) (2024)
- [Benchmarking Neural Network Training Algorithms](https://mlsanity.com/paper/2306.07179/) (2023)
- [Online Adaptive Methods, Universality and Acceleration](https://mlsanity.com/paper/1809.02864/) (2018)
- [Adam Exploits ℓ_∞-geometry of Loss Landscape via Coordinate-wise Adaptivity](https://mlsanity.com/paper/2410.08198/) (2024)
- [A Unified Approach to Adaptive Regularization in Online and Stochastic Optimization](https://mlsanity.com/paper/1706.06569/) (2017)
- [Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information](https://mlsanity.com/paper/2109.05198/) (2021)
- [AdaSGD: Bridging the gap between SGD and Adam](https://mlsanity.com/paper/2006.16541/) (2020)

## Built on by (most cited first, 30 of 33)

- [ASGO: Adaptive Structured Gradient Optimization](https://mlsanity.com/paper/2503.20762/) (2025)
- [MuonBP: Faster Muon via Block-Periodic Orthogonalization](https://mlsanity.com/paper/2510.16981/) (2025)
- [Purifying Shampoo: Investigating Shampoo's Heuristics by Decomposing its Preconditioner](https://mlsanity.com/paper/2506.03595/) (2025)
- [AdaGrad Meets Muon: Adaptive Stepsizes for Orthogonal Updates](https://mlsanity.com/paper/2509.02981/) (2025)
- [Low-rank Orthogonalization for Large-scale Matrix Optimization with Applications to Foundation Model Training](https://mlsanity.com/paper/2509.11983/) (2025)
- [Understanding and Improving Shampoo and SOAP via Kullback-Leibler Minimization](https://mlsanity.com/paper/2509.03378/) (2025)
- [Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2602.08232/) (2026)
- [Sharp Capacity Scaling of Spectral Optimizers in Learning Associative Memory](https://mlsanity.com/paper/2603.26554/) (2026)
- [SGD with Adaptive Preconditioning: Unified Analysis and Momentum Acceleration](https://mlsanity.com/paper/2506.23803/) (2025)
- [On the Width Scaling of Neural Optimizers Under Matrix Operator Norms I: Row/Column Normalization and Hyperparameter Transfer](https://mlsanity.com/paper/2603.09952/) (2026)
- [Preconditioned Norms: A Unified Framework for Steepest Descent, Quasi-Newton and Adaptive Methods](https://mlsanity.com/paper/2510.10777/) (2025)
- [Enhancing LLM Training via Spectral Clipping](https://mlsanity.com/paper/2603.14315/) (2026)
- [Non-Euclidean SGD for Structured Optimization: Unified Analysis and Improved Rates](https://mlsanity.com/paper/2511.11466/) (2025)
- [Clarifying Shampoo: Adapting Spectral Descent to Stochasticity and the Parameter Trajectory](https://mlsanity.com/paper/2602.09314/) (2026)
- [On Learning Verifiers and Implications to Chain-of-Thought Reasoning](https://mlsanity.com/paper/2505.22650/) (2025)
- [On the Convergence Analysis of Muon](https://mlsanity.com/paper/2505.23737/) (2025)
- [Conda: Column-Normalized Adam for Training Large Language Models Faster](https://mlsanity.com/paper/2509.24218/) (2025)
- [A Tale of Two Geometries: Adaptive Optimizers and Non-Euclidean Descent](https://mlsanity.com/paper/2511.20584/) (2025)
- [Provable Benefit of SignGD: A Minimal Model Under Heavy-Tailed Class Imbalance](https://mlsanity.com/paper/2512.00763/) (2025)
- [Optimizer-Model Consistency: Full Finetuning with the Same Optimizer as Pretraining Forgets Less](https://mlsanity.com/paper/2605.06654/) (2026)
- [DASH: Faster Shampoo via Batched Block Preconditioning and Efficient Inverse-Root Solvers](https://mlsanity.com/paper/2602.02016/) (2026)
- [PRISM: Structured Optimization via Anisotropic Spectral Shaping](https://mlsanity.com/paper/2602.03096/) (2026)
- [A unified convergence theory for adaptive first-order methods in the nonconvex case, including AdaNorm, full and diagonal AdaGrad and Muon](https://mlsanity.com/paper/2604.17423/) (2026)
- [FOAM: Frequency and Operator Error-Based Adaptive Damping Method for Reducing Staleness-Oriented Error for Shampoo](https://mlsanity.com/paper/2606.02365/) (2026)
- [Learning by solving differential equations](https://mlsanity.com/paper/2505.13397/) (2025)
- [Convergence Rate Analysis of the AdamW-style Shampoo: Unifying One-Sided and Two-Sided Preconditioning](https://mlsanity.com/paper/2601.07326/) (2026)
- [Optimal Projection-Free Adaptive SGD for Matrix Optimization](https://mlsanity.com/paper/2604.02505/) (2026)
- [Deterministic Adam-Inspired Methods with Accelerated Convergence Rate](https://mlsanity.com/paper/2604.08742/) (2026)
- [Pro-KLShampoo: Projected KL-Shampoo with Whitening Recovered by Orthogonalization](https://mlsanity.com/paper/2605.06316/) (2026)
- [Matrix AdaGrad: Row-wise and Column-wise Adaptive Subgradient Methods](https://mlsanity.com/paper/2609.21815/) (2026)

## Abstract (arXiv)

We present a novel unified analysis for a broad class of adaptive optimization algorithms with structured (e.g., layerwise, diagonal, and kronecker-factored) preconditioners for both online regret minimization and offline convex optimization. Our analysis not only provides matching rate to several important structured preconditioned algorithms including diagonal AdaGrad, full-matrix AdaGrad, and AdaGrad-Norm, but also gives an improved convergence rate for a one-sided variant of Shampoo over that of original Shampoo. Interestingly, more structured preconditioners (e.g., diagonal Adagrad, AdaGrad-Norm which use less space and compute) are often presented as computationally efficient approximations to full-matrix Adagrad, aiming for improved optimization performance through better approximations. Our unified analysis challenges this prevailing view and reveals, perhaps surprisingly, that more structured preconditioners, despite using less space and computation per step, can outperform their less structured counterparts. To demonstrate this, we show that one-sided Shampoo, which is relatively much cheaper than full-matrix AdaGrad could outperform it both theoretically and experimentally.