# Beyond tildeO(√T) Constraint Violation for Online Convex Optimization with Adversarial Constraints

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2025.

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

- [Convex Optimization with Nested Evolving Feasible Sets](https://mlsanity.com/paper/2605.07386/) (2026)
- [Multi-Objective textitmin-max Online Convex Optimization](https://mlsanity.com/paper/2510.13560/) (2025)
- [Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions](https://mlsanity.com/paper/2609.11207/) (2026)

## Abstract (arXiv)

We study Online Convex Optimization with adversarial constraints (COCO). At each round a learner selects an action from a convex decision set and then an adversary reveals a convex cost and a convex constraint function. The goal of the learner is to select a sequence of actions to minimize both regret and the cumulative constraint violation (CCV) over a horizon of length T. The best-known policy for this problem achieves O(√T) regret and tildeO(√T) CCV. In this paper, we improve this by trading off regret to achieve substantially smaller CCV. This trade-off is especially important in safety-critical applications, where satisfying the safety constraints is non-negotiable. Specifically, for any bounded convex cost and constraint functions, we propose an online policy that achieves tildeO(√dT+ Tβ) regret and tildeO(dT1-β) CCV, where d is the dimension of the decision set and β ∈ [0,1] is a tunable parameter. We begin with a special case, called the textsfConstrained Expert problem, where the decision set is a probability simplex and the cost and constraint functions are linear. Leveraging a new adaptive small-loss regret bound, we propose a computationally efficient policy for the textsfConstrained Expert problem, that attains O(√Tln N+Tβ) regret and tildeO(T1-β ln N) CCV for N number of experts. The original problem is then reduced to the textsfConstrained Expert problem via a covering argument. Finally, with an additional M-smoothness assumption, we propose a computationally efficient first-order policy attaining O(√MT+Tβ) regret and tildeO(MT1-β) CCV.