Universal Dynamic Regret and Constraint Violation Bounds for Constrained Online Convex Optimization
This work addresses a generalization of online convex optimization for applications requiring robust constraint handling under adversarial conditions, representing an incremental advancement.
The paper tackles constrained online convex optimization with adversarial constraints by proposing two modular algorithms that achieve universal dynamic regret and cumulative constraint violation bounds, improving state-of-the-art results in scenarios without common feasible points.
We consider a generalization of the celebrated Online Convex Optimization (OCO) framework with online adversarial constraints. We present two algorithms having simple modular structures that yield universal dynamic regret and cumulative constraint violation bounds, improving upon the state-of-the-art results. Our results hold in the most general case when both the cost and constraint functions are chosen arbitrarily by an adversary, and the constraint functions need not contain any common feasible point. The results are established by reducing the constrained learning problem to an instance of the standard OCO problem with specially constructed surrogate cost functions.