Preprint
Stochastic Primal-Dual Algorithms with Faster Convergence than $O(1/\sqrt{T})$ for Problems without Bilinear Structure
The journal of ancient architecture
04/22/2019
DOI: 10.48550/arxiv.1904.10112
Abstract
Previous studies on stochastic primal-dual algorithms for solving min-max
problems with faster convergence heavily rely on the bilinear structure of the
problem, which restricts their applicability to a narrowed range of problems.
The main contribution of this paper is the design and analysis of new
stochastic primal-dual algorithms that use a mixture of stochastic gradient
updates and a logarithmic number of deterministic dual updates for solving a
family of convex-concave problems with no bilinear structure assumed. Faster
convergence rates than $O(1/\sqrt{T})$ with $T$ being the number of stochastic
gradient updates are established under some mild conditions of involved
functions on the primal and the dual variable. For example, for a family of
problems that enjoy a weak strong convexity in terms of the primal variable and
has a strongly concave function of the dual variable, the convergence rate of
the proposed algorithm is $O(1/T)$. We also investigate the effectiveness of
the proposed algorithms for learning robust models and empirical AUC
maximization.
Details
- Title: Subtitle
- Stochastic Primal-Dual Algorithms with Faster Convergence than $O(1/\sqrt{T})$ for Problems without Bilinear Structure
- Creators
- Yan YanYi XuQihang LinLijun ZhangTianbao Yang
- Resource Type
- Preprint
- Publication Details
- The journal of ancient architecture
- DOI
- 10.48550/arxiv.1904.10112
- ISSN
- 2785-3861
- Language
- English
- Date posted
- 04/22/2019
- Academic Unit
- Business Analytics; Computer Science
- Record Identifier
- 9984380585002771
Metrics
15 Record Views