Lazy OCO: Online Convex Optimization on a Switching Budget
This work provides new algorithms and regret bounds for online convex optimization under switching constraints, which is relevant for practitioners in scenarios requiring infrequent decision changes.
This paper addresses online convex optimization where the decision-maker has a budget of at most S switches in expectation over T rounds. The authors develop computationally efficient algorithms for the oblivious setting, achieving a regret bound of O(T/S) for general convex losses and O(T/S^2) for strongly convex losses.
We study a variant of online convex optimization where the player is permitted to switch decisions at most $S$ times in expectation throughout $T$ rounds. Similar problems have been addressed in prior work for the discrete decision set setting, and more recently in the continuous setting but only with an adaptive adversary. In this work, we aim to fill the gap and present computationally efficient algorithms in the more prevalent oblivious setting, establishing a regret bound of $O(T/S)$ for general convex losses and $\widetilde O(T/S^2)$ for strongly convex losses. In addition, for stochastic i.i.d.~losses, we present a simple algorithm that performs $\log T$ switches with only a multiplicative $\log T$ factor overhead in its regret in both the general and strongly convex settings. Finally, we complement our algorithms with lower bounds that match our upper bounds in some of the cases we consider.