Breaking the O ⁡ ( T ) O(\sqrt{T}) Cumulative Constraint Violation Barrier while Achieving O ⁡ ( T ) O(\sqrt{T}) Static Regret in Constrained Online Convex Optimization

Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze · 2026

Read Breaking the O ⁡ ( T ) O(\sqrt{T}) Cumulative Constraint Violation Barrier while Achieving O ⁡ ( T ) O(\sqrt{T}) Static Regret in Constrained Online Convex Optimization by Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-20671.txt.

Description

Balasundaram and co-authors revisit constrained online convex optimization. Each round, a learner picks an act before seeing that round's loss and constraint. The goals are low regret and low total constraint violation. Many believed square root growth in violation was forced at square root regret. They refute this for two dimensions. An earlier algorithm, they show, keeps regret at square root order. Its violation grows only as the cube root of the round count.

Catalog record

CREATORHaricharan Balasundaram, Karthick Krishna Mahendran, Rahul Vaze
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30997
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.20671

Browse the full library · About the Tower of Babel