非凸 -(强) 凹最小极大问题的两种完全无参参数的交替梯度投影算法
内容提要
本文提出了一种统一的单循环交替梯度投影算法，旨在解决光滑的非凸-凹和凸-非凹极小-最大化问题。证明该算法在不同设置下能够找到ε-稳定点，且梯度复杂度为O(ε^-2)或O(ε^-4)。研究还涵盖了零阶和二阶算法，展示了其在确定性和随机设置下的有效性及复杂度保证。
延伸解读
算法统一性与复杂度
本文提出的单循环交替梯度投影算法统一处理非凸-凹和凸-非凹极小极大问题，扩展了BAPG算法。其梯度复杂度为O(ε^-2)或O(ε^-4)，能够找到ε-稳定点。这种统一框架简化了算法设计，为不同凸性结构的问题提供了理论保证。
零阶算法的突破
针对非凸凹极小极大问题，本文提出的ZO-PDAPG和ZO-RMPDPG是首个具有迭代复杂度保证的零阶算法。在确定性设置下复杂度为O(ε^-2)和O(ε^-4)，随机设置下为Õ(ε^-3)和Õ(ε^-6.5)。这为仅能获取函数值的问题提供了有效解决方案。
二阶算法的参数自由化
本文提出的LF-CR和FF-CR算法解决了凸凹极小极大问题，其中FF-CR是首个完全无参数的二阶算法，无需Lipschitz常数或问题参数。其迭代复杂度与现有带参数二阶算法的最优下界一致，实验证明了有效性，降低了参数调优的负担。
收敛速率与实验验证
在纳什均衡问题中，交替GDA和平滑GDA算法在Polyak-Lojasiewicz条件下分别需要O(κ²ε⁻²)和O(κε⁻²)次迭代，是目前最佳的单循环复杂度结果。实验显示这些算法在生成对抗网络训练和非线性回归中高效，验证了理论结果的实际适用性。
Q&A
什么是交替梯度投影算法？
交替梯度投影算法是一种用于解决光滑的非凸-凹和凸-非凹极小-最大化问题的算法，能够找到目标函数的ε-稳定点。
该算法的梯度复杂度是多少？
该算法的梯度复杂度为O(ε^-2)或O(ε^-4)。
零阶算法在非凸最小最大问题中的应用是什么？
零阶算法在非凸最小最大问题中提供了两种单环算法，ZO-PDAPG和ZO-RMPDPG，具有迭代复杂度保证。
FF-CR算法有什么特点？
FF-CR算法是首个完全无参数的二阶算法，解决凸凹极小极大问题，其迭代复杂度与现有带参数算法的最优下界一致。
如何提高纳什均衡问题的收敛速度？
通过使用交替GDA和平滑GDA算法，可以在满足Polyak-Lojasiewicz条件时提高纳什均衡问题的收敛速度。
加速近端梯度法在非凸优化中的作用是什么？
加速近端梯度法在非凸优化中能够证明生成序列的极限点是目标函数的临界点，并获得线性和次线性的收敛速率。
