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.
翻译:在目标具有有限总和结构的情况下,遇到大规模单一体包容问题是常见的。我们为这一问题制定了一个减少差异的前向后分解算法总框架。这个框架包括一些现有的确定和差异后分解算法,作为特殊情况尽量减少功能,还适用于诸如马鞍点问题和变异性不平等等更一般性的问题。我们通过精心构建的Lyapunov功能,表明我们框架所涵盖的算法在轻度假设下享有预期线性趋同率。我们进一步考虑加速和不同步地实施以降低算法复杂性和计算时间。我们把我们提议的框架应用于政策评价问题和强烈单调双玩游戏,两者都不属于功能最小化。