论文标题
随机变化不平等的简单和最佳方法，I：操作员外推
Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation
论文作者
论文摘要
在本文中，我们首先提出了一种新型操作员外推（OE）方法，用于解决确定性变分不平等（VI）问题。与梯度（操作员）投影方法类似，OE通过在每次迭代中求解一个单个投影子问题来更新一个搜索序列。我们表明，OE可以以比现有方法更简单地解决各种VI问题的最佳收敛速率。然后，我们介绍随机操作员外推（SOE）方法，并建立其最佳收敛行为以解决不同的随机VI问题。特别是，在文献中，SOE达到了解决基本问题的最佳复杂性，即随机平滑而强烈的单调VI。我们还提出了一种随机块操作员外推（SBOE）方法，以进一步降低使用特定块结构的大规模确定性VIS的OE方法的迭代成本。已经进行了数值实验，以证明所提出算法的潜在优势。实际上，所有这些算法都用于求解概括的单调变化不平等（GMVI）问题，其运算符不一定是单调。我们还将在同伴论文中讨论基于OE的最佳政策评估方法。
In this paper we first present a novel operator extrapolation (OE) method for solving deterministic variational inequality (VI) problems. Similar to the gradient (operator) projection method, OE updates one single search sequence by solving a single projection subproblem in each iteration. We show that OE can achieve the optimal rate of convergence for solving a variety of VI problems in a much simpler way than existing approaches. We then introduce the stochastic operator extrapolation (SOE) method and establish its optimal convergence behavior for solving different stochastic VI problems. In particular, SOE achieves the optimal complexity for solving a fundamental problem, i.e., stochastic smooth and strongly monotone VI, for the first time in the literature. We also present a stochastic block operator extrapolations (SBOE) method to further reduce the iteration cost for the OE method applied to large-scale deterministic VIs with a certain block structure. Numerical experiments have been conducted to demonstrate the potential advantages of the proposed algorithms. In fact, all these algorithms are applied to solve generalized monotone variational inequality (GMVI) problems whose operator is not necessarily monotone. We will also discuss optimal OE-based policy evaluation methods for reinforcement learning in a companion paper.
