# Optimal Bounds for Adversarial Constrained Online Convex Optimization

Source: [Optimal Bounds for Adversarial Constrained Online Convex Optimization](<https://www.sota2.com/research/paper/68fa5d851e209131ce9daf26>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T18:18:08.889Z

Authors: Ricardo N. Ferreira, Cl\\'audia Soares

Published: 2025-03-17T16:51:16.000Z

## Abstract

Constrained Online Convex Optimization (COCO) can be seen as a generalization of the standard Online Convex Optimization (OCO) framework. At each round, a cost function and constraint function are revealed after a learner chooses an action. The goal is to minimize both the regret and cumulative constraint violation (CCV) against an adaptive adversary. We show for the first time that is possible to obtain the optimal $O(\\sqrt{T})$ bound on both regret and CCV, improving the best known bounds of $O \\left( \\sqrt{T} \\right)$ and $\\tilde{O} \\left( \\sqrt{T} \\right)$ for the regret and CCV, respectively. Based on a new surrogate loss function enforcing a minimum penalty on the constraint function, we demonstrate that both the Follow-the-Regularized-Leader and the Online Gradient Descent achieve the optimal bounds.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2503.13366>)

[PDF](<https://arxiv.org/pdf/2503.13366.pdf>)