Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints
This paper considers online convex optimization with long term constraints, where constraints can be violated in intermediate rounds, but need to be satisfied in the long run. The cumulative constraint violation is used as the metric to measure constraint violations, which excludes the situation that strictly feasible constraints can compensate the effects of violated constraints. A novel algorithm is first proposed and it achieves an šŖ(T^max{c,1-c}) bound for static regret and an šŖ(T^(1-c)/2) bound for cumulative constraint violation, where cā(0,1) is a user-defined trade-off parameter, and thus has improved performance compared with existing results. Both static regret and cumulative constraint violation bounds are reduced to šŖ(log(T)) when the loss functions are strongly convex, which also improves existing results. to bound the regret with respect to any comparator sequence, In order to achieve the optimal regret with respect to any comparator sequence, another algorithm is then proposed and it achieves the optimal šŖ(ā(T(1+P_T))) regret and an šŖ(ā(T)) cumulative constraint violation, where P_T is the path-length of the comparator sequence. Finally, numerical simulations are provided to illustrate the effectiveness of the theoretical results.
READ FULL TEXT