A Tight Lower Bound for Online Convex Optimization with Switching Costs

We investigate online convex optimization with switching costs (OCO; Lin et al., INFOCOM 2011), a natural online problem arising when rightsizing data centers: A server initially located at p_0 on the real line is presented with an online sequence of non-negative convex functions f_1, f_2, ..., f_n: R -> R_+. In response to each function f_i, the server moves to a new position p_i on the real line, resulting in cost |p_i-p_{i-1}|+f_i(p_i). The total cost is the sum of costs of all steps. One is interested in designing competitive algorithms.

In this paper, we solve the problem in the classical sense: We give a lower bound of 2 on the competitive ratio of any possibly randomized online algorithm, matching the competitive ratio of previously known deterministic online algorithms (Andrew et al., COLT 2013/arXiv 2015; Bansal et al., APPROX 2015). It was previously conjectured that (2-eps)-competitive algorithms exist for some eps>0 (Bansal et al., APPROX 2015).

This is joint work with Antonios Antoniadis and was presented at WAOA 2017.