上海科技大学知识管理系统

This paper considers online convex optimization with hard constraints and analyzes achievable regret and cumulative hard constraint violation (violation for short). The problem distinguishes itself from online convex optimization with soft constraints, where a violation at one round can be compensated/cancelled by a conservative decision at a different round. We propose a RECtified Online Optimization algorithm (RECOO) and consider two settings: fixed constraints and adversarial constraints. Both settings have been considered in the literature. Compared with existing results, RECOO achieves the best of two worlds and beyond. For the fixed-constraints setting, RECOO achieves (Equation presented) regret and O(1) violation, where T is the learning horizon. The best known results in this case are (Equation presented) regret and (Equation presented) violation. For the adversarial-constraints setting, it guarantees (Equation presented) regret and (Equation presented) violation, which match the best existing results. When the loss function is strongly convex, RECOO can guarantee O(log T) regret and O(1) violation for fixed constraints, and O(log T) regret and (Equation presented) violation for adversarial constraints. Both these results are order-wise better than the existing bounds. The regret and violation bounds mentioned above use the best fixed decision in hindsight as the baseline. This paper further considers a dynamic baseline where the comparator sequence is time-varying. This paper shows that RECOO not only improves the existing bounds for the fixed-constraints setting but also for the first time, establishes dynamic regret and violation bounds for the adversarial-constraints setting. Our experiment results confirm that RECOO outperforms several existing algorithms for both fixed and adversarial constraints. © 2022 Neural information processing systems foundation. All rights reserved.