# Projection-Free Online Convex Optimization with Stochastic Constraints

arXiv: https://arxiv.org/abs/2305.01333 · HTML: https://mlsanity.com/paper/2305.01333/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 28 references that are in the map.
- First posted on arXiv 2 May 2023.

## Builds on (most cited first, 15 of 15)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Convex Optimization with Stochastic Constraints](https://mlsanity.com/paper/1708.03741/) (2017)
- [Adaptive Algorithms for Online Convex Optimization with Long-term Constraints](https://mlsanity.com/paper/1512.07422/) (2015)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Faster Projection-free Online Learning](https://mlsanity.com/paper/2001.11568/) (2020)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Online Continuous Submodular Maximization](https://mlsanity.com/paper/1802.06052/) (2018)
- [Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity](https://mlsanity.com/paper/1802.08183/) (2018)
- [Online Primal-Dual Mirror Descent under Stochastic Constraints](https://mlsanity.com/paper/1908.00305/) (2019)
- [Efficient Projection-Free Online Methods with Stochastic Recursive Gradient](https://mlsanity.com/paper/1910.09396/) (2019)
- [Online Convex Optimization with Perturbed Constraints](https://mlsanity.com/paper/1906.00049/) (2019)
- [Conservative Stochastic Optimization with Expectation Constraints](https://mlsanity.com/paper/2008.05758/) (2020)
- [Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints](https://mlsanity.com/paper/1907.00316/) (2019)

## Built on by (most cited first, 2 of 2)

- [Revisiting Projection-Free Online Learning with Time-Varying Constraints](https://mlsanity.com/paper/2501.16046/) (2025)
- [Nonsmooth Projection-Free Optimization with Functional Constraints](https://mlsanity.com/paper/2311.11180/) (2023)

## Abstract (arXiv)

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(√T) regret and O(T3/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.