D2L 11 优化算法

优化和深度学习

经验风险是训练数据集的平均损失，而风险则是整个数据群的预期损失

深度学习优化存在许多挑战。其中一些最令人烦恼的是局部最小值、鞍点和梯度消失

鞍点（saddle point）是指函数的所有梯度都消失但既不是全局最小值也不是局部最小值的任何位置

凸性

定义

1. 凸集

   简单地说，如果对于任何 $a，b∈X$，连接 a 和 b 的线段也位于 X 中，则向量空间中的一个集合 X 是凸（convex）的

2. 凸函数

   给定一个凸集 X，如果对于所有 $x,x′∈X$ 和所有 $λ∈[0,1$，一个函数 $f:X→R$ 是凸的，我们可以得到

   $$\lambda f(x)+(1-\lambda) f\left(x^{\prime}\right) \geq f\left(\lambda x+(1-\lambda) x^{\prime}\right)$$

3. 琴森不等式（Jensen’s inequality）

   $$\sum_{i} \alpha_{i} f\left(x_{i}\right) \geq f\left(\sum_{i} \alpha_{i} x_{i}\right) \text { and } E_{X}[f(X)] \geq f\left(E_{X}[X]\right)$$

   换句话说，凸函数的期望不小于期望的凸函数

性质

1. 局部最小值就是全局最小值。证明通过反证法，假设存在更小值，则与局部最小值矛盾

2. 水平集与凸函数。对于凸函数定于如下集合

   $$\mathcal{S}_{b}:=\{x \mid x \in \mathcal{X} \text { and } f(x) \leq b\}$$

   可以证明该集合是凸集，也称其为水平集。证明也很简单，直接按照定义进行证明：集合内任意两点连线上的所有的点都在集合内

3. 凸性和二阶导数。Hessian 矩阵半正定与凸函数是等价的，当然还要二阶可微的条件

约束

这里需要更多凸优化的知识…暂略

凸约束可以通过拉格朗日函数来添加。在实践中，只需在目标函数中加上一个惩罚就可以了

投影映射到凸集中最接近原始点的点

梯度下降

多元梯度下降

多元泰勒展开的一阶公式

$$f(\mathbf{x}+\boldsymbol{\epsilon})=f(\mathbf{x})+\boldsymbol{\epsilon}^{\top} \nabla f(\mathbf{x})+\mathcal{O}\left(\|\boldsymbol{\epsilon}\|^{2}\right)$$

使用一阶近似函数，只需要沿着梯度的负方向走合适的步长，就能够使得函数值下降

$$\mathbf{x} \leftarrow \mathbf{x}-\eta \nabla f(\mathbf{x})$$

牛顿法

多元泰勒展开的二阶公式

$$f(\mathbf{x}+\boldsymbol{\epsilon})=f(\mathbf{x})+\boldsymbol{\epsilon}^{\top} \nabla f(\mathbf{x})+\frac{1}{2} \boldsymbol{\epsilon}^{\top} \nabla^{2} f(\mathbf{x}) \boldsymbol{\epsilon}+\mathcal{O}\left(\|\boldsymbol{\epsilon}\|^{3}\right)$$

其中，定义海森矩阵 Hessian Matrix

$$\mathbf H = \nabla^{2} f(\mathbf{x})$$

对于关于 ε 的二次函数，我们可以直接求得其极值，直接求导为零

$$\nabla f(\mathbf{x})+\mathbf{H} \boldsymbol{\epsilon}=0 \text { and hence } \boldsymbol{\epsilon}=-\mathbf{H}^{-1} \nabla f(\mathbf{x})$$

牛顿法在凸问题中速度很快，但在非凸问题中显得不那么好用

因为在牛顿法中，我们最终将除以 Hessian。 这意味着如果二阶导数是负的，函数的值可能会趋于增加。 这是这个算法的致命缺陷！

随机梯度下降

在深度学习中，目标函数通常是训练数据集中每个样本的损失函数的平均值

如果使用梯度下降法，则每个自变量迭代的计算代价为 O(n)，它随 n 线性增长。因此，当训练数据集较大时，每次迭代的梯度下降计算代价将较高

在随机梯度下降的每次迭代中，我们对数据样本随机均匀采样一个索引 i，其中 i∈{1,…,n}，并计算梯度以更新 x

小批量随机梯度下降

随机梯度下降的“统计效率”与大批量一次处理数据的“计算效率”之间存在权衡。小批量随机梯度下降提供了两全其美的答案：计算和统计效率

事实上我们可能会问：假设有足够的硬件条件，batch size 真的越大越好吗？通常来讲 batch size 是训练网络的一个重要超参数，而 batch size 并不是越大越好，CSDN

较大的 batch size 容易使模型收敛在局部最优点，而使用 mini batch，甚至单个数据训练时，相当于人为给训练加入了噪声，使模型走出局部最优（鞍点），从而在更大的范围内寻找收敛点

这也是为什么使用更大的 batch size 往往会采用更大的学习率的原因之一，帮助走出局部最优

动量法

使用动量 Momentum 替代梯度，参数更新方程如下

$$\begin{array}{l} \mathbf{v}_{t} \leftarrow \beta \mathbf{v}_{t-1}+\mathbf{g}_{t, t-1} \\ \mathbf{x}_{t} \leftarrow \mathbf{x}_{t-1}-\eta_{t} \mathbf{v}_{t} \end{array}$$

• 动量法用过去梯度的平均值来替换梯度，这大大加快了收敛速度
• 动量法可以防止在随机梯度下降的优化过程停滞的问题
• 由于对过去的数据进行了指数降权，有效梯度数为1 / (1 - β)

如果了解指数加权移动平均 EWMA，能够很快地理解这个平均的概念，EWA 的更新公式如下

$$\begin{array}{l} \mathbf{v}_{t} \leftarrow \beta \mathbf{v}_{t-1}+ (1 - \beta)\mathbf{g}_{t, t-1} \\ \end{array}$$

从 pytorch 中对 SGD 的介绍来看，是使用的教材中的更新公式，如需要类似 EWA 的功能可设置 dampening 参数

这里再补充一下对于 EWMA 的理解，来自 沐神 ppt。下面这个展开式就完全告诉我们加权体现在什么地方

AdaGrad

更新公式如下

$$\begin{aligned} \mathbf{g}_{t} &=\partial_{\mathbf{w}} l\left(y_{t}, f\left(\mathbf{x}_{t}, \mathbf{w}\right)\right) \\ \mathbf{s}_{t} &=\mathbf{s}_{t-1}+\mathbf{g}_{t}^{2} \\ \mathbf{w}_{t} &=\mathbf{w}_{t-1}-\frac{\eta}{\sqrt{\mathbf{s}_{t}+\epsilon}} \cdot \mathbf{g}_{t} \end{aligned}$$

这里我将采用 cs231n 中做的笔记

Added element-wise scaling of the gradient based on the historical sum of squares in each dimension

AdaGrad 能够对梯度的每一维进行缩放，该优化方法能够解决 zigzag 前进问题，我们不希望走陡峭的路径，而是想走到更平滑的全局最优点，对于稀疏特征比较有效。但我们通常不使用该方法，理由：随着不断地更新，累计量 $s_t$ 会越来越大，步长变短可能过于迅速，这对于非凸问题来说是不合适的

RMSProp

RootMeanSquareProp 更新公式如下

$$\begin{array}{l} \mathbf{s}_{t} \leftarrow \gamma \mathbf{s}_{t-1}+(1-\gamma) \mathbf{g}_{t}^{2} \\ \mathbf{x}_{t} \leftarrow \mathbf{x}_{t-1}-\frac{\eta}{\sqrt{\mathbf{s}_{t}+\epsilon}} \odot \mathbf{g}_{t} \end{array}$$

既然累计量不合适，那么就采取平均量来对梯度的每一维进行缩放。采用 EWA 平均再合适不过了，因为 EWA 平均在实现上非常简单，代码简洁且空间复杂度低

Adam

现在我们要将 RMSProp 和 Momentum 结合起来，其实二者一个是对方向的平滑/平均，另一个是对模的平滑/平均

$$\begin{array}{l} \mathbf{v}_{t} \leftarrow \beta_{1} \mathbf{v}_{t-1}+\left(1-\beta_{1}\right) \mathbf{g}_{t} \\ \mathbf{s}_{t} \leftarrow \beta_{2} \mathbf{s}_{t-1}+\left(1-\beta_{2}\right) \mathbf{g}_{t}^{2} \end{array}$$

我们同时更新动量/一阶矩 $v_t$ 和二阶矩 $s_t$（随机变量 x 的 n 阶矩为 $E[x^n]$）。当 t 比较小的时候，一阶矩和二阶矩会与其估计出现较大的偏差，在更新通过以下式子进行修正

$$\hat{\mathbf{v}}_{t}=\frac{\mathbf{v}_{t}}{1-\beta_{1}^{t}} \text { and } \hat{\mathbf{s}}_{t}=\frac{\mathbf{s}_{t}}{1-\beta_{2}^{t}}$$

最后更新参数，注意 ε 是在根号外面的，与 RMSProp 不同，在实践中效果略好，深层原因不明…

$$\mathbf{g}_{t}^{\prime}=\frac{\eta \hat{\mathbf{v}}_{t}}{\sqrt{\hat{\mathbf{s}}_{t}}+\epsilon} \\ \mathbf{x}_{t} \leftarrow \mathbf{x}_{t-1}-\eta_{t} \mathbf{g}_{t}^{\prime}$$

可以看 pytorch 上的 Adam 文档，其算法流程也写的很清楚

学习率调度器

用与时间相关的学习率 $η(t)$ 取代 $η$ 增加了控制优化算法收敛的复杂性，通常学习率会随着时间衰减，常用以下衰减策略：

1. 分段常数

2. 指数衰减

3. 多项式衰减

4. 余弦衰减

   $$\eta_{t}=\eta_{T}+\frac{\eta_{0}-\eta_{T}}{2}(1+\cos (\pi t / T))$$

5. 先预热后衰减，在 OpenPCDet 中遇到的 one cycle policy，参考链接：CSDN-深度学习优化策略—-优化器的学习率调节one cycle policy

补充：信息论基础

TODO