求解一类随机变分不等式问题的带方差缩减的近端镜像滑动算法

考虑了一类具有特殊结构的随机单调变分不等式(Stochastic Monotone Variational Inequalities,SMVI)问题的求解算法.所考虑的SMVI问题涉及到一个梯度算子与单调算子的和,其中梯度算子的精确信息是可知的,而单调算子的信息通过随机样本估计得到,这使得求解问题的算法具有不确定性.随机近端镜像滑动(Stochastic Mirror-Prox Sliding,SMPS)算法是求解SMVI问题的一种有效算法,但SMPS使用随机信息引入的扰动破坏了单调算子的最优计算复杂度.该文在SMPS的基础上对随机单调算子使用方差缩减技术,提出了带有方差缩减的随机近端镜像滑动(Vraiance Reduced Stochastic Mirror-Prox Sliding,VRSMPS)算法.并且,在一般性的方差可控假设下证明与SMPS相比,使用VRSMPS求解SMVI,获得梯度算子最优计算复杂度O(√L/ε)的同时,把H的计算复杂度从O(√L/ε+M/ε+σ^(2)/ε^(2))降低到O(√L/ε+√(α+M^(2))^(2)/Lε^(3)).