Variance-Reduced Fast Krasnosel’skiǐ-Mann Methods for Finite-Sum Root-Finding Problems

We develop a new class of fast Krasnosel’skiǐ-Mann methods with variance reduction to solve a finite-sum cocoercive equation, $Gx=0$. Our algorithm is single loop and leverages a new family of unbiased variance-reduced estimators specifically designed for a wider class of root-finding algorithms. Our method achieves both $\mathcal{O}(1/k^2)$ and $o(1/k^2)$ last-iterate convergence rates in terms of $\mathbb{E}[\Vert G{x}^k{\Vert }^2]$, where k is the iteration counter, and $\mathbb{E}[·]$ is the total expectation. We also establish almost-sure $o(1/k^2)$ convergence rates and the almost-sure convergence of iterates $\{x^k\}$ to a solution of $Gx=0$. We instantiate our framework for two prominent estimators: SVRG and SAGA. By an appropriate choice of parameters, both variants attain an oracle complexity of $\mathcal{O}(n+n^{2/3}{ϵ}^{-1})$ to reach an $ϵ$-solution, where n denotes the number of summands in the finite-sum operator G. Furthermore, under $\sigma$-strong quasimonotonicity, our method achieves a linear convergence rate and an oracle complexity of $\mathcal{O}(n+\text{max}\{n,n^{2/3}\kappa \}\text{log}(\frac{1}{ϵ}))$, where $\kappa ≔L/\sigma$. We extend our approach to solve a class of finite-sum inclusions (possibly nonmonotone), demonstrating that our schemes retain the same theoretical guarantees as in the equation setting. Finally, numerical experiments demonstrate that our methods exhibit promising performance compared with state-of-the-art methods.

Funding: This work was partially supported by the U.S. National Science Foundation [Grant RTG-DMS-2134107] and the Office of Navel Research [Grant N00014-23-1-2588].