带约束的非光滑非凸随机优化的最优算法

arXiv:2610.13787v1 公告类型：cross 摘要：我们针对目标函数既不光滑也不凸、且带有凸约束集的随机优化问题，提出了新的算法。我们的算法能够返回一个 $(\delta,\varepsilon)$-Goldstein stationary point，该概念最近由 Liu et al. (2024) 针对带约束问题提出；同时，算法具有更优的复杂度，并且在多种情形下首次实现了该任务的最优收敛率。具体而言，我们设计了基于投影和无投影的算法：使用随机梯度时，可达到 $\widetilde O(\delta^{-1}\varepsilon^{-3})$ 的复杂度，我们证明该复杂度是最优的；使用零阶查询时，可达到 $\widetilde O(d\delta^{-1}\varepsilon^{-3})$ 的复杂度，该复杂度关于维度 $d$ 的依赖也是最优的，并且优于已有工作。值得注意的是，我们以下界的形式给出了 Frank-Wolfe gap，并且即使对于光滑问题也成立，这一结果本身也具有独立意义。这些结果表明，在非凸随机优化中，约束的存在和非光滑性都不会导致收敛率下降。我们的分析基于将问题归约为在线线性优化，并扩展了无约束优化中的相关技术。