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
$\mathcal{O}(T^{\max\{c,1-c\}})$ bound for static regret and an
$\mathcal{O}(T^{(1-c)/2})$ bound for cumulative constraint violation, where
$c\in(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 $\mathcal{O}(\log(T))$ when the loss
functions are strongly convex, which also improves existing results. %In order
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
$\mathcal{O}(\sqrt{T(1+P_T)})$ regret and an $\mathcal{O}(\sqrt{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.
