用于随机双层优化的单循环、恒定批量一阶惩罚方法

arXiv:2610.07290v1 公告类型：cross 摘要：随机双层优化（SBO）中基于惩罚的方法近期取得了进展，已经无需二阶导数预言机。然而，对于随机非凸-强凸双层问题，现有的一阶方法通常依赖嵌套循环和/或大批量，才能在标准有界方差假设或均方光滑性假设下达到 $O(\epsilon^{-6})$ 或 $O(\epsilon^{-4})$ 的样本复杂度。由于需要较大的惩罚参数才能实现精确近似，使用单循环惩罚方法和恒定批量大小达到这些复杂度仍然具有挑战性。为应对这一挑战，我们提出了一种随机单循环恒定批量一阶惩罚方法（SICO），该方法结合了两个互补的组成部分。首先，对于原始下层问题和惩罚问题，它在每次迭代中各执行一次随机梯度更新，并通过投影控制两者迭代点之间的距离。其次，它采用指数移动平均来稳定上层梯度估计器。我们证明，在随机梯度无偏且具有有界方差的条件下，这一组合方法仅需每次迭代使用 $O(1)$ 个随机梯度样本，即可达到 $O(\epsilon^{-6})$ 的样本复杂度。在进一步假设下层随机梯度具有均方光滑性的情况下，同一算法在批量大小仍为 $O(1)$ 时，可将复杂度提升至 $O(\epsilon^{-4})$。据我们所知，这是首项使用单循环和恒定批量大小、达到全一阶 SBO 方法已知最佳收敛速率的工作。该结果解决了相关文献中提出的一个开放问题。