BDA for Bilevel Optimization
Published:
Paper Reading: A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton.
Introduction and Motivation
文章[1]考虑如下的双层优化问题，
\[\begin{align*} \min_{x \in \mathbb{R}^{d_x},y \in Y^*(x)} f(x,y) \quad {\rm s.t.} \quad Y^*(x) = \arg \min_{y \in \mathcal{Y}} g(x,y) \end{align*}\]其中 $\mathcal{Y} \subseteq \mathbb{R}^{d_y}$ 是一个紧集。 我们定义如下的hyper-objective
\[\begin{align*} \varphi(x) = \min_{y \in Y^*(x)} f(x,y), \quad {\rm s.t.} \quad Y^*(x) = \arg \min_{y \in \mathcal{Y}} g(x,y) \end{align*}\]则问题可以转化为关于 $\min_x \varphi(x)$ 的单层优化问题。
注意到给定$x$, 对于$\varphi(x)$ 的估计实际上是一个关于 $y$ 的简单双层优化问题 。利用 [2] 的结论，使用如下的聚合算法
\[\begin{align*} y_{k+1}(x) = y^k(x) - \alpha_k \nabla_y f(x,y_k(x)) - (1-\alpha_k) \nabla_y g(x,y_k(x)) \end{align*}\]可以使得当 $k \rightarrow \infty$ 的时候成立
\[\begin{align*} g(x,y_k(x)) \rightarrow g^*(x) \rightarrow 0, \quad f(x,y_k(x)) \rightarrow \varphi(x) \end{align*}\]根据上述发现，文章提出利用上述算法得到的 $y_K(x)$ 定义如下的函数序列
\[\begin{align*} \varphi_K(x) = f(x,y_K(x)) \end{align*}\]作为最终想要优化的目标 $\varphi(x)$ 的一个有效近似。在实际使用中，选取一个较大的 $K$， 使用Pytorch等自动求导框架可以计算得到 $\varphi_K(x)$ 的导数，从而对其进行梯度下降。下面将对该算法提供理论保证。
Theoretical Investigation
本节给出文章的理论保证。如果得到序列
\[\begin{align*} x_k \in \arg \min_x f(x,y_k(x)). \end{align*}\]那么可以证明如果序列 ${ x_k}$ 存在极限点 $\bar x$, 那么成立 $\bar x \in \arg \min_x \varphi(x)$.
Proof of LL Problem
本节我们对内层算法进行分析，我们证明
\[\begin{align*} g(x,y_k(x)) \rightarrow g^*(x) \quad \Rightarrow \quad {\rm dist}(y_k(x),Y^*(x)) \rightarrow 0. \end{align*}\]下面我们首先证明如果 $y_k(x) \rightarrow \bar y$, 那么该极限点 $ \bar y$ 一定属于 $Y^\ast(x)$.
根据 $g$ 的连续性，对于任意给定的 $\epsilon>0$, 存在 $\delta_1$，使得对于任意的 $\Vert y - \bar y \Vert \le \delta_1$ 都成立 $ \vert g(x,\bar y) - g(x,y) \vert \le \delta_1 $.
而对于 $\delta_1$, 存在 $K_1$, 使得对于任意的$k \ge K_1$ 都有 $ \Vert y_k - \bar y \Vert \le \delta_1$. 因此对于任意的 $x$ 都有
\[\begin{align*} g(x,\bar y) \le g(x,y_k(x)) + \epsilon, \quad \forall k \ge K_1. \end{align*}\]根据假设 $g(x,y_k(x)) \rightarrow g^\ast(x)$, 存在 $K_2$， 使得对于任意的 $k \ge K_2$ 都有 $\vert g(x,y_k) - g^\ast(x) \vert \le \epsilon$. 因此对于任意的 $x$ 都有
\[\begin{align*} g(x,\bar y) \le g(x,y_k(x)) + \epsilon \le g^*(x) + 2 \epsilon, \quad \forall k \ge \max(K_1,K_2). \end{align*}\]由于 $\epsilon$ 的任意性，我们证明了 $\bar y \in Y^\ast(x)$, 换句话说成立 $ {\rm dist}(\bar y, Y^\ast(x)) = 0$.
下面我们用反证法证明所需要的结论。
假设该结论不成立那么存在 $\epsilon>0$, 使得对于任意的 $k$, 都存在 $i(k) \ge K$ 使得 $ {\rm dist}(y_{i(k)}(x),Y^\ast(x)) \ge \epsilon$.
我们选取 ${y_k }$ 的一个收敛子列 ${y_{j}}$, 记其极限点为 $\bar y$, 也即 $y_j \rightarrow \bar y$.
由于 $y_j \rightarrow \bar y$, 那么对于任意给定的 $\epsilon>0$ 都存在 $K_3$ 使得对于任意的 $k \ge K_3$ 都有 $ \Vert y_j - \bar y \Vert \le \epsilon/2 $, 由于距离函数是一个 1-Lipschitz 函数，那么
\[\begin{align*} {\rm dist} (y_j, Y^*(x)) = \vert {\rm dist} (y_j, Y^*(x)) - {\rm dist} (\bar y, Y^*(x))\vert \le \epsilon/2, \quad \forall j \ge K_3. \end{align*}\]可是我们又知道 ${\rm dist} (y_{i(K_3)}(x), Y^\ast(x)) \ge \epsilon$, 这就导出了矛盾。
Proof of UL Problem
如果 $y_k(x_k)$ 不收敛的话我们总可以找到一个收敛的子列，所以不妨设 $y_k(x_k)$ 收敛于极限点 $\bar y$,
根据上文类似的证明我们可以推出 $\bar y \in Y^\ast(\bar x)$, 详细的分析过程如下。
根据 $g$ 的连续性，对于任意给定的 $\epsilon>0$, 存在 $\delta_1$，使得对于任意的 $\Vert y - \bar y \Vert \le \delta_1$ 和 $\Vert x - \bar x\Vert \le \delta_1$ 都成立 $ \vert g(\bar x,\bar y) - g(x,y) \vert \le \delta_1 $.
而对于 $\delta_1$, 存在 $K_1$, 使得对于任意的$k \ge K_1$ 都有 $ \Vert y_k(x_k) - \bar y \Vert \le \delta_1$. 和 $\Vert x_k - \bar x \Vert \le \delta_1$, 因此
\[\begin{align*} g(\bar x,\bar y) \le g(x_k,y_k(x_k)) + \epsilon, \quad \forall k \ge K_1. \end{align*}\]根据假设 $g(x,y_k(x)) \rightarrow g^\ast(x)$, 存在 $K_2$, 使得对于任意的 $k \ge K_2$ 都有 $\vert g(x,y_k) - g^\ast(x) \vert \le \epsilon$. 因此
\[\begin{align*} g(\bar x,\bar y) \le g(x_k,y_k(x_k)) + \epsilon \le g^*(x_k) + 2 \epsilon, \quad \forall k \ge \max(K_1,K_2). \end{align*}\]可以由 $g$ 的连续性来推出 $g^\ast(x)$ 的连续性，那么存在 $\delta_2$, 使得对于任意的 $ \Vert x - \bar x\Vert \le \delta_2$ 都有 $ \vert g^\ast(x) - g^\ast(\bar x) \vert \le \epsilon $.
根据 $x_k \rightarrow \bar x$, 存在 $K_3$, 使得对于任意的 $ k\ge K_3$ 都有 $ \Vert x_k - \bar x \Vert \le \delta_2 $, 因此
\[\begin{align*} g(\bar x, \bar y) \le g^*(x_k) + 2 \epsilon \le g^*(\bar x) + 3 \epsilon, \quad \forall k \ge K_3. \end{align*}\]由于 $\epsilon$ 的任意性，我们证明了 $\bar y \in Y^\ast(\bar x)$.
根据 $f$ 的连续性以及 $ (x_k,y_k(x_k)) \rightarrow (\bar x, \bar y)$, 因此对于任意的 $\epsilon>0$ 都存在 $K_4$ 使得
\[\begin{align*} \varphi(\bar x) = \min_{y \in Y^*(\bar x)} f(\bar x,y) \le f( \bar x, \bar y) \le f(x_k , y_k(x_k)) + \epsilon, \quad \forall k \ge K_4. \end{align*}\]由于 $x_k = \arg \min_{x} f(x,y_k(x))$， 因此对于任意的 $x$ 都有
\[\begin{align*} \varphi(\bar x) \le f(x_k,y_k(x_k)) + \epsilon \le f(x,y_k(x)) + \epsilon, \quad \forall k \ge K_4. \end{align*}\]根据 $f(x,y_k(x)) \rightarrow \varphi(x)$, 存在 $K_5$ 使得对于任意的$x$ 都有
\[\begin{align*} \varphi(\bar x) \le \varphi(x) + 2 \epsilon, \quad \forall k \ge \max(K_4,K_5). \end{align*}\]最后由于 $\epsilon$ 的任意性，令 $\epsilon \rightarrow 0 $ 就可以得到 $\bar x \in \arg \min_x \varphi(x)$.
Improving Existing LLS Theories
本文的理论对于内层函数没有强凸但是 $Y^*(x) = {y^\ast(x) }$ 为单点集的情况也具有指导意义。
此时相同的结论仍然满足，但是算法以及证明可以被简化。
这时候考虑的优化问题形式为
\[\begin{align*} \min_{x \in \mathbb{R}^{d_x}} f(x,y^*(x)) \quad {\rm s.t.} \quad y^*(x) = \arg \min_{y \in \mathcal{Y}} g(x,y) \end{align*}\]只要对内层函数使用加速梯度下降 (AGD) 等算法，可以保证 $g(x,y_k(x)) \rightarrow g^\ast(x) $.
根据之前相同的分析，这蕴含着 $ {\rm dist}(y_k(x), y^\ast(x)) \rightarrow 0 $.
基于此，我们选取
\[\begin{align*} x_k = \arg \min_{x} f(x,y_k(x)). \end{align*}\]假设 $x_k \rightarrow \bar x$, 可以证明 $\bar x \in \arg \min_x \varphi(x)$.
如果 $y_k(x_k)$ 不收敛的话我们总可以找到一个收敛的子列，所以不妨设 $y_k(x_k)$ 收敛于极限点 $\bar y$.
根据上文相同的分析，我们知道 $\bar y = y^\ast(\bar x)$.
根据 $f$ 的连续性以及 $(x_k,y_k(x_k)) \rightarrow (\bar x, \bar y)$，对于任意的 $\epsilon>0$, 存在 $K_1$ 使得
\[\begin{align*} \varphi(\bar x) = f(\bar x,y^*(\bar x)) = f(\bar x,\bar y) \le f(x_k,y_k(x_k)) + \epsilon, \quad k \ge K_1. \end{align*}\]根据 $x_k = \arg \min_x f(x,y_k(x))$, 对于任意的 $x$ 都有
\[\begin{align*} \varphi(\bar x) \le f(x_k,y_k(x_k)) + \epsilon \le f(x,y_k(x)) + \epsilon, \quad k \ge K_1. \end{align*}\]根据 $f$ 的连续性，存在 $\delta_1$, 使得对于任意的 $ \Vert y - y ‘ \Vert \le \delta $ 都有 $\vert f(x,y) - f(x,y’) \vert \le \epsilon$,
由于对于任意的 $x$ 都成立 $ {\rm dist}(y_k(x), y^\ast(x)) \rightarrow 0 $， 那么存在 $K_2$ 使得对于任意的 $k \ge K_2$ 都有 $\Vert y_k(x_k) - y^\ast(x_k) \Vert \le \delta_1$
因此那么对于任意的$x$ 都有
\[\begin{align*} \varphi(\bar x) \le f(x,y_k(x)) + \epsilon \le f(x,y^*(x)) = \varphi(x), \quad K \ge \max( K_1,K_2). \end{align*}\]最后由于 $\epsilon$ 的任意性，令 $\epsilon \rightarrow 0 $ 就可以得到 $\bar x \in \arg \min_x \varphi(x)$.
Reference
[1] A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton. In ICML, 2020.
[2] A first order method for solving convex bilevel optimization problems. SIAM Journal on Optimization, 2017.