TL;DR: This paper tackles Online Convex Optimization (OCO) with hard constraints, where constraint violations at any step strictly accumulate and cannot be offset by future conservative actions. The authors introduce RECOO, an algorithm using rectified penalties to achieve state-of-the-art regret and violation bounds for both fixed and adversarial constraint settings. Notably, it achieves $O(1)$ constraint violation for fixed constraints, answering a prior open conjecture in the field.
The Challenge of Hard Constraints in OCO
Online Convex Optimization (OCO) is a foundational framework for real-time decision-making in uncertain environments, such as online ad bidding or data center resource allocation. In the real world, these decisions are subject to constraints like budgets or server capacities.
Most prior work focuses on soft constraints, where a violation today is acceptable as long as you compensate for it tomorrow. In soft constraints, performance is measured by the simple sum of constraint values, meaning negative values cancel out positive ones.
However, safety-critical applications require hard constraints. If a self-driving car exceeds a safety boundary, or a data center drops a critical job, you cannot "un-violate" that constraint later. This paper addresses COCO-Hard (Constrained OCO with Hard Constraints), where every violation is strictly penalized. The challenge is to minimize both the cumulative loss (regret) and the cumulative hard constraint violations, especially when the constraints are either unknown but fixed, or completely adversarial (changing unpredictably over time).
The RECOO Algorithm: The Power of Pessimism
The authors propose RECOO (RECtified Online Optimization), a unifying algorithm that handles both fixed and adversarial constraints without needing to know the operating setting beforehand.
RECOO is inspired by primal-dual optimization methods, which use a "dual variable" as a penalty price for violating constraints. However, standard primal-dual methods fail for hard constraints: if the penalty price drops to zero, the algorithm can make overly aggressive decisions that lead to massive violations. To fix this, RECOO introduces rectifiers in two places:
- Rectified Decision: It rectifies the constraint function itself during the decision-making step so the algorithm doesn't become overly optimistic when past constraints were easily satisfied.
- Rectified Penalty Update: It imposes a round-dependent minimum penalty price. Even if the algorithm has been perfectly safe recently, the penalty price never drops to zero.
This dual-rectification forces the algorithm to remain pessimistic and conservative, creating a "self-bounding property" that is key to strictly bounding hard constraint violations.
Theoretical Guarantees: The Best of Two Worlds
RECOO achieves "the best of two worlds and beyond" by matching or beating state-of-the-art (SOTA) theoretical bounds across multiple settings.
Fixed Constraints
Prior work hypothesized that achieving an $O(1)$ (constant) hard constraint violation bound for fixed constraints might only be possible under a strict feasibility assumption called "Slater's condition." This paper proves that $O(1)$ violation is achievable even without Slater's condition.
As shown in the table above, for convex loss functions, RECOO achieves $O(\sqrt{T})$ regret and $O(1)$ violation, a massive improvement over the previous best $O(T^{1/4})$ violation. For strongly convex losses, regret drops to $O(\log T)$ while maintaining the $O(1)$ violation.
Adversarial Constraints
Real-world optimal targets often move over time. RECOO is the first algorithm to establish dynamic regret and violation bounds when both the target baseline is moving and the constraints are adversarial.
For adversarial constraints with convex losses, RECOO achieves $O(\sqrt{T})$ regret and $O(T^{3/4})$ violation, matching the SOTA. If the loss function is strongly convex, it achieves $O(\log T)$ regret and $O(\sqrt{T \log T})$ violation—order-wise better than existing bounds.
Empirical Performance
The authors evaluated RECOO using both synthetic data and a real-world online job scheduling task for distributed data centers. Using real electricity price traces from the New York ISO (NYISO) and calibrated job arrivals from a recent systems benchmark, RECOO significantly outperformed the SOTA baseline. It reduced the cumulative constraint violation (number of delayed jobs) from ~1684 down to ~713, while simultaneously achieving slightly lower average energy costs.
Limitations and Future Directions
Practically, RECOO requires solving an "almost" unconstrained optimization problem at each time step. This assumes the base feasible set is simple enough that gradient-based methods can find the minimizer efficiently.
For future work, the paper highlights an ongoing open question in the field: whether it is mathematically possible to reduce the $O(T^{3/4})$ violation bound for adversarial constraints while keeping $O(\sqrt{T})$ regret, without relying on Slater's condition.
Summary updated