基于压缩架构的结构化演化以实现可扩展策略优化

经典的演化算法很难解决高纬问题。然而，Salimans等人的研究表明黑盒优化算法在机器人控制任务可展现与RL相媲美的性能。同时，演化策略拥有相对简单性、通用性、以及并行化的特点，因此对它的研究又产生了兴趣。Krzysztof等人利用结构化随机正交矩阵进行梯度近似，从而学习出了一个可快速训练和快速推理的策略。确切的说，作者们做出了两种创新：

• 结构化探索：实验与理论证明随机正交拟Monte-Carlo有限微分方向比随机化高斯方向的探索方式更有效。
• 压缩策略：通过在策略架构上实施参数共享，可在不损失精确率的情况降低问题的维度。

对于该策略的并行化，感兴趣的同学，可进一步阅读论文。

高斯平滑与Monte-Carlo梯度估计

首先，作者们引入了对目标函数高斯平滑的概念
$$
\begin{aligned}
F_{\sigma}(\theta)=\mathbb{E}_{\epsilon\sim\mathcal{N}(0,I)}[F(\theta+\sigma\epsilon)] \\
=(2\pi)^{-\frac{d}{2}}\int_{\mathbb{R}^d}F(\theta+\sigma\epsilon)e^{-\frac{1}{2}\Vert\epsilon\Vert_2^2}d\epsilon
\end{aligned}\tag{1}
$$
式(1)中$\sigma$用于平滑参数，$d$为参数的维度或参数量。$F_{\sigma}$是通过沿着高斯方向扰动$F$，再取估计的均值获得。正式的说，即使$F$不可微分，$F_{\sigma}$也可微分，即$F_{\sigma}$处处可微分。同时，$F_{\sigma}$用于$F$的所有特性。$F$与$F_{\sigma}$之间的欧式距离属于点级别有界的。因此，利用$F_{\sigma}$替换$F$属于合理的，可见式(2)
$$
\begin{aligned}
\underset{\theta\in\mathbb{R}^{d}}{max} F_{\sigma}(\theta)
\end{aligned}\tag{2}
$$
平滑后问题的最优值为原始问题的下界。尽管平滑后问题的最优参数与原始问题的最优参数相近不存在理论上保证，但是平滑后问题的最优解决方案为更平滑的解，从而产生更鲁棒性的解。

高斯平滑的梯度估计

$F_{\sigma}$的梯度为
$$
\begin{aligned}
\nabla F_{\sigma}(\theta)=\frac{1}{\sigma}\mathbb{E}_{\epsilon\sim\mathcal{N}(0,I)}[F(\theta+\sigma\epsilon)\epsilon] \\
=(2\pi)^{-\frac{d}{2}}\int_{\mathbb{R}^d}F(\theta+\sigma\epsilon)e^{-\frac{1}{2}\Vert\epsilon\Vert_2^2}\epsilon d\epsilon
\end{aligned}\tag{3}
$$
实践中，梯度是无法计算，需要基于Monte-Carlo方法估计，作者们探索了三种估计器

原始ES梯度估计器：根据REINFORCE算法的Monte-Carlo估计器，梯度估计为
$$
\begin{aligned}
\hat{\nabla}^{V}_{N}F_{\sigma}(\theta)=\frac{1}{N\sigma}\sum_{i=1}^N F(\theta+\sigma\epsilon_i)\epsilon_i
\end{aligned}\tag{4}
$$
式(4)中$(\epsilon_i)_{i=1}^N\stackrel{\mathrm{iid}}{\sim}\mathcal{N}(0,1)$可被解释为参数探索方向，即通过参数空间的扰动进行探索。

对偶ES梯度估计器：利用对偶变量增强原始ES梯度估计器
$$
\begin{aligned}
\hat{\nabla}^{AT}_{N}F_{\sigma}(\theta)=\frac{1}{2N\sigma}\sum_{i=1}^{N}(F(\theta+\sigma\epsilon_i)\epsilon_i-F(\theta-\sigma\epsilon_i)\epsilon_i)
\end{aligned}\tag{5}
$$
式(5)中$(\epsilon_i)_{i=1}^N\stackrel{\mathrm{iid}}{\sim}\mathcal{N}(0,1)$。

前向有限微分ES梯度估计器：对原始ES梯度估计器引入控制变量，即为
$$
\begin{aligned}
\hat{\nabla}^{FD}_{N}F_{\sigma}(\theta)=\frac{1}{N\sigma}\sum_{i=1}^N(F(\theta+\sigma\epsilon_i)-F(\theta))\epsilon_i
\end{aligned}\tag{6}
$$
式(6)中$(\epsilon_i)_{i=1}^N\stackrel{\mathrm{iid}}{\sim}\mathcal{N}(0,1)$。该估计器可被视为原始ES梯度估计器迁移了一个常量。

在统计与计算效率方面，以上每个估计器均不比其它两个估计器更有优势。为了比较以上估计器，作者们把它们视为独立同分布的估计器，进行了如下相关分析。

基于正交的拟Monte-Carlo探索降低方差

为了提升梯度估计器的质量，作者们引入了关于探索方向$(\epsilon_i)_{i=1}^N$联合分布的明智选择。确切的说，作者们以对偶ES估计器为例，研究了探索方法。

高斯正交探索

为了参数探索，作者们对高斯扰动施加了正交条件，对应的估计器如下：

定义1: 高斯平滑对偶ES梯度估计器的正交中心化FD估计量为
$$
\begin{aligned}
\hat{\nabla}_N^{AT,ort}F_{\sigma}(\theta)=\frac{1}{2N\sigma}\sum_{i=1}^N(F(\theta+\sigma{\epsilon}'_i){\epsilon}'_i-F(\theta-\sigma{\epsilon}'_i){\epsilon}'_i)
\end{aligned}\tag{7}
$$
式(7)中$({\epsilon}'_i)_{i=1}^N$的边缘分布为$\mathcal{N}(0,I)$，联合分布为：若$N\le d$，那么向量是正交的。若$N>d$，那么每个连续的$d$个向量是正交，且$d$个向量构成的集合之间属于独立关系。

以上探索方式，对于$N\le d$可被编码为一个结构化随机矩阵。其中，“结构化”意味着随机矩阵的行向量之间无依赖关系，可通过堆叠探索方向${\epsilon}'_{i}$获得。作者们把其命名为高斯正交矩阵，用$G_{ort}$表示。

研究结果表明，对梯度估计的不同方向施加精确的正交，可获得对应独立同分布梯度估计器更低的MSE。

离散正交探索

通过利用正交探索方向可了解到梯度估计器的统计提升，接下来作者们探讨了计算方面的提升。在高斯正交探索下，优化步骤中每次迭代需要计算史密斯正交化，该步骤需要大量的计算。然而，在压缩的神经网络策略场景下，参数量少于100，因此正交化的计算复杂度并不高，且能学习出较好的策略。

即使对于高纬问题，也可以利用正交探索方向的优势，且不增加高的正交化计算成本。确切的说，可利用扰动方向的边缘高斯分布集合$\{d_1,\ldots,d_N\}$替换正交向量$\{{\epsilon}'_1,\ldots,{\epsilon}'_N\}$，其中$d_i^T$为结构化离散随机矩阵$M_{struct}\in\mathbb{R}^{N\times d}$的第$i$行。换句话说，利用无正交初始化就可构建的结构化随机矩阵替换$G_{rot}$，且拥有相似的特性。

同时，作者们还给出了矩阵$M_{struct}\in\mathbb{R}^{N\times d}$的例子，详情可见论文。

Quasi Monte-Carlo探索

除此之外，作者们也提出了QMC近似，对式(3)的积分构建梯度估计器。QMC技术构建了数值积分的一家族方法，把该积分转换为单位立方体的积分问题，利用点集$S$近似
$$
\begin{aligned}
\int_{[0,1]^d}f(x)dx\approx\frac{1}{\vert S\vert}\sum_{w\in S}f(w)
\end{aligned}\tag{8}
$$
在QMC近似中，点集$S$为低差异序列，与随机点集Monte-Carlo积分相比，可提供更快的拟合。其中，“差异”式指点集不均匀的度量。构建低差异序列点集的方法有很多方法，作者们利用了Halton序列。

学习压缩策略

深度神经网络的参数量大，对资源受限的硬件仍然不可行。因此，作者们利用参数共享结构，即在权重矩阵上施加Toeplitz结构。一个$n\times n$的Toeplitz矩阵有常量的对角，可通过快速傅立叶变换执行快速矩阵向量乘积。同时，Toeplitz矩阵系列可泛化到低秩矩阵，从而进行更复杂的容量-精度-时间平滑。

相关思考

本篇论文，作者们对演化算法的探索方法进行了研究，并设计了一个高效的性能优越的算法。本质上来说，利用正交信息无关的知识，改进了探索。