Search papers, labs, and topics across Lattice.
This paper introduces novel variance-reduction techniques for the forward-reflected-backward splitting (FRBS) method to solve stochastic composite inclusions, addressing the challenge of developing stochastic biased variants. The core idea involves constructing stochastic variance-reduced estimators for the forward-reflected direction and using them for iterate updates, encompassing both unbiased (mini-batch SGD, loopless-SVRG, SAGA) and biased (SARAH, Hybrid SGD, Hybrid SVRG) estimators. The analysis establishes $\mathcal{O}(1/k)$ convergence rates and derives oracle complexities, demonstrating the efficacy of the proposed framework through numerical experiments on AUC optimization and policy evaluation.
Biased variance-reduced estimators, previously unutilized for stochastic composite inclusions, can now be handled within a new FRBS framework, offering a viable alternative to unbiased methods.
This paper develops new variance-reduction techniques for the forward-reflected-backward splitting (FRBS) method to solve a class of possibly nonmonotone stochastic composite inclusions. Unlike unbiased estimators such as mini-batching, developing stochastic biased variants faces a fundamental technical challenge and has not been utilized before for inclusions and fixed-point problems. We fill this gap by designing a new framework that can handle both unbiased and biased estimators. Our main idea is to construct stochastic variance-reduced estimators for the forward-reflected direction and use them to perform iterate updates. First, we propose a class of unbiased variance-reduced estimators and show that increasing mini-batch SGD, loopless-SVRG, and SAGA estimators fall within this class. For these unbiased estimators, we establish a $\mathcal{O}(1/k)$ best-iterate convergence rate for the expected squared residual norm, together with almost-sure convergence of the iterate sequence to a solution. Consequently, we prove that the best oracle complexities for the $n$-finite-sum and expectation settings are $\mathcal{O}(n^{2/3}ε^{-2})$ and $\mathcal{O}(ε^{-10/3})$, respectively, when employing loopless-SVRG or SAGA, where $ε$ is a desired accuracy. Second, we introduce a new class of biased variance-reduced estimators for the forward-reflected direction, which includes SARAH, Hybrid SGD, and Hybrid SVRG as special instances. While the convergence rates remain valid for these biased estimators, the resulting oracle complexities are $\mathcal{O}(n^{3/4}ε^{-2})$ and $\mathcal{O}(ε^{-5})$ for the $n$-finite-sum and expectation settings, respectively. Finally, we conduct two numerical experiments on AUC optimization for imbalanced classification and policy evaluation in reinforcement learning.
