在非凸--凹极小极大优化中带方差缩减的随机一阶算法的下界

arXiv:2610.01662v1 发布类型：cross 摘要：我们为非凸--凹极小极大优化中的随机一阶算法建立了复杂度下界，并允许算法使用方差缩减。我们的主要贡献是针对允许方差缩减的零尊重算法类给出一个下界，从而突破了某些现有下界所施加的算法限制。我们考虑目标函数具有 $L$-Lipschitz 连续的联合梯度，具有欧氏半径至多为 $D_Y$ 的紧凸对偶域，以及一个原始值函数；该函数定义为对对偶变量最大化目标函数，并且初始次优性至多为 $\Delta$。目标精度 $\varepsilon$ 通过带参数 $1/(2L)$ 的受约束原始值函数的 Moreau 包络的梯度范数来度量。在方差至多为 $\sigma^2$ 且满足均方光滑性的无偏随机一阶预言机下，我们证明了下界 $\Omega\!\left(L^2D_Y\Delta\varepsilon^{-3}+L^3D_Y^2\Delta\sigma^2\varepsilon^{-6}\right)$。即使允许使用方差缩减，该结果仍量化了复杂度对精度、对偶域半径和预言机噪声的依赖关系。我们还为非凸--强凹极小极大优化建立了互补的下界。设对偶强凹参数为 $\mu>0$，条件数为 $\kappa:=L/\mu$，则在有界方差预言机模型下，我们得到 $\Omega\!\left(L\Delta\sqrt{\kappa}\,\varepsilon^{-2}+L\Delta\kappa\sigma^2\varepsilon^{-4}\right)$。在额外满足常数为 $\bar L$ 的均方光滑性条件时，我们得到 $\Omega\!\left(L\Delta\sqrt{\kappa}\,\varepsilon^{-2}+\Delta\bar L\sigma\kappa^{3/2}\varepsilon^{-3}\right)$。综上，这些结果揭示了凹和强凹情形下的复杂度壁垒，其中主要的非凸--凹下界对于使用方差缩减的算法仍然成立。