New Accelerated Past-Extragradient Methods with Variance Reduction for Generalized Equations

Abstract

We develop a novel past-extragradient-type algorithmic framework, combining both Nesterov's \textit{acceleration} and \textit{variance-reduction} techniques, to solve a class of generalized equations involving possibly \textit{nonmonotone operators} in data-driven applications. Our framework covers a wide class of stochastic variance-reduced schemes, including mini-batching and both unbiased and biased control-variate estimators. We establish that our method achieves $\mathcal{O}(1/k^2)$ convergence rates in expectation for the squared norm of the residual under Lipschitz continuity and a ``co-hypomonotonicity-type'' assumption, significantly improving upon non-accelerated counterparts by a factor of $1/k$. We also prove faster $o(1/k^2)$ convergence rates, both in expectation and almost surely. In addition, we show that the sequence of iterates generated by our method almost surely converges to a solution of the underlying problem. We demonstrate the applicability of our method using general error approximation criteria, covering mini-batch stochastic estimators as well as three well-known control variate estimators: Loopless SVRG, SAGA, and Loopless SARAH. The resulting three variants attain significantly better oracle complexities than existing methods. We validate our framework and theoretical results through three numerical examples. The numerical results illustrate promising performance of our accelerated method over its non-accelerated counterparts.

59 pages, 6 figures, and 1 table