Journal article
Accelerated Stochastic Algorithms for Convex-Concave Saddle-Point Problems
Mathematics of operations research, Vol.47(2), pp.1443-1473
05/01/2022
DOI: 10.1287/moor.2021.1175
Abstract
We develop stochastic first-order primal-dual algorithms to solve a class of convex-concave saddle-point problems. When the saddle function is strongly convex in the primal variable, we develop the first stochastic restart scheme for this problem. When the gradient noises obey sub-Gaussian distributions, the oracle complexity of our restart scheme is strictly better than any of the existing methods, even in the deterministic case. Furthermore, for each problem parameter of interest, whenever the lower bound exists, the oracle complexity of our restart scheme is either optimal or nearly optimal (up to a log factor). The subroutine used in this scheme is itself a new stochastic algorithm developed for the problem where the saddle function is nonstrongly convex in the primal variable. This new algorithm, which is based on the primal-dual hybrid gradient framework, achieves the state-of-the-art oracle complexity and may be of independent interest.
Details
- Title: Subtitle
- Accelerated Stochastic Algorithms for Convex-Concave Saddle-Point Problems
- Creators
- Renbo Zhao - MIT, Operat Res Ctr, Cambridge, MA 02142 USA
- Resource Type
- Journal article
- Publication Details
- Mathematics of operations research, Vol.47(2), pp.1443-1473
- Publisher
- Informs
- DOI
- 10.1287/moor.2021.1175
- ISSN
- 0364-765X
- eISSN
- 1526-5471
- Number of pages
- 32
- Language
- English
- Date published
- 05/01/2022
- Academic Unit
- Business Analytics
- Record Identifier
- 9984446273102771
Metrics
2 Record Views