Research map / Bandits and online learning / Online convex optimization and games
Parameter-free Algorithms for the Stochastically Extended Adversarial Model
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.
Develops the first parameter-free algorithms (comparator-adaptive CA-OONS and comparator- and Lipschitz-adaptive CLA-OONS) for the stochastically extended adversarial (SEA) model, using optimistic online Newton step with multi-scale MsMwC meta-algorithms, with regret scaling in the stochastic and adversarial variance terms.
Problem
Parameter-free online convex optimization in the Stochastically Extended Adversarial (SEA) model, where the domain diameter D and Lipschitz constant G are unknown and the domain may be unbounded, while regret should scale with stochastic variance and adversarial variation rather than T.
Approach
Use Optimistic Online Newton Step with adaptive step sizes as base learner; a multi-scale MsMwC meta-algorithm over base learners with geometrically spaced domain diameters yields comparator adaptivity, and a gradient-clipping reduction with a doubling-trick diameter estimate yields Lipschitz adaptivity.
Key results
- CA-OONS achieves expected regret Õ(||u||^2 + ||u||(sqrt(sigma^2_{1:T}) + sqrt(Sigma^2_{1:T}))) with unknown domain diameter D and known G.
- CLA-OONS extends this to unknown D and G, with regret Õ(||u||^2(sqrt(sigma^2)+sqrt(Sigma^2)) + ||u||^4 + sqrt(sigma_{1:T}+G_{1:T})) plus G-dependent terms.
- Proposition shows sigma^2_{1:T} can be Θ(T) smaller than the Jensen-style alternative tilde-sigma^2_{1:T}.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive step sizes in OONS with D and G known | OONS · SEA model | expected regret | Helped |
| Remove prior knowledge of D while retaining known G, using CA-OONS | OONS · SEA model | expected regret | Mixed |
| Remove prior knowledge of both D and G, using CLA-OONS | OONS · SEA model | expected regret | Mixed |
Limitations
- Dependence on ||u||_2^2 in the leading term rather than the desired ||u||_2, falling short of the best worst-case bound when specialized to adversarial OCO.
- CA-OONS requires O(log T) base learners, so gradient queries scale with log T per round.
- Bounds are for expected regret only; no high-probability guarantees.
Experimental setup
Metrics: expected regret
Baselines: OFTRL (Sachs et al.) OMD (Chen et al.) Cutkosky 2019 comparator-adaptive OCO Mhammedi and Koolen 2020 Cutkosky and Mhammedi 2020
Builds on: Optimistic Online Newton Step MsMwC Optimistic mirror descent Optimistic FTRL
Closest papers by meaning
- Online Composite Optimization Between Stochastic and Adversarial Environments (NeurIPS 2024 · similarity 0.91)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.88)
- Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.88)
- Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints (NeurIPS 2025 · similarity 0.87)
- Projection-Free Online Convex Optimization with Time-Varying Constraints (ICML 2024 · similarity 0.87)
- Minimax Adaptive Online Nonparametric Regression over Besov spaces (NeurIPS 2025 · similarity 0.87)
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.