Projection-Free Online Convex Optimization with Time-Varying Constraints
Dan Garber Ben Kretzu
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
$\tilde{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.