min-max问题可比变分不等式更快求解，因能利用变量不对称性。
Min-Max Optimization Is Strictly Easier Than Variational Inequalities
- 直接求解min-max问题，不经过变分不等式转化。
- 无约束二次目标下，收敛速率严格优于对应变分不等式。
- 利用极值多项式与保角映射分析最优速率，揭示不对称优势。
传统方法常将凸-凹min-max问题转化为其一阶最优性条件对应的变分不等式求解。能否绕过此约化，更高效地求解min-max问题？本文首次开展此研究。在经典的无约束二次目标场景下，我们证明：针对一阶算法，min-max问题的最优收敛速率严格优于其对应的变分不等式。关键原因在于，min-max算法可利用最小化与最大化变量间的不对称性——而该性质在约化至变分不等式时丢失。分析核心是通过格林函数与保角映射，计算极值多项式以精确刻画最优收敛速率。
原文摘要 · Abstract (English)
Classically, a mainstream approach for solving a convex-concave min-max problem is to instead solve the variational inequality problem arising from its first-order optimality conditions. Is it possible to solve min-max problems faster by bypassing this reduction? This paper initiates this investigation. We show that the answer is yes in the textbook setting of unconstrained quadratic objectives: the optimal convergence rate for first-order algorithms is strictly better for min-max problems than for the corresponding variational inequalities. The key reason that min-max algorithms can be faster is that they can exploit the asymmetry of the min and max variables--a property that is lost in the reduction to variational inequalities. Central to our analyses are sharp characterizations of optimal convergence rates in terms of extremal polynomials which we compute using Green's functions and conformal mappings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。