Research map / Bandits and online learning / Online convex optimization and games
Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes online policies for convex-constrained online learning (COCO) that trade regret for much smaller cumulative constraint violation, via a small-loss adaptive Hedge and a Lyapunov-based regret decomposition, with a covering reduction for general convex functions.
Problem
Online convex optimization with adversarial time-varying convex constraints: minimizing both regret and cumulative constraint violation (CCV), where prior best achieved O(sqrt T) regret and Õ(sqrt T) CCV.
Approach
Uses an exponential Lyapunov function on accumulated violation to turn constraint handling into a surrogate cost, then runs a scale-free adaptive small-loss Hedge (for the Constrained Expert problem) or OGD with adaptive step sizes (for smooth functions), tuning lambda with beta to trade regret T^beta against CCV T^(1-beta).
Key results
- For the Constrained Expert problem, the algorithm attains O(sqrt(T ln N)+T^beta) regret and Õ(T^(1-beta) ln N) CCV, improving on the O(sqrt T) CCV of prior work.
- For general convex Lipschitz costs/constraints via a delta-cover reduction, the policy achieves Õ(sqrt(dT)+T^beta) regret and Õ(dT^(1-beta)) CCV.
- With M-smoothness, a projection-based OGD policy achieves O(sqrt(MT)+T^beta) regret and Õ(MT^(1-beta)) CCV; with beta=1 and zero costs the CCV is O(M ln T).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the adaptive Hedge-based policy instead of the OGD-based policy | Constrained Expert · Synthetic dataset | CCV | Helped |
| Increase the tuning parameter β | Adaptive Hedge-based policy · Constrained Expert | regret | Mixed |
| Increase the tuning parameter β | Adaptive Hedge-based policy · Constrained Expert | CCV | Hurt |
Surprising findings
- With zero cost functions and smoothness, CCV can be made logarithmic in T (O(M ln T)), far below the sqrt(T) barrier.
Limitations
- Computational cost of the covering-based reduction grows as T^d, prohibitive for large d.
- Smoothness assumption is needed for the efficient first-order policy; the CCV bounds for general convex functions are only achieved via the expensive covering approach.
- Experiments are limited to a single synthetic instance.
Experimental setup
Datasets: synthetic Constrained Expert instance (N=20 experts, T=5000)
Benchmarks: synthetic Constrained Expert problem
Metrics: regret cumulative constraint violation (CCV)
Baselines: OGD-based COCO policy (Sinha & Vaish style) Online Constraint Satisfaction OGD policy
Builds on: Hedge Online Gradient Descent with adaptive step sizes Lyapunov regret decomposition for constrained OCO
Closest papers by meaning
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.95)
- Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints (ICML 2026 · similarity 0.92)
- $O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization (NeurIPS 2025 · similarity 0.92)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.91)
- Projection-Free Online Convex Optimization with Time-Varying Constraints (ICML 2024 · similarity 0.90)
- An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraints (ICML 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.