---
title: "On the Power of Optimism in Constrained Online Convex Optimization"
authors:
  - "Haobo Zhang"
  - "Hengquan Guo"
  - "Xin Liu"
doi: "10.24963/ijcai.2025/776"
url: "https://ijcai.org/proceedings/2025/776"
pdf: "https://ijcai.org/proceedings/2025/0776.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "6976-6983"
track: "Main Track"
keywords:
  - "Machine Learning: ML: Online learning"
  - "Constraint Satisfaction and Optimization: CSO: Constraint optimization problems"
  - "Machine Learning: ML: Learning theory"
---

# 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*, pages 6976-6983. DOI: [10.24963/ijcai.2025/776](https://doi.org/10.24963/ijcai.2025/776)

## 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.