提出新型方差减少方法,提升非单调随机复合包含问题求解效率。
Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions
- 构建基于前向-反射-后向方向的随机方差减少估计器框架
- 证明无偏与有偏估计器均实现1/k收敛率,有偏者复杂度更高但适用更广
- 适用于不平衡分类和强化学习策略评估等实际任务
本文针对可能非单调的随机复合包含问题,发展了前向-反射-后向分裂(FRBS)方法的新方差减少技术。不同于传统的无偏估计(如小批量),本文首次将有偏估计引入此类问题求解,并设计统一框架同时支持两类估计。核心思路是构建前向-反射方向的方差减少估计器用于迭代更新。首先,提出一类无偏方差减少估计器,涵盖增大小批量SGD、无循环SVRG和SAGA;在该类下,建立期望平方残差范数的$×(1/k)$最优收敛率,并证明迭代序列几乎必然收敛至解。由此可得,当使用无循环SVRG或SAGA时,有限和与期望情形下的最优查询复杂度分别为$×(n^{2/3}ε^{-2})$和$×(ε^{-10/3})$。其次,提出一类新的有偏方差减少估计器,包含SARAH、混合SGD和混合SVRG作为特例;虽收敛率保持不变,但复杂度升为$×(n^{3/4}ε^{-2})$和$×(ε^{-5})$。最后,在不均衡分类的AUC优化与强化学习策略评估中进行了数值实验。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。