In this paper, we propose the bi-sub-gradient (Bi-SG) method, which is a
generalization of the classical sub-gradient method to the setting of convex
bi-level optimization problems. This is a first-order method that is very easy
to implement in the sense that it requires only a computa
本文主要研究双层优化的一阶算法,目标函数在两个层次上都是光滑但可能非凸的,变量限制在闭凸集合中。首先通过罚函数方法,研究了双层优化的景观,并建立了罚函数与超目标之间的强连接。接着,提出了一阶算法来优化罚函数,以找到一个 ε- 稳定解。在满足小误差近似条件的情况下,算法以 O (ε^{-3}) 和 O (ε^{-7}) 程度的复杂度达到 ε- 稳定点。在随机预言机的额外假设下,算法的实现可以完全使用单循环方式,并分别达到 O (ε^{-3}) 和 O (ε^{-5}) 的优化复杂度。