Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint

Juncheng Wang, Bingjie Yan, Yituo LiuAAAI 2025 · DOI

Introduction

Online Convex Optimization (OCO) is a fundamental framework for sequential decision-making under uncertainty, with applications ranging from network routing to power grid management. Traditional OCO models often assume static or "soft" constraints. However, real-world environments frequently impose time-varying constraints where violations cannot be simply averaged out over time. This paper introduces COLDQ (Constrained Online Learning with Doubly-bounded Queue), the first algorithm to achieve performance bounds that dynamically adapt to environmental shifts, recovering optimal static performance as the system stabilizes.

The Challenge of Hard Constraints

In many sequential tasks, every violation at every time step matters. Previous algorithms struggled to balance minimizing "regret" (performance relative to an optimal benchmark) with minimizing these "hard" constraint violations. Specifically, older methods failed to "scale down"—even when constraints stopped changing, their violation bounds continued to grow with time (e.g., $O(T^{1/2})$).

The COLDQ Algorithm

The core innovation of COLDQ is the Doubly-Bounded Virtual Queue. While standard virtual queues track constraint violations to prevent them from becoming too large (upper bound), COLDQ enforces both a lower and an upper bound.

  • Primal-Dual Updates: The algorithm selects decisions by balancing the gradient of the previous loss with the current state of the virtual queue. The dual update incorporates a penalty term ($-\eta Q_{t-1}$) to prevent queue explosion, while a lower bound ($\gamma$) maintains sensitivity to small violations.
  • Lyapunov Stability: The authors utilize a novel Lyapunov drift analysis to track system stability. This mathematical framework leverages the double bounds to provide tighter performance guarantees than previously possible.

Key Results and Empirical Performance

COLDQ's performance is explicitly linked to the "path length" ($V_x$) of optimal solutions and the "variation" ($V_g$) of constraints. If the environment changes slowly, COLDQ performs better; if it stops changing ($V_g = 0$), the total violation becomes $O(1)$, meaning it does not grow with time.

Figure 6: Hard constraint violation comparison. COLDQ significantly outperforms RECOO and Yi et al. 2023, achieving much lower cumulative violations over time.

In empirical tests, COLDQ reduced constraint violations by over 40% compared to state-of-the-art methods like RECOO. This was achieved without increasing the accumulated loss, demonstrating a superior Pareto frontier for the regret-violation tradeoff.

Real-World Application: Job Scheduling

The algorithm was evaluated on an online job scheduling task using real-world data center datasets. The goal was to minimize energy costs while adhering to strict job delay constraints.

Figure 2: Average delayed jobs over time in a data center scheduling simulation. COLDQ quickly reduces delays to near-zero levels, outperforming the benchmark by Yi et al. 2023.

Conclusion

COLDQ represents a significant step forward in constrained online learning. By introducing the doubly-bounded virtual queue, it provides a robust mechanism for handling time-varying hard constraints without requiring restrictive assumptions like the Slater condition. While the algorithm currently requires some knowledge of environmental dynamics, its ability to "keep pace" with both loss and constraint dynamics makes it a powerful tool for modern, volatile systems.

Summary updated

BibTeX
@inproceedings{wang2025doubly,
  author = {Juncheng Wang and Bingjie Yan and Yituo Liu},
  title = {{Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i20.35411},
}
Figure