Constrained Online Convex Optimization without Slater’s Condition

Constrained Online Convex Optimization (COCO) involves making sequential decisions to minimize cumulative loss while satisfying functional constraints. Traditional algorithms for stochastic constraints often rely on Slater's condition—the assumption that a strictly feasible point exists—which can lead to performance degradation as the feasibility margin approaches zero. This paper addresses whether these regularity assumptions can be removed while maintaining optimal regret and constraint violation bounds.

The authors propose a unified primal-dual framework that functions in an anytime manner, meaning it does not require prior knowledge of the time horizon. The core innovation is the inclusion of an adaptive regularizer in the dual update. This regularizer stabilizes the dual variables by offsetting the growth of the Lyapunov function, effectively replacing the negative drift typically provided by Slater's condition. The framework is flexible, applying to both stochastic and adversarial constraint settings, as well as convex and strongly convex loss functions.

• For stochastic constraints and convex losses, the algorithm achieves O(sqrt(T)) expected regret and O(sqrt(T) log T) expected cumulative constraint violation.
• Under strongly convex losses, the regret bound improves to O(log T) while maintaining the same violation bounds.
• The framework provides high-probability guarantees for stochastic constraints and extends to adversarial constraints, where it achieves similar bounds for hard constraint violations.
• The algorithm is anytime, meaning it does not require the doubling trick or prior knowledge of the total number of rounds.

This work bridges a significant gap in online learning theory by demonstrating that regularity assumptions like Slater's condition are not strictly necessary for achieving optimal performance in constrained settings. By providing a unified approach that handles both stochastic and adversarial constraints, the paper simplifies the algorithmic landscape for COCO and offers a more robust solution for real-world applications like budget-constrained advertising and risk-constrained portfolio optimization.