A Unifying Framework for Variance Reduction Algorithms for Finding Zeroes of Monotone Operators
arXiv:1906.09437
Abstract
It is common to encounter large-scale monotone inclusion problems where the objective has a finite sum structure. We develop a general framework for variance-reduced forward-backward splitting algorithms for this problem. This framework includes a number of existing deterministic and variance-reduced algorithms for function minimization as special cases, and it is also applicable to more general problems such as saddle-point problems and variational inequalities. With a carefully constructed Lyapunov function, we show that the algorithms covered by our framework enjoy a linear convergence rate in expectation under mild assumptions. We further consider Catalyst acceleration and asynchronous implementation to reduce the algorithmic complexity and computation time. We apply our proposed framework to a policy evaluation problem and a strongly monotone two-player game, both of which fall outside of function minimization.
References in corpus (6)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
- A Universal Catalyst for First-Order Optimization
- Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
- A Lower Bound for the Optimization of Finite Sums
- A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints