Adaptive Algorithms for Online Convex Optimization with Long-term Constraints
This provides improved theoretical guarantees for online optimization problems with cumulative constraints, which is incremental but practically relevant for applications like resource allocation.
The paper tackles online convex optimization with long-term constraints by proposing an adaptive gradient descent algorithm that achieves cumulative regret bounds of O(T^max{β,1-β}) for loss and O(T^(1-β/2)) for constraint violations, improving over previous best bounds of O(T^1/2) and O(T^3/4) for general convex domains.
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 $β$ $\in$ (0, 1), the proposed algorithm achieves cumulative regret bounds of O(T^max{$β$,1--$β$}) and O(T^(1--$β$/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.