求解非凸强凹极小极大问题的两种信赖域型算法
内容提要
本文综述最小最大优化问题的算法进展，涵盖椭圆域二次函数最大化、加速近端点法、随机TR/ARC方法、非凸强凹问题下界、单循环AGP算法、不精确Hessian信任域法、近似近端点迭代求纳什均衡、黎曼梯度下降及平滑最小最大一阶方法，分别达到线性时间、O(κx√κy)等复杂度，改进了已知最优速率。
延伸解读
算法演进与复杂度改进
文章梳理了极小极大优化算法的多个进展，包括椭圆域二次函数最大化的线性时间近似算法、加速近端点法达到O(κx√κy)梯度复杂度、单循环AGP算法实现O(ε^-2)或O(ε^-4)复杂度，以及非凸强凹问题下界的建立。这些工作在不同设定下改进了已知最优速率，反映了该领域在理论复杂度上的持续优化。
不精确计算与随机方法的应用
随机TR和ARC方法允许使用不精确的Hessian、梯度和函数值，减少每次迭代开销，同时保持与精确计算同级的迭代复杂度。不精确Hessian信任域法也通过渐进解和子问题近似，在松弛条件下达到二阶最优。这些方法为大规模问题提供了更实用的计算途径。
问题设定与算法适用性
文章涵盖强凸强凹、凸凹、非凸强凹和非凸凹等多种函数类型，以及黎曼流形上的优化。不同算法针对特定结构设计，如AGP算法统一处理非凸-（强）凹和（强）凸-非凹问题，黎曼梯度下降适用于紧致流形约束。读者需根据问题特性选择合适方法。
Q&A
求解非凸强凹极小极大问题有哪些最新的算法进展？
文章综述了多种算法，包括加速近端点法（梯度复杂度O(κx√κy)）、随机TR/ARC方法、单循环AGP算法（梯度复杂度O(ε^-2)或O(ε^-4)）、不精确Hessian信任域法、近似近端点迭代求纳什均衡（复杂度O(√(κxκy)log(1/ε))）以及黎曼梯度下降等，这些算法在复杂度上改进了已知最优速率。
非凸强凹极小极大问题的复杂度下界是多少？
文章在一般和平均平滑有限和设置中建立了非平凡的较低复杂度下界，并提出了一种通用加速方案，使用现有基于梯度的方法解决强凸-强凹子问题，缩小了复杂度差距，在一般情况下算法的复杂度几乎与下界相当。
有哪些算法可以求解非凸强凹极小极大问题并达到线性时间？
文章提到一种在椭圆域上求解一般二次函数最大化问题的近似算法，时间复杂度为线性，能获得ϵ-近似解，与Nesterov加速梯度下降和Lanczos方法的运行时相匹配。
随机TR和ARC方法在非凸强凹问题中有什么优势？
通过使用随机TR和ARC方法，可以在提供Hessian矩阵、梯度和函数值的不精确计算的基础上，减少每次迭代的传播开销，获得与准确计算同级别的迭代复杂度以实现近似二阶最优性，且每次迭代计算开销更少。
单循环AGP算法适用于哪些类型的极小极大问题？
单循环AGP算法适用于光滑的非凸-（强）凹和（强）凸-非凹的极小极大问题，扩展了BAPG算法，能在不同设置下找到ε-稳定点，梯度复杂度为O(ε^-2)或O(ε^-4)。
如何利用近似近端点迭代求解纳什均衡？
文章提出一种算法，通过在原函数上执行近似的近端点迭代，并利用Nesterov算法在正则化函数上运行不精确的神谕，找到关于站点准则的(εx, εy)第一阶纳什均衡，将梯度计算复杂度降至O(√(κxκy)log(1/ε))。
