8 A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton 笔记

文献阅读笔记

文献简介

• 文献地址：https://arxiv.org/abs/2006.04045
• 文献发布于2020年6月

ps：发现06/10的版本有两处书写错误：

• (9)式上面有个”We”写成了”W e”
• 5.2节最后一段方法名字写错了…”BAD”

阅读笔记——文章主题整理

这篇文章研究的对象是双边优化Bi-Level问题，记为BLP。该类问题虽然早就被提出，但最近一段时间，各种深度学习的应用、元学习中都开始使用它作为目标函数。它的一般形式如下：

ps：我喜欢的Meta-Weight-Net的目标也属于此类问题

$$\min_\limits{x\in \mathcal{X}} F(x,y),\ s.t.\ y\in\mathcal{S}(x),\ where\ \mathcal{S}(x):=\arg\min_\limits{y}f(x,y).$$

传统的方法是交替迭代优化的方法，但是它们能针对的是上述双边优化问题中的一小类，即条件中的$y$是单一解，而一般双边优化中$y$可以有多解。当底层优化条件退化为单一解时，这个条件定义为LLS(Lower-Level Singleton)。那么有LLS条件的双边优化问题形式为：

ps：查阅百度、谷歌、wiki均未查到此LLS，应该是本文先这样称谓

$$\min_\limits{x\in \mathcal{X}} F(x,y),\ s.t.\ y=\arg\min_\limits{y}f(x,y).$$

定义名称，高层优化问题为upper level，底层为lower level，分别记为UL问题和LL子问题。那么传统方法不细说，就是我了解的那种交替迭代，放张Meta-Weight-Net的图自行体会吧🤭：

那么传统方法不行啊，因为一般LLS条件是不满足的（文中举了反例并实验验证），研究一般的双边优化问题更有意义。传统方法不好的原因是UL和LL问题中的变量是相互依存的，直接梯度方法交替迭代不能考虑这种联系，因此理论上不能完全保证收敛正确，一旦不满足LLS条件就会螺旋升天。

基于此提出BDA方法，即Bi-level Descent Aggregation，基本思想就是集合UL和LL问题中变量的联系，力图解决一般的BLP问题。BDA方法的理论我还不完全明白，因为其中包含了很多优化领域的名词、条件，这个暂时没时间一一理解；索性思想是可以明白的，因此大致介绍BDA方法如下：

• 一般的BLP问题可以写成single-level model：

$$\min_\limits{x\in \mathcal{X}} \varphi(x),\ with\ \varphi(x):=\inf_\limits{y\in \mathcal{S}(x)}F(x,y).$$

• 那么当有数据观测$x$（固定$x$）时，上述问题简化为：

$$\min_\limits{y} F(x,y),\ s.t.\ y\in \mathcal{S}(x).$$

• 那么LL子问题中$y$的更新要同时考虑$x$与$y$的联系：

$$y_{k+1}(x)=\tau_k (x,y_k(x)),\ k=0,\cdots,K-1.$$

其中$\tau_k (x,\cdot)$是更新策略，可以自行调整，且需要初始化$y_0=\tau_0(x)$。这个更新策略要求考虑$x$与$y$的联系！

• BLP问题的UL更新转化为：

$$\min_\limits{x\in\mathcal{X}} \varphi_K(x):=F(x,y_K(x)).$$

• 其实就是这么个小东西$\tau$需要很多条件支撑，证明内容也很多

  ps：文中表示这些条件不像LLS难以满足，这些条件都是正常的一般条件，易满足

最终的反例，数据标签重学，元学习的实验结果表示，这个BDA方法很棒：

• 比对比用的RHG(Reverse Hyper-Gradient)方法普遍效果更好，也很稳定
• 关键是不受LLS条件约束，不会收敛到虚假的极小
• 在LL子问题的序列长度$K$增大时效果更强

阅读的不足之处：

这次笔记没有直接翻译，读了之后按自己的理解捋了一遍。但是其实和翻译差不到哪去…有个问题是只知道BDA方法的改进思想是结合UL和LL问题中变量的相关信息，但不知道理论上究竟为何$\tau$就能成功