Summary of Doubly-bounded Queue For Constrained Online Learning: Keeping Pace with Dynamics Of Both Loss and Constraint, by Juncheng Wang et al.
Doubly-Bounded Queue for Constrained Online Learning: Keeping Pace with Dynamics of Both Loss and Constraint
by Juncheng Wang, Bingjie Yan, Yituo Liu
First submitted to arxiv on: 14 Dec 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: None
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary This paper presents a new algorithm for online convex optimization with time-varying constraints called Constrained Online Learning with Doubly-bounded Queue (COLDQ). The proposed method introduces a novel virtual queue that is both lower and upper bounded, allowing tight control of the constraint violation without requiring the Slater condition. The authors prove that COLDQ achieves an O(T^{(1+V_x)/2}) dynamic regret and O(T^{V_g}) hard constraint violation using a new Lyapunov drift analysis. These bounds approach the best-known O(T^{1/2}) regret and O(1) violation as the dynamics of the losses and constraints diminish. For strongly convex loss functions, COLDQ matches the best-known O() static regret while maintaining the O(T^{V_g}) hard constraint violation. The authors also introduce an expert-tracking variation of COLDQ that achieves the same performance bounds without prior knowledge of the system dynamics. Simulation results demonstrate that COLDQ outperforms state-of-the-art approaches. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary The paper proposes a new algorithm for online convex optimization with time-varying constraints called Constrained Online Learning with Doubly-bounded Queue (COLDQ). The algorithm is designed to work well in situations where the constraints change over time. The authors show that their algorithm can achieve good results, such as minimizing regret and constraint violations, while also being efficient. |
Keywords
» Artificial intelligence » Online learning » Optimization » Tracking
