Online convex optimization for cumulative constraints
We propose the algorithms for online convex optimization which lead to cumulative squared constraint violations of the form
β ∈ (0, 1) . Previous literature has focused on long-term constraints of the form
g(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.
The paper studies the usual online convex optimization framework with the additional twist that the algorithm can predict a point outside of the decision set. The decision set is specified by a set of convex constraints g_i(x) <= 0, i=1,2,...,m.  The goal of the algorithm is to achieve small regret with respect to the best point the decision set and at the same time achieve small sum of constraint violations. A constraint violation is penalized with the square, (g_i(x))^2.  The motivation for this somewhat artificial looking problem is to avoid projections to the decision set in every round, which would be otherwise required.  The paper attacks the problem via Lagrangian relaxation. The resulting algorithm is primal-dual algorithm that operates both on primal variables as well the Lagrangian variables. The resulting algorithm is an algorithm similar to subgradient descent that at the same time adjusts the Lagrangian variables.  The paper proves that the algorithm has O(sqrt(T)) regret and O(sqrt(T)) sum of constraint violations in the case when both the cost functions and functions specifying the constraints are (convex) and Lipchitz.  In the case when the cost functions are strongly convex and constraints are Lipchitz, the proves O(log(T)) regret bound and a bound O(sqrt(log(T) * T)) on sum of constraint violations.  ---  Suggestions for improvement:  1) In the introduction (Lines 29-32) g(x_t) is used without first explaining that S is expressed as S = {x : g_i(x) <= 0, i=1,2,...,m}. This is confusing and the reader is left wondering where g comes from.  2) Use a different letters of the alphabet for the unit ball \mathbb{B} and the enlarged set \mathcal{B}; different fonts are not good enough distinction. I overlooked the definition of \mathcal{B} line 70 and was left wondering if it is a typo.  3) Line 102: max --> \max  4) Line 162: argmin --> \DeclareMathOperator{\argmin}{argmin} \argmin  5) Section 5.2. You have equality constraints in equation (11). Explain how did you transform them into inequality constraints.