Stochastic Variance Reduction Methods for Saddle-Point Problems
arXiv:1605.06398
Abstract
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 is 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.
Neural Information Processing Systems (NIPS), 2016, Barcelona, Spain
References in corpus (6)
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- Sketching as a Tool for Numerical Linear Algebra
- Convex Sparse Matrix Factorizations
- Stop Wasting My Gradients: Practical SVRG
- A Stochastic forward-backward splitting method for solving monotone inclusions in Hilbert spaces
- Adaptive Stochastic Primal-Dual Coordinate Descent for Separable Saddle Point Problems
Cited by in corpus (4)
- Efficient Algorithms for Federated Saddle Point Optimization
- A Unified Analysis of Variational Inequality Methods: Variance Reduction, Sampling, Quantization and Coordinate Descent
- CDMA: A Practical Cross-Device Federated Learning Algorithm for General Minimax Problems
- Method with Batching for Stochastic Finite-Sum Variational Inequalities in Non-Euclidean Setting