Paradigm of Bi-level Optimization
本文调研了双层优化问题的解决范式，对两种popular的基于梯度的方法——AID、ITD作出介绍与总结。最后，本文对如何利用bilevel optimization解决sim2real问题难点作出梳理。
本调研的motivation来自于sim2real问题——借助少量的仿真数据，如何找到一组仿真器参数$\phi$，在该组参数下的仿真数据上训练一个异常检测模型，将会在现实数据中有较好的效果——这可以类比于一个超参数调优问题。
1. Formulation of Bilevel Optimization
双层优化问题的形式一般定义为
$$ \begin{array}{rl} \min & \Phi(\boldsymbol{x}):=f(\boldsymbol{x}, \boldsymbol{y}^{\star}) \\ \text { s.t. } & \boldsymbol{y}^{\star}=\underset{\boldsymbol{y}}{\arg \min } g\left(\boldsymbol{x}, \boldsymbol{y}\right) \\ \text { var. } & \boldsymbol{x}, \boldsymbol{y}, \end{array} $$
在双层优化中，一个优化问题嵌入或嵌套在另一个问题中。外部优化问题被称为上层优化问题，而内部优化问题被称作下层优化问题，$\boldsymbol{x}, \boldsymbol{y}$ 分别为上下层的优化变量。双层优化问题的解决范式包括以下两类：
Double Loop / gradient-based：内外层问题分别根据其问题特性（可微、平滑、凸等），采用不同的优化方法，两个问题的解通过超梯度串联起来，以寻找一个全局的（渐进）最优解。这类方法可以概括为“启发式”——有方向的迭代，一般来说给一个初始可行解然后按照实际问题确定一个下降方向，不断搜索直到gap满足精度要求，但这里必须注意，启发式算法很有可能得到的不是最优解，一定要对结果进行论证。
- 此类范式的方法包括：approximate implicit differentiation (AID)、iterative differentiation (ITD)，这两类方法均为基于梯度的方法。
Single Loop / constrain-based：在这种方法中，下层优化问题可以视为是上层优化问题的约束，因此双层优化也可以视为约束优化的特殊情况。这类方法可以概括为“解析式”——接算出解析节，这种方法的逻辑大都使用KKT，对偶，罚函数等将双层规划转化成单层，然后利用单层的方法求解。
- 解决带约束优化的方法包括但不限于：Karush–Kuhn–Tucker（KKT，KKT条件表现为拉格朗日和互补约束，并将整体双层优化问题简化为单级约束优化问题），Penalty Function Methods等[1]。
[1] Sinha, A., Malo, P., & Deb, K. (2017). A review on bilevel optimization: From classical to evolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22(2), 276-295.
2. Gradient-based iterative methods
Single Loop / constrain-based 方法往往涉及大量约束因此难以在机器学习任务中应用。在下文中，将对两种 Double Loop / gradient-based 的方法——AID / ITD作出总结。主要的formulation参考下文：
Ji, K., Yang, J., & Liang, Y. (2021, July). Bilevel optimization: Convergence analysis and enhanced design. In International conference on machine learning (pp. 4882-4892). PMLR.
这两种算法均涉及到一个概念：hyper-gradient（超梯度） link
- 梯度（gradient）：在一个基于梯度的优化问题中，优化目标对模型参数的梯度，被称为 basic gridient，简称为梯度
- 超梯度（hyper-gridient）：在上述的优化问题中，将优化目标对优化过程的超参数（如 learning rate, momentum, regularization parameters, etc.）求梯度，则称为超梯度。
在双层优化中，待优化的参数往往是内层优化问题的变量（如模型参数），而外层优化问题的变量一般为算法超参数（如模型超参），因此这里称：外层优化目标对外层变量的梯度——超梯度。超梯度的复杂度分析可以参考下文
Grazzi, R., Franceschi, L., Pontil, M., & Salzo, S. (2020, November). On the iteration complexity of hypergradient computation. In International Conference on Machine Learning (pp. 3748-3758). PMLR.
🌟 AID 和 ITD 的不同之处在于，他们计算超梯度的方法不同，因此使用了不同的近似方法
⬇️ 一些有用的链接
https://github.com/JunjieYang97/stocBiO
2.1 Approximate Implicit Differentiation (AID)
AID方法的核心是：用一个近似值来代替隐微分（implicit differentitation），以构造超梯度。AID的超梯度计算公式为：
$$ \nabla \Phi\left(x_k\right)=\nabla_x f\left(x_k, y^{*}\left(x_k\right)\right)-\nabla_x \nabla_y g\left(x_k, y^{*}\left(x_k\right)\right) v_k^{*} $$
其中 $v_k^{*}$ 是下面的线性系统 $\nabla_y^2 g\left(x_k, y^{*}\left(x_k\right)\right) v=\nabla_y f\left(x_k, y^{*}\left(x_k\right)\right)$ 的解。以上是超梯度的原始计算公式。AID的求解思路如下：
- 利用 $N-step$ 的 conjugate-gradient (CG) 方法来求解线性系统的解 $v_k^N$。
- 将上述解 $v_k^N$ 和内层的最近一次的迭代解 $y_k^T$ 带入上述的超梯度公式，得到超梯度的近似值，即：
$$ \nabla \Phi\left(x_k\right)=\nabla_x f\left(x_k, y_k^T\right)-\nabla_x \nabla_y g\left(x_k, y_k^T\right) v_k^N $$
⚠️ Note：注意——上式中的最后一项 Jacobian-vector product 可以通过自动微分求出，因此上式可以被计算。
2.2 Iterative Differentiation (ITD)
ITD方法的核心是：超梯度的近似值具有一个解析形式，该解析形式可以通过迭代的方式求出。ITD的超梯度计算公式为：
$$ \nabla \Phi\left(x_k\right)=\frac{\partial f\left(x_k, y^{*}\left(x_k\right)\right)}{\partial x_k} $$
其近似估计为$\frac{\partial f\left(x_k, y_k^D\left(x_k\right)\right)}{\partial x_k}$，而该梯度存在下述的解析形式，因此可以被计算：$$ \begin{aligned} \frac{\partial f\left(x_{k}, y_{k}^{D}\right)}{\partial x_{k}}= & \nabla_{x} f\left(x_{k}, y_{k}^{D}\right)-\alpha \sum_{t=0}^{D-1} \nabla_{x} \nabla_{y} g\left(x_{k}, y_{k}^{t}\right) \\ & \times \prod_{j=t+1}^{D-1}\left(I-\alpha \nabla_{y}^{2} g\left(x_{k}, y_{k}^{j}\right)\right) \nabla_{y} f\left(x_{k}, y_{k}^{D}\right) \end{aligned} $$
2.3 Other Methods
基于梯度的方法，其精髓就在于计算超梯度的方式，这里还列出一些不属于上述范式的方法，有空可以看看
Franceschi, L., Donini, M., Frasconi, P., & Pontil, M. (2017, July). Forward and reverse gradient-based hyperparameter optimization. In International Conference on Machine Learning (pp. 1165-1173). PMLR.
3. 利用双层优化解sim2real问题的难点
简要梳理：AID ITD分别是两种借助超梯度进行内外层优化串联的方法，但在实际计算的过程中对外层优化问题仍有诸多限制，如：smoothness, twice differentiability and an invertible Hessian。
对比domain randomization可以发现，DR问题的外层优化问题依然是不可微的[1]。解决这类不可微问题，常用的转换思路有
- 用非梯度算法：贝叶斯优化、RL
- 将 non-smooth 问题近似成 smooth 的问题来求解，这样就可以用大部分的 bilevel 的工作
因此，利用双层优化问题解DR问题的难点在于——如何解不可微优化问题 或 如何转换不可微问题为可微问题。这也是下一篇survey的调研重点。
[1] Ruiz, N., Schulter, S., & Chandraker, M. Learning To Simulate. In International Conference on Learning Representations, 2019.