Adaptive Algorithms for Online Convex Optimization with Long-term
  Constraints
  We present an adaptive online gradient descent algorithm to solve online
convex optimization problems with long-term constraints , which are constraints
that need to be satisfied when accumulated over a finite number of rounds T ,
but can be violated in intermediate rounds. For some user-defined trade-off
parameter $\beta$ $\in$ (0, 1), the proposed algorithm achieves cumulative
regret bounds of O(T^max{$\beta$,1--$\beta$}) and O(T^(1--$\beta$/2)) for the
loss and the constraint violations respectively. Our results hold for convex
losses and can handle arbitrary convex constraints without requiring knowledge
of the number of rounds in advance. Our contributions improve over the best
known cumulative regret bounds by Mahdavi, et al. (2012) that are respectively
O(T^1/2) and O(T^3/4) for general convex domains, and respectively O(T^2/3) and
O(T^2/3) when further restricting to polyhedral domains. We supplement the
analysis with experiments validating the performance of our algorithm in
practice.
