Online Convex Optimization with Continuous Switching Constraint

Abstract

In many sequential decision making applications, the change of decision would bring an additional cost, such as the wear-and-tear cost associated with changing server status. To control the switching cost, we introduce the problem of online convex optimization with continuous switching constraint, where the goal is to achieve a small regret given a budget on the \emph{overall} switching cost. We first investigate the hardness of the problem, and provide a lower bound of order $\Omega (\sqrt{T})$ when the switching cost budget $S=\Omega (\sqrt{T})$, and $\Omega (\min \{\frac{T}{S},T\})$ when $S=O(\sqrt{T})$, where $T$ is the time horizon. The essential idea is to carefully design an adaptive adversary, who can adjust the loss function according to the cumulative switching cost of the player incurred so far based on the orthogonal technique. We then develop a simple gradient-based algorithm which enjoys the minimax optimal regret bound. Finally, we show that, for strongly convex functions, the regret bound can be improved to $O(\log T)$ for $S=\Omega (\log T)$, and $O(\min \{T/\exp (S)+S,T\})$ for $S=O(\log T)$.

arXiv comment18 pages, 2 figures

References in corpus (6)

• Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
• Adaptive Bound Optimization for Online Convex Optimization
• Online Learning: A Modern Introduction Using Convex Optimization
• Online Convex Optimization with Time-Varying Constraints
• Minimax Regret of Switching-Constrained Online Convex Optimization: No Phase Transition
• Multinomial Logit Bandit with Low Switching Cost