A Stochastic Proximal Point Algorithm for Saddle-Point Problems
This work addresses a bottleneck in optimization for machine learning, offering an incremental improvement for researchers and practitioners dealing with high-condition-number saddle-point problems.
The paper tackles the slow convergence of variance reduction methods for saddle-point problems with large condition numbers by proposing a stochastic proximal point algorithm that accelerates SAGA, reducing a logarithmic term in iteration complexity and showing greater efficiency in policy evaluation experiments.
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.