Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds
We revisit smoothed online learning and develop algorithms with improved competitive ratios, optimal dynamic regret with switching cost, and best-of-both-worlds guarantees. Surprisingly, minimizing the hitting cost alone is $\max(1,\frac{2}α)$-competitive for $α$-polyhedral functions under the $\ell_2$-norm switching cost and $1+\frac{4}λ$-competitive for $λ$-quadratic growth functions under the squared $\ell_2$-norm switching cost, significantly improving existing guarantees. The polyhedral bound is tight for this naive algorithm, and we establish a matching lower bound for $α\geq1$. For convex $λ$-quadratic growth hitting costs, minimizing a suitably weighted sum of hitting and squared ...
| Authors | Lijun Zhang, Linzhe He, Wei Jiang et al. |
|---|---|
| Primary category | cs.LG |
| Published | 17 October 2026 |
| Last updated at source | 17 October 2026 |
Popularity, last 4 days
0 now. Counts as reported by the source, snapshotted daily by Silytics.
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 23 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.