# Tight Bounds for Online Convex Optimization with Adversarial Constraints

Source: [Tight Bounds for Online Convex Optimization with Adversarial Constraints](<https://www.sota2.com/research/paper/68fa5bcf1e209131ce9cba59>)

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

Data updated: 2025-10-25T17:17:33.138Z

Authors: Abhishek Sinha, Rahul Vaze

Published: 2024-05-15T12:37:03.000Z

## Abstract

A well-studied generalization of the standard online convex optimization (OCO) is constrained online convex optimization (COCO). In COCO, on every round, a convex cost function and a convex constraint function are revealed to the learner after the action for that round is chosen. The objective is to design an online policy that simultaneously achieves a small regret while ensuring small cumulative constraint violation (CCV) against an adaptive adversary. A long-standing open question in COCO is whether an online policy can simultaneously achieve $O(\\sqrt{T})$ regret and $O(\\sqrt{T})$ CCV without any restrictive assumptions. For the first time, we answer this in the affirmative and show that an online policy can simultaneously achieve $O(\\sqrt{T})$ regret and $\\tilde{O}(\\sqrt{T})$ CCV. We establish this result by effectively combining the adaptive regret bound of the AdaGrad algorithm with Lyapunov optimization - a classic tool from control theory. Surprisingly, the analysis is short and elegant.

## 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/2405.09296>)

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