论文标题
近距离和无参数单调包容性的Halpern迭代以及变异不平等的强大解决方案
Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities
论文作者
论文摘要
我们利用非专用图，单调Lipschitz运算符和近端映射之间的连接，以获得近乎最佳的（即，就迭代复杂性而言，最佳的多志因子）和无参数的方法来解决解决单调包含问题的无参数方法。这些结果立即转化为近似最佳的保证，以近似于差异不平等问题的强大解决方案，近似于凸 - concove min-max优化问题，并最大程度地减少在最小最大优化问题中梯度的范围。我们的分析基于Halpern迭代的新颖且基于简单的基于潜在的潜在融合证明，这是一种经典的迭代，用于查找非专用图的固定点。此外，我们还提供一系列算法减少，突出显示不同问题类别之间的连接，并导致较低的界限，以证明所研究方法的近距离观点。
We leverage the connections between nonexpansive maps, monotone Lipschitz operators, and proximal mappings to obtain near-optimal (i.e., optimal up to poly-log factors in terms of iteration complexity) and parameter-free methods for solving monotone inclusion problems. These results immediately translate into near-optimal guarantees for approximating strong solutions to variational inequality problems, approximating convex-concave min-max optimization problems, and minimizing the norm of the gradient in min-max optimization problems. Our analysis is based on a novel and simple potential-based proof of convergence of Halpern iteration, a classical iteration for finding fixed points of nonexpansive maps. Additionally, we provide a series of algorithmic reductions that highlight connections between different problem classes and lead to lower bounds that certify near-optimality of the studied methods.
