Proceedings

On the Power of Optimism in Constrained Online Convex Optimization

Haobo Zhang, Hengquan Guo, Xin Liu

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 6976-6983.

https://doi.org/10.24963/ijcai.2025/776

Keywords

  • Machine Learning: ML: Online learning
  • Constraint Satisfaction and Optimization: CSO: Constraint optimization problems
  • Machine Learning: ML: Learning theory

Abstract

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.

Haobo Zhang, Hengquan Guo, and Xin Liu. 2025. On the Power of Optimism in Constrained Online Convex Optimization. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 6976–6983. https://doi.org/10.24963/ijcai.2025/776
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards