Research map / Bandits and online learning / Online convex optimization and games
Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization
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 |
|---|---|---|---|
| Add an explicit step toward the current hitting-cost minimizer after the OBD step | OBD, yielding G-OBD · SOCO with quasiconvex hitting costs and squared ℓ2 movement | competitive ratio: OBD: \Omega(m^{-\frac{2}{3}}); G-OBD: O\left(m^{-1/2}\right) | Helped |
| Add a regularization term encouraging the update to approach the hitting-cost minimizer | OBD, yielding R-OBD · SOCO with m-strongly convex hitting costs and squared ℓ2 movement | competitive ratio: \frac{1}{2}\left(1 + \sqrt{1 + \frac{4}{m}}\right) | Helped |
| Set λ2 = 0, removing the minimizer-attraction regularizer (ablation) | R-OBD · SOCO with quasiconvex hitting costs and squared ℓ2 movement | competitive ratio: \Omega(1/m) | Hurt |
| Use R-OBD with the stated parameter choice to balance regret and competitiveness | R-OBD · SOCO with strongly convex hitting costs and bounded feasible set and gradient | L-constrained dynamic regret: O(G\sqrt{TL}) | Helped |
| Use R-OBD with the stated regret-compatible parameters | R-OBD · SOCO with strongly convex hitting costs and bounded feasible set and gradient | competitive ratio: \max\left( \frac{1}{2}\left(1 + \sqrt{1 + \frac{4\beta^2}{\alpha m}}\right), 1 - \frac{\beta}{4\alpha} + \frac{\beta^2}{ | Mixed |
Closest papers by meaning
- Revisiting Smoothed Online Learning (NeurIPS 2021 · similarity 0.92)
- Online Optimization with Memory and Competitive Control (NeurIPS 2020 · similarity 0.91)
- Designing smoothing functions for improved worst-case competitive ratio in online optimization (NeurIPS 2016 · similarity 0.91)
- Fairness-Regularized Online Optimization with Switching Costs (NeurIPS 2025 · similarity 0.90)
- A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees (NeurIPS 2026 · similarity 0.89)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.88)
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.