Double Momentum Method for Lower-Level Constrained Bilevel Optimization

最近，由于双层优化（BO）能够捕捉这些问题中固有的嵌套结构，因此在许多机器学习应用中得到了广泛应用。最近，许多超梯度方法已被提出作为解决大规模问题的有效解决方案。然而，当前用于下层约束双层优化（LCBO）问题的超梯度方法需要非常严格的假设，即最优性条件满足可微性和可逆性条件，并缺乏收敛速度的可靠分析。更糟糕的是，现有方法要求进行双层循环更新，有时效率较低。为了解决这个问题，在本文中，我们提出了一个新的LCBO超梯度，利用非光滑隐函数定理的理论而不是使用严格的假设。此外，我们提出了一种基于双动量方法和自适应步长方法的“单循环单时间尺度”算法，并证明它可以在$\tilde{\mathcal{O}}(d_2^2\epsilon^{-4})$次迭代中返回一个$(\delta, \epsilon)$-稳定点。两个应用程序的实验表明了我们提出的方法的有效性。

解决问题：论文旨在解决下限约束双层优化（LCBO）问题的超梯度方法需要很多限制性假设的问题，以及缺乏收敛速率的可靠分析的问题。

关键思路：论文提出了一种新的超梯度方法，利用非光滑隐式函数定理的理论，而不是使用限制性假设。此外，提出了一种基于双动量方法和自适应步长方法的单循环单时间尺度算法，并证明它可以在$\tilde{\mathcal{O}}(d_2^2\epsilon^{-4})$次迭代中返回一个$(\delta, \epsilon)$-稳定点。

其他亮点：论文的实验结果表明了所提出方法的有效性。实验中使用了两个应用程序，并且论文提供了开源代码。此外，论文提出的方法也有很大的推广价值，值得进一步深入研究。

相关研究：最近在这个领域中，也有许多相关的研究，如“Bilevel Optimization: A Review and Directions for Future Research”和“Efficient hypergradient computation for deep learning”等。