Research map / Optimization / Optimizers
Remove that Square Root: A New Efficient Scale-Invariant Version of AdaGrad
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.
Proposes KATE, a scale-invariant AdaGrad variant that removes the square root from the denominator and adds an increasing numerator sequence, with scale-invariance proof for GLMs and O(log T/sqrt T) non-convex convergence.
Problem
AdaGrad's performance deteriorates on poorly scaled or ill-conditioned data; existing scale-invariant AdaGrad variants rely on feature vectors explicitly, limiting use beyond GLMs.
Approach
Replace AdaGrad's square-root denominator with its square and add an adaptive increasing numerator sequence m_t, so the stepsize is scale-invariant for generalized linear models while retaining AdaGrad-like convergence for smooth non-convex stochastic problems.
Key results
- On synthetic logistic regression with Delta=1e-8, KATE reaches functional value about 1e-3 after 1e4 iterations while other adaptive methods fail even after 1e5.
- On image classification (ResNet18, CIFAR10), KATE with different eta values outperforms Adam and AdaGrad in test accuracy and loss.
- KATE achieves O(log T/sqrt T) convergence in min E||grad f||^2 for smooth non-convex problems under bounded variance, matching AdaGrad and Adam rates.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use KATE instead of AdaGrad | Logistic regression on simulated poorly scaled data, Δ = 10⁻⁸ · Logistic regression | loss: 10^{-3} after only 10^4 iterations; AdaGrad does not achieve this even after 10^5 iterations | Helped |
| Use KATE instead of AdaGradNorm, SGD-decay, or SGD-constant | Logistic regression on simulated poorly scaled data, small Δ · Logistic regression | loss | Helped |
| Use KATE instead of AdaGrad | Logistic regression on simulated poorly scaled data, large Δ · Logistic regression | loss | No clear effect |
| Use KATE instead of the other tested algorithms | LIBSVM heart, australian, and splice logistic-regression datasets · heart, australian, splice | loss and accuracy | Helped |
| Use KATE instead of Adam or AdaGrad | ResNet18 image classification · CIFAR10 | top-1 accuracy and cross-entropy loss | Helped |
| Use KATE instead of AdaGrad | BERT fine-tuning · Emotion | top-1 accuracy and cross-entropy loss | Helped |
| Use KATE instead of Adam | BERT fine-tuning · Emotion | top-1 accuracy and cross-entropy loss | No clear effect |
| Use KATE with the alternative learning rate and Δ, retaining the referenced scheduler | DistilRoBERTa-base emotion classification · Emotion | performance | No clear effect |
| Use KATE with the alternative learning rate and Δ, retaining the referenced scheduler | Image classification · Image classification | accuracy | No clear effect |
| Vary η across the reported settings (ablation) | KATE on image classification · CIFAR10 | top-1 accuracy | Helped |
Surprising findings
- Authors note that the KATE convergence result does not apply to the epsilon=1/2 case of a related AdaGrad variant, where the step size decays too quickly.
Limitations
- Deterministic convergence theorem requires nu_0 <= 1/L (not parameter-free); parameter-free extension left to future work.
- Scale-invariance proven only for GLMs with zero initialization; neural network experiments are preliminary.
- Stochastic rate is O(log^{1/2} T / T^{1/4}) for E||grad f|| metric, slower than deterministic setting.
Experimental setup
Datasets: CIFAR10 Emotion (Hugging Face Hub) LIBSVM heart LIBSVM australian LIBSVM splice synthetic logistic regression data
Benchmarks: CIFAR10 Emotion LIBSVM heart LIBSVM australian LIBSVM splice
Metrics: functional value (loss) top-1 accuracy cross-entropy loss gradient norm
Baselines: AdaGrad AdaGradNorm Adam SGD-decay SGD-constant
Builds on: AdaGrad AdaGradNorm D-Adaptation Prodigy
Closest papers by meaning
- Prodigy: An Expeditiously Adaptive Parameter-Free Learner (ICML 2024 · similarity 0.88)
- A Comprehensive Framework for Analyzing the Convergence of Adam: Bridging the Gap with SGD (ICML 2025 · similarity 0.86)
- AdaGrad under Anisotropic Smoothness (ICLR 2025 · similarity 0.86)
- Adam Reduces a Unique Form of Sharpness: Theoretical Insights Near the Minimizer Manifold (NeurIPS 2025 · similarity 0.86)
- Clipping Improves Adam-Norm and AdaGrad-Norm when the Noise Is Heavy-Tailed (ICML 2025 · similarity 0.85)
- Adaptive Methods through the Lens of SDEs: Theoretical Insights on the Role of Noise (ICLR 2025 · similarity 0.85)
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.