Research map / Optimization / Nonconvex and smooth optimization
Accelerated Distance-adaptive Methods for Hölder Smooth and 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 AGDA, a parameter-free accelerated distance-adaptive method (DOG-style distance estimates plus line search) achieving near-optimal anytime rates for convex Hölder smooth problems, and a line-search-free LF-AGDA for stochastic convex optimization over bounded domains.
Problem
Parameter-free first-order optimization of convex Hölder smooth (and stochastic convex) objectives without knowing the smoothness exponent, Hölder constant, initial distance D_0, or a target accuracy, and without line search in the stochastic case.
Approach
Combines Nesterov-style accelerated regularized dual averaging with DOG-style distance adaptation: the averaging weights and the Hölder-smoothness-adaptive stepsize are driven by a running estimate of the distance to the minimizer, removing the need for a target accuracy epsilon; the stochastic variant replaces line search with a closed-form balance-equation update for beta.
Key results
- On softmax and matrix game problems, the proposed method is reported to converge fastest among DOG, DADA, and universal FGM, with the authors claiming empirical advantage.
- Theory gives an anytime rate of O(D_0^{1+nu} M log^2(D_0/rbar) / k^{(1+3nu)/2}) with near-optimal complexity tilde O(D_0^{2(1+nu)/(1+3nu)} eps^{-2/(1+3nu)}) without knowing nu, L_nu, or epsilon.
- The line-search-free LF-AGDA achieves E[psi gap] in O(M D^{1+nu}/K^{(1+3nu)/2} + sigma D/sqrt K) under bounded domain assumption.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AGDA instead of DOG, DADA, or FGM | Softmax · Softmax problem | convergence speed | Helped |
| Use AGDA instead of the compared baselines | Matrix game · Matrix game (896, 128) | convergence performance | Helped |
| Use AGDA instead of the compared baselines | Matrix game · Matrix game (448, 64) | convergence performance | Helped |
| Use LF-AGDA instead of USFGM or Adam | LF-AGDA · diabetes | robustness to stepsize-related inputs | Helped |
| Use LF-AGDA instead of the compared methods | LF-AGDA · Boston housing | long-term performance | Mixed |
| Use LF-AGDA instead of DoG | CIFAR-10 ResNet18 training · CIFAR-10 | training and validation performance | Helped |
| Use LF-AGDA instead of AdamW | CIFAR-10 ResNet18 training · CIFAR-10 | training and validation performance | No clear effect |
| Vary the initial distance estimate \bar{r} across several orders of magnitude | AGDA · Softmax problem | iterations to target accuracy | No clear effect |
Limitations
- Theory requires initial guess rbar <= 4D_0 and the local Hölder smoothness assumption within a ball of radius 3D_0.
- Line search adds O(K log K) total line-search operations versus O(K) for FGM.
- Stochastic analysis assumes a bounded domain, and the dependence on D_0 is not optimal.
Experimental setup
Datasets: LIBSVM diabetes Boston housing CIFAR-10
Metrics: objective gap versus iterations iterations to reach tolerance validation loss and accuracy (neural network)
Baselines: DOG DADA Universal fast gradient method (FGM) USFGM AdamW
Builds on: DOG Universal fast gradient method Accelerated regularized dual averaging DADA
Closest papers by meaning
- Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness (NeurIPS 2025 · similarity 0.90)
- Universal Gradient Methods for Stochastic Convex Optimization (ICML 2024 · similarity 0.89)
- Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization (AAAI 2024 · similarity 0.89)
- Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints (NeurIPS 2024 · similarity 0.88)
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity (ICLR 2025 · similarity 0.88)
- Adaptive Proximal Gradient Methods Are Universal Without Approximation (ICML 2024 · similarity 0.88)
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.