Online convex optimization for cumulative constraints
This work addresses the problem of constraint handling in online optimization for researchers and practitioners, offering a novel constraint form that is incremental over prior long-term constraint methods.
The paper tackles online convex optimization with cumulative constraints by proposing algorithms that achieve cumulative squared constraint violations of O(T^{1-β}), penalizing large violations and preventing cancellation effects, while generalizing or improving regret bounds for convex and strongly convex objectives.
We propose the algorithms for online convex optimization which lead to cumulative squared constraint violations of the form $\sum\limits_{t=1}^T\big([g(x_t)]_+\big)^2=O(T^{1-β})$, where $β\in(0,1)$. Previous literature has focused on long-term constraints of the form $\sum\limits_{t=1}^Tg(x_t)$. There, strictly feasible solutions can cancel out the effects of violated constraints. In contrast, the new form heavily penalizes large constraint violations and cancellation effects cannot occur. Furthermore, useful bounds on the single step constraint violation $[g(x_t)]_+$ are derived. For convex objectives, our regret bounds generalize existing bounds, and for strongly convex objectives we give improved regret bounds. In numerical experiments, we show that our algorithm closely follows the constraint boundary leading to low cumulative violation.