Variance reduction for root-finding problems

• 成果类型: Article
• 署名作者: Davis, Damek
• 署名单位: Cornell University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01758-4
• 发表日期: 2023
• 页码: 375-410
• 关键词: monotone inclusions; parallel; Iterations; algorithm

摘要

Minimizing finite sums of smooth and strongly convex functions is an important task in machine learning. Recent work has developed stochastic gradient methods that optimize these sums with less computation than methods that do not exploit the finite sum structure. This speedup results from using efficiently constructed stochastic gradient estimators, which have variance that diminishes as the algorithm progresses. In this work, we ask whether the benefits of variance reduction extend to fixed point and root-finding problems involving sums of nonlinear operators. Our main result shows that variance reduction offers a similar speedup when applied to a broad class of root-finding problems. We illustrate the result on three tasks involving sums of n nonlinear operators: averaged fixed point, monotone inclusions, and nonsmooth common minimizer problems. In certain poorly conditioned regimes, the proposed method offers an n-fold speedup over standard methods.