On the Power of Optimism in Constrained Online Convex Optimization

Haobo Zhang, Hengquan Guo, Xin LiuIJCAI 2025 · DOI

In online decision-making—spanning fields from portfolio management to network routing—agents must maximize an objective while adhering to strict resource or budget constraints. This framework, known as Constrained Online Convex Optimization (COCO), presents a fundamental challenge: how to adapt to environmental changes without prior knowledge of the future.

A recent study by researchers at ShanghaiTech University introduces Optimistic-COCO, a breakthrough algorithm that achieves both problem-dependent regret and constant constraint violation in an environment-agnostic manner.

The Challenge of Adaptivity in COCO

Standard Online Convex Optimization (OCO) algorithms typically aim for $O(\sqrt{T})$ regret, where $T$ is the time horizon. In constrained settings, the goal is to minimize this regret while ensuring that cumulative constraint violations grow sublinearly. However, real-world environments are often "benign," where loss functions change slowly. Ideally, an algorithm should achieve better performance—proportional to the gradient variation ($V_T$)—when the environment is stable.

Previous "adaptive" algorithms were often non-causal, requiring the total variation or the time horizon to be known in advance to tune parameters like the learning rate. The open question remained: Can we design a causal, environment-agnostic algorithm that achieves $O(\sqrt{V_T})$ regret and $O(1)$ constraint violation?

The Optimistic-COCO Framework

Optimistic-COCO addresses this by integrating two distinct optimization paradigms:

  1. Optimistic Gradient Descent: Unlike standard reactive methods, this approach uses a "two-step" update. It incorporates a prediction of the next gradient (often the previous one), allowing the learner to anticipate the environment's trajectory. If the environment is static ($\nabla f_t = \nabla f_{t-1}$), the regret term effectively vanishes.
  2. Lyapunov Optimization (Drift-plus-Penalty): To manage long-term constraints, the algorithm employs "virtual queues" that track cumulative violations. By minimizing a combination of the "drift" (change in queue size) and the "penalty" (the loss function), the algorithm balances objective performance with feasibility.

Causal Adaptivity and Decoupling

The core innovation lies in how the algorithm updates its parameters. The learning rate ($\eta_t$) and the trade-off parameter ($\phi_t$) are updated dynamically based on the observed cumulative gradient variation ($V_t$). Crucially, the authors decouple the trade-off parameter from the queue update mechanism. This allows for a constant $O(1)$ violation bound while maintaining the flexibility needed for adaptive regret.

Empirical Performance

The researchers validated Optimistic-COCO against state-of-the-art baselines across various synthetic scenarios simulating different environmental dynamics.

Performance comparison of Optimistic-COCO against baselines in terms of cumulative loss and violation across different environmental dynamics.

As shown in the experimental results, Optimistic-COCO (blue line) demonstrates superior performance:

  • In Slowly Changing Environments: It significantly outperforms baselines in cumulative loss by leveraging the low gradient variation.
  • In Highly Dynamic Environments: It remains competitive with non-adaptive algorithms that have the advantage of knowing the time horizon.
  • Constraint Stability: Across all scenarios, the cumulative violation remains low and stable, confirming the theoretical $O(1)$ bound.

Key Theoretical Results

  • Anytime Regret: The algorithm achieves $O(\sqrt{V_t})$ regret at any time $t$, adapting automatically to the environment's smoothness.
  • Constant Violation: It guarantees $O(1)$ constraint violation, ensuring long-term feasibility without the violation growing over time.
  • Environment-Agnostic: No prior knowledge of $T$ or $V_T$ is required, making it truly practical for real-world deployment.

Conclusion and Future Directions

Optimistic-COCO resolves a significant open problem by proving that adaptivity and constant constraint violation are not mutually exclusive. While the current work assumes convexity and relies on Slater's condition for the violation bound, it sets a new standard for adaptive constrained learning. Future research may extend these "optimistic" principles to non-convex settings or scenarios with limited "bandit" feedback.

Reference: Zhang, H., Guo, H., & Liu, X. (2025). On the Power of Optimism in Constrained Online Convex Optimization. Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25).

Summary updated

BibTeX
@inproceedings{zhang2025power,
  author = {Haobo Zhang and Hengquan Guo and Xin Liu},
  title = {{On the Power of Optimism in Constrained Online Convex Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/776},
}
Figure