08.网络优化算法

文档摘要

网络优化深度学习中的优化算法在这里建立了基于梯度的优化算法的基本分析框架，并讨论了它如何应用在深度学习中。 Gradient descent 1. Formalizing the Taylor Expansion Descent lemma for gradient descent Stochastic gradient descent Accelerated Gradient Descent Local Runtime Analysis of GD Pre-conditioners 梯度下降（GD）假设我们现在想要找出一个多元连续函数 ![[公式]](https://www.zhihu.com/equation?tex=f%28%5Comega%29) 的最小值 !

网络优化

深度学习中的优化算法

在这里建立了基于梯度的优化算法的基本分析框架，并讨论了它如何应用在深度学习中。

Gradient descent
1. Formalizing the Taylor Expansion
2. Descent lemma for gradient descent
Stochastic gradient descent
Accelerated Gradient Descent
Local Runtime Analysis of GD
Pre-conditioners

梯度下降（GD）

假设我们现在想要找出一个多元连续函数 $f(\omega)$ 的最小值 $\min _{w \in \mathbb{R}^{d}} f(w)$

梯度下降算法是这样的： $\begin{aligned} w_{0} &=\text { initializaiton } \\ w_{t+1} &=w_{t}-\eta \nabla f\left(w_{t}\right) \end{aligned}$ ，其中 $\eta$ 称为步长或学习率。

设计出GD算法的一个核心思想就是找出局部最陡的梯度下降方向 $-\nabla f\left(w_{t}\right)$

我们来考虑该点的泰勒展开式： $f(w)=f\left(w_{t}\right)+\underbrace{\left\langle\nabla f\left(w_{t}\right), w-w_{t}\right\rangle}_{\text {linear in } w}+\cdots$

假设我们去掉高阶项，只在 $w_{t}$ 的一个邻域内优化一阶近似式，即 $\begin{array}{c}\underset{w \in \mathbb{R}^{d}}{\arg \min } f\left(w_{t}\right)+\left\langle\nabla f\left(w_{t}\right), w-w_{t}\right\rangle \\ \text { s.t. }\left\|w-w_{t}\right\|_{2} \leq \epsilon\end{array}$ ，它的最优解是 $w+\delta$ ，其中 $\delta=-\alpha \nabla f\left(w_{t}\right)$

泰勒展开的形式化

我们下面来陈述一个引理，它刻画了GD算法下函数值的下降。我们先假设函数 $f(w)$ 的二阶梯度是有界的，即 $\nabla^{2} f(w) \in [-L,L] \,\,\,\,\forall w$ ，我们称满足这个条件的函数为L-光滑函数。

$\begin{array}{l}\text { Definition}\left(L \text { -smoothness). } \text { A function } f: \mathbb{R}^{n} \rightarrow \mathbb{R} \text { is called } L \text { -smooth iffor all } x, y \in \mathbb{R}^{n}\right. \text { , the following inequality } \\ \text { holds: } \\ \qquad\|\nabla f(x)-\nabla f(y)\| \leq L\|x-y\| . \\ \text { If the function } f \text { is } L \text { -smooth, then for all } x, y \in \mathbb{R}^{n} \\ \qquad f(y) \leq f(x)+\langle\nabla f(x), y-x\rangle+\frac{L}{2}\|y-x\|^{2} . \\ \text { Next, if } f \text { is additionally convex and } x^{*} \text { is its minimizer, then for all } x \in \mathbb{R}^{d} \\ \qquad\|\nabla f(x)\|^{2} \leq 2 L\left(f(x)-f\left(x^{*}\right)\right)\end{array}$

这使我们能够在下面这个意义上使用泰勒展开精确的近似函数： $f(w) \leq f\left(w_{t}\right)+\left\langle\nabla f\left(w_{t}\right), w-w_{t}\right\rangle+\frac{L}{2}\left\|w-w_{t}\right\|_{2}^{2}$

GD的下降引理

下面我们将说明，在下降梯度和足够小的学习率下，函数值总是减小，除非迭代处的梯度为零。

$\begin{array}{l}\text { Lemma (Descent Lemma). Suppose } f \text { is } L \text { -smooth. Then, if } \eta< \\ 1 /(2 L), \text { we have } \\ \qquad f\left(w_{t+1}\right) \leq f\left(w_{t}\right)-\frac{\eta}{2} \cdot\left\|\nabla f\left(w_{t}\right)\right\|_{2}^{2}\end{array}$

证明：

随机梯度下降（SGD）

Motivation：损失函数的梯度的计算代价可能很大。

在深度学习里，目标函数通常是训练数据集中有关各个样本的损失函数的平均。设 $f_i(\boldsymbol{x})$ 是有关索引为i的训练数据样本的损失函数，n是训练数据样本数， $\boldsymbol{x}$ 是模型的参数向量，那么目标函数定义为

$f(\boldsymbol{x}) = \frac{1}{n} \sum_{i = 1}^n f_i(\boldsymbol{x}).$

目标函数在 $\boldsymbol{x}$ 处的梯度计算为

$\nabla f(\boldsymbol{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla f_i(\boldsymbol{x}).$

如果使用梯度下降，每次自变量迭代的计算开销为 $\mathcal{O}(n)$ ，它随着n线性增长。因此，当训练数据样本数很大时，梯度下降每次迭代的计算开销很高。

随机梯度下降（stochastic gradient descent，SGD）减少了每次迭代的计算开销。在随机梯度下降的每次迭代中，我们随机均匀采样的一个样本索引 $i\in\{1,\ldots,n\}$ ，并计算梯度 $\nabla f_i(\boldsymbol{x})$ 来迭代 $\boldsymbol{x}$ ：

$\boldsymbol{x} \leftarrow \boldsymbol{x} - \eta \nabla f_i(\boldsymbol{x}).$

这里 $\eta$ 同样是学习率。可以看到，每次迭代的计算开销从梯度下降的 $\mathcal{O}(n)$ 降到了常数 $\mathcal{O}(1)$ 。值得强调的是，随机梯度 $\nabla f_i(\boldsymbol{x})$ 是对梯度 $\nabla f(\boldsymbol{x})$ 的无偏估计：

$E_i \nabla f_i(\boldsymbol{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla f_i(\boldsymbol{x}) = \nabla f(\boldsymbol{x}).$

这意味着，平均来说，随机梯度是对梯度的一个良好的估计。

加速梯度下降（AGD）

让我们考虑一个输入和输出分别为二维向量 $\boldsymbol{x} = [x_1, x_2]^\top$ 和标量的目标函数 $f(\boldsymbol{x})=0.1x_1^2+2x_2^2$ 。

可以看到，同一位置上，目标函数在竖直方向（ $x_2$ 轴方向）比在水平方向（ $x_1$ 轴方向）的斜率的绝对值更大。因此，给定学习率，梯度下降迭代自变量时会使自变量在竖直方向比在水平方向移动幅度更大。那么，我们需要一个较小的学习率从而避免自变量在竖直方向上越过目标函数最优解。然而，这会造成自变量在水平方向上朝最优解移动变慢。

学习率调得稍大一点，此时自变量在竖直方向不断越过最优解并逐渐发散。

动量法的提出是为了解决梯度下降的上述问题。设时间步t的自变量为 $\boldsymbol{x}_t$ ，学习率为 $\eta_t$ 。在时间步0，动量法创建速度变量 $\boldsymbol{v}_0$ ，并将其元素初始化成0。在时间步t>0，动量法对每次迭代的步骤做如下修改：

$\begin{split}\begin{aligned} \boldsymbol{v}_t &\leftarrow \gamma \boldsymbol{v}_{t-1} + \eta_t \boldsymbol{g}_t, \\ \boldsymbol{x}_t &\leftarrow \boldsymbol{x}_{t-1} - \boldsymbol{v}_t, \end{aligned}\end{split}$

其中，动量超参数 $\gamma$ 满足 $0 \leq \gamma < 1$ 。当 $\gamma=0$ 时，动量法等价于小批量随机梯度下降。

指数加权移动平均：为了从数学上理解动量法，让我们先解释一下指数加权移动平均（exponentially weighted moving average）。给定超参数 $0 \leq \gamma < 1$ ，当前时间步t的变量 $y_t$ 是上一时间步t-1的变量 $y_{t-1}$ 和当前时间步另一变量 $x_t$ 的线性组合：

$y_t = \gamma y_{t-1} + (1-\gamma) x_t.$

我们可以对 $y_t$ 展开：

$\begin{split}\begin{aligned} y_t &= (1-\gamma) x_t + \gamma y_{t-1}\\ &= (1-\gamma)x_t + (1-\gamma) \cdot \gamma x_{t-1} + \gamma^2y_{t-2}\\ &= (1-\gamma)x_t + (1-\gamma) \cdot \gamma x_{t-1} + (1-\gamma) \cdot \gamma^2x_{t-2} + \gamma^3y_{t-3}\\ &\ldots \end{aligned}\end{split}$

令 $n = 1/(1-\gamma)$ ，那么 $\left(1-1/n\right)^n = \gamma^{1/(1-\gamma)}$ 。因为

$\lim_{n \rightarrow \infty} \left(1-\frac{1}{n}\right)^n = \exp(-1) \approx 0.3679,$

所以当 $\gamma \rightarrow 1$ 时， $\gamma^{1/(1-\gamma)}=\exp(-1)$ ，如 $0.95^{20} \approx \exp(-1)$ 。如果把 $\exp(-1)$ 当作一个比较小的数，我们可以在近似中忽略所有含 $\gamma^{1/(1-\gamma)}$ 和比 $\gamma^{1/(1-\gamma)}$ 更高阶的系数的项。例如，当 $\gamma=0.95$ 时，

$y_t \approx 0.05 \sum_{i=0}^{19} 0.95^i x_{t-i}.$

因此，在实际中，我们常常将 $y_t$ 看作是对最近 $1/(1-\gamma)$ 个时间步的 $x_t$ 值的加权平均。例如，当 $\gamma = 0.95$ 时， $y_t$ 可以被看作对最近20个时间步的 $x_t$ 值的加权平均；当 $\gamma = 0.9$ 时， $y_t$ 可以看作是对最近10个时间步的 $x_t$ 值的加权平均。而且，离当前时间步t越近的 $x_t$ 值获得的权重越大（越接近1）。

现在，我们对动量法的速度变量做变形：
$\boldsymbol{v}_t \leftarrow \gamma \boldsymbol{v}_{t-1} + (1 - \gamma) \left(\frac{\eta_t}{1 - \gamma} \boldsymbol{g}_t\right).$
由指数加权移动平均的形式可得，速度变量 $\boldsymbol{v}_t$ 实际上对序列 $\{\eta_{t-i}\boldsymbol{g}_{t-i} /(1-\gamma):i=0,\ldots,1/(1-\gamma)-1\}$ 做了指数加权移动平均。换句话说，相比于小批量随机梯度下降，动量法在每个时间步的自变量更新量近似于将前者对应的最近 $1/(1-\gamma)$ 个时间步的更新量做了指数加权移动平均后再除以 $1-\gamma$ 。所以，在动量法中，自变量在各个方向上的移动幅度不仅取决于当前梯度，还取决于过去的各个梯度在各个方向上是否一致。

本地运行时间分析

当迭代接近局部极小值时，梯度下降行为更为明显，因为该函数可以用二次函数进行局部逼近。因此这里为了简单起见，我们假设我们正在优化一个凸二次函数，并了解函数的曲率如何影响算法的收敛性。

我们用梯度下降方法来优化 $\min _{w} \frac{1}{2} w^{\top} A w$ ，其中 $w \in R^d$ ， $A\in R^{d \times d}$ 是半正定矩阵。
注：w.l.o.g，我们可以假设A是对角矩阵（对角化是线性代数中的一个基本idea）。假设A的SVD分解： $A = U\Sigma U^{T}$ ，其中 $\Sigma$ 是个对角矩阵。我们可以简单的验证得到 $w^{T}Aw = \hat{w}^{T}\Sigma \hat{w}$ ，其中 $\hat{w} = U^{T}w$ 。换句话说，在由U定义的一个不同的坐标系中，我们处理的是一个以对角矩阵 $\Sigma$ 为系数的二次型。注意这里的对角化技术仅用于分析。

因此我们假设 $A = diag(\lambda_{1},\cdots,\lambda_d)$ ，其中 $\lambda_1\geq \lambda_2\geq \cdots \geq \lambda_d$ ，这样该函数就可以化简为 $f(w) = \frac{1}{2} \sum^{d}_{i = 1}\lambda_i w_i^{2}$ ，这样梯度下降更新可以写成： $x \leftarrow w - \eta \nabla f(w) = w-\eta\Sigma w$