Search papers, labs, and topics across Lattice.
This paper addresses the challenge of constrained online convex optimization under adversarial losses and constraints, particularly when traditional algorithms rely on Slater's condition. The authors introduce an anytime primal-dual framework that incorporates an adaptive regularizer, allowing for optimal regret and constraint violation bounds without the need for restrictive assumptions. Their algorithm achieves $O(\sqrt{T})$ expected regret and $O(\sqrt{T}\log T)$ expected cumulative constraint violation for stochastic constraints, with improved bounds for strongly convex losses, thereby bridging a critical gap in the existing literature.
Achieving optimal regret and constraint violation without relying on Slater's condition could revolutionize how we approach online convex optimization.
We study constrained online convex optimization with adversarial losses and stochastic or adversarial constraints. For stochastic constraints, existing algorithms that achieve nearly optimal regret and constraint violation bounds typically rely on regularity assumptions such as Slater's condition, while adversarial-constraint algorithms avoid these assumptions by using a rather restrictive round-wise feasible comparator. We bridge this gap with an anytime primal-dual framework that incorporates an adaptive regularizer into the dual update. The regularizer stabilizes the dual process without relying on the negative drift induced by Slater's condition. For stochastic constraints and convex losses, our algorithm achieves $O(\sqrt{T})$ expected regret and $O(\sqrt{T}\log T)$ expected cumulative constraint violation. Furthermore, we show that our algorithm also admits high-probability bounds of the same order on regret and constraint violation. For strongly convex losses, the regret bound improves to $O(\log T)$ with a violation bound of the same order. With a minor modification, the framework also applies to adversarial constraints and provides guarantees for hard constraint violation.
