Projection-Free Online Convex Optimization with Time-Varying Constraints

We consider the setting of online convex optimization with adversarial time-varying constraints in which actions must be feasible w. r. t. a fixed constraint set, and are also required on average to approximately satisfy additional time-varying constraints. Motivated by scenarios in which the fixed feasible set (hard constraint) is difficult to project on, we consider projection-free algorithms that access this set only through a linear optimization oracle (LOO). We present an algorithm that, on a sequence of length T and using overall T calls to the LOO, guarantees O (T^3/4) regret w. r. t. the losses and O (T^7/8) constraints violation (ignoring all quantities except for T). In particular, these bounds hold w. r. t. any interval of the sequence. We also present a more efficient algorithm that requires only first-order oracle access to the soft constraints and achieves similar bounds w. r. t. the entire sequence. We extend the latter to the setting of bandit feedback and obtain similar bounds (as a function of T) in expectation.