Smoothed online learning algorithms improve decision making costs
Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds
Machine Learning
Summary
This paper looks at making better decisions over time when there are costs both for making wrong choices and for changing decisions too often. The authors show that even a simple way of minimizing immediate costs can be surprisingly good in some cases, and they offer new methods that balance quickly adapting to changes while avoiding too many switches. Their algorithms work optimally in some settings and combine the best features of two common approaches. They also find limits on how well these methods can perform, helping us understand the challenges in this area.
What this means in practice
- •For real-time decision makers: Improve algorithms for making sequential decisions where switching costs matter, such as in dynamic pricing or online advertising.
- •For control system engineers: Optimize adaptive control strategies with trade-offs between reacting to changes and minimizing costly switches in system settings.
Authors
Lijun Zhang, Linzhe He, Wei Jiang, Shiyin Lu
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}α)$-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 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.