Notes

# 梯度下降优化算法总结

WARNING

UNDER CONSTRUCTION

# 背景

回顾一下，现实中我们有了数据集 D={(x(1),y(1)),⋯,(x(m),y(m))}D = \lbrace(x^{(1)},y^{(1)}),\cdots,(x^{(m)},y^{(m)})\rbrace，也定义了损失函数 ℓ ⁣:Y×Y→R\ell\colon\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}，我们想要寻找一个假设函数 hh（其所有参数由 θ\theta 表示），which 能最小化经验误差：

min⁡θE^(θ;D),where E^(θ;D)=1m∑i=1mℓ(h(x(i);θ),y(i)).\min_\theta \widehat{E}(\theta;D)\text{,}\quad\text{where } \widehat{E}(\theta;D)=\frac{1}{m}\sum_{i=1}^m \ell\mathopen{}\left(h(x^{(i)};\theta), y^{(i)}\right)\mathclose{}.

这个优化问题就可以用梯度下降来解决

θ′=θ−η⋅g\theta^\prime = \theta - \eta\cdot g

其中 η\eta 为学习率 (learning rate)，g=∇θE^(θ)g = \nabla_\theta\widehat{E}(\theta) 为梯度（方便起见，下文将经验误差 E^\widehat{E} 简记为 ff）

假设当前时刻的神经网络权值为 θt\theta_t，经过梯度下降更新后为 θt+1\theta_{t+1}，引入如下标记

  • 原始梯度 gt=∇θf(θt)g_t = \nabla_\theta f(\theta_t)
  • 权值更新量 utu_t（与学习率无关），满足 θt+1=θt−η⋅ut\theta_{t+1} = \theta_t - \eta\cdot u_t

很显然，对于随机梯度下降 (SGD) 来说，ut=gtu_t = g_t，即 θt+1=θt−η⋅gt\theta_{t+1} = \theta_t - \eta\cdot g_t

TODO

  • 一阶动量 mtm_t
  • 二阶动量 vtv_t

full GD vs. mini-batch GD

# 朴素

# 挑战

  • 选择学习率
  • 选择学习率 scheduler
  • 如果数据稀疏或特征频率不同（？），我们想给不常出现的特征更大的 update
  • 局部极小值

# SGD

ut=gtθt+1=θt−η⋅ut.\begin{alignedat}{2} u_t &= g_t \\ \theta_{t+1} &= \theta_t - \eta\cdot u_t. \end{alignedat}

# SGD with momentum

——引入一阶动量

gt=∇θf(θt)m0=g0mt=γ⋅mt−1+gtut=mtθt+1=θt−η⋅ut.\begin{alignedat}{2} \textcolor{#8b959e}{g_t} &\textcolor{#8b959e}{= \nabla_\theta f(\theta_t)} \\ \textcolor{#8b959e}{m_0} &\textcolor{#8b959e}{= g_0} \\ \textcolor{#F26400}{m_t} &= \textcolor{#F26400}{\gamma\cdot m_{t-1}} + g_t \\ u_t &= \textcolor{#F26400}{m_t} \\ \theta_{t+1} &= \theta_t - \eta\cdot u_t. \end{alignedat}

可见一阶动量 mtm_t 即为历史梯度的指数移动平均 (exponential moving average)，其权重 γ\gamma 常取 0.9

  • 优点：有助于加速优化过程（跨过平坦区域，平滑震荡的梯度）
  • 缺点：可能冲出最小值区域，「停不下来」（TODO）

NOTE

上述 SGD with Momentum 的公式为 PyTorch 中的实现方式 (opens new window)，与论文[1]略有不同，其学习率 η\eta 是乘在梯度 gg 上而不是动量 mtm_t 上，即

mt=γ⋅mt−1+η⋅gtθt+1=θt−mt.\begin{alignedat}{2} m_t &= \gamma\cdot m_{t-1} + \eta\cdot g_t \\ \theta_{t+1} &= \theta_t - m_t. \end{alignedat}

对于固定的学习率 η\eta 两者是等价的（对动量权重 γ\gamma 进行缩放即可），而考虑到网络实际训练时往往需要动态调节学习率 (lr schedule)，前者在改变学习率的时候不会影响动量 mtm_t 的计算。

下文统一采用与 PyTorch 一致的写法。

# SGD with Nesterov accelerated gradient (NAG)

gt=∇θf(θt)m0=g0g~t=∇θf(θt−γ⋅mt−1)mt=γ⋅mt−1+g~tut=mtθt+1=θt−η⋅ut.\begin{alignedat}{2} \textcolor{#8b959e}{g_t} &\textcolor{#8b959e}{= \nabla_\theta f(\theta_t)} \\ \textcolor{#8b959e}{m_0} &\textcolor{#8b959e}{= g_0} \\ \textcolor{#F26400}{\tilde{g}_t} &= \nabla_\theta f(\theta_t\textcolor{#F26400}{- \gamma\cdot m_{t-1}}) \\ m_t &= \gamma\cdot m_{t-1} + \textcolor{#F26400}{\tilde{g}_t} \\ u_t &= m_t \\ \theta_{t+1} &= \theta_t - \eta\cdot u_t. \end{alignedat}

PyTorch

gt=∇θf(θt)m0=g0mt=γ⋅mt−1+gtut=γ⋅mt+ut−1θt+1=θt−η⋅ut.\begin{alignedat}{2} \textcolor{#8b959e}{g_t} &\textcolor{#8b959e}{= \nabla_\theta f(\theta_t)} \\ \textcolor{#8b959e}{m_0} &\textcolor{#8b959e}{= g_0} \\ m_t &= \gamma\cdot m_{t-1} + g_t \\ u_t &= \gamma\cdot m_t + u_{t-1} \\ \theta_{t+1} &= \theta_t - \eta\cdot u_t. \end{alignedat}

# Adagrad

——引入二阶动量。自适应学习率 优化算法的到来

gt,i=∇f(θt,i).g_{t,i} = \nabla f(\theta_{t,i}).

(θt+1,i=θt,i−η⋅gt,i\theta_{t+1,i} = \theta_{t,i} - \eta\cdot g_{t,i})

θt+1,i=θt,i−ηGt,ii+ϵ⋅gt,i\theta_{t+1,i} = \theta_{t,i} - \frac{\eta}{\textcolor{#F26400}{\sqrt{G_{t,ii}+\epsilon}}}\cdot g_{t,i}

GtG_t

Adadelta

RMSprop

# Adam

——Adaptive Moment Estimation 同时使用一阶动量与二阶动量

# (AdaMax, Nadam, AMSGrad)

# 阅读材料

总览：

Momentum/NAG:

  • https://towardsdatascience.com/adam-latest-trends-in-deep-learning-optimization-6be9a291375c
  • https://blog.christianperone.com/2020/11/optimization-deep-learning/

  1. Sutskever et al. “On the importance of initialization and momentum in deep learning”. ICML. 2013. ↩︎

Last updated: 4/5/2022, 2:02:36 PM

←