A Stochastic Proximal Point Algorithm for Saddle-Point Problems

Abstract

We consider saddle point problems which objective functions are the average of $n$ strongly convex-concave individual components. Recently, researchers exploit variance reduction methods to solve such problems and achieve linear-convergence guarantees. However, these methods have a slow convergence when the condition number of the problem is very large. In this paper, we propose a stochastic proximal point algorithm, which accelerates the variance reduction method SAGA for saddle point problems. Compared with the catalyst framework, our algorithm reduces a logarithmic term of condition number for the iteration complexity. We adopt our algorithm to policy evaluation and the empirical results show that our method is much more efficient than state-of-the-art methods.

References in corpus (6)

• A Universal Catalyst for First-Order Optimization
• Convex Sparse Matrix Factorizations
• A Simple Practical Accelerated Method for Finite Sums
• A Stochastic forward-backward splitting method for solving monotone inclusions in Hilbert spaces
• Exploiting Strong Convexity from Data with Primal-Dual First-Order Algorithms
• SAGA with Arbitrary Sampling

Cited by in corpus (7)

• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence
• Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
• Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimization