Optimization in Deep Learning.

本文目录：

1. 深度学习中的优化问题
2. 基于梯度的优化算法
3. 常用的梯度下降算法
4. 其他优化算法

1. 深度学习中的优化问题

深度学习中的优化(optimization)问题通常是指在已有的数据集上实现最小的训练误差(training error)。记深度网络的待优化参数为$\theta$，包含$N$个训练样本$x$的数据集为$X$，损失度量为$l(x;\theta)$；则损失函数定义为：

优化问题建模为寻找使得损失函数为全局最小(global minima)的参数$\theta^*$:

在实践中，优化深度网络存在以下困难：

1. 网络结构多样性：深度网络是高度非线性的模型，网络结构的多样性阻碍了构造通用的优化方法；网络通常含有比较多的参数，难以优化。
2. 非凸优化：深度网络的损失函数是高维空间的非凸函数，其损失曲面存在大量局部极小(local minima)和鞍点(saddle point)，这些点也满足梯度为$0$。 目前常用的优化方法大多数是基于梯度的，因此在寻找损失函数的全局最小值点的过程中，有可能会落入局部极小值点或鞍点上。

注：鞍点是指梯度为$0$但是Hessian矩阵不是半正定的点。

目前深度学习中的优化问题尚没有通用的解决方法，有许多工作尝试给出优化过程和损失函数的直觉解释：

• Deep Ensembles: A Loss Landscape Perspective：通过随机初始化训练一系列模型，使每个模型都收敛到不同的局部极小值，将这些模型集成起来对最终的结果有很大的提升。
• Implicit Gradient Regularization：梯度下降过程会在损失函数中隐式地引入损失梯度的梯度惩罚项，具有正则化模型的效果。
• Every Model Learned by Gradient Descent Is Approximately a Kernel Machine：使用梯度下降优化的深度学习模型近似于使用路径核的核方法构造的模型。
• Identifying and attacking the saddle point problem in high-dimensional non-convex optimization：极小值点要求在特征的每个维度上都是极小点，这种情况概率比较低。在实践中，损失曲面上大部分梯度为零的点都是鞍点。
• The Loss Surfaces of Multilayer Networks：在非常大的神经网络中，大部分局部极小点和全局最小点是近似的；因此在训练神经网络时，通常没有必要找全局最小点，这反而可能过拟合。
• Visualizing the Loss Landscape of Neural Nets：由于深度网络的参数非常多且有一定的冗余性，每个参数对总损失的影响非常小。这使得损失函数在局部极小点附近通常是一个平坦的区域，即平坦最小值(flat minima)而不是尖锐最小值(sharp minima)，如下图所示。这使得模型收敛于局部极小值时更加robust，即微小的参数变动不会剧烈地影响模型能力。

2. 基于梯度的优化算法

深度学习中的优化问题通常用梯度下降(Gradient Descent, GD)算法求解，它是一种一阶近似方法。将神经网络的参数为$θ$初始化为$θ_0$，对损失函数$l(θ)$在$θ_0$处进行一阶Taylor展开：

注意到若使损失函数$l(θ)$减小，需要满足：

当梯度$\nabla_{\theta} l(θ_0)$大于零时，应该减小$\theta$；当梯度$\nabla_{\theta} l(θ_0)$小于零时，应该增大$\theta$。综上所述，应该沿梯度$\nabla_{\theta}$的负方向更新参数。

在执行梯度下降时需要指定每次计算梯度时所使用数据的批量(batch) $\mathcal{B}$ 和学习率(learning rate) $\gamma$。若记第$t$次参数更新时的梯度为$g_t=\frac{1}{|\mathcal{B}|}\sum_{x \in \mathcal{B}}^{}\nabla_{\theta} l(θ_{t-1})$，则参数更新公式：

(1) 超参数的选择

① 超参数 batch size

损失函数$L(\theta)$是在整个训练集上定义的，因此计算更新梯度时需要考虑所有训练数据。这种方法称为全量梯度下降，此时batch size为整个训练集大小：$|\mathcal{B}|=N$。

通常训练数据的规模比较大，如果梯度下降在整个训练集上进行，需要比较多的计算资源；此外大规模训练集中的数据通常非常冗余。因此在实践中，把训练集分成若干批次(batch)的互补的子集，每次在一个子集上计算梯度并更新参数。这种方法称为小批量梯度下降(mini batch gradient descent)，此时$|\mathcal{B}|<N$。

特别地，把每个数据看作一个批次，对应batch size=1时，称为随机梯度下降(stochastic gradient descent, SGD)，此时$|\mathcal{B}|=1$。

每一批量数据的梯度都是总体数据梯度的近似，由于mini batch的数据分布和总体的分布有所差异，并且batch size越小这种差异越大；因此batch size越小，则梯度近似误差的方差越大，引入的噪声就越大，可能导致训练不稳定。

② 超参数 learning rate

学习率$\gamma$决定了梯度下降时的更新步长。学习率太大，可能会使梯度更新不收敛甚至发散(diverge)；学习率太小，导致收敛速度慢。

③ 选择超参数

学习率$\gamma$和批量大小$|\mathcal{B}|$的选择可以参考以下工作：

• Don't Decay the Learning Rate, Increase the Batch Size：在训练模型时通过增加批量大小替代学习率衰减，在相同的训练轮数下能够取得相似的测试精度，但前者所进行的参数更新次数更少，并行性更好，缩短了训练时间。
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour：学习率的线性缩放规则(linear scaling rule)：当批量大小增大$k$倍时，学习率也增大$k$倍，并保持其它超参数不变。学习率的warmup：训练开始时使用较小的学习率。
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima：较大的批量使网络倾向于收敛到尖锐极小值(sharp minima)，从而导致较差的泛化性。

(2) 从不同角度理解梯度下降

① 动力学角度

把神经网络建模为一个动力系统(dynamical system)，则梯度下降算法描述了参数$\theta$随时间(即梯度更新轮数)的演化情况。该动力系统的规则是参数$\theta$的变化率为损失函数的梯度$g=\nabla_{\theta}l(θ)$的负值：

该动力系统是一个保守动力系统，因此它最终可以收敛到一个不动点($\dot \theta = 0$)，并可以进一步证明该稳定的不动点是一个极小值点。求解上述常微分方程ODE可以采用欧拉解法（该方法是指将方程$dy/dx=f(x,y)$转化为$y_{n+1}-y_n≈f(x_n,y_n)h$）。因此有：

上式即为梯度下降算法的更新公式。对于小批量梯度下降，其每一批量上损失函数的梯度是总损失函数的梯度的近似估计，假设梯度估计的误差服从方差为$\sigma^2$的正态分布，则相当于在动力系统中引入高斯噪声：

该系统用随机微分方程SDE描述，称为朗之万方程。该方程的解可以用平衡状态下的概率分布描述：

从上式中可以看出，当$\sigma^2$越大时，$P(\theta)$越接近均匀分布，此时参数$\theta$可能的取值范围也越大，允许探索更大比例的参数空间。当$\sigma^2$越小时，$P(\theta)$的极大值点(对应$l(\theta)$的极小值点)附近的区域越突出，则参数$\theta$落入极值点附近。在实践中，batch size越小，则参数$\sigma^2$越大。

② 逼近角度

深度学习问题的优化函数$f(x)$通常是复杂的非线性函数，优化的目的是求其全局最小值。根据逼近理论，在函数$f(x)$上的任意一点$x_n$，可以用一条近似的曲线逼近原函数。如果近似的曲线容易求得最小值，则可以用该最小值近似替代原函数的最小值。

注意到所求极值为最小值，因此在$x_n$处采用一个开口向上的抛物线$g(x)$近似替代原函数曲线$f(x)$：

该抛物线$g(x)$具有如下特点：

1. $g(x)$与原曲线$f(x)$在$x_n$处具有一阶近似，即具有相同的数值和一阶导数。
2. $g(x)$具有容易求得的极小值点$x_n - hf’(x_n)$。

使用$g(x)$的极小值点近似替代原函数$f(x)$的极小值点，即为梯度下降算法的基本形式：

③ 概率角度

从概率视角建模优化问题，记模型当前参数为$\theta$，优化目标为$l(\theta)$，将下一步的更新量$\Delta \theta$看作随机变量。则使得$l(\theta+\Delta \theta)$的数值越小的$\Delta \theta$出现的概率越大，用下面的分布表示：

式中$Z(\theta)$是归一化因子。参数$\alpha>0$调整分布的形状；当$\alpha \to ∞$时，$p(\Delta \theta | \theta)$趋近于均匀分布，参数可以向任意方向变化；当$\alpha \to 0$时，只有使得$l(\theta+\Delta \theta)$最小的$\Delta \theta$对应的概率$p(\Delta \theta | \theta)$不为$0$，因此$\Delta \theta$将选择损失下降最快的方向。

参数的实际更新量可以选择上式的期望：

通常$p(\Delta \theta | \theta)$很难直接求得。假设$l(\theta)$是一阶可导的，由Taylor展开得：

其中梯度$g=\nabla_\theta l(\theta)$。若约束参数更新的步长不超过$\epsilon$，即$||\Delta \theta|| \leq \epsilon$，则概率$p(\Delta \theta | \theta)$表示为：

概率的期望表示为：

假设更新量$\Delta \theta$与梯度$g$的夹角为$\eta$，则$Z(g)$表示为：

上式表示一个高维球体内的积分，由于积分空间具有各向同性，因此该积分只和梯度的模长$||g||$有关，因此将积分$Z(g)$记为$Z(||g||)$，则有：

上式表示参数更新的最佳方向与梯度方向相反，即为梯度下降算法。

3. 常用的梯度下降算法

标准的批量梯度下降方法存在一些缺陷：

• 更新过程中容易陷入局部极小值或鞍点(这些点处的梯度也为$0$)；常见解决措施是在梯度更新中引入动量(如momentum, NAG, Funnelled SGDM)。
• 参数的不同维度的梯度大小不同，导致参数更新时在梯度大的方向震荡，在梯度小的方向收敛较慢；损失函数的条件数(Condition number，指损失函数的Hessian矩阵最大奇异值与最小奇异值之比)越大，这一现象越严重。常见解决措施是为每个特征设置自适应学习率(如RProp, AdaGrad, RMSprop, AdaDelta)。这类算法的缺点是改变了梯度更新的方向，一定程度上造成精度损失。
• 可以结合基于动量的方法和基于自适应学习率的方法，如Adam, AdamW, Adamax, Nadam, AMSGRad, Radam, AdaX, Amos, Lion。这类方法需要同时存储与模型参数具有相同尺寸的动量和方差，通常会占用较多内存，一些减少内存占用的优化算法包括Adafactor, SM3。
• 批量大小难以选择。批量较小时，引入较大的梯度噪声；批量较大时，内存负担较大。在分布式训练大规模神经网络时，整体批量通常较大，训练的模型精度会剧烈降低。这是因为总训练轮数保持不变时，批量增大意味着权重更新的次数减少。常见解决措施是通过层级自适应实现每一层的梯度归一化(如LARS, LAMB, NovoGrad)，从而使得更新步长依赖于参数的数值大小而不是梯度的大小。

在实际应用梯度下降算法时，可以根据截止到当前步$t$的历史梯度信息\(\{g_{1},...,g_{t}\}\)计算修正的参数更新量$h_t$（比如累积动量、累积二阶矩校正学习率等），从而弥补上述缺陷。因此梯度下降算法的一般形式可以表示为：

下面介绍一些常见的基于梯度的优化算法，部分算法的代码实现可参考Pytorch文档。在选择合适的优化器时可参考Descending through a Crowded Valley - Benchmarking Deep Learning Optimizers。

4. 其他优化算法

⚪ Averaging Weights Leads to Wider Optima and Better Generalization：随机权重平均 SWA

随机权重平均是指在梯度下降过程中累积历史权重的平均值，通常与周期或恒定学习率一起使用。 若学习率变化周期为$c$(对于恒定学习率$c=1$)，当训练轮数$i$每完成一个周期时($\text{mod}(i,c)=0$)，通过已累积的模型数量$n_{\text{model}} = i/c$累积平均权重$w_{\text{SWA}}$：

如果网络存在BatchNorm，则应在训练结束后使用平均权重$w_{\text{SWA}}$对数据额外进行一次前向传播，从而计算每一层神经元的相关统计量。

使用Pytorch实现SWA：

dataloader, optimizer, model, loss_fn = ...
swa_model = torch.optim.swa_utils.AveragedModel(model)
scheduler = torch.optim.lr_scheduler.CosineAnnealingLR(optimizer, T_max=300)
swa_start = 160  # 从160轮开始累积权重
swa_scheduler = torch.optim.swa_utils.SWALR(
    optimizer, anneal_strategy="linear", anneal_epochs=5, swa_lr=0.05)
# SWALR在每轮的前5次更新内将学习率线性退火到0.05并保持恒定

for epoch in range(300):
    for input, target in dataloader:
        optimizer.zero_grad()
        loss_fn(model(input), target).backward()
        optimizer.step()
    if epoch > swa_start:
        swa_model.update_parameters(model)
        swa_scheduler.step()
    else:
        scheduler.step()
    
torch.optim.swa_utils.update_bn(dataloader, swa_model)  # 更新bn参数
preds = swa_model(test_input)  # 测试数据

在实践中，也可以累积权重的指数滑动平均值(exponential moving average, EMA, 也称Polyak averaging):

ema_avg = lambda averaged_model_parameter, model_parameter, num_averaged:\
        0.1 * averaged_model_parameter + 0.9 * model_parameter
ema_model = torch.optim.swa_utils.AveragedModel(model, avg_fn=ema_avg)

⚪ Gradientless Descent: High-Dimensional Zeroth-Order Optimization：不计算梯度的零阶优化方法

零阶优化泛指不需要梯度信息的优化方法。可以通过采样和差分这两种方法来估计参数更新的方向，从而省略梯度的计算。

基于差分的零阶优化是指通过采样求得梯度的近似表示：

其中$\epsilon$是小正数；$p(u)$是具有零均值和单位协方差矩阵的分布，通常用标准正态分布。通过上述估计梯度可以更新参数。

基于采样的零阶优化是一种参数搜索方法。其基本思路是给定采样分布$\mathcal{D}$和参数初始值$x_0$，在第$t$轮循环中设置一个标量半径$r_t$，从以$x_t$为中心的分布$r_t\mathcal{D}$中采样$y_t$。如果$f(y_t)<f(x_t)$，则更新$x_{t+1}=y_t$；否则$x_{t+1}=x_t$。

尽管零阶优化中的采样分布是固定的(通常选择均匀分布)，可以在算法的每次迭代中选择采样半径$r_t$。如简单地通过二分搜索设置一系列半径：

⚪ Gradients without Backpropagation：使用前向梯度代替反向传播梯度

本文提出了一种基于方向导数的梯度计算方法，通关单次前向传播同时计算损失函数值和前向梯度(forward gradient)。前向梯度 $g:\Bbb{R}^{n} \to \Bbb{R}^{n}$定义为：

其中$\theta \in \Bbb{R}^{n}$是计算梯度的参数点，$v \in \Bbb{R}^{n}$是从多元标准正态分布中采样的干扰向量$v\text{~}\mathcal{N}(0,I)$，$\nabla f(\theta)\cdot v \in \Bbb{R}$表示在$\theta$点指向$v$的方向导数，可以在单次前向传播中计算得到。

前向梯度$g(\theta)$是真实梯度$\nabla f(\theta)$的无偏估计。使用前向梯度代替反向传播计算的梯度，可以实现仅依赖单次前向传播的前向梯度下降(forward gradient descent, FGD)算法，从而省去反向传播过程。

⚪ Lookahead: 快权重更新k次,慢权重更新1次

lookahead迭代地更新两组权重：慢权重 $\phi$ 和快权重 $\theta$。快权重 $\theta$是通过任意一种标准优化算法$A$进行更新的；慢权重 $\phi$是通过在参数空间$\theta-\phi$中进行线性插值得到的；快权重每经过$k$次更新后，慢权重更新$1$次。

lookahead算法相比于直接使用优化器更新$k$次，运算操作数变为$O(\frac{k+1}{k})$倍。当快权重沿低曲率方向进行更新时，慢权重通过参数插值平滑振荡，实现快速收敛。当快权重在极小值附近探索时，慢权重更新将推向一个测试精度更高的区域。

⚪ Data Echoing: 通过buffer加速模型训练

在深度学习模型流水线中，通常上游任务（数据预处理）是在CPU上进行的，而下游任务（深度学习任务）是在GPU上进行的；模型对一批数据进行预处理的时间要长于使用数据进行学习的时间；

data echoing将预处理的数据放入一个buffer中，使用数据更新参数时从这个buffer直接或再进行一些处理来获得一个批量的数据；不断从buffer中采样直到upstream处理好了一批新的数据，更新buffer。

⚪ 参考文献

• A Direct Adaptive Method for Faster Backpropagation Learning: The RPROP Algorithm：(ICNN 1993)RProp：一种快速反向传播学习的直接自适应方法。
• ADADELTA: An Adaptive Learning Rate Method：(arXiv1212)Adadelta：一种自适应学习率方法。
• On the importance of initialization and momentum in deep learning：(ICML 2013)Nesterov Momentum：一种动量梯度更新方法。
• Adam: A Method for Stochastic Optimization：(arXiv1412)Adam：自适应矩估计。
• Incorporating Nesterov Momentum into Adam：(ICLR 2016)Nadam：将Nesterov动量引入Adam算法。
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour：(arXiv1706)大批量分布式训练的线性缩放规则和warmup。
• Large Batch Training of Convolutional Networks：(arXiv1708)LARS：层级自适应学习率缩放。
• Don't Decay the Learning Rate, Increase the Batch Size：(arXiv1711)通过增加批量大小代替学习率衰减。
• Averaging Weights Leads to Wider Optima and Better Generalization：(arXiv1803)SWA：通过随机权重平均寻找更宽的极小值。
• Adafactor: Adaptive Learning Rates with Sublinear Memory Cost：(arXiv1804)Adafactor：减少Adam的显存占用。
• Memory-Efficient Adaptive Optimization：(arXiv1901)SM3：内存高效的自适应优化算法。
• On the Convergence of Adam and Beyond：(arXiv1904)AMSGrad：改进Adam算法的收敛性。
• Large Batch Optimization for Deep Learning: Training BERT in 76 minutes：(arXiv1904)LAMB：结合层级自适应学习率与Adam。
• Stochastic Gradient Methods with Layer-wise Adaptive Moments for Training of Deep Networks：(arXiv1905)NovoGrad：使用层级自适应二阶矩进行梯度归一化。
• Lookahead Optimizer: k steps forward, 1 step back：(arXiv1907)Lookahead：快权重更新k次，慢权重更新1次。
• Faster Neural Network Training with Data Echoing：(arXiv1907)Data Echoing：一种加速模型训练的方法。
• On the Variance of the Adaptive Learning Rate and Beyond：(arXiv1908)Radam：修正Adam算法中自适应学习率的早期方差。
• Gradientless Descent: High-Dimensional Zeroth-Order Optimization：(arXiv1911)高维参数空间中的零阶优化方法。
• Deep Ensembles: A Loss Landscape Perspective：(arXiv1912)探讨深度集成学习的损失曲面。
• AdaX: Adaptive Gradient Descent with Exponential Long Term Memory：(arXiv2004)AdaX：基于指数长期记忆的自适应梯度下降。
• Descending through a Crowded Valley - Benchmarking Deep Learning Optimizers：(arXiv2007)对不同深度学习优化器的基准测试。
• Implicit Gradient Regularization：(arXiv2009)隐式梯度正则化。
• Every Model Learned by Gradient Descent Is Approximately a Kernel Machine：(arXiv2012)使用梯度下降优化的深度学习模型近似于核方法。
• Step-size Adaptation Using Exponentiated Gradient Updates：(arXiv2202)基于指数梯度更新的步长自适应学习率。
• Gradients without Backpropagation：(arXiv2202)使用前向梯度代替反向传播。
• Amos: An Adam-style Optimizer with Adaptive Weight Decay towards Model-Oriented Scale：(arXiv2210)Amos：一种面向模型的自适应权重衰减的Adam风格优化器。
• Symbolic Discovery of Optimization Algorithms：(arXiv2302)优化算法的符号发现。