# $O(\\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization

Source: [$O(\\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization](<https://www.sota2.com/research/paper/68fa76e11e209131cea6f96a>)

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

Data updated: 2025-10-26T04:04:15.628Z

Authors: Rahul Vaze, Abhishek Sinha

Published: 2025-02-07T15:47:04.000Z

## Abstract

The constrained version of the standard online convex optimization (OCO) framework, called COCO is considered, where on every round, a convex cost function and a convex constraint function are revealed to the learner after it chooses the action for that round. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV). An algorithm is proposed that guarantees a static regret of $O(\\sqrt{T})$ and a CCV of $\\min\\{\\cV, O(\\sqrt{T}\\log T) \\}$, where $\\cV$ depends on the distance between the consecutively revealed constraint sets, the shape of constraint sets, dimension of action space and the diameter of the action space. For special cases of constraint sets, $\\cV=O(1)$. Compared to the state of the art results, static regret of $O(\\sqrt{T})$ and CCV of $O(\\sqrt{T}\\log T)$, that were universal, the new result on CCV is instance dependent, which is derived by exploiting the geometric properties of the constraint sets.

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

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