Projection-Free Online Convex Optimization with Stochastic Constraints
It addresses optimization problems with constraints in online settings, offering efficient methods for applications like resource allocation, but is incremental as it builds on existing projection-free frameworks.
The paper tackles online convex optimization with stochastic constraints by developing projection-free algorithms, achieving sublinear regret and constraint violation bounds, including O(sqrt(T)) regret and O(T^{3/4}) constraint violations for smooth functions.
This paper develops projection-free algorithms for online convex optimization with stochastic constraints. We design an online primal-dual projection-free framework that can take any projection-free algorithms developed for online convex optimization with no long-term constraint. With this general template, we deduce sublinear regret and constraint violation bounds for various settings. Moreover, for the case where the loss and constraint functions are smooth, we develop a primal-dual conditional gradient method that achieves $O(\sqrt{T})$ regret and $O(T^{3/4})$ constraint violations. Furthermore, for the setting where the loss and constraint functions are stochastic and strong duality holds for the associated offline stochastic optimization problem, we prove that the constraint violation can be reduced to have the same asymptotic growth as the regret.