Trading regret for efficiency: online convex optimization with long term constraints

By Mehrdad Mahdavi, Rong Jin, Tianbao Yang. Journal of machine learning research, 2011

313 citations recorded by the source corpus.

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 Κ 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 Κ for all rounds, we only require that the constraints, which define the set Κ, 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(√T) regret bound and O(T3/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(T3/4) regret bound. Our second algorithm is based on the mirror prox method (Nemirovski, 2005) to solve variational inequalities which achieves O(T2/3) bound for both regret and the violation of constraints when the domain Κ 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 Κ and propose a multipoint bandit feedback algorithm with the same bounds in expectation as our first algorithm.

Subfields: Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/fb7e68405e2ab12ed7e824864f261b1e895541c6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Online Convex Optimization with Stochastic Constraints (2017, methodology): “To avoid high complexity involved in the projection onto X as in Zinkevich’s algorithm, work in [10], [11], [12] develops low complexity algorithms that use projections onto a simpler set X 0 by allowing g k ( x ( t )) > 0 for certain rounds but ensuring lim sup T →∞ 1 T =1 g k ( x ( t )) ≤ 0 .”
Asynchronous Saddle Point Algorithm for Stochastic Optimization in Heterogeneous Networks (2019, methodology): “This technique is inspired by the approach in [43], [52].”
A Stochastic Primal-Dual Method for Optimization with Conditional Value at Risk Constraints (2019, background): “A regularization term in the dual update has been proposed in [30, 31] to circumvent this limitation.”
Conservative Stochastic Optimization With Expectation Constraints (2020, methodology): “The proposed algorithm is essentially a stochastic Frank-Wolfe version of the saddle point algorithm but again uses the idea of forcing zero average constraint violation from [27].”