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.

基于Halpern迭代的潜能函数收敛证明，我们利用非扩张映射、单调Lipschitz算子和近端映射之间的联系，得到了解决单调包含问题的近乎最优无参方法，同时转化为解决变分不等式问题、拟凸-凹极小极大优化问题的近乎最优保证，并在分析中提供了一系列的算法降低证明复杂度。

近最优无参数单调包含和变分不等式有限强解的哈尔普恩迭代