Abstract

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 β ∈ (0, 1), the proposed algorithm achieves cumulative regret bounds of and respectively for the loss and the constraint violations. Our results hold for convex losses, can handle arbitrary convex constraints and rely on a single computationally efficient algorithm. Our contributions generalize over the best known cumulative regret bounds of Mahdavi et al. (2012a), which are respectively and for general convex domains, and respectively and when the domain is further restricted to be a polyhedral set. We supplement the analysis with experiments validating the performance of our algorithm in practice.