Research map / Bandits and online learning / Online convex optimization and games
Revisiting Smoothed 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 |
|---|---|---|---|
| Minimize hitting cost alone instead of using OBD | Smoothed online learning with α-polyhedral hitting costs · α-polyhedral functions | competitive ratio: 3+\frac{8}{\alpha} -> max(1, \frac{2}{\alpha}) | Helped |
| Minimize hitting cost alone rather than use the earlier naive bound | Smoothed online learning with α-polyhedral hitting costs · α-polyhedral functions | competitive ratio: 1+ \frac{2}{\alpha} -> \max(1, \frac{2}{\alpha}) | Helped |
| Minimize hitting cost alone rather than use the earlier naive bound | Smoothed online learning with λ-quadratic growth hitting costs · λ-quadratic growth functions | competitive ratio: \max(1+\frac{6}{\lambda},4) -> 1 + \frac{4}{\lambda} | Helped |
| Add a weighted switching-cost term to the greedy objective | Naive Approach on convex λ-quadratic growth functions · Convex λ-quadratic growth functions | competitive ratio: 1 + \frac{4}{\lambda} -> 1 + \frac{2}{\sqrt{\lambda}} | Helped |
| Add switching cost to the loss used for expert weighting | Ader for dynamic regret with switching cost · Convex functions with bounded gradients and bounded domain | dynamic regret with switching cost: O\left(\sqrt{T(1+P_T)} \right) | Helped |
| Use hitting-cost lookahead and greedy experts, removing the bounded-gradient requirement | SAder · Convex functions with known hitting costs and bounded domain | dynamic regret with switching cost: O\left(\sqrt{T(1+P_T)} \right) | Helped |
| Ignore the switching cost when choosing actions (ablation) | Greedy approach for α-polyhedral hitting costs · α-polyhedral functions | competitive ratio: max(1, \frac{2}{\alpha}) | Helped |
| Ignore the switching cost when choosing actions (ablation) | Greedy approach for λ-quadratic growth hitting costs · λ-quadratic growth functions | competitive ratio: 1 + \frac{4}{\lambda} | Helped |
Closest papers by meaning
- Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization (NeurIPS 2019 · similarity 0.92)
- Dynamic Regret in Online Convex Optimization with Indicator Switching Costs (NeurIPS 2026 · similarity 0.91)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.90)
- Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability (ICML 2025 · similarity 0.89)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.89)
- Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously (NeurIPS 2024 · 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.