Machine learning approaches relying on such criteria as adversarial
robustness or multi-agent settings have raised the need for solving
game-theoretic equilibrium problems. Of particular relevance to these
applications are methods targeting finite-sum structure, which generically
arises in empirical variants of learning problems in these contexts. Further,
methods with computable approximation errors are highly desirable, as they
provide verifiable exit criteria. Motivated by these applications, we study
finite-sum monotone inclusion problems, which model broad classes of
equilibrium problems. Our main contributions are variants of the classical
Halpern iteration that employ variance reduction to obtain improved complexity
guarantees in which $n$ component operators in the finite sum are ``on
average'' either cocoercive or Lipschitz continuous and monotone, with
parameter $L$. The resulting oracle complexity of our methods, which provide
guarantees for the last iterate and for a (computable) operator norm residual,
is $\widetilde{\mathcal{O}}( n + \sqrt{n}L\varepsilon^{-1})$, which improves
upon existing methods by a factor up to $\sqrt{n}$. This constitutes the first
variance reduction-type result for general finite-sum monotone inclusions and
for more specific problems such as convex-concave optimization when operator
norm residual is the optimality measure. We further argue that, up to
poly-logarithmic factors, this complexity is unimprovable in the monotone
Lipschitz setting; i.e., the provided result is near-optimal.

应用机器学习方法解决针对敌对鲁棒性或多主体环境产生的博弈均衡问题，提出了基于有限和结构的方法。使用方差缩减技术改进了经典的 Halpern 迭代，通过在求和中的组分算子上引入可比较的 cocoercive 或 Lipschitz 连续单调性，取得了性能改进。所提出的方法具有可验证的退出准则，并且在最后迭代次数和（可计算的）操作符范数残差方面提供了保证。其 oracle 复杂性为 $𝜃(𝑛+√𝑛𝐿𝜖^{-1})$，相较于现有方法提升了多达√𝑛倍，将方差缩减引入到通用有限和单调包含问题和具体问题中，如算子范数残差是最优性度量的凸 - 凹优化，创造了一项新的成果。进一步论证表明，在单调 Lipschitz 设置中，除去多项式对数因子，这种复杂性是无法被改进的，即提供的结果几乎是最优的。

有限和单调包含的方差减少哈尔彭迭代

Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions

We consider the convex-concave saddle point problem $\min_{x}\max_{y}
f(x)+y^\top A x-g(y)$ where $f$ is smooth and convex and $g$ is smooth and
strongly convex. We prove that if the coupling matrix $A$ has full column rank,
the vanilla primal-dual gradient method can achieve linear convergence even if
$f$ is not strongly convex. Our result generalizes previous work which either
requires $f$ and $g$ to be quadratic functions or requires proximal mappings
for both $f$ and $g$. We adopt a novel analysis technique that in each
iteration uses a "ghost" update as a reference, and show that the iterates in
the primal-dual gradient method converge to this "ghost" sequence. Using the
same technique we further give an analysis for the primal-dual stochastic
variance reduced gradient (SVRG) method for convex-concave saddle point
problems with a finite-sum structure.

本研究针对具有凸 - 凹鞍点问题的优化进行了研究，证明了即使 $f$ 不强凸，使用一般的原始 - 对偶梯度方法也可以实现线性收敛，并给出了具有有限和结构的凸 - 凹鞍点问题的原始 - 对偶随机方差减少梯度方法的分析。