Research map / Optimization / Nonconvex and smooth optimization
Universal Gradient Methods for Stochastic Convex Optimization
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 line-search-free universal stochastic gradient and fast gradient methods that adapt to Hölder smoothness exponent, constant, and gradient noise level given only a diameter bound D, via a balance-equation step-size rule using symmetrized Bregman distance.
Problem
Stochastic convex optimization where the objective is Hölder smooth with unknown exponent and constant and the stochastic gradient oracle has unknown variance; existing methods need knowledge of these parameters or line search.
Approach
Replace AdaGrad-style gradient-norm accumulation with a balance equation that sets the step-size coefficient so that the Bregman-type error term equals the diameter-scaled growth term, using stochastic symmetrized Bregman distance (gradient and iterate differences); this yields universal rates without line search and optimal accelerated variants.
Key results
- Universal Stochastic Gradient Method guarantees E[F(xbar_k)]-F* <= inf_nu 8 L_nu D^{1+nu}/k^{(1+nu)/2} + 4 sigma D/sqrt(k), i.e. O(inf_nu [L_nu/eps]^{2/(1+nu)} D^2 + sigma^2 D^2/eps^2) oracle calls.
- Universal Stochastic Fast Gradient Method attains O(inf_nu [L_nu D^{1+nu}/eps]^{2/(1+3nu)} + sigma^2 D^2/eps^2) oracle calls, claimed optimal.
- Experiments show USGM matches AdaGrad and AcceleGrad on least squares and is slightly faster than AdaGrad on logistic regression; on MNIST it is competitive with AdaGrad and Adam.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use USGM with an adaptive step-size based on gradient and iterate differences | Stochastic gradient optimization · Diabetes | training error convergence | No clear effect |
| Use USGM instead of AdaGrad | Stochastic gradient optimization · a1a and ionosphere | training error convergence | Helped |
| Use USGM instead of UniXGrad | Stochastic gradient optimization · a1a and ionosphere | training error convergence | No clear effect |
| Adapt step sizes to both stochastic noise and Hölder smoothness | USGM · Stochastic convex optimization | expected function residual | Helped |
| Use acceleration with the adaptive step-size rule | USFGM · Stochastic convex optimization | oracle complexity | Helped |
Experimental setup
Datasets: diabetes (LIBSVM) a1a (LIBSVM) ionosphere (LIBSVM) MNIST
Benchmarks: diabetes (LIBSVM) least squares a1a logistic regression ionosphere logistic regression MNIST neural network training
Metrics: function residual vs oracle calls training error test accuracy
Baselines: AdaGrad AcceleGrad UniXGrad SGD Adam
Builds on: Universal Gradient Method (Nesterov) AdaGrad Method of Similar Triangles
Closest papers by meaning
- Universality of AdaGrad Stepsizes for Stochastic Optimization: Inexact Oracle, Acceleration and Variance Reduction (NeurIPS 2024 · similarity 0.92)
- Simple Stochastic Gradient Methods for Non-Smooth Non-Convex Regularized Optimization (ICML 2019 · similarity 0.91)
- Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities (AAAI 2021 · similarity 0.91)
- A Universally Optimal Multistage Accelerated Stochastic Gradient Method (NeurIPS 2019 · similarity 0.90)
- Last-Iterate Convergence of Single-Loop Stochastic Methods for Constrained Convex-Concave Minimax Problems (NeurIPS 2026 · similarity 0.89)
- Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods (ICLR 2024 · 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.