非凸-凹极小极大优化中随机一阶算法的方差降低复杂度下界

该研究建立了允许使用方差降低的随机一阶算法在非凸-凹极小极大优化中的复杂度下界。在L-Lipschitz连续联合梯度、欧几里得半径不超过D_Y的紧凸对偶域条件下，目标精度ε的测量基于Moreau包络梯度范数，得到下界Ω(L²D_YΔε⁻³ + L³D_Y²Δσ²ε⁻⁶)。同时给出了非凸-强凹情形的下界结果，揭示了不同凹性 regime 下的复杂度壁垒。