Research map / Bandits and online learning / Online convex optimization and games
Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint
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 COLDQ, an online convex optimization algorithm with a doubly-bounded virtual queue that gets dynamic regret O(T^((1+V_x)/2)) and hard constraint violation O(T^{V_g}) without Slater condition, with simulation-only validation.
Problem
Online convex optimization with time-varying constraints, where the goal is dynamic regret and hard (non-compensated) constraint violation bounds that adapt to the dynamics of losses and constraints, without requiring the Slater condition.
Approach
A virtual queue clipped from both below (minimum gamma) and above (via a leak term eta), giving a lower and upper bound; a new Lyapunov drift that uses both bounds yields bounds that smoothly approach O(T^{1/2}) regret and O(1) violation as the loss/constraint dynamics vanish.
Key results
- COLDQ achieves over 40% lower hard constraint violation than RECOO on time-varying constraint experiments without sacrificing accumulated loss.
- Theoretical bounds: O(T^((1+V_x)/2)) dynamic regret and O(T^{V_g}) hard constraint violation for convex losses; O(log T) static regret for strongly convex losses.
- For fixed constraints, COLDQ achieves O(1) hard constraint violation, improving on prior O(log T) bounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a doubly-bounded virtual queue | COLDQ · Time-varying constraints, convex loss | hard constraint violation: \mathcal{O}(T^\frac{1}{2}\log T) -> \mathcal{O}(T^{V_g}) | Helped |
| Use a doubly-bounded virtual queue | COLDQ · Time-varying constraints, convex loss | dynamic regret: \mathcal{O}(T^\frac{1}{2}+V_x) -> \mathcal{O}(T^\frac{1+V_x}{2}) | Helped |
| Use COLDQ | Constrained OCO with time-varying constraints and strongly convex loss · Time-varying constraints | dynamic regret: \mathcal{O}(T^{\frac{1}{2}+V_x}) -> \mathcal{O}(T^{\frac{1+V_x}{2}}) | Helped |
| Use COLDQ | Constrained OCO with time-varying constraints and strongly convex loss · Time-varying constraints | hard constraint violation: \mathcal{O}(T^\frac{1}{2}(\log{T})^\frac{1}{2}) -> \mathcal{O}(T^{V_g}) | Helped |
| Use COLDQ | Constrained OCO with fixed constraints · Fixed constraints, convex and strongly convex losses | hard constraint violation: \mathcal{O}(\log{T}) -> \mathcal{O}(1) | Helped |
| Use COLDQ instead of RECOO | Time-varying constrained OCO · Time-varying constraints experiment | hard constraint violation: over 40% lower | Helped |
| Use expert tracking to set the algorithm parameters without prior knowledge of system dynamics | COLDQ · Constrained OCO with time-varying constraints | dynamic regret | No clear effect |
Limitations
- Experiments are limited to simulations on synthetic and job-scheduling settings with few baselines.
- Dynamic regret bound depends on path-length variation V_x and constraint variation V_g; bounds degrade when dynamics are large.
- Expert-tracking variant relies on running multiple instances in parallel.
Experimental setup
Datasets: synthetic quadratic programming instances synthetic linear programming instances real-world datasets for online job scheduling
Benchmarks: synthetic time-varying constrained quadratic programming synthetic fixed-constraint online quadratic and linear programming online job scheduling energy cost
Metrics: accumulated loss hard constraint violation time-averaged energy cost number of delayed jobs
Baselines: RECOO Algorithm 1 (time-varying constrained OCO saddle-point method)
Builds on: online gradient descent virtual queue Lyapunov optimization multiplicative weights expert tracking
Closest papers by meaning
- Constrained Online Convex Optimization with Memory and Predictions (AAAI 2026 · similarity 0.91)
- Revisiting Projection-Free Online Learning with Time-Varying Constraints (AAAI 2025 · similarity 0.91)
- Optimal Algorithms for Online Convex Optimization with Adversarial Constraints (NeurIPS 2024 · similarity 0.89)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.88)
- $O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization (NeurIPS 2025 · similarity 0.88)
- Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints (NeurIPS 2025 · similarity 0.88)
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.