  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.
