【科研喂饭】深度学习算法收敛性证明之Adam

这是我“科研喂饭”系列的第三篇文章，希望它能为正在从事算法研发以及对算法研发感兴趣的小伙伴带来帮助。我写这个专栏的目的是希望能尽力降低科研的门槛，让大家更好地享受科研的乐趣。

文章中会涉及到论文的细节，以数学推导过程为主。限于篇幅以及讲解的便利性，我将会对原文作出调整和删减。如果大家在阅读本文时感到困惑，可以进一步参阅文献，看一看原作者的讲解。

由于本文篇幅较长，大家可以根据实际情况挑选自己感兴趣的部分来读：

我是小白：不妨从第1章开始
我只想看算法和收敛性证明部分：直接从第2章开始，遇到不明含义的数学符号参考前文
我只想看拓展的部分（Amsgrad）：直接从第4章开始，遇到不明含义的数学符号参考前文

1.1 SGD和Adagrad

在上两篇文章里我们详细介绍了最朴素的SGD算法和Adagrad算法的收敛性证明（SGD：【科研喂饭】深度学习算法收敛性证明之SGD；Adagrad：【科研喂饭】深度学习算法收敛性证明之Adagrad），我们做一个简单的回顾：

? SGD的变量迭代表达式：

$\\boldsymbol{\ heta}^{(t+1)}=\\boldsymbol{\ heta}^{(t)}-\\alpha_{t}\\mathbf{g}_{t}$

其中 $\\alpha_{t}$ 是学习率， $\\mathbf{g}_{t}=\ abla f_{t}\\left(\\boldsymbol{\ heta}^{(t)}\\right)$ 是 $t$ 时刻目标函数 $f_{t}$ 在 $\\boldsymbol{\ heta}=\\boldsymbol{\ heta}^{(t)}$ 处的梯度。

? Adagrad的变量迭代表达式：

$\\boldsymbol{\ heta}^{(t+1)}=\\boldsymbol{\ heta}^{(t)}-\\boldsymbol{\\alpha}_{t}\\odot\\mathbf{g}_{t}$

其中 $\\mathbf{g}_{t}=\ abla f_{t}\\left(\\boldsymbol{\ heta}^{(t)}\\right)$ ，与SGD相同； $\\odot$ 为两个向量在对应位置做乘积（哈达玛积）； $\\alpha_{t}$ 从标量变成了向量：

$\\boldsymbol{\\alpha}_{t}=\\frac{\\alpha}{\\sqrt{\\sum_{s=1}^{t}\\mathbf{g}_{t}^{2}}}$

向量的数值运算（加减乘除、乘方开方、指数对数）是指对向量的各个元素做数值运算。标量除以向量的运算是指让标量除以向量的各个元素，最终输出向量的运算。

它们的收敛性证明基于以下前提假设（来自参考文献[1, 第2.1节]）：

对于任意 $t$ ， $f_{t}\\left(\\boldsymbol{\ heta}\\right)$ 都是关于 $\\boldsymbol{\ heta}$ 的convex函数
变量有界：

$\\left\\Vert \\boldsymbol{\ heta}-\\boldsymbol{\ heta}^{\\prime}\\right\\Vert _{2}\\leq D,\\,\\,\\forall\\boldsymbol{\ heta},\\boldsymbol{\ heta}^{\\prime}$

或者对于变量的任意一维 $i$

$\\left\\Vert \ heta_{i}-\ heta_{i}^{\\prime}\\right\\Vert _{2}\\leq D_{i},\\,\\,\\forall\ heta_{i},\ heta_{i}^{\\prime}$

梯度有界：

$\\left\\Vert \\mathbf{g}_{t}\\right\\Vert _{2}\\leq G,\\,\\,\\forall t$

或者对于变量的任意一维 $i$

$\\left\\Vert g_{t,i}\\right\\Vert _{2}\\leq G_{i},\\,\\,\\forall t$

判定收敛的指标为统计量 $R\\left(T\\right)$ （Regret）：

$R\\left(T\\right)=\\sum_{t=1}^{T}f_{t}\\left(\\boldsymbol{\ heta}^{(t)}\\right)-\\min_{\\boldsymbol{\ heta}}\\sum_{t=1}^{T}f_{t}\\left(\\boldsymbol{\ heta}\\right)$

若当 $T\\rightarrow\\infty$ ， $R\\left(T\\right)$ 的均摊值 $R\\left(T\\right)/T\\rightarrow0$ ，我们认为这样的算法是收敛的，并且一般认为 $R\\left(T\\right)$ 随着 $T$ 增长得越慢，算法收敛越快。这些的前提假设与判定收敛指标将在Adam算法的收敛性证明中继续沿用。

Adam算法的参考文献是[2]。本文中的证明步骤将参考[2]，然而由于其Lemma 10.3和Lemma 10.4存在错误，因此本文将作出调整和删改。 Adam的变量迭代式比SGD和Adagrad更复杂些：（ $\\mathbf{m}^{(0)}$ 、 $\\mathbf{v}^{(0)}$ 初始化为 $\\mathbf{0}$ ， $\\boldsymbol{\ heta}^{(1)}$ 随机初始化）

$\\begin{aligned}& \\mathbf{m}^{(t)}=\\beta_{1}\\mathbf{m}^{(t-1)}+\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t}& & \\hat{\\mathbf{m}}^{(t)}=\\mathbf{m}^{(t)}/\\left(1-\\beta_{1}^{t}\\right)\\end{aligned}$

$\\begin{aligned}& \\mathbf{v}^{(t)}=\\beta_{2}\\mathbf{v}^{(t-1)}+\\left(1-\\beta_{2}\\right)\\mathbf{g}_{t}^{2}& & \\hat{\\mathbf{v}}^{(t)}=\\mathbf{v}^{(t)}/\\left(1-\\beta_{2}^{t}\\right)\\end{aligned}$

$\\boldsymbol{\ heta}^{(t+1)}=\\boldsymbol{\ heta}^{(t)}-\\alpha_{t}\\hat{\\mathbf{m}}^{(t)}/\\sqrt{\\hat{\\mathbf{v}}^{(t)}}$

其中 $\\mathbf{g}_{t}=\ abla f_{t}\\left(\\boldsymbol{\ heta}^{(t)}\\right)$ 。在深度学习框架TensorFlow中，我们通过调用优化器API的形式来实现Adam算法：

$\ extrm{tf.optimizers.Adam(learning_rate=}\\alpha)$

Adam对比Agadrad有以下这些亮点：

? 引进了动量（momentum）：

$\\mathbf{g}_{t}\\longrightarrow\\mathbf{m}^{(t)}$

? 改进了Adagrad的分母：

$\\sqrt{\\sum_{s=1}^{t}\\mathbf{g}_{s}^{2}}\\longrightarrow\\sqrt{\\mathbf{v}^{(t)}}$

2.1 算法细节：均值校正

我们可以根据 $\\mathbf{m}^{(t)}$ 和 $\\mathbf{v}^{(t)}$ 的迭代式算出它们的闭式解，我们以 $\\mathbf{m}^{(t)}$ 为例：

$\\begin{aligned}\\mathbf{m}^{(t)}=& \\beta_{1}\\mathbf{m}^{(t-1)}+\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t}\\\\=& \\beta_{1}^{2}\\mathbf{m}^{(t-2)}+\\beta_{1}\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t-1}+\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t}\\\\=& \\beta_{1}^{3}\\mathbf{m}^{(t-3)}+\\beta_{1}^{2}\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t-2}+\\beta_{1}\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t-1}+\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t}\\\\=& \\beta_{1}^{t}\\mathbf{m}^{(0)}+\\beta_{1}^{t-1}\\left(1-\\beta_{1}\\right)\\mathbf{g}_{1}+\\cdots+\\beta_{1}^{2}\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t-2}+\\beta_{1}\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t-1}+\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t}\\\\ \\overset{\\left(a\\right)}{=}& \\beta_{1}^{t-1}\\left(1-\\beta_{1}\\right)\\mathbf{g}_{1}+\\cdots+\\beta_{1}^{2}\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t-2}+\\beta_{1}\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t-1}+\\left(1-\\beta_{1}\\right)\\mathbf{g}_{t}\\\\=& \\sum_{s=1}^{t}\\left(1-\\beta_{1}\\right)\\beta_{1}^{t-s}\\mathbf{g}_{s}=\\left(1-\\beta_{1}\\right)\\sum_{s=1}^{t}\\beta_{1}^{t-s}\\mathbf{g}_{s}\\end{aligned}$

其中（a）处因为 $\\mathbf{m}^{(0)}=\\mathbf{0}$ 。同理，

$\\mathbf{v}^{(t)}=\\left(1-\\beta_{2}\\right)\\sum_{s=1}^{t}\\beta_{2}^{t-s}\\mathbf{g}_{s}^{2}$

我们观察 $\\mathbb{E}\\left[\\mathbf{m}^{(t)}\\right]$ 和 $\\mathbb{E}\\left[\\mathbf{v}^{(t)}\\right]$ ：

$\\mathbb{E}\\left[\\mathbf{m}^{(t)}\\right]=\\left(1-\\beta_{1}\\right)\\sum_{s=1}^{t}\\beta_{1}^{t-s}\\mathbb{E}\\left[\\mathbf{g}_{s}\\right]=\\mathbb{E}\\left[\\mathbf{g}_{s}\\right]\\cdot\\left(1-\\beta_{1}^{t}\\right)$

$\\mathbb{E}\\left[\\mathbf{v}^{(t)}\\right]=\\left(1-\\beta_{2}\\right)\\sum_{s=1}^{t}\\beta_{2}^{t-s}\\mathbb{E}\\left[\\mathbf{g}_{s}^{2}\\right]=\\mathbb{E}\\left[\\mathbf{g}_{s}^{2}\\right]\\cdot\\left(1-\\beta_{2}^{t}\\right)$

为了使 $\\mathbb{E}\\left[\\mathbf{m}^{(t)}\\right]=\\mathbb{E}\\left[\\mathbf{g}_{s}\\right]$ ， $\\mathbb{E}\\left[\\mathbf{v}^{(t)}\\right]=\\mathbb{E}\\left[\\mathbf{g}_{s}^{2}\\right]$ ，我们需要作出以下校正：

$\\begin{aligned}& \\mathbf{m}^{(t)}\\longrightarrow\\hat{\\mathbf{m}}^{(t)}=\\mathbf{m}^{(t)}/\\left(1-\\beta_{1}^{t}\\right), & & \\mathbf{v}^{(t)}\\longrightarrow\\hat{\\mathbf{v}}^{(t)}=\\mathbf{v}^{(t)}/\\left(1-\\beta_{2}^{t}\\right)\\end{aligned}$

Adam 改进了Adagrad的分母，具体表现为：

$\\begin{aligned}\\sqrt{\\sum_{s=1}^{t}\\mathbf{g}_{s}^{2}}\\longrightarrow\\sqrt{\\mathbf{v}^{(t)}}=& \\sqrt{\\sum_{s=1}^{t}\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}\\mathbf{g}_{s}^{2}}\\end{aligned}$

? Adagrad：所有的梯度分配相同的权重，新梯度的影响力越来越弱；分母的数值越来越大，数值计算不稳定，引发数值溢出；

? Adam：旧梯度分配的权重越来越小，例如 $\\mathbf{g}_{1}^{2}$ 的权重 $\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-1}$ 随 $t$ 的增大呈指数衰减；分母的数值始终可控，如果对任意 $s$ ， $\\left\\Vert \\mathbf{g}_{s}^{2}\\right\\Vert _{2}\\leq C$ ，那么 $\\left\\Vert \\mathbf{v}^{(t)}\\right\\Vert _{2}\\leq\\left(1-\\beta_{2}\\right)\\sum_{s=1}^{t}\\beta_{2}^{t-s}\\left\\Vert \\mathbf{g}_{s}^{2}\\right\\Vert _{2}\\leq C\\left(1-\\beta_{2}^{t}\\right)\\leq C.$

2.2 收敛性证明

基本假设与判定指标与SGD、Adagrad完全一致，不做赘述，我们直接进入证明环节。由于基本假设与判定指标没变，我们可以复用SGD、Adagrad证明中的一些结论。

2.2.1 从统计量 $R\\left(T\\right)$ 开始

在Adagrad证明中（大厂推荐算法：【科研喂饭】深度学习算法收敛性证明之Adagrad），我们将 $R\\left(T\\right)$ 的上界具体拆分到每一维变量上，以双重求和的形式呈现

$R\\left(T\\right)\\leq\\sum_{i=1}^{d}\\sum_{t=1}^{T}g_{t,i}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)$

2.2.2 建立联系：从 $\\boldsymbol{\ heta}^{(t)}$ 迭代式到 $\\left\\langle \\mathbf{g}_{t},\\boldsymbol{\ heta}^{(t)}-\\boldsymbol{\ heta}^{\\star}\\right\\rangle$

仿照Adagrad证明，我们需要分离出 $g_{t,i}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)$ 。首先从Adam的迭代表达式出发：对于变量的任意一维 $i$

$\\begin{aligned}\ heta_{i}^{(t+1)}=& \ heta_{i}^{(t)}-\\alpha_{t}\\frac{\\hat{m}_{i}^{(t)}}{\\sqrt{\\hat{v}_{i}^{(t)}}}\\\\=& \ heta_{i}^{(t)}-\\alpha_{t}\\frac{1}{1-\\beta_{1}^{t}}\\frac{m_{i}^{(t)}}{\\sqrt{\\hat{v}_{i}^{(t)}}}\\\\=& \ heta_{i}^{(t)}-\\alpha_{t}\\frac{1}{1-\\beta_{1}^{t}}\\frac{\\beta_{1}m_{i}^{(t-1)}+\\left(1-\\beta_{1}\\right)g_{t,i}}{\\sqrt{\\hat{v}_{i}^{(t)}}}\\end{aligned}$

根据文献[2]，当 $\\beta_{1}$ 取值为常数时算法收敛性难以证明，于是我们令 $\\beta_{1}=\\beta_{1,t}$ ，即让 $\\beta_{1}$ 随迭代次数的增加而变化，且 $\\beta_{1,t}$ 单调不增，即 $\\beta_{1,1}\\geq\\beta_{1,2}\\geq\\ldots\\geq\\beta_{1,t}\\geq\\ldots$ ，也就是说动量将逐渐消失，最终 $m_{i}$ 将趋近于 $g_{i}$ 。此时 $\ heta_{i}^{(t+1)}$ 变成了

$\ heta_{i}^{(t+1)}=\ heta_{i}^{(t)}-\\alpha_{t}\\frac{1}{1-\\prod_{s=1}^{t}\\beta_{1,s}}\\frac{\\beta_{1,t}m_{i}^{(t-1)}+\\left(1-\\beta_{1,t}\\right)g_{t,i}}{\\sqrt{\\hat{v}_{i}^{(t)}}}$

从 $\ heta_{i}^{(t)}$ 到 $\ heta_{i}^{(t+1)}$ 依然是加性的更新。由于形式较为复杂，我们考虑换元，令

$\\gamma_{t}=\\alpha_{t}\\frac{1}{1-\\prod_{s=1}^{t}\\beta_{1,s}}$

于是

$\ heta_{i}^{(t+1)}=\ heta_{i}^{(t)}-\\gamma_{t}\\frac{\\beta_{1,t}m_{i}^{(t-1)}+\\left(1-\\beta_{1,t}\\right)g_{t,i}}{\\sqrt{\\hat{v}_{i}^{(t)}}}$

接下来我们进行分离 $g_{t,i}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)$ 的工作：

$\\begin{aligned}& \ heta_{i}^{(t+1)}=\ heta_{i}^{(t)}-\\gamma_{t}\\frac{\\beta_{1,t}m_{i}^{(t-1)}+\\left(1-\\beta_{1,t}\\right)g_{t,i}}{\\sqrt{\\hat{v}_{i}^{(t)}}}\\\\ \\Longrightarrow & \\left(\ heta_{i}^{(t+1)}-\ heta_{i}^{\\star}\\right)^{2}=\\left[\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)-\\gamma_{t}\\frac{\\beta_{1,t}m_{i}^{(t-1)}+\\left(1-\\beta_{1,t}\\right)g_{t,i}}{\\sqrt{\\hat{v}_{i}^{(t)}}}\\right]^{2}\\\\ \\Longrightarrow & 2\\gamma_{t}\\frac{\\beta_{1,t}m_{i}^{(t-1)}+\\left(1-\\beta_{1,t}\\right)g_{t,i}}{\\sqrt{\\hat{v}_{i}^{(t)}}}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)=\\\\ & \\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}-\\left(\ heta_{i}^{(t+1)}-\ heta_{i}^{\\star}\\right)^{2}+\\gamma_{t}^{2}\\frac{\\left[\\beta_{1,t}m_{i}^{(t-1)}+\\left(1-\\beta_{1,t}\\right)g_{t,i}\\right]^{2}}{\\hat{v}_{i}^{(t)}}\\end{aligned}$

由于 $\\beta_{1,t}m_{i}^{(t-1)}+\\left(1-\\beta_{1,t}\\right)g_{t,i}=m_{i}^{(t)}$ ，

$\\begin{aligned}& g_{t,i}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)=\緻set{\\left(1\\right)}{\緻brace{\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}\\left[\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}-\\left(\ heta_{i}^{(t+1)}-\ heta_{i}^{\\star}\\right)^{2}\\right]}{2\\gamma_{t}\\left(1-\\beta_{1,t}\\right)}}}\\\\ & \緻set{\\left(2\\right)}{\緻brace{-\\frac{\\beta_{1,t}}{1-\\beta_{1,t}}m_{i}^{(t-1)}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)}}+\緻set{\\left(3\\right)}{\緻brace{\\frac{\\gamma_{t}}{2\\left(1-\\beta_{1,t}\\right)}\\frac{\\left(m_{i}^{(t)}\\right)^{2}}{\\sqrt{\\hat{v}_{i}^{(t)}}}}}\\end{aligned}$

接下来我们将对（1）、（2）、（3）三项分别放缩。

2.2.3 对 $R\\left(T\\right)$ 的上界做放缩

在Adam算法中，对 $R\\left(T\\right)$ 上界的放缩即对上述（1）、（2）、（3）三项的放缩。

关于（1），我们有

$\\begin{aligned}& \\sum_{t=1}^{T}\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}\\left[\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}-\\left(\ heta_{i}^{(t+1)}-\ heta_{i}^{\\star}\\right)^{2}\\right]}{2\\gamma_{t}\\left(1-\\beta_{1,t}\\right)}\\\\=& \\sum_{t=1}^{T}\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}\\left[\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}-\\left(\ heta_{i}^{(t+1)}-\ heta_{i}^{\\star}\\right)^{2}\\right]}{2\\alpha_{t}\\frac{1}{1-\\prod_{s=1}^{t}\\beta_{1,s}}\\left(1-\\beta_{1,t}\\right)}\\\\=& \\sum_{t=1}^{T}\\frac{\\sqrt{v_{i}^{(t)}}\\left[\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}-\\left(\ heta_{i}^{(t+1)}-\ heta_{i}^{\\star}\\right)^{2}\\right]\\left(1-\\prod_{s=1}^{t}\\beta_{1,s}\\right)}{2\\alpha_{t}\\left(1-\\beta_{1,t}\\right)}\\\\ \\leq & \\sum_{t=1}^{T}\\frac{\\sqrt{v_{i}^{(t)}}\\left[\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}-\\left(\ heta_{i}^{(t+1)}-\ heta_{i}^{\\star}\\right)^{2}\\right]}{2\\alpha_{t}\\left(1-\\beta_{1,1}\\right)}\\end{aligned}$

随即错位重组求和

$\\begin{aligned}& \\sum_{t=1}^{T}\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}\\left[\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}-\\left(\ heta_{i}^{(t+1)}-\ heta_{i}^{\\star}\\right)^{2}\\right]}{2\\gamma_{t}\\left(1-\\beta_{1,t}\\right)}\\\\ \\leq & \\sum_{t=1}^{T}\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}}{2\\alpha_{t}\\left(1-\\beta_{1,1}\\right)}-\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}\\left(\ heta_{i}^{(t+1)}-\ heta_{i}^{\\star}\\right)^{2}}{2\\alpha_{t}\\left(1-\\beta_{1,1}\\right)}\\\\=& \\frac{\\sqrt{\\hat{v}_{i}^{(1)}}\\left(\ heta_{i}^{(1)}-\ heta_{i}^{\\star}\\right)^{2}}{2\\alpha_{1}\\left(1-\\beta_{1,1}\\right)}-\\frac{\\sqrt{\\hat{v}_{i}^{(T)}}\\left(\ heta_{i}^{(T+1)}-\ heta_{i}^{\\star}\\right)^{2}}{2\\alpha_{T}\\left(1-\\beta_{1,1}\\right)}\\\\ & +\\sum_{t=2}^{T}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}\\cdot\\left[\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}}{2\\alpha_{t}\\left(1-\\beta_{1,1}\\right)}-\\frac{\\sqrt{\\hat{v}_{i}^{(t-1)}}}{2\\alpha_{t-1}\\left(1-\\beta_{1,1}\\right)}\\right]\\end{aligned}$

我们重点看第三项 $\\sum_{t=2}^{T}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}\\cdot\\left[\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}}{2\\alpha_{t}\\left(1-\\beta_{1,1}\\right)}-\\frac{\\sqrt{\\hat{v}_{i}^{(t-1)}}}{2\\alpha_{t-1}\\left(1-\\beta_{1,1}\\right)}\\right]$ ，这一项的放缩时常为人诟病，因为它是有条件的，当 $\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}}{\\alpha_{t}}\\geq\\frac{\\sqrt{\\hat{v}_{i}^{(t-1)}}}{\\alpha_{t-1}}$ 对任意 $t$ 恒成立时：

$\\begin{aligned}& \\sum_{t=2}^{T}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}\\cdot\\left[\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}}{2\\alpha_{t}\\left(1-\\beta_{1,1}\\right)}-\\frac{\\sqrt{\\hat{v}_{i}^{(t-1)}}}{2\\alpha_{t-1}\\left(1-\\beta_{1,1}\\right)}\\right]\\\\ \\leq & \\sum_{t=2}^{T}D_{i}^{2}\\cdot\\left[\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}}{2\\alpha_{t}\\left(1-\\beta_{1,1}\\right)}-\\frac{\\sqrt{\\hat{v}_{i}^{(t-1)}}}{2\\alpha_{t-1}\\left(1-\\beta_{1,1}\\right)}\\right]\\\\=& D_{i}^{2}\\left[\\frac{\\sqrt{\\hat{v}_{i}^{(T)}}}{2\\alpha_{T}\\left(1-\\beta_{1,1}\\right)}-\\frac{\\sqrt{\\hat{v}_{i}^{(1)}}}{2\\alpha_{1}\\left(1-\\beta_{1,1}\\right)}\\right]\\end{aligned}$

其中用到了变量有界假设。需要注意的是，Adam算法不能使 $\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}}{\\alpha_{t}}\\geq\\frac{\\sqrt{\\hat{v}_{i}^{(t-1)}}}{\\alpha_{t-1}}$ 对任意 $t$ 恒成立，于是有人提出Amsgrad[3]，补上了这一漏洞。最后还剩下些扫尾的工作，因为 $-\\frac{\\sqrt{\\hat{v}_{i}^{(T)}}\\left(\ heta_{i}^{(T+1)}-\ heta_{i}^{\\star}\\right)^{2}}{2\\alpha_{T}\\left(1-\\beta_{1,1}\\right)}\\leq0$ ， $\\frac{\\sqrt{\\hat{v}_{i}^{(1)}}\\left(\ heta_{i}^{(1)}-\ heta_{i}^{\\star}\\right)^{2}}{2\\alpha_{1}\\left(1-\\beta_{1,1}\\right)}\\leq\\frac{D_{i}^{2}\\sqrt{\\hat{v}_{i}^{(1)}}}{2\\alpha_{1}\\left(1-\\beta_{1,1}\\right)}$ ，于是（1）放缩到

接下来我们关注 $\\hat{v}_{i}^{(T)}$ 以便进一步放缩，前面我们有提到 $v_{i}^{(t)}=\\left(1-\\beta_{2}\\right)\\sum_{s=1}^{t}\\beta_{2}^{t-s}g_{s,i}^{2}$ ，我们借此机会来探索 $\\hat{v}_{i}^{(t)}$ 和 $v_{i}^{(t)}$ 的有界性：运用梯度有界假设

$\\left.\\begin{array}{c}v_{i}^{(t)}\\leq\\\\ \\hat{v}_{i}^{(t)}=\\end{array}\\right\\}\\frac{v_{i}^{(t)}}{1-\\beta_{2}^{t}}\\leq\\frac{\\left(1-\\beta_{2}\\right)\\sum_{s=1}^{t}\\beta_{2}^{t-s}G_{i}^{2}}{1-\\beta_{2}^{t}}=\\frac{G_{i}^{2}\\left(1-\\beta_{2}^{t}\\right)}{1-\\beta_{2}^{t}}=G_{i}^{2}$

那么最终（1）放缩到

我们保留 $\\alpha_{T}$ 以便后续设计最优学习率。

关于（2），我们首先运用运用变量有界假设

$\\begin{aligned}\\sum_{t=1}^{T}-\\frac{\\beta_{1,t}}{1-\\beta_{1,t}}m_{i}^{(t-1)}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)=& \\sum_{t=1}^{T}\\frac{\\beta_{1,t}}{1-\\beta_{1,t}}m_{i}^{(t-1)}\\left[-\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)\\right]\\\\ \\leq & \\sum_{t=1}^{T}\\frac{\\beta_{1,t}}{1-\\beta_{1,t}}\\left|m_{i}^{(t-1)}\\right|D_{i}\\end{aligned}$

接着我们关注 $m_{i}^{(t-1)}$ ：

$\\begin{aligned}m_{i}^{(t)}=& \\beta_{1,t}m_{i}^{(t-1)}+\\left(1-\\beta_{1,t}\\right)g_{t,i}\\\\=& \\beta_{1,t}\\beta_{1,t-1}m_{i}^{(t-2)}+\\beta_{1,t}\\left(1-\\beta_{1,t-1}\\right)g_{t-1,i}+\\left(1-\\beta_{1,t}\\right)g_{t,i}\\\\=& \\beta_{1,t}\\beta_{1,t-1}\\beta_{1,t-2}m_{i}^{(t-3)}+\\beta_{1,t}\\beta_{1,t-1}\\left(1-\\beta_{1,t-2}\\right)g_{t-2,i}\\\\ & +\\beta_{1,t}\\left(1-\\beta_{1,t-1}\\right)g_{t-1,i}+\\left(1-\\beta_{1,t}\\right)g_{t,i}\\\\=& \\beta_{1,t}\\beta_{1,t-1}\\cdots\\beta_{1,1}m_{i}^{(0)}+\\beta_{1,t}\\beta_{1,t-1}\\cdots\\left(1-\\beta_{1,1}\\right)g_{1,i}+\\cdots\\\\ & +\\beta_{1,t}\\beta_{1,t-1}\\left(1-\\beta_{1,t-2}\\right)g_{t-2,i}+\\beta_{1,t}\\left(1-\\beta_{1,t-1}\\right)g_{t-1,i}+\\left(1-\\beta_{1,t}\\right)g_{t,i}\\\\ \\overset{\\left(a\\right)}{=}& \\beta_{1,t}\\beta_{1,t-1}\\cdots\\left(1-\\beta_{1,1}\\right)g_{1,i}+\\cdots+\\beta_{1,t}\\beta_{1,t-1}\\left(1-\\beta_{1,t-2}\\right)g_{t-2,i}\\\\ & +\\beta_{1,t}\\left(1-\\beta_{1,t-1}\\right)g_{t-1,i}+\\left(1-\\beta_{1,t}\\right)g_{t,i}\\\\=& \\sum_{s=1}^{t}\\left(1-\\beta_{1,s}\\right)\\left(\\prod_{k=s+1}^{t}\\beta_{1,k}\\right)g_{s,i}\\end{aligned}$

其中（a）处因为 $m_{i}^{(0)}=0$ 。此时我们运用梯度有界假设，对任意 $t$ 都有

$\\begin{aligned}\\left|m_{i}^{(t)}\\right|\\leq & \\sum_{s=1}^{t}\\left(1-\\beta_{1,s}\\right)\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)\\left|g_{s,i}\\right|\\\\ \\leq & \\sum_{s=1}^{t}\\left(1-\\beta_{1,s}\\right)\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)G_{i}=G_{i}\\left(1-\\prod_{s=1}^{t}\\beta_{1,s}\\right)\\leq G_{i}\\end{aligned}$

这样我们就能放缩（2）式了：

$\\begin{aligned}& \\sum_{t=1}^{T}-\\frac{\\beta_{1,t}}{1-\\beta_{1,t}}m_{i}^{(t-1)}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)\\\\ \\leq & \\sum_{t=1}^{T}\\frac{\\beta_{1,t}}{1-\\beta_{1,t}}G_{i}D_{i}\\\\=& G_{i}D_{i}\\sum_{t=1}^{T}\\frac{\\beta_{1,t}}{1-\\beta_{1,t}}\\end{aligned}$

关于（3），我们重点研究 $\\frac{\\left(m_{i}^{(t)}\\right)^{2}}{\\sqrt{\\hat{v}_{i}^{(t)}}}=\\sqrt{1-\\beta_{2}^{t}}\\frac{\\left(m_{i}^{(t)}\\right)^{2}}{\\sqrt{v_{i}^{(t)}}}\\leq\\frac{\\left(m_{i}^{(t)}\\right)^{2}}{\\sqrt{v_{i}^{(t)}}}$ ，分别看分子和分母：

$\\begin{alignedat}{1}m_{i}^{(t)}=& \\sum_{s=1}^{t}\\left(1-\\beta_{1,s}\\right)\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)g_{s,i}\\\\ v_{i}^{(t)}=& \\left(1-\\beta_{2}\\right)\\sum_{s=1}^{t}\\beta_{2}^{t-s}g_{s,i}^{2}\\end{alignedat}$

在充分考虑 $m_{i}^{(t)}$ 和 $v_{i}^{(t)}$ 的形式后，我们对 $\\left(m_{i}^{(t)}\\right)^{2}$ 做如下变换

$\\left(m_{i}^{(t)}\\right)^{2}=\\left(\\sum_{s=1}^{t}\\frac{\\left(1-\\beta_{1,s}\\right)\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)}{\\sqrt{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}}\\cdot\\sqrt{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}g_{s,i}\\right)^{2}$

这样的变换方便我们应用柯西不等式：

$\\begin{aligned}& \\left(m_{i}^{(t)}\\right)^{2}=\\left(\\sum_{s=1}^{t}\\frac{\\left(1-\\beta_{1,s}\\right)\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)}{\\sqrt{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}}\\cdot\\sqrt{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}g_{s,i}\\right)^{2}\\\\ & \\leq\\sum_{s=1}^{t}\\left(\\frac{\\left(1-\\beta_{1,s}\\right)\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)}{\\sqrt{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}}\\right)^{2}\\cdot\\sum_{s=1}^{t}\\left(\\sqrt{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}g_{s,i}\\right)^{2}\\\\ &=\\sum_{s=1}^{t}\\frac{\\left(1-\\beta_{1,s}\\right)^{2}\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)^{2}}{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}\\cdot\緻set{v_{i}^{(t)}}{\緻brace{\\sum_{s=1}^{t}\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}g_{s,i}^{2}}}\\end{aligned}$

这样我们就能处理（3）式了

$\\begin{aligned}& \\sum_{t=1}^{T}\\frac{\\gamma_{t}}{2\\left(1-\\beta_{1,t}\\right)}\\frac{\\left(m_{i}^{(t)}\\right)^{2}}{\\sqrt{\\hat{v}_{i}^{(t)}}}\\leq\\sum_{t=1}^{T}\\frac{\\gamma_{t}}{2\\left(1-\\beta_{1,t}\\right)}\\cdot\\\\ & \\sum_{s=1}^{t}\\frac{\\left(1-\\beta_{1,s}\\right)^{2}\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)^{2}}{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}\\cdot\\frac{\\sum_{s=1}^{t}\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}g_{s,i}^{2}}{\\sqrt{\\sum_{s=1}^{t}\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}g_{s,i}^{2}}}\\\\ &=\\sum_{t=1}^{T}\\frac{\\gamma_{t}}{2\\left(1-\\beta_{1,t}\\right)}\\sum_{s=1}^{t}\\frac{\\left(1-\\beta_{1,s}\\right)^{2}\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)^{2}}{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}\\sqrt{v_{i}^{(t)}}\\\\ & \\leq\\sum_{t=1}^{T}\\frac{\\gamma_{t}}{2\\left(1-\\beta_{1,t}\\right)}\\cdot\\sum_{s=1}^{t}\\frac{\\left(1-\\beta_{1,s}\\right)^{2}\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)^{2}}{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}\\cdot G_{i}\\end{aligned}$

最后一步放缩利用了 $v_{i}^{(t)}$ 的有界性。

在整理出 $R\\left(T\\right)$ 的上界之前，我们做个小小的总结：对于（1），当 $\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}}{\\alpha_{t}}\\geq\\frac{\\sqrt{\\hat{v}_{i}^{(t-1)}}}{\\alpha_{t-1}}$ 对任意 $t$ 恒成立时，

$\\sum_{t=1}^{T}\\frac{\\sqrt{v_{i}^{(t)}}\\left[\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}-\\left(\ heta_{i}^{(t+1)}-\ heta_{i}^{\\star}\\right)^{2}\\right]}{2\\gamma_{t}\\left(1-\\beta_{1,t}\\right)}\\leq\\frac{D_{i}^{2}G_{i}}{2\\alpha_{T}\\left(1-\\beta_{1,1}\\right)}$

对于（2），

$\\sum_{t=1}^{T}-\\frac{\\beta_{1,t}}{1-\\beta_{1,t}}m_{i}^{(t-1)}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)\\leq G_{i}D_{i}\\sum_{t=1}^{T}\\frac{\\beta_{1,t}}{1-\\beta_{1,t}}$

对于（3），

最后我们整理出 $R\\left(T\\right)$ 的上界

$\\begin{aligned}R\\left(T\\right)\\leq & \\sum_{i=1}^{d}\\frac{D_{i}^{2}G_{i}}{2\\alpha_{T}\\left(1-\\beta_{1,1}\\right)}+\\sum_{i=1}^{d}G_{i}D_{i}\\sum_{t=1}^{T}\\frac{\\beta_{1,t}}{1-\\beta_{1,t}}\\\\ & +\\sum_{i=1}^{d}G_{i}\\sum_{t=1}^{T}\\frac{\\gamma_{t}}{2\\left(1-\\beta_{1,t}\\right)}\\cdot\\sum_{s=1}^{t}\\frac{\\left(1-\\beta_{1,s}\\right)^{2}\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)^{2}}{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}\\\\=& \\frac{\\sum_{i=1}^{d}D_{i}^{2}G_{i}}{2\\alpha_{T}\\left(1-\\beta_{1,1}\\right)}+\\left(\\sum_{i=1}^{d}G_{i}D_{i}\\right)\\left(\\sum_{t=1}^{T}\\frac{\\beta_{1,t}}{1-\\beta_{1,t}}\\right)+\\left(\\sum_{i=1}^{d}G_{i}\\right)\\cdot\\\\ & \\left[\\sum_{t=1}^{T}\\frac{\\gamma_{t}}{2\\left(1-\\beta_{1,t}\\right)}\\cdot\\sum_{s=1}^{t}\\frac{\\left(1-\\beta_{1,s}\\right)^{2}\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)^{2}}{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}\\right]\\end{aligned}$

2.2.4 设计最优超参数

本节我们关注超参数 $\\left\\{ \\gamma_{t}\\right\\}$ 、 $\\left\\{ \\beta_{1,t}\\right\\}$ 、 $\\beta_{2}$ 的设计。首先是 $\\left\\{ \\beta_{1,t}\\right\\}$ 和 $\\beta_{2}$

$\\beta_{1,t}\\in\\left(0,1\\right)$ ， $\\forall t$ ，随迭代步数递减，即 $\\beta_{1,1}\\geq\\beta_{1,2}\\geq\\ldots\\geq\\beta_{1,T}\\geq\\ldots$
$\\beta_{2}\\in\\left(0,1\\right)$ ， $\\frac{\\beta_{1,t}}{\\sqrt{\\beta_{2}}}\\leq\\sqrt{c}<1$ ， $\\forall t$

根据 $\\left\\{ \\beta_{1,t}\\right\\}$ 和 $\\beta_{2}$ ，我们继续放缩：关于（1），保持不变

$\\frac{\\sum_{i=1}^{d}D_{i}^{2}G_{i}}{2\\alpha_{T}\\left(1-\\beta_{1,1}\\right)}$

关于（2），

$\\left(\\sum_{i=1}^{d}G_{i}D_{i}\\right)\\left(\\sum_{t=1}^{T}\\frac{\\beta_{1,t}}{1-\\beta_{1,t}}\\right)\\leq\\left(\\sum_{i=1}^{d}G_{i}D_{i}\\right)\\left(\\frac{1}{1-\\beta_{1,1}}\\sum_{t=1}^{T}\\beta_{1,t}\\right)$

关于（3），

$\\begin{aligned}& \\left(\\sum_{i=1}^{d}G_{i}\\right)\\cdot\\sum_{t=1}^{T}\\frac{\\gamma_{t}}{2\\left(1-\\beta_{1,t}\\right)}\\cdot\\sum_{s=1}^{t}\\frac{\\left(1-\\beta_{1,s}\\right)^{2}\\left(\\prod_{r=s+1}^{t}\\beta_{1,r}\\right)^{2}}{\\left(1-\\beta_{2}\\right)\\beta_{2}^{t-s}}\\\\=& \\left(\\sum_{i=1}^{d}G_{i}\\right)\\cdot\\sum_{t=1}^{T}\\frac{\\alpha_{t}}{2\\left(1-\\beta_{1,t}\\right)\\left(1-\\prod_{s=1}^{t}\\beta_{1,s}\\right)}\\cdot\\sum_{s=1}^{t}\\left(\\frac{1-\\beta_{1,s}}{\\sqrt{1-\\beta_{2}}}\\right)^{2}\\prod_{r=s+1}^{t}\\left(\\frac{\\beta_{1,r}}{\\sqrt{\\beta_{2}}}\\right)^{2}\\\\ \\overset{\\left(a\\right)}{\\leq}& \\left(\\sum_{i=1}^{d}G_{i}\\right)\\cdot\\sum_{t=1}^{T}\\frac{\\alpha_{t}}{2\\left(1-\\beta_{1,1}\\right)^{2}\\left(1-\\beta_{2}\\right)}\\sum_{s=1}^{t}\\prod_{r=s+1}^{t}c\\\\=& \\left(\\sum_{i=1}^{d}G_{i}\\right)\\cdot\\sum_{t=1}^{T}\\frac{\\alpha_{t}}{2\\left(1-\\beta_{1,1}\\right)^{2}\\left(1-\\beta_{2}\\right)\\left(1-c\\right)}=\\left(\\sum_{i=1}^{d}G_{i}\\right)\\cdot\\frac{\\sum_{t=1}^{T}\\alpha_{t}}{2\\left(1-\\beta_{1,1}\\right)^{2}\\left(1-\\beta_{2}\\right)\\left(1-c\\right)}\\end{aligned}$

其中（a）处根据假设 $\\frac{\\beta_{1,t}}{\\sqrt{\\beta_{2}}}\\leq\\sqrt{c}<1$ 。

至此， $R\\left(T\\right)$ 上界的数量级仅与 $\\frac{1}{\\alpha_{T}}$ 、 $\\sum_{t=1}^{T}\\beta_{1,t}$ 、 $\\sum_{t=1}^{T}\\alpha_{t}$ 有关。根据SGD中的结论，如果 $\\alpha_{t}=C/t^{p}$ ， $\\frac{1}{\\alpha_{T}}=\\mathcal{O}\\left(T^{p}\\right)$ ， $\\sum_{t=1}^{T}\\alpha_{t}=\\mathcal{O}\\left(T^{1-p}\\right)$ ；当 $p=1/2$ 时，取到最优上界 $\\mathcal{O}\\left(T^{1/2}\\right)$ ，这意味着 $R\\left(T\\right)$ 的最优上界不会低于 $\\mathcal{O}\\left(T^{1/2}\\right)$ 。如果我们希望 $\\beta_{1,t}$ 衰减尽可能慢（动量项衰减尽可能慢），可使

$\\beta_{1,t}=\\frac{\\beta_{1}}{\\sqrt{t}}$

这样 $\\sum_{t=1}^{T}\\beta_{1,t}=\\mathcal{O}\\left(T^{1/2}\\right)$ ， $R\\left(T\\right)$ 的数量级也就维持在最优状态 $\\mathcal{O}\\left(T^{1/2}\\right)$ 。

至此我们做个总结：

? 当目标函数 $f_{t}\\left(\\boldsymbol{\ heta}\\right)$ 对任意 $t$ 均为convex函数时，SGD、Adagrad、Adam的 $R\\left(T\\right)$ 上界最优数量级均为 $\\mathcal{O}\\left(T^{1/2}\\right)$ ，算法均收敛。

? 从理论上来看，三者的收敛速率相同；在工程实际中，Adam的收敛速率一般最快。

? 在工程实践中， $f_{t}\\left(\\boldsymbol{\ heta}\\right)$ 为convex函数的情形十分少见，以推荐系统的场景为例，仅有逻辑回归符合要求。

? 在现有证明框架下，Adam算法的动量项必须衰减，并且至少以平方根的速率衰减；然而在工程实践中，动量项的超参数 $\\beta_{1,t}$ 一般设置为常数，不影响算法的实际收敛性。若要证明 $\\beta_{1,t}=\\beta_{1}\\left(<1\\right)$ 时Adam算法依旧收敛，可考虑修改算法的前提假设、评价指标、证明框架等。

$R\\left(T\\right)$ 上界的计算与放缩步骤可总结为以下几个步骤：

$R\\left(T\\right)\\leq\\sum_{i=1}^{d}\\sum_{t=1}^{T}g_{t,i}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)$ ；
从 $\ heta_{i}^{(t)}$ 的迭代式中分离出 $g_{t,i}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)$ ；
对分离后的结果分部分放缩，常用手段有：（i）变量、梯度有界假设，（ii）错位重组求和，（iii）数学不等式：级数求和、柯西不等式；
令 $\\alpha_{t}=C/t^{p}$ ，兼顾其他超参数，设计最优学习率。

为克服Adam算法收敛性证明中的缺陷，Reddi et al.[3]提出Amsgrad，旨在对Adam做的改进：从 $\\hat{\\mathbf{v}}^{(t)}=\\mathbf{v}^{(t)}/\\left(1-\\beta_{2}^{t}\\right)$ 改进为

$\\hat{\\mathbf{v}}^{(t)}=\\max\\left(\\hat{\\mathbf{v}}^{(t-1)},\\mathbf{v}^{(t)}/\\left(1-\\beta_{2}^{t}\\right)\\right)$

TensorFlow 2.0版本的Adam优化器可以很方便地实现Amsgrad：

$\ extrm{tf.optimizers.Adam(learning_rate=}\\alpha_{t}\ extrm{，amsgrad=True)}$

参数amsgrad的默认值为False，amsgrad=False对应Adam算法。文献[3]中Amsgrad未做均值校正，为了最大限度复用Adam的证明，我们补充均值校正的操作。均值校正操作不影响算法收敛性。

Amsgrad收敛性证明以复用Adam证明为主，仍然成立的核心结论有：

$\\begin{aligned}R\\left(T\\right)\\leq & \\sum_{i=1}^{d}\\sum_{t=1}^{T}g_{t,i}\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)\\end{aligned}$

我们依然是对（1）、（2）、（3）三项分别放缩，由于（2）不涉及 $\\hat{v}_{i}^{(t)}$ ，结论可以全部复用，我们只需关注（1）和（3）。关于（1），我们可以复用 $\\hat{v}_{i}^{(t)}$ 展开前的所有结论：当 $\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}}{\\alpha_{t}}\\geq\\frac{\\sqrt{\\hat{v}_{i}^{(t-1)}}}{\\alpha_{t-1}}$ 对任意 $t$ 恒成立时，

$\\begin{aligned}\\sum_{t=1}^{T}\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}\\left[\\left(\ heta_{i}^{(t)}-\ heta_{i}^{\\star}\\right)^{2}-\\left(\ heta_{i}^{(t+1)}-\ heta_{i}^{\\star}\\right)^{2}\\right]}{2\\gamma_{t}\\left(1-\\beta_{1,t}\\right)}\\leq & \\frac{D_{i}^{2}\\sqrt{\\hat{v}_{i}^{(T)}}}{2\\alpha_{T}\\left(1-\\beta_{1,1}\\right)}\\end{aligned}$

我们接下来验证 $\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}}{\\alpha_{t}}\\geq\\frac{\\sqrt{\\hat{v}_{i}^{(t-1)}}}{\\alpha_{t-1}}$ 对任意 $t$ 恒成立。 $\\sqrt{\\hat{v}_{i}^{(t)}}=\\sqrt{\\max\\left(\\hat{v}_{i}^{(t-1)},\\frac{v_{i}^{(t)}}{1-\\beta_{2}^{t}}\\right)}\\geq\\sqrt{\\hat{v}_{i}^{(t-1)}}$ ， $\\alpha_{t}$ 在单调不增的情况下： $\\alpha_{t}\\leq\\alpha_{t-1}$ ，即 $\\frac{1}{\\alpha_{t}}\\geq\\frac{1}{\\alpha_{t-1}}$ ，因此 $\\frac{\\sqrt{\\hat{v}_{i}^{(t)}}}{\\alpha_{t}}\\geq\\frac{\\sqrt{\\hat{v}_{i}^{(t-1)}}}{\\alpha_{t-1}}$ 对任意 $t$ 恒成立。我们还需要重新审视 $\\hat{v}_{i}^{(t)}$ 和 $v_{i}^{(t)}$ 的有界性：

$v_{i}^{(t)}\\leq\\frac{v_{i}^{(t)}}{1-\\beta_{2}^{t}}\\leq\\frac{\\left(1-\\beta_{2}\\right)\\sum_{s=1}^{t}\\beta_{2}^{t-s}G_{i}^{2}}{1-\\beta_{2}^{t}}=\\frac{G_{i}^{2}\\left(1-\\beta_{2}^{t}\\right)}{1-\\beta_{2}^{t}}=G_{i}^{2}$

$\\hat{v}_{i}^{(0)}=0\\leq G_{i}^{2}$

若 $\\hat{v}_{i}^{(t-1)}\\leq G_{i}^{2}$ ，

$\\hat{v}_{i}^{(t)}=\\max\\left(\\hat{v}_{i}^{(t-1)},\\frac{v_{i}^{(t)}}{1-\\beta_{2}^{t}}\\right)=\\max\\left\\{ \\begin{array}{c}\\hat{v}_{i}^{(t-1)}\\leq G_{i}^{2}\\\\ \\frac{v_{i}^{(t)}}{1-\\beta_{2}^{t}}\\leq G_{i}^{2}\\end{array}\\right.\\leq G_{i}^{2}$

于是 $\\hat{v}_{i}^{(t)}$ 和 $v_{i}^{(t)}$ 的有界性与Adam中一致，因此第一项的结论可以直接复用。

关于（3），我们通过观察发现

$\\frac{\\left(m_{i}^{(t)}\\right)^{2}}{\\sqrt{\\hat{v}_{i}^{(t)}}}=\\frac{\\left(m_{i}^{(t)}\\right)^{2}}{\\sqrt{\\max\\left(\\hat{v}_{i}^{(t-1)},\\frac{v_{i}^{(t)}}{1-\\beta_{2}^{t}}\\right)}}\\leq\\frac{\\left(m_{i}^{(t)}\\right)^{2}}{\\sqrt{\\frac{v_{i}^{(t)}}{1-\\beta_{2}^{t}}}}=\\sqrt{1-\\beta_{2}^{t}}\\frac{\\left(m_{i}^{(t)}\\right)^{2}}{\\sqrt{v_{i}^{(t)}}}\\leq\\frac{\\left(m_{i}^{(t)}\\right)^{2}}{\\sqrt{v_{i}^{(t)}}}$

即 $\\frac{\\left(m_{i}^{(t)}\\right)^{2}}{\\sqrt{\\hat{v}_{i}^{(t)}}}\\leq\\frac{\\left(m_{i}^{(t)}\\right)^{2}}{\\sqrt{v_{i}^{(t)}}}$ 依然成立，因此第三项的结论也可以直接复用，Amsgrad收敛性证毕。

最后我们简单评价一下Amsgrad：Amsgrad改进了 $\\hat{\\mathbf{v}}^{(t)}$ ，给Adam算法从收敛性证明的角度打了补丁；但在工程实践中，Amsgrad的性能未必会比Adam更胜一筹，时至今日，Adam依然是使用最广泛的优化器。

[1]M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” in Proceedings of the 20th international conference on machine learning (ICML-03), 2003, pp. 928– 936.

[2]D. P. Kingma and J. Ba, "Adam: A method for stochastic optimization," arXiv preprint arXiv:1412.6980, 2014.

[3]S. J. Reddi, S. Kale, and S. Kumar, "On the convergence of adam and beyond," arXiv preprint arXiv:1904.09237, 2019.

上一篇：一篇搞懂留学存款证明所有问题

下一篇：时评丨强化要素保障优化营商环境

【科研喂饭】深度学习算法收敛性证明之Adam

推荐阅读

推荐产品

北京某某塑料板材有限公司

公司新闻

相关资讯

联系我们