On the Power of Optimism in Constrained Online Convex Optimization
On the Power of Optimism in Constrained Online Convex Optimization
Haobo Zhang, Hengquan Guo, Xin Liu
Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence
Main Track. Pages 6976-6983.
https://doi.org/10.24963/ijcai.2025/776
This paper studies the constrained online convex optimization problem (COCO) where the learner makes sequential decisions within a constrained set. We present Optimistic-COCO, an adaptive gradient-based algorithm that incorporates optimistic design with the Lyapunov optimization technique. The proposed algorithm achieves strong theoretical guarantees: 1) Optimistic-COCO provides a tight gradient-variation regret bound and constant constraint violation; 2) Optimistic-COCO is environment-agnostic, utilizing adaptive learning rates that rely solely on causal information. These results resolve an open question posed in prior work regarding whether an adaptive algorithm can achieve problem-dependent regret and constant constraint violation in COCO. We establish these robust guarantees through carefully designed adaptive parameters and a refined multi-step Lyapunov drift analysis. Experimental results further validate our theoretical findings, demonstrating the practical efficacy of the proposed algorithm.
Keywords:
Machine Learning: ML: Online learning
Constraint Satisfaction and Optimization: CSO: Constraint optimization problems
Machine Learning: ML: Learning theory
