Research map / Optimization / Optimizers
Structured Preconditioners in Adaptive Optimization: A Unified Analysis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a unified regret and convergence analysis for adaptive optimizers with "well-structured" (subalgebra-induced) preconditioner sets, and shows one-sided Shampoo has a better rate than full-matrix AdaGrad on some problems.
Problem
Unified theory for adaptive optimizers with structured preconditioners (diagonal, Kronecker-factored, layerwise) in online regret and stochastic convex optimization, and whether more structure can hurt or help convergence.
Approach
Defines well-structured preconditioner sets H = S_+^d ∩ K for matrix subalgebras K containing I, which guarantees operator monotonicity of the preconditioner map and yields a unified analysis via an adaptive gradient norm and a domain norm; this shows the regret trade-off between domain metric and gradient norm, so one-sided Shampoo can beat full-matrix AdaGrad.
Key results
- One-sided Shampoo achieves worst-case convergence rate 1/T on the studied quadratic class, versus min(d_L,d_R)/T for AdaGrad-Norm and d_L d_R/T for diagonal AdaGrad, and min(d_L,d_R) d_R/T for full-matrix AdaGrad.
- Regret bound for one-sided Shampoo is always no larger than the existing two-sided Shampoo bound and can be smaller by a factor min(d_L,d_R)d_L^{1/4}d_R^{3/4} in a constructed example.
- In a 1000-dimensional linear regression experiment, one-sided Shampoo outperforms AdaGrad-Norm, AdaGrad, and full-matrix AdaGrad on both last-iterate and average-iterate loss, with full-matrix AdaGrad the worst.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use one-sided Shampoo instead of AdaGrad-Norm | Adaptive optimization on bounded-trace Hessian quadratic losses · Bounded-trace Hessian quadratic loss class | worst-case convergence rate: \frac{1}{T} vs. \frac{\min{(d_L, d_R)}}{T} | Helped |
| use one-sided Shampoo instead of AdaGrad | Adaptive optimization on bounded-trace Hessian quadratic losses · Bounded-trace Hessian quadratic loss class | worst-case convergence rate: \frac{1}{T} vs. \frac{d_L d_R}{T} | Helped |
| use one-sided Shampoo instead of full-matrix AdaGrad | Adaptive optimization on bounded-trace Hessian quadratic losses · Bounded-trace Hessian quadratic loss class | worst-case convergence rate: \frac{1}{T} vs. \frac{\min{(d_L, d_R)} d_R}{T} | Helped |
| use one-sided Shampoo instead of two-sided Shampoo | Shampoo · Online convex optimization | regret bound: \min(d_L,d_R)d_L^\frac{1}{4} d_R^\frac{3}{4} | Helped |
| use one-sided Shampoo instead of full-matrix AdaGrad | Adaptive optimizers on the linear regression experiment · Linear regression, last iterate loss | loss | Helped |
| use one-sided Shampoo instead of full-matrix AdaGrad | Adaptive optimizers on the linear regression experiment · Linear regression, average iterate training loss | loss | Helped |
| use EMA versions of the adaptive algorithms | AdaSGD, Adam, one-sided EMA Shampoo, and full-matrix AdaSGD · Linear regression experiment | loss | No clear effect |
Surprising findings
- Full-matrix AdaGrad performs worst among the compared methods in the experiment, suggesting more adaptivity does not always help for a fixed step budget.
- More structured one-sided Shampoo can provably outperform full-matrix AdaGrad in convergence rate on a class of quadratic problems.
Limitations
- Two-sided Shampoo's fixed form is not covered by the well-structured framework as stated, since its preconditioner set is not closed under addition.
- Experiments are limited to a single synthetic linear regression setting with d=1000 and 100 steps.
- Theoretical advantage is shown on a specific loss class; the general claim about deep learning is not established.
Experimental setup
Datasets: synthetic linear regression problem
Benchmarks: synthetic quadratic loss f(X)=<H,(X-X*)(X-X*)^T> with d=1000
Metrics: last-iterate loss average-iterate loss regret bound convergence rate
Baselines: AdaGrad-Norm diagonal AdaGrad full-matrix AdaGrad two-sided Shampoo Adam AdaSGD
Builds on: AdaGrad Shampoo AdaReg Adam
Closest papers by meaning
- A New Perspective on Shampoo's Preconditioner (ICLR 2025 · similarity 0.88)
- Purifying Shampoo: Investigating Shampoo's Heuristics by Decomposing its Preconditioner (NeurIPS 2025 · similarity 0.87)
- Universal Sequence Preconditioning (NeurIPS 2025 · similarity 0.86)
- Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions (ICML 2024 · similarity 0.86)
- On The Concurrence of Layer-wise Preconditioning Methods and Provable Feature Learning (ICML 2025 · similarity 0.86)
- Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.