# Constrained Online Convex Optimization without Slater's Condition

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 42 references that are in the map.
- First posted on arXiv 30 Jun 2026.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [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)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [Online Primal-Dual Mirror Descent under Stochastic Constraints](https://mlsanity.com/paper/1908.00305/) (2019)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2412.08060/) (2024)
- [Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2501.16919/) (2025)
- [Projection-Free Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/2402.08799/) (2024)
- [Revisiting Projection-Free Online Learning with Time-Varying Constraints](https://mlsanity.com/paper/2501.16046/) (2025)
- [A Geometric Approach to Constrained Online Learning](https://mlsanity.com/paper/2605.21107/) (2026)
- [Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization](https://mlsanity.com/paper/2510.01867/) (2025)
- [Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint](https://mlsanity.com/paper/2412.10703/) (2024)
- [Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2510.22579/) (2025)
- [Distributed Online Convex Optimization with Nonseparable Costs and Constraints](https://mlsanity.com/paper/2602.10452/) (2026)

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

- [Constrained Online Learning with Noisy Constraint Values](https://mlsanity.com/paper/2609.06921/) (2026)
- [Rate-Optimal Algorithm for Adversarial Linear CMDPs](https://mlsanity.com/paper/2610.00927/) (2026)

## Abstract (arXiv)

We study constrained online convex optimization with adversarial losses and stochastic or adversarial constraints. For stochastic constraints, existing algorithms that achieve nearly optimal regret and constraint violation bounds typically rely on regularity assumptions such as Slater's condition, while adversarial-constraint algorithms avoid these assumptions by using a rather restrictive round-wise feasible comparator. We bridge this gap with an anytime primal-dual framework that incorporates an adaptive regularizer into the dual update. The regularizer stabilizes the dual process without relying on the negative drift induced by Slater's condition. For stochastic constraints and convex losses, our algorithm achieves O(√T) expected regret and O(√Tlog T) expected cumulative constraint violation. Furthermore, we show that our algorithm also admits high-probability bounds of the same order on regret and constraint violation. For strongly convex losses, the regret bound improves to O(log T) with a violation bound of the same order. With a minor modification, the framework also applies to adversarial constraints and provides guarantees for hard constraint violation.