Research map / Bandits and online learning / Online convex optimization and games
A Simple and Optimal Approach for Universal Online Learning with Gradient Variations
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 a simple two-layer online ensemble for universal online learning that achieves optimal gradient-variation regret for strongly convex, exp-concave, and convex functions with one gradient query per round and O(log T) base learners.
Problem
Universal online learning with gradient-variation regret: achieving optimal regret for unknown curvature (strongly convex, exp-concave, convex) without prior curvature knowledge, while being computationally efficient (few base learners, one gradient query per round).
Approach
Replaces the algorithmic-stability control used in prior gradient-variation analyses with a Bregman-divergence negative term from linearization plus a smoothness property (squared gradient difference bounded by 2L times Bregman divergence), and uses a two-layer ensemble (OPTIMISTIC-ADAPT-ML-PROD meta over OOMD base learners on surrogate losses).
Key results
- Achieves O(log V_T), O(d log V_T), and O(sqrt(V_T)) regret simultaneously for strongly convex, exp-concave, and convex functions, improving the O(sqrt(V_T) log V_T) convex bound of Yan et al. 2023.
- Uses one gradient query per round and O(log T) base learners, versus O(log T) gradient queries for Zhang et al. 2022a and O((log T)^2) base learners for Yan et al. 2023.
- Implies optimal universal small-loss regret (O(log F_T), O(d log F_T), O(sqrt(F_T))) and matches best known SEA model guarantees of Chen et al. 2024 with a single algorithm.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed universal approach instead of Yan et al. (2023) | Universal online learning with convex functions · Convex functions | regret: O(√VT log VT) -> O(√VT) | Helped |
| Use the proposed universal approach instead of Yan et al. (2023) | Universal online learning with strongly convex functions · Strongly convex functions | regret: O(1/λ log VT) -> O(1/λ log VT) | No clear effect |
| Use the proposed universal approach instead of Yan et al. (2023) | Universal online learning with exp-concave functions · Exp-concave functions | regret: O(d/α log VT) -> O(d/α log VT) | No clear effect |
| Use the proposed universal approach in the SEA model instead of Chen et al. (2024) | Universal online learning · Strongly convex SEA | regret | No clear effect |
| Use the proposed universal approach in the SEA model instead of Chen et al. (2024) | Universal online learning · Exp-concave SEA | regret | No clear effect |
| Use the proposed universal approach in the SEA model instead of Chen et al. (2024) | Universal online learning · Convex SEA | regret | No clear effect |
Limitations
- Analysis does not strictly outperform stability-based approach (Yan et al. 2023) for fast rates in multi-player games, since stability is not controlled directly.
- Assumes bounded domain and gradients and smoothness (relaxed to X+), and results are for constrained domains only.
- Fixed-point computation for convex optimism adds implementation complexity.
Experimental setup
Metrics: regret bound order (O-notation)
Baselines: van Erven and Koolen 2016 Wang et al. 2019 Zhang et al. 2022a Yan et al. 2023 Chen et al. 2024 Sachs et al. 2022
Builds on: MetaGrad Yan et al. 2023 three-layer ensemble Zhang et al. 2022a universal online learning Wei et al. 2016 optimistic adapt-ML-prod Chiang et al. 2012 gradient-variation regret
Closest papers by meaning
- Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.93)
- Discounted Adaptive Online Learning: Towards Better Regularization (ICML 2024 · similarity 0.90)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.90)
- Gradient-Variation Online Adaptivity for Accelerated Optimization with Hölder Smoothness (NeurIPS 2025 · similarity 0.89)
- Universal Online Convex Optimization with $1$ Projection per Round (NeurIPS 2024 · similarity 0.89)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 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.