optimizer

SGD

随机梯度下降

由于实际计算梯度需要采样 \(m\) 次, 将每次的损失求平均

\[\frac 1m \nabla_\theta\sum_{i=1}^m L[f(x^{(i)}; \theta), y^{(i)}]\]

所以计算量比较大

一个想法就是每次只采样一次

这样得到的损失在期望上与求平均值是一样的

SGD 的优点是一定会收敛到局部极小值, 缺点是慢

收敛证明

统一的分析方法见 blog

假设梯度有界, 变量有界

\[|g_t|^2\leq G^2, |\theta_t-\theta^{* }|^2\leq D^2\]

如果函数 \(f_t(\theta)\) 是凸函数, 那么有

\[f_t(\theta_2)-f_t(\theta_1) \geq \braket{\nabla f_t(\theta_1), \theta_2-\theta_1} \]

考虑一个后悔值

\[R(T)=\sum_{t=1}^T[f_t(\theta_t)-f_t(\theta^{* })]\]

即第 \(t\) 个参数 \(\theta_t\) 与最优参数 \(\theta^{* }\) 之间的差的求和

当 \(\lim_{T\to\infty} R(T)/T= 0\) 时认为算法收敛

把 \(\theta_t,\theta^{* }\) 代入凸函数性质:

\[f_t(\theta_t) - f_t(\theta^{* }) \leq \braket{g_t, \theta_t-\theta^{* } } \]

所以

\[R(T)\leq \sum_{t=1}^T\braket{g_t, \theta_t-\theta^{* } }\]

同时由于

\[|\theta_{t+1}-\theta^{* }|^2=|\theta_t-\alpha_t g_t-\theta^{* }|^2\]

\[=|\theta_t-\theta^{* }|^2-2\alpha_t \braket{g_t,\theta_t-\theta^{* } } +\alpha_t^2 |g_t|^2 \]

\[\braket{g_t,\theta_t-\theta^{* } }=\frac{1}{2\alpha_t}[|\theta_{t}-\theta^{* }|^2-|\theta_{t+1}-\theta^{* }|^2]+\frac{\alpha_t}{2} |g_t|^2\]

所以

\[R(T)\leq \sum_{t=1}^T\frac{1}{2\alpha_t}[|\theta_{t}-\theta^{* }|^2-|\theta_{t+1}-\theta^{* }|^2]+\sum_{t=1}^T\frac{\alpha_t}{2} |g_t|^2\]

前一部分错位相减:

\[=\frac{1}{2\alpha_1}|\theta_1-\theta^{* }|^2+\sum_{t=1}^{T-1}[\frac{1}{2\alpha_{t+1} }-\frac 1{2\alpha_t}]|\theta_{t}-\theta^{* }|^2-\frac 1{2\alpha_{T} }|\theta_{T+1}-\theta^{* }|^2\]

由于前面假设梯度有界

\[|\theta_t-\theta^{* }|^2\leq D^2\]

且

\[-\frac 1{2\alpha_{T} }|\theta_{T+1}-\theta^{* }|^2\leq 0\]

所以原式

\[R(T)\leq [\frac{1}{2\alpha_1}+\sum_{t=1}^{T-1}[\frac 1{2\alpha_{t+1} }-\frac 1{2\alpha_t}] ]D^2+\sum_{t=1}^T\frac{\alpha_t}{2} |g_t|^2\]

\[=\frac{1}{2\alpha_T}D^2+\sum_{t=1}^T\frac{\alpha_t}{2} |g_t|^2\]

\[\leq \frac{1}{2\alpha_T}D^2 + \frac{G^2}{2}\sum_{t=1}^T\alpha_t\]

此时假设 \(\alpha_t=t^{-p}\)

前一部分 \(/T\) 得到 \(t^{(p-1)}\)

所以只要 \(p<1\) 就收敛到 \(0\)

后一部分 \(/T\) 得到 \(\displaystyle \frac{\sum_{t=1}^Tt^{-p}}{T}\)

那么我们断言

\[\forall \epsilon >0, \exists N>0 \text{ s.t. } \forall T>N, \lim_{T\to\infty}\frac{\sum_{t=1}^T t^{-p} }{T}\leq \epsilon\]

实际上, 我们取 \(N_0\geq \frac{1}{\epsilon^{1/p} }\), 即 \(N_0^{-p}\leq \epsilon\)

对于 \(t\leq N\), \(\sum_{t=1}^N t^{-p} / T\to 0\)

可以找到一个 \(N_1\) 使得 \(\sum_{t=1}^{N_1} t^{-p} / T \leq \epsilon\)

那么取 \(N=\max(N_0,N_1)\)

对于 \(t>N\), 我们有 \(t^{-p}\leq \epsilon\)

所以原式:

\[\sum_{t=1}^N t^{-p} / T + \sum_{t=N+1}^T t^{-p} / T \leq C / T + T\epsilon / T \leq \epsilon + \epsilon = 2\epsilon\]

收敛速度

要想看到他有多慢, 可以看下面的图:

alt text

给两个矩阵小知识:

Poor conditioning

考虑函数 \(f(x)=A^{-1}x\)

对于矩阵 \(A\) 的 condition number 等于特征值的最大最小之比

\[\max_{i,j}|\frac{\lambda_i}{\lambda_j}|\]

这个 condition nubmer 越大, 函数 \(f(x)\) 对于输入 \(x\) 的变化越敏感

即 \(x\) 一个小的变化可能引起 \(f(x)\) 变化很大

Hessian matrix

向量函数 \(f: \mathbb R^n\to \mathbb R^m\) 的一阶偏导组成的矩阵为 Jacobian matrix , 记作 \(J(f)_{m\times n}\)

典型的应用是多元函数积分换元:

\[\int_{X,Y}f(x,y)\text dx\text dy = \int_{U,V}f(u,v)\cdot |\det J|\text du\text dv\]

标量函数的二阶偏导组成的矩阵为 Hessian matrix, 记作 \(H(f)_{n\times n}\)

他们两个的关系是:

\[H(f)=J(\nabla f)\]

即多维标量函数的 Hessian matrix 为函数梯度的 Jacobian matrix

上面图片中函数的 Hessian matrix 的 condition number \(= 5\)

所以 SGD 对于 \([-1,1]^T\) 方向的梯度不敏感, 对于 \([1,1]^T\) 方向的梯度敏感, 所以看起来一直在撞墙, 而没有很快地下降到谷底

Momentum SGD

为了加速收敛设计出来的

定义一个速度矢量 \(v\)

它指代参数在参数空间中移动的速率与方向

在参数使用单位质量时, 速度 \(v\) 就是动量, 所以是这个叫法

定义一个超参数 \(\alpha\in [0, 1)\)

更新规则:

\[v \leftarrow \alpha v - \epsilon \nabla_\theta(\frac 1m \sum_{i=1}^mL[f(x^{(i)};\theta), y^{(i)}])\]

\[\theta \leftarrow \theta + v\]

把负梯度看作一个力, \(\epsilon\) 看作一个调整单位的参数

所以第一个式子就是冲量转成动量

第二个式子是单位时间的距离变化

于 SGD 相比:

alt text

可以看到负梯度中沿着 \([1,1]^T\) 方向的分量在每次更新 \(v\) 时都会相互抵消, 而沿着 \([-1,1]^T\) 方向的分良在每次更新 \(v\) 时会一直累积

所以朝着谷底运动的速度越来越快

形式化地, 要想求出最大的最终速度, 考虑运行过程, 速度会沿着负梯度的方向加速, 最后的收敛到连续几步内的梯度都是相同的大小与方向

如果从第一步开始采样得到的梯度都为 \(g\), 那么最终的最大速度是

\[v_{\max}=\epsilon ||g|| +\epsilon \alpha ||g||+\cdots \]

\[=\frac{\epsilon ||g||}{1-\alpha}\]

相比于无 Momentum 的 SGD 加速的 \(\frac{1}{1-\alpha}\) 倍

nature

本质是在通过数值模拟求解一阶微分方程组:

\[v(t)=\frac{\partial \theta(t)}{\partial t}\]

\[f(t)=\frac{\partial v(t)}{\partial t}\]

其中取单位质量, 所以 \(f(t)=a(t)\)

同时 \(\theta(t)\) 是位移

数值模拟解微分方程组的一个方法是 Euler 方法, 即模拟取每个梯度方向的一小步来计算

这正是 Momentum SGD 在做的事

具体地, 取一个主动力为负梯度, 在取一个被动力, 通过系数 \(\alpha\) 正比于 \(-v(t)\)

这个被动力可以看作粘滞力, 因为正比于 \(v\), 而不像动摩擦力不与 \(v\) 相关, 或者空气阻力正比于 \(v^2\)

Nesterov Momentum SGD

迭代公式为

\[v \leftarrow \alpha v - \epsilon \nabla_\theta(\frac 1m\sum_{i=1}^m L[f(x^{(i)};\theta+\alpha v),y^{(i)}])\]

\[\theta \leftarrow \theta + v\]

即在采样梯度前先将当前速度应用于位移 \(\theta\)

对于 convex batch gradient 有显著速度提升, 但是对 stochastic gradient 没有理论保证的提升

adaptive learning rate optimizer

上面的几个算法学习率 \(\epsilon\) 都是固定的

下面介绍几个自适应学习率的算法

AdaGrad

通过累积的平方梯度来调节学习率, 使收敛更稳定

给定静态学习率 \(\epsilon\) 和防止除零异常的小常数 \(\delta \approx 10^{-7}\), 迭代公式为:

\[g\leftarrow \frac 1m \nabla_\theta\sum_{i=1}^mL[f(x^{(i)};\theta), y^{(i)}]\]

\[r \leftarrow r + g\cdot g\]

\[\Delta \theta \leftarrow -\frac{\epsilon}{\delta + \sqrt{r} } \cdot g\]

\[\theta \leftarrow \theta + \Delta\theta\]

在凸优化中有理论优势, 但实际训练神经网络往往导致学习率过早过大衰减, 因为有时函数是非凸的

收敛证明

与 SGD 收敛证明类似

同样假设凸函数, 假设梯度收敛到 \(0\)

可以写出

\[R(T)\leq \frac{\delta+\sqrt{r_T} }{2\epsilon}D^2+\frac{\epsilon}{2}\sum_{t=1}^T\frac{|g_t|^2}{\delta+\sqrt{r_t} }\]

前一部分 \(/T\) 为

\[\frac{\delta+\sqrt{\sum_{t=1}^T |g_t|^2} }{2\epsilon}D^2 / T\]

\[\leq \frac{\delta+G\sqrt T}{2\epsilon} D^2 / T\to 0\]

后一部分 \(/T\) 为

\[\frac 1T\sum_{t=1}^T\frac{|g_t|^2}{\delta+\sqrt{\sum_{i=1}^t |g_i|^2} } \leq \frac 1T\sum_{t=1}^T\frac{|g_t|^2}{\sqrt{\sum_{i=1}^t |g_i|^2} }\]

\[\leq \frac2T\sum_{t=1}^T\frac{|g_t|^2}{\sqrt{\sum_{i=1}^{t-1} |g_i|^2}+\sqrt{\sum_{i=1}^t |g_i|^2} }=\frac 2T\sum_{t=1}^T\frac{|g_t|^2}{|g_t|^2}[\sqrt{\sum_{i=1}^{t}|g_i|^2}-\sqrt{\sum_{i=1}^{t-1}|g_i|^2}]\]

\[\leq \frac 2T\sum_{t=1}^T\sqrt{G^2T}=\frac{2G}{\sqrt T}\to 0\]

RMSProp

为了使得 AdaGrad 在非凸场景下效果更好, 将学习率改成指数级衰减

在非凸场景下, 函数可能在某些邻域内形成一个局部凸壳

AdaGrad 由于考虑了整体的 history, 可能在没到达局部凸壳之前经过了一段梯度很大的坡, 导致学习率衰减变得很小

RMSProp 的指数级衰减让学习率能够遗忘过远的 history

给定学习率衰减速率 \(\rho\), 更新规则为:

\[g\leftarrow \frac 1m \nabla_\theta\sum_{i=1}^mL[f(x^{(i)};\theta), y^{(i)}]\]

\[r \leftarrow \rho r + (1-\rho) g\cdot g\]

\[\Delta \theta \leftarrow -\frac{\epsilon}{\sqrt{\delta + r} } \cdot g\]

\[\theta \leftarrow \theta + \Delta\theta\]

可以看到与 AdaGrad 区别在 \(r\) 和 \(\frac 1 {\sqrt{\delta + r} }\) 上

还有一个带 Nesterov Momentum 的 RMSProp:

\[\tilde \theta \leftarrow \theta+\alpha v\]

\[g\leftarrow \frac 1m \nabla_{\tilde \theta}\sum_{i=1}^mL[f(x^{(i)};\tilde \theta), y^{(i)}]\]

\[r \leftarrow \rho r + (1-\rho) g\cdot g\]

\[v \leftarrow \alpha v-\frac{\epsilon}{\sqrt{r} } \cdot g\]

\[\theta \leftarrow \theta + \Delta\theta\]

Adam

algorithm

alt text

可以看作 RMSProp 与 Momentum 的一个结合, 只不过与上面的 Nesterov Momentum 版本有区别

给定几个参数 \(\rho_1=0.9,\rho_2=0.999,\epsilon=0.001,\delta=10^{-8}\)

迭代公式为:

\[g\leftarrow \frac 1m \nabla_\theta\sum_{i=1}^mL[f(x^{(i)};\theta), y^{(i)}]\]

\[\text{biased first moment estimate: }s \leftarrow \rho_1 s + (1-\rho_1) g\]

\[\text{biased second moment estimate: }r \leftarrow \rho_2 r + (1-\rho_2) g \cdot g\]

\[\text{correct bias in first moment: } \hat s\leftarrow \frac{s}{1-\rho_1^t}\]

\[\text{correct bias in second moment: } \hat r\leftarrow \frac{r}{1-\rho_2^t}\]

\[\Delta \theta \leftarrow -\epsilon\frac{\hat s}{\delta+\sqrt{ \hat r} }\]

\[\theta \leftarrow \theta + \Delta\theta\]

initialization bias correction

对于 \(v_t\) 有

\[v_t=(1-\beta_2)\sum_{i=1}^t\beta_2^{t-i}\cdot g_i^2\]

求一阶矩 \(\mathbb E[v_t]\) 与梯度二阶矩 \(\mathbb E[g_t^2]\) 的关系

\[\mathbb E[v_t]=\mathbb E[(1-\beta_2)\sum_{i=1}^t\beta_2^{t-i}\cdot g_i^2]\]

\[=\mathbb E[g_t^2]\cdot (1-\beta_2)\sum_{i=1}^t\beta_2^{t-i} + \zeta\]

\[=\mathbb E[g_t^2]\cdot (1-\beta_2^t) + \zeta\]

其中当 \(\mathbb E[g_i^2]\) 不变时, \(\zeta=0\)

否则 \(\zeta\) 会是一个很小的值, 因为可以合理选择 \(\beta_2\in[0,1)\) 使得 \(v_t\) 被更远的梯度影响很小, 所以 \(\mathbb E[g_i^2]\) 更接近 \(\mathbb E[g_t^2]\)

convergence

Lemma 1 凸函数性质

\[\lambda f(x)+(1-\lambda) f(y)\geq f(\lambda x + (1-\lambda y))\]

Lemma 2 凸函数性质, 另一种表达

\[f(y)\geq f(x)+\nabla f(x)^T(y-x)\]

Lemma 3

令 \(g_t=\nabla f_t(\theta_t)\), \(||g_t||_2\leq G\), \(||g_t||_\infty\leq G_\infty\), \(g_{1:t,i}=[g_{1,i},\cdots,g_{t,i}]\), 那么

\[\sum_{t=1}^T\sqrt{\frac{g_{t,i}^2}{t} }\leq 2G_\infty||g_{1:T,i}||_2\]

Lemma 4

令 \(\gamma=\frac{\beta_1^2}{\sqrt{\beta_2} }<1\), 且 \(||g_t||_2<G\), \(||g_t||_\infty<G_\infty\), 那么

\[\sum_{t=1}^T\frac{\hat m_{t,i}^2 }{\sqrt{t\hat v_{t,i} } }\leq \frac{2}{1-\gamma}\frac{1}{\sqrt{1-\beta_2} }||g_{1:T,i}||_2\]

我们假设 \(\alpha_t\) 随着时间呈 \(t^{-1/2}\) 速率衰减, \(\beta_{1,t}\) 随着时间呈 \(\lambda^t\) 速率衰减, \(\lambda=1-10^{-8}\)

同时参数间的距离有界, 即 \(||\theta_n-\theta_m||_2\leq D, ||\theta_n-\theta_m||_\infty\leq D_\infty\) 对于任意 \(m,n\in \set{1, \cdots, T}\) 成立

那么

Theorem 5

假设 \(\alpha_t=\frac{\alpha}{\sqrt t}\), \(\beta_{1,t}=\lambda^{t-1}\), 且 \(\gamma<1\), 那么

\[R(T)\leq \frac{D^2}{2\alpha(1-\beta_1)}\sum_{i=1}^d\sqrt{T\hat v_{T,i} }\]

\[+\frac{\alpha(1+\beta_1)G_\infty}{(1-\beta_1)\sqrt{1-\beta_2} (1-\gamma)^2}\sum_{i=1}^d||g_{1:T,i}||_2\]

\[+\sum_{i=1}^d\frac{D^2_\infty G_\infty\sqrt{1-\beta_2} }{2\alpha(1-\beta_1)(1-\lambda)^2}\]

这是原文给出的定理, 可惜他是错的

non-convergence

具体见 blog

AMSGrad

alt text

可以看到与 Adam 的区别就是 \(\hat v_t\) 与过去取了一个最大值

在 Adam 中, 由于 \(v_{t,i}=\beta_2v_{t-1,i}+(1-\beta_2)g_{t,i}^2\)

所以当 \(v_{t-1,i}>g_{t,i}^2>0\) 时 \(v_{t,i}<v_{t-1,i}\)

那么学习率可能会增大

但是 AMSGrad 取最大值可以保证 \(\frac{\sqrt{\hat v_t,i} }{\alpha_t}\) 单调不减, 那么学习率就是单调不增的

convergence

<!-- > Theorem 1

对于 \(\alpha_t=\alpha/\sqrt t\), \(\beta_{1,t}\leq \beta_1\) 以及 \(\gamma = \beta_1/\sqrt \beta_2<1\)

且梯度与参数距离有界

那么

\[R(T)\leq \frac{D_{\infty}^2\sqrt T}{\alpha(1-\beta_1)}\sum_{i=1}^d\hat v_{T,i}^{1/2}\tag{1.1}\]

\[+\frac{D_\infty^2}{(1-\beta_1)^2}\sum_{t=1}^T\sum_{i=1}^d\frac{\beta_{1,t}\hat v_{t,i}^{1/2} }{\alpha_t}\tag{1.3}\]

\[+\frac{\alpha\sqrt{1+\log T} }{(1-\beta_1)^2(1-\gamma)\sqrt{1-\beta_2} }\sum_{i=1}^d||g_{1:T,i}||_2\tag{1.2}\]

\(\underline{证明}\)

按照 Online Convex Programming 的统一分析方法来做

还是先把 \(x_{t+1}\) 按更新规则展开

\[x_{t+1}=\Pi_{\mathcal F, \sqrt {\hat V_t} }(x_t-\alpha_t \hat V_t^{-1/2}m_t)=\text{argmin}_{x\in \mathcal F}||\hat V_t^{1/4}(x-(x_t-\alpha_t\hat V_t^{-1/2}m_t))||\]

所以把 \(||\hat V_t^{1/4}(x_{t+1}-x^{* })||^2\) 展开

\[||\hat V_t^{1/4}(x_{t+1}-x^{* })||^2\leq ||\hat V_t^{1/4}(x_{t}-x^{* })||^2+\alpha_t^2||\hat V_t^{-1/4}m_t||^2-2\alpha_t\braket{m_t,x_t-x^{* } }\]

\[=||\hat V_t^{1/4}x_{t}-x^{* }||^2+\alpha_t^2||\hat V_t^{-1/4}m_t||^2-2\alpha_t\braket{\beta_{1,t}m_{t-1}+(1-\beta_{1,t})g_t,x_t-x^{* } }\]

所以整理得到

\[\sum_{t=1}^T\braket{g_t, x_t-x^{* } }\leq \sum_{t=1}^T\frac{1}{2\alpha_t(1-\beta_{1,t})}[||\hat V_t^{1/4}(x_t-x^{* })||^2-||\hat V_t^{1/4}(x_{t+1}-x^{* })||^2]\tag{2.1}\]

\[+\sum_{t=1}^T\frac{\alpha_t}{2(1-\beta_{1,t})}||\hat V_t^{-1/4}m_t||^2\tag{2.2}\]

\[+\sum_{t=1}^T\frac{\beta_{1,t} }{2(1-\beta_{1,t})}\alpha_t||\hat V_t^{-1/4}m_{t-1}||^2\tag{2.2'}\]

\[+\sum_{t=1}^T\frac{\beta_{1,t} }{2\alpha_t(1-\beta_{1,t})}||\hat V_t^{1/4}(x_t-x^{* } )||^2\tag{2.3}\]

后一项用了 \(\braket{a,b}\leq ||a||\cdot ||b||\) 与 \(ab\leq (a^2+b^2)/2\) 把 \(\frac{\beta_{1,t} }{1-\beta_{1,t}}\braket{m_{t-1},x_t-x^{* } }\) 展开成 \((6.2'),(6.3)\)

(\(\alpha_t\) 是凑进去的)

其实是柯西不等式和杨氏不等式

那么由于 \(\hat v_{t,i}\geq \hat v_{t-1,i}\)

所以中间两项合并变成

\[(2.2')+(2.3)\leq \sum_{t=1}^T\frac{\alpha_t}{1-\beta_1}||\hat V_t ^{-1/4}m_t||^2\tag{2.2''}\]

Lemma 2

\[\sum_{t=1}^T\alpha_t||\hat V_t ^{-1/4}m_t||^2\leq \frac{\alpha\sqrt{1+\log T} }{(1-\beta_1)(1-\gamma)\sqrt{1-\beta_2} }\sum_{i=1}^d||g_{1:T,i}||_2\]

\(\underline{证明}\)

将求和最后一项按照更新规则展开

\[\sum_{t=1}^T\alpha_t||\hat V_t ^{-1/4}m_t||^2=\sum_{t=1}^{T-1}\alpha_t||\hat V_t ^{-1/4}m_t||^2+\alpha\sum_{i=1}^d\frac{(\sum_{j=1}^T(1-\beta_{1,j})[\prod_{k=1}^{T-j}\beta_{1,T-k+1}]g_{j,i} )^2}{\sqrt{T\sum_{j=1}^T(1-\beta_2)\beta_2^{T-j}g_{j,i}^2 } }\]

\[=\sum_{t=1}^{T-1}\alpha_t||\hat V_t ^{-1/4}m_t||^2+\alpha\sum_{i=1}^d\frac{(\sum_{j=1}^T\prod_{k=1}^{T-j}\beta_{1,T-k+1} )\cdot (\sum_{j=1}^T\prod_{k=1}^{T-j}\beta_{1,T-k+1}g_{j,i}^2 )}{\sqrt{T\sum_{j=1}^T(1-\beta_2)\beta_2^{T-j}g_{j,i}^2 } }\]

\[\leq \sum_{t=1}^{T-1}\alpha_t||\hat V_t ^{-1/4}m_t||^2+\alpha\sum_{i=1}^d\frac{(\sum_{j=1}^T\beta_1^{T-j})\cdot (\sum_{j=1}^T\beta_1^{T-j}g_{j,i}^2)}{\sqrt{T\sum_{j=1}^T(1-\beta_2)\beta_2^{T-j}g_{j,i}^2 } }\]

\[= \sum_{t=1}^{T-1}\alpha_t||\hat V_t ^{-1/4}m_t||^2+\frac{\alpha}{(1-\beta_1)\sqrt{T(1-\beta_2)} }\sum_{i=1}^d\sum_{t=1}^T\frac{\beta_1^{T-j}g_{j,i}^2}{ \sqrt{\beta_2^{T-j}g_{j,i}^2 } }\]

\[= \sum_{t=1}^{T-1}\alpha_t||\hat V_t ^{-1/4}m_t||^2+\frac{\alpha}{(1-\beta_1)\sqrt{T(1-\beta_2)} }\sum_{i=1}^d\sum_{j=1}^T\gamma^{T-j} |g_{j,i}|\]

依次把所有的项都展开

\[= \sum_{t=1}^T\frac{\alpha}{(1-\beta_1)\sqrt{t(1-\beta_2)} }\sum_{i=1}^d\sum_{j=1}^t\gamma^{t-j} |g_{j,i}|\]

常数提出来:

\[= \frac{\alpha}{(1-\beta_1)\sqrt{(1-\beta_2)} }\sum_{i=1}^d\sum_{t=1}^T\frac1{\sqrt t}\sum_{j=1}^t\gamma^{t-j} |g_{j,i}|\]

对于 \(\sum_{t=1}^T\frac1{\sqrt t}\sum_{j=1}^t\gamma^{t-j} |g_{j,i}|\), 换顺序求和:

\[=\sum_{t=1}^T|g_{t,i}|\sum_{j=t}^T\frac{\gamma^{j-t} }{\sqrt j}\]

\[\leq\sum_{t=1}^T|g_{t,i}|\sum_{j=t}^T\frac{\gamma^{j-t} }{\sqrt t}\]

\[\leq\sum_{t=1}^T|g_{t,i}|\frac{1}{(1-\gamma)\sqrt t}\]

所以原式

\[\leq\frac{\alpha}{(1-\beta_1)\sqrt{(1-\beta_2)} }\sum_{i=1}^d\sum_{t=1}^T|g_{t,i}|\frac{1}{(1-\gamma)\sqrt t}\]

对于每个 \(|g_{t,i}|\), 将 \(\frac 1{\sqrt t}\) 放缩到 \(\sqrt{\sum_{t=1}^T\frac{1}{t} }\):

\[ \leq\frac{\alpha}{(1-\beta_1)(1-\gamma)\sqrt{(1-\beta_2)} }\sqrt{\sum_{t=1}^T\frac{1}{t} }\sum_{i=1}^d\sum_{t=1}^T|g_{t,i}|\]

\[= \frac{\alpha}{(1-\beta_1)(1-\gamma)\sqrt{(1-\beta_2)} }\sqrt{\sum_{t=1}^T\frac{1}{t} }\sum_{i=1}^d||g_{1:T,i}||_2\]

并且 \(\sqrt{\sum_{t=1}^T\frac{1}{t} }\leq \sqrt{1+\int_{1}^T[1/t]\text dt}\leq \sqrt{1+\log T}\)

所以成立

\(\blacksquare\)

这个引理的最后一步实际对应了 Adam 的引理 3, 只不过把 \(G_\infty\) 换成了 \(\sqrt{1+\log T}\)

回到定理, 对于 \((2.1)\), 错位相减得到

\[\sum_{t=1}^T\frac{1}{2\alpha_t(1-\beta_{1,t})}[||\hat V_t^{1/4}(x_t-x^{* })||^2-||\hat V_t^{1/4}(x_{t+1}-x^{* })||^2]\]

\[\leq \frac{1}{2\alpha_1(1-\beta_{1})}||\hat V_1^{1/4}(x_1-x^{* })||^2+\sum_{t=2}^T\frac{1}{2(1-\beta_1)}[\frac{||\hat V_t^{1/4}(x_t-x^{* })||^2}{\alpha_t}-\frac{||\hat V_{t-1}^{1/4}(x_t-x^{* })||^2}{\alpha_{t-1} }]\]

这里 \(\hat v_{T,i}^{1/2}=||\hat V_{T,i}^{1/4}||^2\) 展开:

\[=\sum_{i=1}^d\frac{1}{2\alpha_1(1-\beta_{1})}\hat v_{1,i}^{1/2}(x_{1,i}-x^{* }_i)^2+\sum_{i=1}^d\sum_{t=2}^T\frac{1}{2(1-\beta_1)}(x_{t,i}-x^{* }_i)^2[\frac{\hat v_{t,i}^{1/2} }{\alpha_t}-\frac{\hat v_{t-1,i}^{1/2} }{\alpha_{t-1} }]\]

参数之差放缩到 \(D_\infty\), 有

\[\leq\sum_{i=1}^d\frac{1}{2\alpha_1(1-\beta_{1})}\hat v_{1,i}^{1/2}D_\infty^2+\sum_{i=1}^d\sum_{t=2}^T\frac{1}{2(1-\beta_1)}D_\infty^2[\frac{\hat v_{t,i}^{1/2} }{\alpha_t}-\frac{\hat v_{t-1,i}^{1/2} }{\alpha_{t-1} }]\]

\[=\frac{D_\infty^2}{2\alpha_T(1-\beta_1)}\sum_{i=1}^d\hat v_{T,i}^{1/2}\]

即

\[(2.1)\leq \frac{D_\infty^2\sqrt T}{2\alpha(1-\beta_1)}\sum_{i=1}^d\hat v_{T,i}^{1/2}\]

与 \((1.1)\) 对应

对于 \((2.3)\), 由于

\[\frac{1}{1-\beta_{1,t} }\leq \frac{1}{1-\beta_{1} }\leq \frac{1}{(1-\beta_{1})^2 }\]

所以

\[(2.3)\leq \frac{1}{(1-\beta_1)^2}\sum_{t=1}^T\sum_{i=1}^d\frac{\beta_{1,t} (x_{t,i}-x^{*}_i )^2\hat v_{t,i}^{1/2} }{\alpha_t}\]

\[\leq \frac{D_\infty^2}{(1-\beta_1)^2}\sum_{t=1}^T\sum_{i=1}^d\frac{\beta_{1,t} \hat v_{t,i}^{1/2} }{\alpha_t}\]

与 \((1.3)\) 对应

\(\blacksquare\)

Corollary 1

如果 \(\beta_{1,t}=\beta_1\lambda^{t-1}\), 那么

\[R(T)\leq \frac{D_{\infty}^2\sqrt T}{\alpha(1-\beta_1)}\sum_{i=1}^d\hat v_{T,i}^{1/2}+\frac{\beta_1D_\infty^2G_\infty}{(1-\beta_1)^2(1-\lambda)^2}+\frac{\alpha\sqrt{1+\log T} }{(1-\beta_1)^2(1-\gamma)\sqrt{1-\beta_2} }\sum_{i=1}^d||g_{1:T,i}||_2\]

\(\underline{证明}\)

由于 \(\hat v_{t,i}^{1/2}\leq G_\infty\)

\[(3.3)\leq \frac{D_\infty^2G_\infty}{(1-\beta_1)^2}\sum_{t=1}^T\sum_{i=1}^d\frac{\beta_{1,t}\sqrt t }{\alpha}\]

由于

\[\sum_{t=1}^T\beta_{1,t} \sqrt{t}= \sum_{t=1}^T\beta_{1} \sqrt{t}\lambda^{t-1}\]

\[\leq \beta_1\sum_{t=1}^Tt\lambda^{t-1}\]

\[\leq \frac{\beta_1}{(1-\lambda)^2}\]

所以原式有

\[\leq \frac{\beta_1D^2_\infty G_\infty }{2\alpha(1-\beta_1)^2(1-\lambda)^2}\]

下面的 \(\alpha\) 也是常数, 不用在意

\(\blacksquare\) -->

具体见 Adam and AMSGrad

summary

定义几个符号:

\(\mathcal F\) 表示参数空间

\(S^d_{+ }\) 表示正定的 \(d\times d\) 矩阵空间

\(\Pi_{\mathcal F, A}(y)=\text{argmin}_{x\in \mathcal F}||A^{1/2}(x-y)||,y\in \mathbb R^d, A\in S^d_{+ }\) 投影操作表示在以 \(\sqrt V_t\) 为缩放比例缩放后的 \(\mathcal F\) 空间内找出一个与目标参数 \(y\) 最相近的

那么平均函数 \(\phi_t:\mathcal F^t\to \mathbb R^d\)

方差函数 \(\psi_t:\mathcal F^t\to S^d_{+ }\)

那么统一的自适应算法为:

alt text

这里 \(V_t=\text{diag}(v_t)\), 指的是把 \(v_t\in\mathbb R^d\) 向量的每个元素放到 \(V_t\in S^d_{+ }\) 矩阵的对角线上, 目的是与 \(m_t\) 做逐元素 (element-wise) 的除法, 即 \(m_{t,i} \times V^{-1}_{t,i,i},i=\set{1,\cdots,d}\)

如果特定了 \(\alpha_t=\alpha/\sqrt t\):

alt text

所有算法的 \(\phi_t,\psi_t\) 可以整理到表格里:

alt text

其中 SGD 的 \(\psi_t=\mathbb I\) 是恒等变换

Adam 的 \(\alpha_t\) 是 \(\alpha\cdot\sqrt{1-\beta_2^t}/(1-\beta_1^t)\)

second order optimizer

下面补充几个二阶的方法

Newton's method

就是牛顿迭代法

我们考虑误差函数

\[J(\theta)=\frac{1}{m}\sum_{i=1}^mL[f(x^{(i)};\theta), y^{(i)}]\]

利用泰勒展开:

\[J(\theta)=J(\theta_0)+(\theta-\theta_0)^T\nabla_\theta J(\theta_0)+\frac 12(\theta-\theta_0)^TH(\theta-\theta_0)\]

\[=J(\theta_0)+(\theta-\theta_0)^Tg+\frac 12(\theta-\theta_0)^TH\]

\(H\) 是黑塞矩阵, 即二阶导

那么由优化版的二阶牛顿迭代法, 我们更新的步长为:

\[\Delta\theta=-H^{-1}g\]

算法迭代公式为:

\[g\leftarrow \frac{1}{m}\nabla_\theta\sum_{i=1}^mL[f(x^{(i)};\theta), y^{(i)}]\]

\[H\leftarrow \frac{1}{m}\nabla_\theta^2\sum_{i=1}^mL[f(x^{(i)};\theta), y^{(i)}]\]

\[\Delta\theta\leftarrow H^{-1}g\]

\[\theta \leftarrow \theta+\Delta\theta\]

conjugate gredient method

BFGS

这俩不具体介绍了, 具体见 Deep Learning 的第 8 章

参考: