Research map / Optimization / Optimizers
AdaGrad under Anisotropic Smoothness
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.
Proves convergence guarantees for AdaGrad under a novel anisotropic (coordinate-wise) smoothness and noise assumption, plus a generalized anisotropic (L0,L1)-smoothness, showing better dimensional dependence than SGD and AdaGrad-Norm in large-batch settings, supported by logistic regression and GPT-2 instruction-tuning experiments.
Problem
Theory explaining when and why adaptive gradient methods (AdaGrad) outperform coordinate-uniform methods like SGD in smooth, large-batch stochastic optimization, where existing analyses give no dimensional benefit.
Approach
Replace isotropic smoothness and noise assumptions with coordinate-wise (anisotropic) L-smoothness in the L-weighted norm and per-coordinate noise bounds sigma_j, and extend to anisotropic (L0,L1)-generalized smoothness where local smoothness depends on absolute coordinate gradients; this yields AdaGrad bounds in l1-norms that can beat SGD's l2-based bounds when the problem is sparse/imbalanced.
Key results
- On logistic regression (a9a), AdaGrad reaches loss gap around 0.14e-3 at M=1 versus 0.77e-3 for SGD, and stays roughly flat across batch sizes up to M=256.
- On real-sim and rcv1.binary, D_inf/D_2 ratios are 0.05 and 0.02 respectively, indicating the predicted AdaGrad advantage from sparsity.
- Fine-tuning GPT-2 on Alpaca, AdaGrad achieves training loss 2.11 vs 2.29 for SGD at M=128, and 2.12 vs 2.57 at M=1024.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace SGD with Adagrad | Logistic regression · a4a, M=1 and M=1024 | training loss gap × 10^-3: 2.66$\pm$0.08 -> 0.22$\pm$0.03; 8.47$\pm$0.05 -> 0.51$\pm$0.08 | Helped |
| Replace SGD with Adagrad | Logistic regression · a6a, M=1 and M=1024 | training loss gap × 10^-3: 0.87$\pm$0.09 -> 0.16$\pm$0.00; 2.53$\pm$0.03 -> 0.20$\pm$0.02 | Helped |
| Replace SGD with Adagrad | Logistic regression · a9a, M=1 and M=1024 | training loss gap × 10^-3: 0.77$\pm$0.08 -> 0.14$\pm$0.01; 0.76$\pm$0.01 -> 0.12$\pm$0.02 | Helped |
| Replace SGD with Adagrad | Logistic regression · real-sim, M=1 and M=1024 | training loss gap × 10^-1: 0.42$\pm$0.08 -> 0.14$\pm$0.00; 2.68$\pm$0.01 -> 0.19$\pm$0.00 | Helped |
| Replace SGD with Adagrad | Logistic regression · rcv1.binary, M=1 and M=1024 | training loss gap × 10^-1: 0.48$\pm$0.02 -> 0.10$\pm$0.00; 5.02$\pm$0.16 -> 0.20$\pm$0.01 | Helped |
| Replace SGD with Adagrad | GPT-2 fine-tuned on Alpaca · Alpaca instruction following, M=32 and M=1024 | training loss: 2.20 -> 2.14; 2.57 -> 2.20 | Helped |
| Increase batch size from 1 to 1024 | Adagrad logistic regression · a9a | training loss gap × 10^-3: 0.14$\pm$0.01 -> 0.12$\pm$0.02 | No clear effect |
| Increase batch size from 1 to 1024 | Adagrad logistic regression · real-sim | training loss gap × 10^-1: 0.14$\pm$0.00 -> 0.19$\pm$0.00 | Mixed |
Surprising findings
- AdaGrad's convergence is largely unaffected by batch size in logistic regression experiments, unlike SGD whose loss gap grows with batch size.
- The theoretical comparison suggests the bias-term gap between AdaGrad and SGD can be Theta(1/d), larger than the Theta(1/sqrt(d)) variance-term gap.
Limitations
- Comparisons are between upper bounds, which only reflect worst-case performance rather than actual performance.
- The generalized smoothness assumption depends on dimension-related quantities and is verified only on sampled coordinates in GPT-2.
- Theory assumes a bounded domain W and relaxed noise assumptions are left for future work; relation between anisotropic L1 and standard L1 unresolved.
Experimental setup
Datasets: Alpaca a4a a6a a9a real-sim rcv1.binary
Benchmarks: a4a a6a a9a real-sim rcv1.binary Alpaca
Metrics: training loss loss gap f(w)-f(w*) C_var = D_inf/D_2 ratio
Baselines: SGD AdaGrad-Norm
Builds on: AdaGrad AdaGrad-Norm (L0,L1)-smoothness SignSGD clipped SGD
Closest papers by meaning
- AdaGrad Stepsizes: Sharp Convergence Over Nonconvex Landscapes (ICML 2019 · similarity 0.89)
- Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction (NeurIPS 2024 · similarity 0.87)
- Non-asymptotic Analysis of Biased Adaptive Stochastic Approximation (NeurIPS 2024 · similarity 0.87)
- Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness (ICLR 2025 · similarity 0.86)
- Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad (NeurIPS 2024 · similarity 0.86)
- Directional Smoothness and Gradient Methods: Convergence and Adaptivity (NeurIPS 2024 · 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.