Projection-Free Online Convex Optimization with Time-Varying Constraints
This work addresses scenarios in machine learning and optimization where projecting onto constraint sets is computationally expensive, offering efficient algorithms for practitioners dealing with complex constraints.
The paper tackles online convex optimization with adversarial time-varying constraints, where actions must satisfy a fixed constraint set and approximate additional time-varying constraints on average, using projection-free algorithms that rely on a linear optimization oracle. The result includes algorithms achieving $ ilde{O}(T^{3/4})$ regret and $O(T^{7/8})$ constraint violation bounds over sequences of length $T$, with extensions to bandit feedback.
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.