连续时间随机梯度下降：一个中心极限定理

此外，对于具有布朗运动的inSDE模型，Q学习算法可以随着时间步长的增大而膨胀 变小；详见【14】。1.3文件的组织在第2节中，我们陈述了我们的假设和本文的主要结果。p的Lpconvergencerate的proo f≥ 1在第3节中。强凸情形下CLT的证明见第4节。第5节证明了一类非凸模型的中心极限定理。在第6节中，收敛速率结果用于分析连续时间算法中随机梯度下降的行为和动力学。证明所需的一些技术结果见附录A。附录B包含定理2.11的证明，这加强了[14]的收敛结果。特别是在r中，附录B对[14]的证明进行了必要的调整，以确保在允许模型f（x，θ）相对于θ增长的情况下收敛。2主要结果我们证明了三个主要结果。定理2.7是强凸情形下的Lpconvergence。定理2.8是强凸情形的中心极限定理。定理m 2.13是单临界点非凸情形的中心极限定理。如果存在一个C>0的函数，使得zh（θ）z≥ Cz公司z表示任何非零z∈ Rk。h是函数h（θ）的Hessia n矩阵。条件2.6和2.12要求CCα>1，其中Cα是学习率的大小，C是目标函数“g”（θ）的强凸性常数*) 在点θ=θ处*. 这是本文收敛分析的一个重要结论：为了获得最佳的收敛速度，需要充分提高学习速度。

这种收敛率对学习率的依赖性并不特定于本文中的算法SGDCT，但也适用于其他算法（甚至是确定性梯度下降算法）。我们将在第6节对此进行更详细的讨论。应该强调的是，定理2.7和定理2.8（强对流）的假设允许模型f（x，θ）增长到θ的二次方。另一方面，在假设f（x，θ）在θ中线性增长的情况下，证明了定理2.13（非凸情形）。对于定理2.7、2.8和2，允许模型f（x，θ）的增长在x中为多项式。定理2.7、2.8和2.13的证明分别在第3、4和5节。附录A中给出了这些证明需要d的一些技术结果。附录B包含了一些变化，将[14]的收敛性证明从g（θ）有界的情况推广到g（θ）在θ中的平方；有关相应的严格声明，请参见定理2.11。现在让我们列出我们的条件。条件2.1保证了X过程不变测度的唯一性和存在性。条件2.1和条件2.2的第二部分保证方程（1.1）是适定的。我们将使用符号k·k表示向量和矩阵的欧几里德范数。k·k表示l-norm和k·kP表示lp-标准。条件2.1。我们假设σσ是非退化常微分矩阵和lim | x|→∞f*（x） ·x个=-∞.关于所涉及函数的正则性，我们施加以下条件2.2。条件2.2。1、我们假设θg（x，·）∈ 所有x的C（Rk）∈ 十、 Rm，θgx个∈ C十、 Rk公司, θg（·，θ）∈Cα（X）在θ中均匀分布∈ Rk对于某些α∈ (0, 1).2、功能f*（x） 是C2+α（x）和α∈ (0, 1).

也就是说，它在x上有两个导数，所有部分导数都是H¨older连续的，指数α，w相对于x.3。每t≥ 0，方程（1.2）有唯一的强解。施加条件2.3和2.4，以确保θthas有界力矩在时间t内一致。条件2.3。存在常数R<∞ 几乎处处都是正函数κ（x）s uch thath-θg（x，θ），θ/kθki≤ -κ（x）kθk，对于kθk≥ R、 条件2.4。考虑函数τ（x，θ）=θf（x，θ）θf（x，θ）θkθk，θkθk1/2. （2.1）然后，存在一个函数λ（x），在kxk中增长不快于多项式，因此对于任何θ，θ∈ RK和x∈ Rm |τ（x，θ）- τ（x，θ）|≤ |λ（x）|ρ（kθ- θk）（2.2），其中ρ（ξ）是[0]上的增函数，∞) ρ（0）=0且rξ>0ρ-2（ξ）dξ=∞.注意，当θ为一维时，条件2.4相当简单。条件2.4始终适用于以下情况：θf（x，θ）与θ无关（例如，当f（x，θ）是θ中的一个函数时）。此外，如果f（x，θ）和θf（x，θ）在θ中一致有界，在x中多项式有界，条件ns2.3和2。在非凸情况下，CLT不需要4（定理2.13）。有必要使用条件2.3和2.4证明支持≥0E[kθtkp]<k表示p≥ 2、我们在附录e ndix A.1中证明的这种矩的统一性，反过来又需要用于证明定理2.7和2.8中的Lpconvergenceand中心极限定理。函数g（x，θ）允许增长，这意味着θ的矩有一些先验界是必要的。关于学习率，我们假设条件2.5。学习速率为αt=CαC+t，其中Cα>0和C>0为常数。条件2.5使结果更容易呈现。然而，正如我们将在推论2.14中看到的，只要αtsatis满足一定的条件，那么特定形式αt=cαc+是不必要的。

我们选择在本规范下为m呈现结果，既是为了呈现目的，也是因为这是学习率在实践中的常见形式。然而，我们确实在Cor ollary2.14中发送了一般学习率的结果。条件2.6。1.iθf（x，θ）≤ K1+kxkq+kθk（2-（一）∨0, 对于i=0、1、2、3和某些有限常数，q<∞.2.’g（θ）是常数C.3的强凸。CCα>1.4。\'g（θ）∈ 加拿大iθ′g（θ）≤ K1+kθk4-我, 对于i=0、1、2、3和某些有限常数K<∞.从定理2.7和2的证明中可以看出。8，需要控制formRtαs的项(\'g（θs）- g（Xs，θs））ds。由于X过程的遍历性，没人会认为这样的项在数量上很小，并且随着t的增加而变为零→ ∞. 然而，它们归零的速度在这里很重要。我们通过使用适当的泊松型偏微分方程（PDE）等效重写这些项来处理这些项。条件2.1、2.2和2.6保证这些泊松方程具有唯一解，其在x和θ变量s中的增长速度不超过多项式（见附录A中的定理A.1）。定理2.7。假设条件2.1、2.2、2.3、2.4、2.5和2.6成立。那么，对于p≥ 1，存在常数0<K<∞ 这样e[kθt- θ*kp]≤K（C+t）p/2。为了说明中心极限定理的结果，我们需要引入一些符号。让我们用v（x，θ）表示泊松方程（A.5）的解，其中H（x，θ）=θg（x，θ）- θ′g（θ）。让我们also seth（x，θ）=θf（x，θ）（σσ)-1.-xv（x，θ）σσθf（x，θ）（σσ)-1.-xv（x，θ）和'h（θ）=Zh（x，θ）π（dx）。定理2.8。假设条件2.1、2.2、2.3、2.4、2.5和2.6成立。然后√t（θt- θ*)d→ N（0，‘∑），其中‘∑定义为‘∑=CαZ∞e-s（Cα）\'g（θ*)-一） \'h（θ*)e-s（Cα((R)g）(θ*)-一） ds。当然，我们的结果立即暗示了当Xt上存在节点依赖性时的lp收敛速度和CLT。推论2.9。

假设θ*是函数g（θ）的唯一临界点，且dθt=αt- g（θt）dt+dWt. （2.3）具有独特的强大解决方案。此外，我们假设条件2.2.1、2.3（g（θ）代替g（x，θ））、2.5和2.6.2-2.6.4（g（θ）代替g（θ））成立。然后，θtsatis表示Lpconvergence rate[kθt- θ*kp]≤K（C+t）p/2。和CLT√t（θt- θ*)d→ N（0，‘∑），其中‘∑=CαZ∞e-s（Cα）g（θ*)-一） e类-s（Cα(g）(θ*)-一） ds。[14]的主要结果表明，如果g（θ）及其导数与θ相关，则在X过程遍历性的假设下，在Limt→∞kθ′g（θt）k=0。在本文中，我们允许g（θ）相对于kθk的增长。特别是，正如我们在定理2.11中陈述并在附录B中证明的那样，如果允许f（x，θ）相对于θ的线性增长，则[14]的结果是正确的，而无需大量额外工作，这转化为g（θ）的二次增长和\'g（θ）相对于θ。让我们以条件2的形式将所需的假设形式化。这也加强了条件2.6。条件2.10。1.iθf（x，θ）≤ K1+kxkq+kθk（1-（一）∨0, 对于i=0、1、2和某些有限常数，q<∞.2.iθ′g（θ）≤ K1+kθk2-我, 对于i=0、1、2和某些有限常数K<∞.3.\'g（θ）是全局Lipschitz。定理2.11。假设条件2.1、2.2、2.3、2.4、2.5和2.10成立。那么，limt→∞kθ'g（θt）k=0，a.s.定理2.11证明了即使f（x，θ）在θ中线性增长最多，非凸'g（θ）的收敛性。附录B中证明了定理2.11。该证明基于附录A中建立的θ矩的统一界限。证明非凸'g（θ）的中心极限定理需要定理2.11。非凸g（θ）的中心极限定理在定理2.13中得到证明。条件2.12。1.

\'g（θ）可以是非凸的，但有一个临界点θ*.2、存在δ*> 0足够小，使得'g（θ）在区域kθ中是强凸的- θ*k<δ*常数C和CCα>1.3。\'g（θ）∈ C、 4。如果θi，θi'g（θ）>0- θ*i> 兰德公司如果θi，θi'g（θ）<0- θ*i<-Rfor i=1，2，对我来说，足够大了。条件2.12中的第四部分保证θi'g（θ）始终向内指向全局最小θ*如果θi等于ge。定理2.13。假设条件2.1、2.2、2.3、2.4、2.5、2.10和2.12成立。那么，我们有了√t（θt- θ*)d→ N（0，∑），其中∑的定义如定理2.8所示。如果f（x，θ）和θf（x，θ）在θ上一致有界，在x上多项式有界，定理2.13在没有条件2.3和2.4的情况下成立。命题2.14表明，在学习率αt的特定条件下，条件2.5中假设的学习率的特定形式是不必要的。特别是，可以证明一般学习率αt的收敛速度和中心极限定理结果。命题2.14的证明遵循与Theo rems 2.7、2.8和2.13的证明完全相同的步骤，尽管更繁琐的代数，但省略了。提案2.14。让我们表示ψ（p）t，s=e-pCRtsαρdρ，对于p≥ 1考虑矩阵值解Φ*t、 sto方程式（4.1）。

定理2.7、2.8和2.13在满足条件Z的一般学习率αt下也成立∞αtdt=∞,Z∞αtdt<∞,Z∞|α′s | ds<∞, p>0，以便限制→∞αttp=0，p≥ 2Ztαs+|α′s|ψ（p）t，sαp/2-1sds≤ O（αp/2t），和ztαsψ（1）t，sds≤ o（α1/2t）Ztα5/2sψ（2）t，十二烷基硫酸钠≤ o（αt），ZtαsΦ*t、 sds=O（αt），p≥ 2ψ（p）t，0≤ O（αp/2t）和ψ（1）t，0≤ o（α1/2t）。特别地，定理2.7、2.8和2.13的陈述采用[kθt]的形式- θ*kp]≤ Kαp/2t和α-1/2t（θt- θ*)d→ N（0，‘∑），其中现在‘∑=“∑i，jki，j=1如（4.9）所示，但带有括号termhCα（λm+λm′）Cα-1替换为限制→∞α-1tZtαse-（λm+λm′）Rtsαududs.很容易检查，如果我们使用αs=CαC+sas作为学习率，那么如果CCα>1，则出现在位置2.14中的条件都成立。我们在结束本节时提到，在后续章节中出现的界限中，0<K<∞表示不重要的固定常数（不依赖于t或其他重要参数）。常数K可能会从一行到另一行发生变化，但它总是由相同的符号K表示。在不丧失一般性的情况下，为了简化证明中的符号，我们将让C=0，考虑t≥ 1（即，初始时间设置为t=1），并设σ为单位矩阵。3定理2.7-强凸情形下的lp收敛速度本文的证明将重复使用两个重要的一致矩界。首先，正如我们在附录A.1中所证明的，对于p≥ 2，那就对了≥0E【kθtkp】<k，第二，从【9】可知，在X过程的施加条件下，对于p≥ 2，支持≥0E【kXtkp】<K。要开始证明lp收敛速度，请重新编写算法（1.2）中的θtin项\'g（θ）。dθt=αtθf（Xt，θt）（dXt- f（Xt，θt）dt）=αtθf（Xt，θt）（f*（十）- f（Xt，θt））dt+αtθf（Xt，θt）dWt=-αtθg（Xt，θt）dt+αtθf（Xt，θt）dWt=-αtθ′g（θt）+αtθ′g（θt）- θg（Xt，θt）dt+αtθf（Xt，θt）dWt。

（3.1）泰勒展开式得出：θ′g（θt）=θ′g（θ*) + \'g（θt）（θt- θ*) = \'g（θt）（θt- θ*),其中θ是连接θ和θ的段中的一个适当选择点*. 将该泰勒展开代入方程（3.1），得到方程：d（θt- θ*) = -αt\'g（θt）（θt- θ*)dt+αt(θ′g（θt）- θg（Xt，θt））dt+αtθf（Xt，θt）dWt。设Yt=θt- θ*. 然后，Y满足SDEdYt=-αt\'g（θt）Ytdt+αt(θ′g（θt）- θg（Xt，θt））dt+αtθf（Xt，θt）dWt。根据It^o公式，我们得到p≥ 2d kYtkp=p kYtkp-2Xi，kYktαt(θf（Xt，θt））k，idWit- pαtkYtkp-2.年初至今，\'g（θt）Ytdt+pαtkYtkp-2hYt，θ′g（θt）-θg（Xt，θt）idt+pαtkYtkp-2.Xi，k(θf（Xt，θt））i，k+ （p- 2） XiXkkYtk公司-1Ykt(θf（Xt，θt））k，i！dt。（3.2）利用g的强凸性，我们得到了不等式D kYtkp≤ p kYtkp-2Xi，kYktαt(θf（Xt，θt））k，idWit- pCαtkYtkpdt+pαtkYtkp-2hYt，θ′g（θt）- θg（Xt，θt）idt+pαtkYtkp-2.Xi，k(θf（Xt，θt））i，k+ （p- 2） XiXkkYtk公司-1Ykt(θf（Xt，θt））k，i！dt。现在我们来定义过程mt=pZte-PCRTαρdραskYskp-2Xi，kYks(θf（Xs，θs））k，idWis，注意Mtsolves the SDEdMt=-pCαtMtdt+p kYtkp-2Xi，kYkt(θf（Xt，θt））k，idWit。接下来，如果我们设置Γt=kYtkp- Mtwe获得that dΓt≤ -pCαtΓtdt+pαtkYtkp-2hYt，θ′g（θt）- θg（Xt，θt）idt+pαtkYtkp-2.Xi，k(θf（Xt，θt））i，k+ （p- 2） XiXkkYtk公司-1Ykt(θf（Xt，θt））k，i！dt。接下来，我们定义函数ψ（p）t，s=e-PCRTαρdρ=st公司pCCα，比较原理给出≤ ψ（p）t，1kYkp+pZthαsψ（p）t，skYskp-2hYs，θ′g（θs）-θg（Xs，θs）iids+pZtψ（p）t，sαskYskp-2.Xi，k(θf（Xs，θs））i，k+ （p- 2） XiXkkYsk公司-1Yks(θf（Xs，θs））k，i！ds=Γt+Γt+Γt.（3.3）下一步是重写（3.3）的第二项，即Γt=pRthαsψ（p）t，skYskp-2hYs，θ′g（θs）- θg（Xs，θs）iids。我们构造了相应的泊松方程，并使用其解来分析Γt。定义G（x，θ）=hθ- θ*, θ′g（θ）- θg（x，θ）i，设v（x，θ）为偏微分方程Lxv（x，θ）=g（x，θ）的解。此处，LX位于X流程的微型发电机内。

根据定理A.1，泊松偏微分方程解的状态为：kv（x，θ）k+kxv（x，θ）k≤ K（1+Kθkm）（1+kxkm），Xi=1,2（四）θi（x，θ）+vx个θ（x，θ）+vx个θ（x，θ）≤ K（1+Kθkm）（1+kxkm）（3.4）对于适当的，但对于我们的目的不重要的常数m，m，m，m。根据It^o的公式：v（Xt，θt）- v（Xs，θs）=ZtsLxv（Xu，θu）du+ZtsLθv（Xu，θu）du+Ztsxv（Xu，θu）dWu+Ztsαuθv（Xu，θu）θf（Xu，θu）dWu+Ztsαuθxv（Xu，θu）θf（Xu，θu）du，其中Lθ是θt过程的最小生成器，lx是Xtprocess的最小生成器。确定vt≡ v（Xt，θt），并认识到：G（Xt，θt）dt=Lxv（Xt，θt）dt=dvt- Lθv（Xt，θt）dt- xv（Xt，θt）dWt- αtθv（Xt，θt）θf（Xt，θt）dWt- αtθxv（Xt，θt）θf（Xt，θt）dt。（3.5）使用该结果，可以将Γtca重写为：Γt=Zthαsψ（p）t，skYskp-2hYs，θ′g（θs）- θg（Xs，θs）iids=Ztαsψ（p）t，skYskp-2dvs-Ztαsψ（p）t，skYskp-2.xv（Xs，θs）dWs-Ztαsψ（p）t，skYskp-2Lθv（Xs，θs）ds-Ztαsψ（p）t，skYskp-2.θv（Xs，θs）θf（Xs，θs）dWs-Ztαsψ（p）t，skYskp-2.θxv（Xs，θs）θf（Xs，θs）ds=Γ2,1t+Γ2,2t+Γ2,3t+Γ2,4t+Γ2,5t。（3.6）让我们首先重写第一个术语Γ2,1t。我们将It^o公式应用于αsψ（p）t，skYskp-2vs：αtψ（p）t，tkYtkp-2vt- αψ（p）t，1kYkp-2v=Ztαsψ（p）t，skYskp-2dvs-ZtCαsψ（p）t，skYskp-2vsds+Ztαsψ（p）t，sskYskp公司-2vsds+Ztαsψ（p）t，svsd kYskp-2+Ztαsψ（p）t，sdhkYskp-2，vsi。然后，我们有以下表示形式，表示Γ2,1t：Γ2,1t=Ztαsψ（p）t，skYskp-2dvs=αtψ（p）t，tkYtkp-2vt- αψ（p）t，1kYkp-2v+ZtCαsψ（p）t，skYskp-2VSD-Ztαsψ（p）t，sskYskp公司-2VSD-Ztαsψ（p）t，svsd kYskp-2.-Ztαsψ（p）t，sdhkYskp-2，vsi=αtψ（p）t，tkYtkp-2vt- αψ（p）t，1kYkp-2v+C-1αZtαsψ（p）t，skYskp-2VSD- pCZtαsψ（p）t，skYskp-2VSD-Ztαsψ（p）t，svsd kYskp-2.-Ztαsψ（p）t，sdhkYskp-2，vsi。（3.7）现在，我们已经准备好把事情放在一起了。方程（3.2）和p-然后用2代替p来计算（3.7）的倒数第二项，类似地，二次协变量项dhkYskp-（3.7）最后一项的vsiof。

在（3.6）和（3.3）中插入（3.7），我们得到了一个不重要的常数K<∞足够大，一个矩阵值函数ζ（x，θ），在x和θ中以most多项式形式增长，使得Γt≤ ψ（p）t，1kYkp+αtψ（p）t，tkYtkp-2vt- αψ（p）t，1kYkp-2v+KZtαsψ（p）t，skYskp-2ζ（Xs，θs）ds+^Mt，（3.8），其中^Mt是平均Zero和平方可积（这源自X和θ过程上的一致矩Bounds）布朗稳定积分。现在回想一下，我们想要评估E kYtkp。回顾（3.8）中对Γ的定义和期望，我们获得了kYtkp≤ Ehψ（p）t，1kYkp+αtkYtkp-2vt- αψ（p）t，1kYkp-2vi+KEZtαsψ（p）t，skYskp-2ζ（Xs，θs）ds。回顾ψ（p）t，1=t-pCCα和CCa>1，我们得到ψ（p）t，1≤ t型-p、 因此，我们得到了对于任何p≥ 2以下不等式适用于kYtkp≤ 千吨级-p+EhαtkYtkp-2vti+KEZtαsψ（p）t，skYskp-2ζ（Xs，θs）ds。（3.9）下一步是进行诱导。利用X和θ的统一矩界以及v（X，θ）和ζ（X，θ）的多项式增长，我们得到了p=2E kYtk≤ 千吨级-2+E[αtvt]+KEZtαsψ（2）t，sζ（Xs，θs）ds≤ Kt型-2+t-1+t-2CCαZts2CCα-2秒≤ 千吨级-1，其中不重要的常数K可能会随着行的变化而变化。因此，对于p=2，所需的语句为true。接下来，我们假设指数p为真-我们想证明这对于指数p是正确的。使用指数r，r>1的H¨older不等式，使1/r+1/r=1，并选择r=p-1便士-2> 1，EhαtkYtkp-2vti≤ αtE kYtkp-1.1/r（E | vt | r）1/r≤ 千吨级-1吨-p-2=千吨-p/2，如图所示Ztαsψ（p）t，skYskp-2ζ（Xs，θs）ds≤Ztαsψ（p）t，sE kYsk（p-2） r1/r（E kζ（Xs，θs）kr）1/rds≤ KZtαsψ（p）t，sE kYsk（p-2） r1/rds≤ KZtαsψ（p）t，ss（p-2） /2秒≤ 千吨级-pCCαZtspCCα-1.-pds≤ Kt型-p/2- t型-pCCα≤ 千吨级-第2页。将两个显示器放在一起，（3.9）给出kYtkp≤ 千吨级-p/2，这是关于整数p的定理2.7的陈述≥ 2、任何p的声明≥ 然后，从H–older ine quality开始。