Stochastic Variance Reduction Methods for Saddle-Point Problems
We consider convex-concave saddle-point problems where the objective functions may be split in many components, and extend recent stochastic variance reduction methods (such as SVRG or SAGA) to provide the first large-scale linearly convergent algorithms for this class of problems which are common in machine learning. While the algorithmic extension is straightforward, it comes with challenges and opportunities: (a) the convex minimization analysis does not apply and we use the notion of monotone operators to prove convergence, showing in particular that the same algorithm applies to a larger class of problems, such as variational inequalities, (b) there are two notions of splits, in terms of functions, or in terms of partial derivatives, (c) the split does need to be done with convex-concave terms, (d) non-uniform sampling is key to an efficient algorithm, both in theory and practice, and (e) these incremental algorithms can be easily accelerated using a simple extension of the "catalyst" framework, leading to an algorithm which is always superior to accelerated batch algorithms.
This paper considers saddle-point problems with a convex-concave property. The authors show how this problem can be addressed using existing stochastic variance reduced techniques (such as SVRG and SAGA) coupled with a proximal operator. They study these algorithms in the monotone operator setting showing linear convergence. They also propose an accelerated variant as well as analyze a non-uniform sampling scheme.
Novelty/originality: The contributions of this paper are significant. The theoretical analysis is thorough and reveals some new insights for saddle-point problems. The authors propose many extensions in this paper, the most significant one being that their method applies to non-separable functions.  Technical quality: Although I really like the theoretical contributions of this paper, I was nevertheless quite disappointed in the way it is presented. I think the authors could have made the paper more accessible by making the connection to monotone operators more clear. This appears as an extension in Section 6 but the analysis provided by the authors is based on monotone operators. On the experimental side, I would have liked to see experimental results on more than two datasets. In the case of separable functions, the authors should also have compared to accelerated methods such as this stochastic variant of Chambolle-Pock algorithm: http://www.jmlr.org/proceedings/papers/v37/zhanga15.pdf Please add this reference to your submission.  There are a few points that I would like the authors should clarify: 1. How strong are the assumptions A-C, particularly assumption (A). For example, I wonder whether their assumptions hold for solving the saddle-point problem induced by SVM. 2. I can not fully understand the differences between stochastic primal-dual method and their suggested method. Can the authors elaborate on this point? 3. In theorem 2, I am not sure about constant \mu. Is it the monotonicity constant mentioned in appendix? How can we compare this result with the result of theorem 1?  4. The transition from assumption (A)-(C) to strong monotonicity (in appendix) is confusing. Do assumptions (A)-(C) imply monotonicity?   Minor issues: Some mix-up with the constant L used as the condition number and the Lipschitz constant: “The quantity L represents the condition number of the problem” and “we need the Lipschitz constant L” Forward-Backward algorithm: please add a reference