上篇调研总结了双层优化问题的解决范式，并梳理了双层优化应用在Sim2real的domain randomization（DR）问题上时的难点在于

• 如何解不可微的外层优化问题
• 如何转换不可微的外层优化问题为smooth的

本文将对其中 “不可微问题的求解” 进行调研。

此外本文也将简要介绍一下关于超参优化（hyperparameter optimization，HO）的内容，调研HO问题的原因是：domain randomization与HO问题具有相似的formulation，但二者又存在区别（最重要的区别在于一般的HO问题是differetiable的，DR问题在没有转换为smooth问题之前是不可微的），因此阅读了一些文献并做了简要总结。

1. Formulation of Domain Randomization

回顾DR的formulation如下

$$ \begin{array}{rl} \min & F(\phi, \theta) = \mathcal{L}(\theta^{*};\mathcal{D}_{real}) \\ s.t. & \theta^{*} = \arg\min_{\theta}f(\phi, \theta) = \mathbb{E}_{x \sim P_{\phi}(x)}[\mathcal{L}(\theta;\mathcal{D}_{x})]\\ var. & \phi, \theta \end{array} $$

可以看到，外层优化问题可微但**内层优化函数不可微，** 原因在于：

1. 采样训练数据 $\mathcal{D}_{x}$ 的分布，其参数受控于优化变量$\phi$ 。
2. 一般来讲，从仿真器中生成仿真数据的过程（如从图形渲染引擎中生成图像）不单纯是一个分布采样问题，为保证问题的一般性，这个数据生成过程要被视为不可微。

Ruiz, N., Schulter, S., & Chandraker, M. Learning To Simulate. In International Conference on Learning Representations, 2019.

2. Solving a Nondifferential Problem

一般来说，不可微问题的解决方法有次 梯度法（subgradient）、近端梯度法（Proximal Gradient）。

2.1 Subgradient

次梯度法一般用于求解convex non-smooth问题，本节的主要参考材料为[1]，同时参考了博客[2]

[1] Polyak, B. T. (1978). Subgradient methods: a survey of Soviet research. Nonsmooth optimization, 3, 5-29.

[2] https://blog.csdn.net/zbwgycm/article/details/104507442

次梯度法适用于所有不可微的目标函数，但其收敛速度较慢。

2.1.1 Definition

对于定义在 $\mathbb{R}^n$ 的连续凸函数 $f(x)$ ，当向量 $\partial f(x) \in \mathbb{R}^n $ 满足以下条件时，可被称为函数 $f(x)$ 在 $x$ 点的次梯度

$$ f(x+y) \geq f(x)+(\partial f(x), y), \forall y \in R^{n} $$

注：这里的 $(\cdot,\cdot)$ 应该是向量积的意思，参考[2]中 $f(y) \geq f(x)+g^{T}(y-x)$。可以看出，相比与梯度的定义（等号），上述条件更为松弛。一些次梯度的性质如下[2]

• 次梯度总是出现在定义域 $dom(f)$ 的内部。
• 对于所有 $x \in \mathbb{R}^n$ ，次梯度都存在（但可能不是唯一的）。如果 $f(x)$ 是可微的，则次梯度是唯一的，并且与梯度。各种类型函数的次梯度计算规则是众所周知的。
• 次梯度的定义可以推广到非凸函数中，但 非凸函数的次梯度可能不存在 。

2.1.2 Gradient Decent

类比于梯度下降法，次梯度法只是将其中的梯度替换为次梯度，其他步骤不变，其更新如下：

$$ x_{k+1} = x_{k} - \gamma_{k} \frac{\partial f(x_k)}{\| \partial f(x_k) \|} $$

其中 $\gamma_k$ 为 step size，上式的简洁写法为 $x_{k+1} = x_k - \gamma_k \cdot g_{k-1}$。梯度法和次梯度法之间的主要区别在于，一般来说，方向 $ \partial f(x_k)$ 不是 $x_k$ 处的下降方向，即：**并非严格下降** ；不可微函数的 $f(x_k)$ 的值**不会单调减小**。

2.1.3 Error and Convergence

Convergence rate $O(1/\epsilon^2)$，慢于梯度下降的 $O(1/\epsilon)$ 。$k$ 次迭代后的error level为 $O(1/\sqrt{k})$。

2.2 Proximal Gradient

本节的主要参考材料如下

[1] Schmidt, M., Roux, N., & Bach, F. (2011). Convergence rates of inexact proximal-gradient methods for convex optimization. Advances in neural information processing systems, 24.

[2] https://zhuanlan.zhihu.com/p/82622940

近端梯度法适用于“整体优化目标不可微分，但可以分解为部分可微、部分不可微”的目标函数。对比次梯度法，该方法具有更快的收敛速度和误差。

2.2.1 Problem Statement

近端梯度用于解决一类复合的不可微问题，可以表示如下

$$ \underset{x \in \mathbb{R}^d}{\operatorname{minimize}} f(x):=g(x)+h(x) $$

其中 $g,h$ 均为凸函数（convex），但 $g$ 是 smooth 的，$h$ 为不可微的非smooth项。

2.2.2 Definition

近端梯度算法的基础是以下的近端算子（proximity operator），其定义如下

$$ \operatorname{prox}_L(y)=\underset{x \in \mathbb{R}^d}{\arg \min } \frac{L}{2}\|x-y\|^2+h(x) $$

其中 $L$ 是函数 $g$ 的 Lipschitz 常数。本质上，**近端算子用平滑项 $g$ 的二次近拟定义了变量向最小值的更新方向**。

上式解读：上式的自变量是 $y$，目标是给定一个 $y$，找到使得后面的式子最小化的 $x$。可以看出，由于后面的最小化问题其优化变量是 $x$，因此近端算子的形式与 $h$ 项密切相关。

🌟 对于几种特殊的 $h$ 形式，例如 $l_1$-norm，上面的近端算子是存在解析解的（详见[1]中的参考文献[5, 6]以及知乎文章）。然而，在许多情况下，邻近算子可能没有解析解，或者精确计算该解可能非常昂贵。

2.2.3 Proximal Gradient Descent

借助近端梯度做优化时的参数更新方法如下（generalized form）

$$ x_k=\operatorname{prox}_L\left[y_{k-1}-(1 / L)\left(\nabla g\left(y_{k-1}\right)+e_k\right)\right] $$

其中 $e_k$ 是计算梯度时引入的误差，此外，如果近端算子被不精确求解，$x_k$ 将还存在一个由此导致的误差项 $\epsilon_k$。

上式的一种更容易理解的写法为（basic gradient descent），其中 $t$ 为迭代的步长≥

$$ x_k=\operatorname{prox}_L\left[x_{k-1}-t\nabla g\left(x_{k-1}\right)\right] $$

相比 generalized form，basic gradient descent 取 $y_k = x_k$，在**accelerated proximal-gradient method**中，$y_k=x_k+\beta_k\left(x_k-x_{k-1}\right)$。

2.2.4 Error

$k$ 次迭代后的error level为 $O(1/k)$。accelerated proximal-gradient 的 error level 为 $O(k^2)$。

3. Hyperparameter Optimization

本节内容参考

Bao, F., Wu, G., Li, C., Zhu, J., & Zhang, B. (2021). Stability and generalization of bilevel programming in hyperparameter optimization. Advances in Neural Information Processing Systems, 34, 4529-4541.

HO 问题的formulation可以写为

$$ \begin{array}{rl} \hat{\lambda}\left(S^{t r}, S^{v a l}\right) & \approx \underset{\lambda \in \Lambda}{\arg \min } \hat{R}^{v a l}\left(\lambda, \hat{\theta}\left(\lambda, S^{t r}\right), S^{v a l}\right) \\ \text{where} \quad \hat{\theta}\left(\lambda, S^{t r}\right) & \approx \underset{\theta \in \Theta}{\arg \min } \hat{R}^{t r}\left(\lambda, \theta, S^{t r}\right) \end{array} $$

上式采用约等于符号，是因为：在大多数情况下（例如，神经网络内层优化变量），上式中的内部和外部问题的**全局最优值是难以实现**的。通常情况下，以某种方式（例如，使用（随机）梯度下降）对其进行近似。

🌟注意：HO问题不存在DR问题中所提到的两个阶段，因此大多数可以认为是可微的。且大多数是带约束的优化（如整数约束等）。

HO的解决方法主要分为以下几种：

• Unrolled differentiation：在内外层上执行有限步数的梯度下降。注意：这里的 $\theta$ 相对于 $\lambda$ 是可微的，因此可以使用梯度下降。具体的分析：将内层变量（神经网络参数）视为一个足够大的矩阵，则外层变量（超参）的变化导致的内层变量变化（如神经网络层数变化）可以被视为矩阵与mask的乘积。因此二者存在函数关系 $\theta = g(\lambda)$，这种函数关系是可微的。
• Cross-validation：CV是HO的经典方法。它首先通过 网格搜索 或 随机搜索 获得一组有限的超参数，通常是 $\Lambda$ 的子集。然后，它训练内层问题，以获得给定超参数的相应参数 $\theta$ 。最后，根据验证误差选择最佳 $(\theta^{\star}, \lambda^{\star})$ 对。
• Implicit gradient：隐式梯度方法直接估计外层问题的梯度，这通常涉及一个迭代过程，如共轭梯度、Neumann近似，以估计Hessian矩阵的逆。
• Bayesian optimization：贝叶斯优化将外层问题视为从高斯过程（GP）采样的黑箱函数，并在评估新的超参数时更新GP的后验。
• Hypernetworks：学习在给定超参数的情况下输出近似最优假设的代理函数。