2019/06/22 by Xun Zhang, William B. Haskell, Zhang, Xun +4
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Search Problems #Optimization and Variational Analysis #Stochastic Gradient Optimization Techniques #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1906.09437
openalex publication_date 2019/06/22 · arxiv created 2021/03/16 · arxiv updated 2021/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.