Timezone: »

 
Poster
Online Convex Optimization with Continuous Switching Constraint
Guanghui Wang · Yuanyu Wan · Tianbao Yang · Lijun Zhang

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @
in Poster Session 1 »
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)$.
Keywords: Optimization

Author Information

Guanghui Wang (Georgia Tech)
Yuanyu Wan (Nanjing University)
Tianbao Yang (The University of Iowa)
Lijun Zhang (Nanjing University (NJU))

More from the Same Authors