Research map / Bandits and online learning / Online convex optimization and games
Combining Adversarial Guarantees and Stochastic Fast Rates in Online Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Squint's second-order individual-sequence guarantee under a (B, κ)-Bernstein condition | Squint · Hedge, (B, κ)-Bernstein stochastic setting | expected regret: O\del*{K_T^{\frac{1}{2-\kappa}}T^{\frac{1-\kappa}{2-\kappa}}} | Helped |
| Use MetaGrad's second-order individual-sequence guarantee under a (B, κ)-Bernstein condition | MetaGrad · Online convex optimization, (B, κ)-Bernstein stochastic setting | expected regret: O\del*{K_T^{\frac{1}{2-\kappa}}T^{\frac{1-\kappa}{2-\kappa}}} | Helped |
| Rely on the Bernstein condition with exponent κ to obtain stochastic fast rates | Squint and MetaGrad · Hedge and online convex optimization | regret rate: T^{\frac{1-\kappa}{2-\kappa}} | Mixed |
| Use second-order guarantees without tuning to the unknown Bernstein parameters | Squint and MetaGrad · Bernstein stochastic environments | regret | Helped |
| Apply a gap condition to the Hedge loss distribution | Squint · Hedge, gap α > 0 | regret: O(K_T) = O(\ln \ln T) | Helped |
| Use Squint rather than ERM/FTL in the constructed Hedge example with infinitely many potentially misleading experts | Hedge · Hedge, (1, κ)-Bernstein example | regret | Helped |
| Retain the second-order method's adversarial guarantee while exploiting favorable stochastic data | Squint and MetaGrad · Adversarial and Bernstein stochastic environments | regret: O(\sqrt{T}) | Mixed |
Closest papers by meaning
- Online Composite Optimization Between Stochastic and Adversarial Environments (NeurIPS 2024 · similarity 0.90)
- Online Learning in the Random-Order Model (ICML 2025 · similarity 0.90)
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.90)
- Parameter-free Algorithms for the Stochastically Extended Adversarial Model (NeurIPS 2025 · similarity 0.90)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.89)
- High-Dimensional Prediction for Sequential Decision Making (ICML 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.