Research map / Optimization / Nonconvex and smooth optimization
Gradient-Variation Online Learning under Generalized 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.
Studies gradient-variation online learning under generalized (l-)smoothness, extends optimistic OMD with trajectory-wise stability, and designs a Lipschitz-adaptive meta-algorithm for universal (curvature-agnostic) regret bounds.
Problem
Gradient-variation regret bounds in online convex optimization typically require a global smoothness constant, which is unrealistic; generalized smoothness (smoothness correlated with gradient norm) breaks existing analyses, and universal methods need unbounded-gradient handling.
Approach
Extend optimistic OMD with optimism set at the intermediate decision and step sizes tuned by locally estimated smoothness along the trajectory, plus a new Lipschitz-adaptive meta-algorithm (optimistic Adapt-ML-Prod with clipping and self-confident learning rate) combined with a function-variation-to-gradient-variation conversion to obtain universal bounds for convex and strongly convex functions.
Key results
- Optimistic OMD under l-smoothness achieves O(sqrt(V_T)) regret for convex and O(log V_T / lambda) for strongly convex functions (up to smoothness-dependent constants).
- A single universal algorithm attains O(sqrt(V_T) log(B_T+log T)) for convex and O(log V_T/lambda + G^2 log^2/lambda) for strongly convex functions without knowing curvature.
- Results extend to SEA model stochastic-adversarial bounds and O(1/T) fast rates for convex-concave games under generalized smoothness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use trajectory-wise local smoothness with optimistic OMD | Convex online learning under generalized smoothness · Generalized-smooth convex online learning | regret: O(D√V_T + L̂_max·D^2) | Helped |
| Use trajectory-wise local smoothness with curvature-dependent step sizes | Strongly convex online learning · Generalized-smooth strongly convex online learning | regret: O((1/λ) log{V_T} + L̂_max·D^2) | Helped |
| Ensemble convex and strongly convex base-learners with the Lipschitz-adaptive meta-algorithm | Universal Gradient-Variation Online Learning · Generalized-smooth convex online learning | regret: O(√V_T·log(B_T + log T)) | Helped |
| Use a universal ensemble without prior curvature knowledge | Universal Gradient-Variation Online Learning · Generalized-smooth strongly convex online learning | regret: O((1/λ)log V_T + Ĝ_max^2(log(B_T + log T))^2/λ) | Helped |
| Apply the universal method under generalized smoothness | Universal Gradient-Variation Online Learning · SEA model, convex | expected regret: O((√σ̃_{1:T}^2 + √Σ_{1:T}^2)·log(Ĝ_maxD)) | Helped |
| Apply the universal method under generalized smoothness | Universal Gradient-Variation Online Learning · SEA model, strongly convex | expected regret: O((σ̃_max^2+Σ_max^2)log(σ̃_{1:T}^2 + Σ_{1:T}^2)) | Helped |
| Use optimistic updates tuned to generalized local smoothness | Optimistic OMD · Convex-concave min-max game | convergence rate: O(1/T) | Helped |
| Add clipping to the OMD gradient update | Optimistic OMD · Generalized-smooth convex online learning | regret: O(Ĝ_max^2D) -> O(Ĝ_maxD) | Helped |
| Use the clipping technique in OMD | Optimistic OMD · Generalized-smooth convex online learning | regret: 5D/2√2V_T + 4L̂_maxD^2 +5Ĝ_maxD | Helped |
Limitations
- Dependence on the maximum smoothness constant along the trajectory, L_max, in the convex bound.
- Exp-concave functions under generalized smoothness remain open.
- Requires a global lower bound on loss functions for the universal algorithm (used for binary search of optimism).
Experimental setup
Metrics: regret gradient-variation regret convergence rate
Baselines: MsMwC-Master Squint+L optimistic OMD with global smoothness
Builds on: optimistic online mirror descent Adapt-ML-Prod MsMwC-Master l-smoothness (L0,L1)-smoothness
Closest papers by meaning
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.93)
- Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness (NeurIPS 2025 · similarity 0.92)
- Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach (NeurIPS 2023 · similarity 0.92)
- Online Composite Optimization Between Stochastic and Adversarial Environments (NeurIPS 2024 · similarity 0.89)
- Discounted Adaptive Online Learning: Towards Better Regularization (ICML 2024 · similarity 0.89)
- Delving into the Convergence of Generalized Smooth Minimax Optimization (ICML 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.