Research map / Bandits and online learning / Online convex optimization and games
Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness
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 expected-loss smoothness in the optimistic regret analysis | Adaptive OFTRL for convex losses · SEA, convex smooth losses | expected regret dependence on gradient scale: O \big( D\big( \bar \sigma_T + \bar\Sigma_T\big)\sqrt{ T }\, + DG + LD^2 \big) | Helped |
| Use OFTL on strongly convex surrogate losses with an optimistic gradient prediction | Strongly convex smooth losses · SEA, strongly convex smooth losses | expected regret dependence on stochastic variance and adversarial variation: \frac{1}{\mu} \left( 8 \sigma_{\max}^2 + 4 \Sigma_{\max}^2 \right)\log T | Helped |
| Allow adversarial perturbations of i.i.d. losses, with total perturbation bounded by C | Adaptive OFTRL · Adversarially corrupted stochastic data | expected regret: O(D \sigma \sqrt{T} + D \sqrt{GC}) | Helped |
| Use random-order sampling instead of adversarial ordering | OFTRL · Single-pass ROM, convex smooth losses | expected regret dependence on gradient variation: O \bigg( D \sigma_1 \sqrt {\log\left( e \frac{\widetilde \sigma_1}{\sigma_1}\right) T} + LD^2 + DG \bigg) | Helped |
| Increase random-order passes to P | OFTRL · Multi-pass ROM, convex smooth losses | expected regret contribution from repeated passes: DG\sqrt P | Hurt |
| Use the negative quadratic iterate-change term in the regret analysis | Adaptive OFTRL for convex smooth losses · SEA, convex smooth losses | expected regret upper bound: \frac{9L^2D^4}{\nu} | Helped |
| Use the negative quadratic iterate-change term with smoothness in the strongly convex analysis | OFTL on surrogate losses · SEA, strongly convex smooth losses | expected regret upper bound: \frac{4D^2 L^2}{\mu} \log \left(1+ \frac{16L}{\mu} \right) | Helped |
| Use optimistic OFTRL without relying on smoothness | Adaptive OFTRL for convex losses · Fully adversarial data | regret: O( DG\sqrt{T}) | No clear effect |
Closest papers by meaning
- Online Composite Optimization Between Stochastic and Adversarial Environments (NeurIPS 2024 · similarity 0.93)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.91)
- Parameter-free Algorithms for the Stochastically Extended Adversarial Model (NeurIPS 2025 · similarity 0.91)
- Gradient-Variation Online Learning under Generalized Smoothness (NeurIPS 2024 · similarity 0.90)
- Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints (NeurIPS 2025 · similarity 0.90)
- A Simple and Optimal Approach for Universal Online Learning with Gradient Variations (NeurIPS 2024 · similarity 0.90)
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.