优化-5-随机优化

随机优化 Stochastic Optimization

不同于前文所述的优化目标，在随机优化中，我们要最小化期望

$$\min_{x\in \mathbb{R}^d} \mathbb{E}_{\xi\in \Xi} [f(x;\xi)]$$

当 是离散且等概率的时候，我们有

$$\min_{x\in \mathbb{R}^d} \frac{1}{n}\sum_{i=1}^n f(x;\xi_i)$$

在许多机器学习问题中， 可以被视为一个样本，而 可以被视为一个损失函数。因此，在样本集合上的损失函数最小化问题可以被视为一个随机优化问题。不失一般性，在本章中我们研究如何在这样的随机优化问题上进行优化。

随机梯度下降 Stochastic Gradient Descent

算法

类似于梯度下降法，随机梯度下降也是一种迭代算法，唯一的区别在于每次只随机选取一个样本来计算梯度，迭代步骤如下：

• 随机选取一个样本 ，计算梯度

我们记 ，我们称其为随机梯度。需要额外说明的是，在这里， 是一个随机变量。

收敛性

在随机优化的情景下，我们无法直接使用在梯度下降法一章中证明 Vanilla Analysis 所使用的凸性

$$f(x_t) - f(x^*) \leq \langle g_t, x_t - x^* \rangle$$

取而代之，我们需要证明上述不等式在期望上成立。首先我们有

$$\mathbb{E}[g_t|x_t] = \frac{1}{n}\sum_{i=1}^n \nabla f(x_t;\xi_i) = \nabla f(x_t)$$

因此 是对 在 处的梯度 的无偏估计。因此我们有

$$\mathbb{E}[\langle g_t, x_t-x^* \rangle|x_t] = \langle \mathbb{E}[g_t|x_t] , x_t-x^* \rangle = \langle \nabla f(x_t) , x_t-x^* \rangle$$

因此我们得到期望意义下的凸性

$$\mathbb{E}[f(x_t) - f(x^*)] \leq \mathbb{E}[\langle g_t, x_t - x^* \rangle]$$

接下来仿照梯度下降法一章中的证明，我们可以得到，在光滑条件

$$\begin{cases} ||x_0 - x^*|| \leq R \\ ||g_t|| \leq B \end{cases}$$

下，选取 ，随机梯度下降法可以保证

$$\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}[f(x_t)] - f(x^*) \leq \frac{RB}{\sqrt{T}}$$

于是可得收敛率

SGD vs GD

可以看到，在收敛率证明上，SGD 和 GD 几乎是一致的，但是相同的迭代轮数下， GD 往往收敛速度要快于 SGD。这是因为在 Lipschitz Continuity 条件下，两者实质上约束不同

$$\begin{cases} ||\frac{1}{n}\sum_{i=1}^n \nabla f(x;\xi_i)|| \leq B_{GD} & \forall x \\ \frac{1}{n}\sum_{i=1}^n || \nabla f(x;\xi_i)|| \leq B_{SGD} & \forall x \\ \end{cases}$$

由 Jensen 不等式可知， 对于相同的优化目标有 ，因此 SGD 收敛速度要慢于 GD。当选取较大的 mini-batch 时，两者将会非常接近，因此 mini-batch SGD 往往能兼具 GD 和 SGD 的优势。

限制方差

在上一节中，我们发现随机梯度带来的方差会抬高 Lipschitz Continuity 的系数，从而导致收敛速度变慢。mini-batch 是一个很好的办法，随着 batch size 增大，方差会减小，因此 SGD 的收敛速度会变快；但是同样计算量也会增大。有没有办法在不增加计算量的情况下减小方差呢？

SAG/SAGA

SAGA 的想法是，如果我们能用历史信息估计出全梯度，那么我们就可以用全梯度来代替随机梯度，从而减小方差。由光滑性我们知道，相距不远的两点他们的梯度值也应当相近，由此我们可以得到 SAGA 的算法思想：使用一个 cache 来记录每一个 batch 的梯度，在每轮迭代中，计算其中一个 batch 的梯度并更新 cache，然后用 cache 中的梯度的均值作为全梯度的估计。

算法如下：

• S1：随机初始化
• S2：初始化梯度 cache 列表 , 其中第 个元素为
• S3：随机选取 ，计算梯度并更新
• S4：计算全梯度的估计
• S5：应用梯度下降
• S6：回到 S3 直到算法收敛

SVRG

SAG/SAGA 算法确实有着很好的效果，但缺点也很明显，需要大量的空间。目前来看，在数据驱动的大模型上，为每一个 batch 开辟一片空间储存梯度无疑是不可接受的。

SVRG 在此基础上去掉了 cache, 直接使用起点处的全梯度，加上当前位置的随机梯度与起点位置的随机梯度的差，来估计当前位置的全梯度。记录起点处的全梯度为

$$\tilde{\mu} = \frac{1}{n}\sum_{i=1}^n \nabla f(x_0;\xi_i)$$

以及当前和起点位置的随机梯度差

$$\Delta g_i = \nabla f(x_t;\xi_i) - \nabla f(x_0;\xi_i)$$

于是我们有更新公式

$$x_{t+1} = x_t - \gamma_t \left(\Delta g_i + \tilde{\mu} \right)$$

需要说明的是，当 远离 时，梯度估计将变得更不准确，因此算法收敛将会逐渐变难。为了解决这个问题，SVRG 需要在一定步数之后重置算法，即重新选取起点 ，并重新计算 。

动量法

动量法思想是，利用动量使得充满噪声的随机梯度变得光滑。换言之，如果连续的随机梯度都指向同一个方向，那么我们就可以认为这个方向是一个较好的下降方向，此时出现一个相反的随机梯度很可能是噪声。因此，我们可以用一个变量 来记录连续的随机梯度的累积量，并使用 来更新参数，而不是直接使用随机梯度。其迭代公式为：

$$v_{t+1} = \mu v_t + (1-\mu) g_t \\ x_{t+1} = x_t - \gamma v_{t+1}$$

由于动量 是一个关于随机梯度的指数滑动平均，因此为了得到一个无偏的梯度估计量，我们需要除以一个系数 ，即

$$x_{t+1} = x_t - \frac{\gamma}{1-\mu^{t+1}} v_{t+1}$$

随着计算进行，这一系数会趋近于 ，因此一定步数之后可以将其忽略。

特征约束

考虑一个极端的例子

$$f(x) = \frac{1}{2}x^T\begin{bmatrix}100 & 0 \\ 0 & 1\end{bmatrix}x$$

在此情况下，假设 不同维度之间值相同，则梯度将相差 倍。在实际计算时，初始化往往都在 0 附近，如此在计算时将会反复震荡减缓收敛速度。如果我们可以给每个维度加上约束，构造如下迭代式

$$x_{t+1} = x_t - \gamma_t D^{-1}\nabla f(x_t) \\$$

对不同特征进行约束，这样就可以加速收敛。问题在于如何构造 。

AdaGrad

AdaGrad 迭代公式如下：

$$G_{t} = G_t + g_{t-1}g_{t-1}^T \\ x_{t+1} = x_t - \gamma_t \frac{1}{\sqrt{\epsilon+G_{t+1}}}g_t$$

其中 是一个足够小的常数，如 ，防止出现除 错误。在使用 AdaGrad 后，在更平坦的方向上，历史梯度相对更小，因此步长更大，从而自适应地调节不同方向上的步长。

AdaDelta

AdaGrad 中的 会随着迭代不断增大，因此需要一个衰减系数，否则会导致训练过快结束。AdaDelta 使用类似动量法的方式，使用指数滑动平均 。AdaDelta 的迭代公式如下：

$$G_{t} = \rho G_{t-1} + (1-\rho)g_{t-1}g_{t-1}^T \\ x_{t+1} = x_t - \gamma_t \frac{1}{\sqrt{\epsilon+G_{t+1}}}g_t$$

Adam

讲到这里， Adam 的出现就顺理成章了。Adam 无外乎 Momentum 和 AdaDelta 的结合，有如下迭代公式：

$$m_t = \beta_1 m_{t-1} + (1-\beta_1)g_t \\ v_t = \beta_2 v_{t-1} + (1-\beta_2)g_t^2 \\ x_{t+1} = x_t - \gamma_t \frac{\hat{m}_t}{\sqrt{\hat{v}_t+\epsilon}}$$

类似地，训练初期为了取得无偏估计，我们要再乘以一个修正量：

$$\hat{m}_t = \frac{m_t}{1-\beta_1^t} \\ \hat{v}_t = \frac{v_t}{1-\beta_2^t} \\$$

于是我们得到了目前最常用的随机梯度下降算法 adam。