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

Abstract: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}{\alpha})$-competitive for $\alpha$-polyhedral functions under the $\ell_2$-norm switching cost and $1+\frac{4}{\lambda}$-competitive for $\lambda$-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 $\alpha\geq1$. For convex $\lambda$-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{\lambda}}$. 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 convex domain, we develop UDNP to aggregate any two experts in the lookahead setting under both switching costs. Its additional cumulative cost is at most $O(1)$ relative to the first expert and $O(\sqrt{T\log T})$ relative to the second, yielding best-of-both-worlds guarantees without bounded gradients.

Machine Learning (cs.LG)

arXiv:2610.24370 [cs.LG]

(or arXiv:2610.24370v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2610.24370 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.