Research map / Bandits and online learning / Online convex optimization and games
Optimal Algorithms 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 a single-gradient-step first-order COCO policy that runs adaptive OGD (AdaGrad) on Lyapunov-based surrogate costs, achieving O(sqrt(T)) regret with O(sqrt(T) log T) cumulative constraint violation, and O(log T) regret for strongly convex costs.
Problem
Constrained online convex optimization (COCO) with time-varying convex constraints revealed after action selection: simultaneously achieving sublinear regret and cumulative constraint violation (CCV) without Slater's condition or other restrictive assumptions.
Approach
Combine adaptive OCO policies (AdaGrad OGD) as a black box with Lyapunov/drift-plus-penalty: the surrogate cost V*f_t + Phi'(Q_t)*g_t, where Q_t is the queue of constraint violations and Phi is an exponential (convex) Lyapunov function, yielding a single inequality that bounds both regret and CCV.
Key results
- Achieves O(sqrt(T)) regret and O(sqrt(T) log T) CCV for convex costs and convex constraints, without Slater's condition, breaking the prior O(T^{3/4}) CCV barrier.
- For alpha-strongly convex costs, regret improves to O(log T) with CCV kept at O(sqrt(T log T)); if worst-case regret is non-negative, CCV improves to O(log T / alpha).
- Lower bound of Omega(sqrt(T)) shown simultaneously for regret and CCV in high dimension (d >= T).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an exponential Lyapunov potential for convex costs | Online Policy for COCO · COCO, convex costs | CCV: O(T^{3/4}) -> 4GD\ln(2\big(1+2T)\big)\sqrt{T} | Helped |
| Use strongly convex costs and a quadratic Lyapunov potential | Online Policy for COCO · COCO, strongly convex costs | regret: O(\sqrt{T}) -> \frac{G^2}{\alpha}\big(1+\ln(t)\big) | Helped |
| Assume non-negative worst-case regret | Online Policy for COCO · COCO, strongly convex costs | CCV: O\big(\sqrt{\frac{t \log T}{\alpha}}\big) -> O(\frac{\log T}{\alpha}) | Helped |
| Relax feasibility to S-feasibility | Online Policy for OCS · OCS, S-feasible | CCV: O(\max(\sqrt{ST},S)) | Helped |
| Allow a P_T-constrained adversary without a feasibility assumption | Online Policy for OCS · OCS, P_T-constrained adversary | CCV: O(P_T^{\nicefrac{1}{3}}T^{\nicefrac{2}{3}})+O(\sqrt{T}) | Helped |
Surprising findings
- When worst-case regret is non-negative at a round, CCV can be improved to logarithmic order even for non-strongly convex constraints.
Limitations
- Assumes horizon T known (doubling trick otherwise)
- Requires convex, Lipschitz cost and constraint functions with bounded diameter
Experimental setup
Datasets: online credit card fraud detection dataset (highly imbalanced)
Benchmarks: online credit card fraud detection
Metrics: regret cumulative constraint violation
Baselines: Yu and Neely 2017 (time-varying constraints, Slater-free) Sun et al. 2017 DPP-based policy Chen et al. 2017 / Yuan and Lamperski Lagrangian primal-dual methods
Builds on: AdaGrad drift-plus-penalty framework online gradient descent
Closest papers by meaning
- Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints (NeurIPS 2025 · similarity 0.95)
- Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints (ICML 2026 · similarity 0.94)
- $O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization (NeurIPS 2025 · similarity 0.93)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.92)
- Projection-Free Online Convex Optimization with Time-Varying Constraints (ICML 2024 · similarity 0.91)
- Capacity-Constrained Online Convex Optimization with Delayed Feedback (NeurIPS 2026 · similarity 0.90)
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.