Online Submodular Minimization with Switching Costs

We consider online submodular minimization with switching costs against an oblivious adversary. The learner chooses a subset in each round, incurs a loss given by a submodular function, and receives full-information or bandit feedback about the loss. In practical applications, repeatedly changing decisions is costly. To address this, we evaluate the learner's performance by regret with switching costs. We study shared-threshold variants of existing submodular subgradient methods. The full-information variant achieves the minimax-optimal expected regret, as shown by a matching lower bound. Furthermore, we establish high-probability regret bounds with switching costs by combining our modified methods with a switching-budget restarting wrapper. These high-probability bounds match the corresponding expected-regret bounds up to a logarithmic factor.