Safety in the Face of Adversity: Achieving Zero Constraint Violation in Online Learning with Slowly Changing Constraints
This addresses safety-critical applications in online learning by ensuring strict constraint adherence, representing a foundational advance over prior incremental approaches that allowed violations.
The paper tackles the problem of maintaining zero constraint violations in Online Convex Optimization with dynamic constraints, achieving this through a primal-dual method and dichotomous learning rate, resulting in provable safety and sublinear regret.
We present the first theoretical guarantees for zero constraint violation in Online Convex Optimization (OCO) across all rounds, addressing dynamic constraint changes. Unlike existing approaches in constrained OCO, which allow for occasional safety breaches, we provide the first approach for maintaining strict safety under the assumption of gradually evolving constraints, namely the constraints change at most by a small amount between consecutive rounds. This is achieved through a primal-dual approach and Online Gradient Ascent in the dual space. We show that employing a dichotomous learning rate enables ensuring both safety, via zero constraint violation, and sublinear regret. Our framework marks a departure from previous work by providing the first provable guarantees for maintaining absolute safety in the face of changing constraints in OCO.