我们研究了一类随机二级优化问题，引入了一种新颖的随机二级优化方法，通过随机切割平面局部逼近下层问题的解集，并运行带有方差减少技术的条件梯度更新来控制由于使用随机梯度引起的误差。在上层函数为凸函数的情况下，我们的方法需要最多 $\tilde {\mathcal {O}}(\max\{1/\epsilon_f^{2},1/\epsilon_g^{2}\})$ 个随机 oracle 查询，得到一个上层函数精度为 $\epsilon_f$、下层函数精度为 $\epsilon_g$ 的解，这一保证改进了之前已知的复杂性 $\mathcal {O}(\max\{1/\epsilon_f^{4},1/\epsilon_g^{4}\})$。此外，在上层函数为非凸函数的情况下，我们的方法需要最多 $\tilde {\mathcal {O}}(\max\{1/\epsilon_f^{3},1/\epsilon_g^{3}\})$ 个随机 oracle 查询，找到一个 $(\epsilon_f, \epsilon_g)$- 稳定点。在有限和问题设置中，对于凸和非凸情况下，我们的方法所需的随机 oracle 调用次数分别为 $\tilde {\mathcal {O}}(\sqrt {n}/\epsilon)$ 和 $\tilde {\mathcal {O}}(\sqrt {n}/\epsilon^{2})$，其中 $\epsilon=\min \{\epsilon_f,\epsilon_g\}$。

Aug, 2023

通过使用 y^*-aware oracle，我们提出了一种简单的一阶方法，它可以使用 O (ε^{-6})，O (ε^{-4}) 的一阶 y^*-aware oracles 来收敛到一个 ε 稳定点。

Feb, 2024

本文讨论了双层优化问题，提出了第一和第二阶段方法，探究了优化的复杂度和速度，并提出了适用于分布式双层问题的简单算法。

Jun, 2023

本研究提出一种全一阶随机逼近方法用于解决双层无约束随机优化问题，该方法具有收敛性及优异的实际性能，并且可以使用动量辅助的梯度估计器进一步提高收敛速度。

Jan, 2023

提出一种基于随机逼近的罚函数方法来解决非线性规划问题，利用噪声梯度或函数值来调用随机一阶或零阶神经网络，通过最小化随机一阶或零阶信息可用的非光滑、非凸罚函数的方法来优化。分析了该罚函数方法通过调用随机一阶（或零阶）神经网络获取 ε- 随机临界点的最坏情况复杂度。

Dec, 2013

本文提出了快速随机化算法来解决非凸随机双层优化问题，在 Lipschitz 连续条件下建立了单一下层问题和具有 $m>1$ 个下层问题（多任务 SBO）的非凸 SBO 的样本复杂度，以及在梯度主导函数下的更快收敛结果。

May, 2021

具有有限时间超梯度稳定性保证的一阶线性约束优化方法在双层优化中遇到了带有高维度的 Hessian 计算，尽管最近的研究提供了非约束双层问题的一阶方法，但约束设置仍然相对较少探讨。我们提出了一种具有有限时间超梯度稳定性保证的一阶线性约束优化方法，在线性等式约束下，我们可以在 O (ϵ^{-2}) 次梯度预言调用中获得 ϵ- 稳定性，这几近是最优的。在线性不等式约束下，我们可以在 O (dδ^{-1}ϵ^{-3}) 次梯度预言调用中获得 (δ,ϵ)-Goldstein 稳定性，其中 d 是上层维度。最后，我们在额外假设有对最优对偶变量的 oracle 访问的情况下，在线性不等式设置下获得无维度的 O (δ^{-1}ϵ^{-4}) 的 oracle 复杂度。在此过程中，我们发展了新的非平滑非凸优化方法来处理不完全的预言。我们通过初步的数值实验验证了这些保证。

Jun, 2024

本文提出了一种基于一阶梯度信息的简单双层优化算法，适用于深度学习中大规模的非凸函数，无需隐式微分，并有指导其在非凸优化问题上收敛于驻点的收敛性分析证明，实验结果表明其优越的性能表现。

Sep, 2022

本文研究使用零阶随机逼近算法解决双层问题，无论是上 / 下目标值还是它们的无偏梯度估计都不可用。通过利用斯坦恩恒等式，首先使用高斯平滑估计具有两个独立块变量的函数的一阶和二阶偏导数。然后，在随机逼近算法框架中使用这些估计来解决双层优化问题，并建立其非渐近收敛分析。据我们所知，这是第一次为完全随机零阶双层优化算法建立样本复杂度界限。

Mar, 2024

本文提出了一种新的完全单循环和免除海森矩阵的算法框架，用于随机双层优化，并在标准光滑性假设下提出了更紧密的分析，进而展示了算法的普遍性。

Jun, 2023