Research map / Optimization / Nonconvex and smooth optimization
Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction
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 AdaGrad-stepsize SGD and accelerated SGD for composite problems with approximately smooth objectives and biased-inexact stochastic oracles, extending to implicit and SVRG-based variance reduction, yielding universal methods needing only a diameter estimate.
Problem
Stochastic convex composite optimization where the objective is only approximately smooth ((δ,L)-smooth) and gradients come from a possibly biased stochastic oracle; prior adaptive methods assume exact smoothness or bounded variance and need problem constants.
Approach
Identifies a single abstract inequality for stepsize rules that AdaGrad-type updates satisfy with a virtual stepsize and a telescoping error term; uses it to analyze SGD and accelerated SGD (and SVRG variants) with AdaGrad stepsizes, requiring only the diameter D.
Key results
- Theoretical O(LfD^2/k^2 + σD/√k + kδf) rates for UniFastSgd with AdaGrad stepsizes, adaptive to Lf and σ, requiring only D.
- UniSvrg and UniFastSvrg reach stochastic-oracle complexity O(nt) with explicit SVRG variance reduction and implicit variance reduction via σ* at the minimizer.
- In experiments on the polyhedron feasibility problem, UniFastSvrg performs best among accelerated SVRG methods and UniSvrg converges faster than AdaSVRG; FastSvrg with constant stepsize fails to converge for non-smooth q<2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SVRG-type variance reduction | SGD methods on the polyhedron feasibility problem · Polyhedron feasibility problem (5) | convergence speed | Helped |
| Use UniSvrg instead of AdaSVRG | non-accelerated SVRG methods · Polyhedron feasibility problem (5) | convergence speed | Helped |
| Use UniFastSvrg instead of the other accelerated SVRG methods | accelerated SVRG methods · Polyhedron feasibility problem (5) | convergence speed | Helped |
| Use constant stepsize FastSvrg | FastSvrg · Polyhedron feasibility problem (5), q < 2 | convergence | Hurt |
| Increase mini-batch size | UniSgd, UniFastSgd, UniSvrg, and UniFastSvrg · Polyhedron feasibility problem (5), q = 1.5 | convergence speed | Helped |
| Add explicit SVRG-type variance reduction | UniSgd and UniFastSgd · Stochastic optimization problem (1) | expected function residual | Helped |
Surprising findings
- Constant-stepsize FastSvrg does not converge when the problem is not Lipschitz smooth (q<2), whereas the universal AdaGrad-based methods do.
Limitations
- Requires knowledge (or estimate) of the feasible-set diameter D; misestimation multiplies complexity bounds.
- Assumption 9 needed for UniSvrg analysis may be artificial.
- Analysis restricted to convex problems.
Experimental setup
Datasets: synthetic polyhedron feasibility / (q-norm hinge) problem
Benchmarks: synthetic polyhedron feasibility problem (q in {1,1.3,1.6,2})
Metrics: function residual vs number of stochastic oracle calls
Baselines: AdaSVRG AdaVRAG AdaVRAE FastSvrg
Builds on: AdaGrad SVRG SVRG++ AdaVRAE (δ,L)-oracle
Closest papers by meaning
- SGD with AdaGrad Stepsizes: Full Adaptivity with High Probability to Unknown Parameters, Unbounded Gradients and Affine Variance (ICML 2023 · similarity 0.94)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 2024 · similarity 0.92)
- On the Convergence of AdaGrad(Norm) on $\mathbb{R}^d$: Beyond Convexity, Non-Asymptotic Rate and Acceleration (ICLR 2023 · similarity 0.92)
- Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities (AAAI 2021 · similarity 0.92)
- Complexity Lower Bounds of Adaptive Gradient Algorithms for Non-convex Stochastic Optimization under Relaxed Smoothness (ICLR 2025 · similarity 0.90)
- Stochastic Gradients under Nuisances (NeurIPS 2025 · similarity 0.89)
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.