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

A variance reduced mirror-prox sliding method for solving a class of stochastic monotone variational inequality

作　　者：王子玲 王丽平[1] WANG Ziling;WANG Liping(School of Mathematics,Nanjing University of Aeronautics and Astronautics,211106,Nanjing,Jiangsu,PRC)

机构地区：[1]南京航空航天大学数学学院,江苏省南京市211106

出　　处：《曲阜师范大学学报（自然科学版）》2024年第4期1-12,F0002,共13页Journal of Qufu Normal University(Natural Science)

基　　金：国家自然科学基金(11971231,12111530001).

摘　　要：考虑了一类具有特殊结构的随机单调变分不等式(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)).In this paper,the authors consider new algorithm for solving a class of structured stochastic monotone variational inequality(SMVI),which is widely used in fields such as statistics,machine learning,and artificial intelligence.Specifically,the SMVI problem involves the sum of a gradient operator whose exact information is known and a monotone operator whose information is estimated by random samples,which makes the algorithm to solve the problem uncertain.The stochastic mirror-prox sliding algorithm is an effective algorithm to solve the SMVI problem,but the stochastic perturbation introduced by random information undermines the optimal computational complexity of monotone operator.Based on SMPS,in this paper,we use variance reduction technique for random monotone operators and propose a new algorithm,called variance reduced stochastic mirror-prox sliding algorithm(VRSMPS).In addition,under the general hypothesis of bounded variance,we prove that compared with SMPS,using VRSMPS to solve SMVI can obtain the optimal computational complexity of gradient operator O(√L/ε)and reduce the computational complexity of monotone operator from O(√L/ε+M/ε+σ^(2)/ε^(2))to O(√L/ε+√(α+M^(2))^(2)/Lε^(3)).

关 键 词：随机变分不等式 近端镜像滑动算法 方差缩减 计算复杂度 

分 类 号：O224[理学—运筹学与控制论]