Alacaoglu Ahmet, Malitsky Yura, Cevher Volkan
École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland.
Linköping University, Linköping, Sweden.
Comput Optim Appl. 2021;80(2):321-346. doi: 10.1007/s10589-021-00305-3. Epub 2021 Aug 19.
We propose a variance reduced algorithm for solving monotone variational inequalities. Without assuming strong monotonicity, cocoercivity, or boundedness of the domain, we prove almost sure convergence of the iterates generated by the algorithm to a solution. In the monotone case, the ergodic average converges with the optimal (1/) rate of convergence. When strong monotonicity is assumed, the algorithm converges linearly, without requiring the knowledge of strong monotonicity constant. We finalize with extensions and applications of our results to monotone inclusions, a class of non-monotone variational inequalities and Bregman projections.
我们提出了一种用于求解单调变分不等式的方差缩减算法。在不假设强单调性、余强制性或定义域有界性的情况下，我们证明了该算法生成的迭代序列几乎必然收敛到一个解。在单调情形下，遍历平均以最优的(1 /)收敛速率收敛。当假设强单调性时，该算法线性收敛，且无需知道强单调性常数。最后，我们将结果扩展并应用于单调包含问题、一类非单调变分不等式以及布雷格曼投影。
