Journal article
Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
Journal of machine learning research, Vol.13, pp.2503-2528
09/01/2012
Abstract
In this paper we propose efficient algorithms for solving constrained online convex optimization problems. Our motivation stems from the observation that most algorithms proposed for online convex optimization require a projection onto the convex set K from which the decisions are made. While the projection is straightforward for simple shapes (e.g., Euclidean ball), for arbitrary complex sets it is the main computational challenge and may be inefficient in practice. In this paper, we consider an alternative online convex optimization problem. Instead of requiring that decisions belong to K for all rounds, we only require that the constraints, which define the set K, be satisfied in the long run. By turning the problem into an online convex-concave optimization problem, we propose an efficient algorithm which achieves O(root T) regret bound and O(T-3/4) bound on the violation of constraints. Then, we modify the algorithm in order to guarantee that the constraints are satisfied in the long run. This gain is achieved at the price of getting O(T-3/4) regret bound. Our second algorithm is based on the mirror prox method (Nemirovski, 2005) to solve variational inequalities which achieves O(T-2/3) bound for both regret and the violation of constraints when the domain K can be described by a finite number of linear constraints. Finally, we extend the results to the setting where we only have partial access to the convex set K and propose a multipoint bandit feedback algorithm with the same bounds in expectation as our first algorithm.
Details
- Title: Subtitle
- Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
- Creators
- Mehrdad Mahdavi - Michigan State UniversityRong Jin - Michigan State UniversityTianbao Yang - Michigan State University
- Resource Type
- Journal article
- Publication Details
- Journal of machine learning research, Vol.13, pp.2503-2528
- Publisher
- Microtome Publ
- ISSN
- 1532-4435
- eISSN
- 1533-7928
- Number of pages
- 26
- Grant note
- N000141210431 / Office of Navy Research; Office of Naval Research IIS-0643494 / National Science Foundation; National Science Foundation (NSF)
- Language
- English
- Date published
- 09/01/2012
- Academic Unit
- Computer Science
- Record Identifier
- 9984259425402771
Metrics
45 Record Views