近最优非凸强凸双层次优化的完全一阶Oracle方法

摘要

本研究考虑了下层问题为强凸情况的双层次优化问题。近期研究表明，使用Hessian-向量积（HVP）Oracle可以在O(ϵ⁻²)次Oracle调用内找到ϵ-稳定点。然而，HVP Oracle在实际中可能难以获取或计算成本高昂。某机构等（ICML 2023）通过提出一阶方法解决了这一问题，但收敛速度较慢，为O~(ϵ⁻³)。

本文通过引入双时间尺度更新改进了该方法，实现了近最优的O~(ϵ⁻²)一阶Oracle复杂度。分析方法具有高度可扩展性：在随机设置下，当随机噪声仅存在于上层目标函数时，算法可实现O~(ϵ⁻⁴)的随机一阶Oracle复杂度；当两个层次目标函数都存在随机噪声时，复杂度为O~(ϵ⁻⁶)。

当目标函数具有高阶光滑性条件时，确定性方法可以通过注入噪声逃离鞍点，并利用某中心的动量加速技术实现更快的O~(ϵ⁻¹.⁷⁵)收敛速度。

关键词：双层次优化、非凸优化、一阶方法、Oracle复杂度、鞍点逃离