Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds

Lijun Zhang, Linzhe He, Wei Jiang, Shiyin Lu

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 $\ell_2$-norm switching costs yields a competitive ratio of $1+\frac{2}{\sqrtλ}$. For dynamic regret with the $\ell_2$-norm switching cost, we develop Smoothed Ader (SAder), which achieves the optimal $O(\sqrt{T(1+P_T)})$ rate in the standard online convex optimization setting, where $P_T$ is the comparator's path-length. Its lookahead version removes the bounded-gradient assumption, and a matching lower bound establishes optimality in this setting. Finally, for convex hitting costs on a bounded…