Research map / Optimization / Nonconvex and smooth optimization
Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder 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.
Proposes gradient-variation online learning for Hölder-smooth convex and strongly convex functions with parameter-free step sizes, and uses it with stabilized online-to-batch conversion and guess-and-check smoothness detection to obtain universal offline methods (accelerated in smooth regime) for stochastic convex and deterministic strongly convex optimization.
Problem
Universal optimization under Hölder smoothness: achieving optimal rates without knowing smoothness parameters, including accelerated convergence for smooth strongly convex objectives, which prior universal methods did not achieve.
Approach
Gradient-variation regret for Hölder-smooth functions via an inexact-smoothness lemma and AdaGrad-style step sizes (virtual clipping) with optimistic OGD, combined with stabilized online-to-batch conversion; for strong convexity, a guess-and-check smoothness detection that halves a weight parameter based on empirical smoothness, plus grid search over the strong convexity parameter.
Key results
- Online Hölder-smooth convex regret O(D√V_T + L_ν D^{1+ν} T^{(1-ν)/2}) without knowing L_ν or ν, recovering optimal smooth and Lipschitz rates.
- Offline stochastic convex optimization achieves O(L_ν D^{1+ν}/T^{(1+3ν)/2} + σD/√T) without knowledge of L_ν or ν.
- Deterministic strongly convex universal method achieves exp(-T/(6√κ)) accelerated rate for smooth Lipschitz objectives, improving on prior exp(-T/κ)·T/κ.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Adapt online step sizes to gradient variation without knowing the Hölder smoothness parameters | Optimistic OGD for convex online optimization · Convex online Hölder smooth optimization | regret bound: O(D\sqrt{V_T} + L_\nu D^{1+\nu}T^{\frac{1-\nu}{2}} + D\norm{\nabla f_1(\x_1)}) | Helped |
| Use stabilized online-to-batch conversion with weights α_t = t | Optimistic OGD for stochastic convex optimization · Stochastic convex Hölder smooth optimization | suboptimality: O(\frac{L_\nu D^{1+\nu}}{T^{\frac{1+3\nu}{2}}} + \frac{\sigma D}{\sqrt{T}} + \frac{D\norm{\nabla \ell(\x_1)}}{T^2}) | Helped |
| Add smoothness detection and guess-and-check to the strongly convex offline method | Universal Accelerated Strongly Convex Optimization · Deterministic strongly convex and G-Lipschitz optimization | suboptimality: O(\frac{G^2}{\lambda}\min\bbr{ \exp\sbr{\frac{-T}{6\sqrt{\kappa}}}, \frac{\log T}{T} }) | Helped |
| Search over candidate strong-convexity curvatures rather than requiring λ as input | Universal Accelerated Strongly Convex Optimization · Deterministic smooth strongly convex optimization | suboptimality: O\sbr{\frac{\norm{\nabla \ell(\x_1)}^2}{\lambda}\exp\sbr{\frac{-T}{(1+4\sqrt{2\kappa})\lceil 2\log_2 T\rceil}}} | Helped |
Surprising findings
- Lipschitz continuity may be necessary for universality in strongly convex optimization (conjectured).
Limitations
- Strongly convex universal results require Lipschitz continuity and the smoothness detection works only in the deterministic setting.
- Unconstrained setting and strong universality in unconstrained stochastic optimization remain open.
- Strong universality for strongly convex optimization (Hölder-adaptive) remains open.
Experimental setup
Metrics: regret optimality gap convergence rate
Baselines: optimistic OGD with smoothness-dependent step size adaptive normalized gradient descent universal method universal strongly convex method with sample complexity guarantee
Builds on: optimistic online gradient descent stabilized online-to-batch conversion gradient-variation online learning AdaGrad
Closest papers by meaning
- Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.92)
- Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality (NeurIPS 2025 · similarity 0.91)
- Anytime Online-to-Batch, Optimism and Acceleration (ICML 2019 · similarity 0.91)
- Accelerated Distance-adaptive Methods for Hölder Smooth and Convex Optimization (NeurIPS 2025 · similarity 0.90)
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.89)
- Online Submodular Maximization via Online Convex Optimization (AAAI 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.