非凸极小极大优化的双时间尺度梯度下降上升算法

摘要

针对结构化非凸极小极大优化问题minₓmaxᵧ∈Y f(x,y)，其中目标函数f(x,y)在x上非凸、在y上凹，且约束集Y⊆ℝⁿ为凸有界集，本文对双时间尺度梯度下降上升(TTGDA)算法进行了统一分析。在凸-凹设置中，单时间尺度梯度下降上升(GDA)算法被广泛应用并已证明具有强收敛性保证。但在更一般的设置中，该算法可能无法收敛。主要贡献在于设计了超越凸-凹设置的有效TTGDA算法，能高效找到函数Φ(·):=maxᵧ∈Y f(·,y)的稳定点。同时建立了平滑与非平滑非凸-凹极小极大优化问题求解复杂度的理论边界。据所知，这是首次对非凸极小极大优化的TTGDA进行系统分析，揭示了其在训练生成对抗网络(GANs)和其他实际应用问题中的优越性能。