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

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Stochastic Gradient Descent in Continuous Time: A Central Limit Theorem》
---
作者：
Justin Sirignano, Konstantinos Spiliopoulos
---
最新提交年份：
2019
---
英文摘要：
  Stochastic gradient descent in continuous time (SGDCT) provides a computationally efficient method for the statistical learning of continuous-time models, which are widely used in science, engineering, and finance. The SGDCT algorithm follows a (noisy) descent direction along a continuous stream of data. The parameter updates occur in continuous time and satisfy a stochastic differential equation. This paper analyzes the asymptotic convergence rate of the SGDCT algorithm by proving a central limit theorem (CLT) for strongly convex objective functions and, under slightly stronger conditions, for non-convex objective functions as well. An $L^{p}$ convergence rate is also proven for the algorithm in the strongly convex case. The mathematical analysis lies at the intersection of stochastic analysis and statistical learning.
---
中文摘要：
连续时间随机梯度下降（SGDCT）为连续时间模型的统计学习提供了一种计算效率高的方法，广泛应用于科学、工程和金融领域。SGDCT算法沿着连续的数据流遵循（有噪声的）下降方向。参数更新是连续发生的，满足一个随机微分方程。本文通过证明强凸目标函数的中心极限定理（CLT）以及在稍强的条件下非凸目标函数的中心极限定理（CLT），分析了SGDCT算法的渐近收敛速度。在强凸情形下，证明了算法的$L ^{p}$收敛速度。数学分析是随机分析和统计学习的交叉点。
---
分类信息：

一级分类：Mathematics        数学
二级分类：Probability        概率
分类描述：Theory and applications of probability and stochastic processes: e.g. central limit theorems, large deviations, stochastic differential equations, models from statistical mechanics, queuing theory
概率论与随机过程的理论与应用：例如中心极限定理，大偏差，随机微分方程，统计力学模型，排队论
--
一级分类：Mathematics        数学
二级分类：Statistics Theory        统计理论
分类描述：Applied, computational and theoretical statistics: e.g. statistical inference, regression, time series, multivariate analysis, data analysis, Markov chain Monte Carlo, design of experiments, case studies
应用统计、计算统计和理论统计：例如统计推断、回归、时间序列、多元分析、数据分析、马尔可夫链蒙特卡罗、实验设计、案例研究
--
一级分类：Quantitative Finance        数量金融学
二级分类：Computational Finance        计算金融学
分类描述：Computational methods, including Monte Carlo, PDE, lattice and other numerical methods with applications to financial modeling
计算方法，包括蒙特卡罗，偏微分方程，格子和其他数值方法，并应用于金融建模
--
一级分类：Statistics        统计学
二级分类：Machine Learning        机器学习
分类描述：Covers machine learning papers (supervised, unsupervised, semi-supervised learning, graphical models, reinforcement learning, bandits, high dimensional inference, etc.) with a statistical or theoretical grounding
覆盖机器学习论文（监督，无监督，半监督学习，图形模型，强化学习，强盗，高维推理等）与统计或理论基础
--
一级分类：Statistics        统计学
二级分类：Statistics Theory        统计理论
分类描述：stat.TH is an alias for math.ST. Asymptotics, Bayesian Inference, Decision Theory, Estimation, Foundations, Inference, Testing.
Stat.Th是Math.St的别名。渐近，贝叶斯推论，决策理论，估计，基础，推论，检验。
--

---
PDF下载：
--> Stochastic_Gradient_Descent_in_Continuous_Time:_A_Central_Limit_Theorem.pdf (394.08 KB)

2022-6-1 12:52:39 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：中心极限定理 中心极限 连续时间 梯度下降 Applications

连续时间的随机梯度下降：中心极限定理Justin Sirignano*和Konstantinos Spiliopoulos+§2019年6月18日摘要连续时间随机梯度下降（SGDCT）为科学、工程和金融领域广泛使用的连续s时间模型的统计学习提供了一种计算高效的方法。SGDCT算法hm沿着连续的数据流遵循（有噪）下降方向。参数更新连续发生，并满足随机微分方程。本文通过证明强凸目标函数的中心极限定理（CLT）以及在稍强的条件下非凸目标函数的中心极限定理（CLT），分析了SGDCT算法的渐近收敛速度。在强凸情况下，证明了该算法的lp收敛速度。数学分析是随机分析和统计学习的交叉点。1引言“连续时间随机梯度下降”（SGDCT）是一种用于连续时间模型的统计学习算法，在科学、工程和金融领域都很常见。给定连续数据流，连续时间随机梯度下降（SGDCT）可以估计随机微分方程（SDE）模型中的未知参数或函数。[14] 分析了SGDCT在金融和引擎方面的大量应用的数值性能。我们证明了SGDCT算法的中心极限定理和Lpconvergencerate；请参阅第1.1节了解我们的结果概述。

分析中出现了一些技术挑战，我们的方法对于研究其他连续时间统计学习方法（例如，[11]、[15]和[6]）可能更为广泛有用。对于观测时间较长的大型数据集，连续时间模型统计估计的批量优化可能不切实际。批处理优化对整个观测数据路径的模型错误采取一系列描述步骤。由于每个下降步骤针对的是整个观测数据路径的模型误差，批量优化在很长一段时间内很慢（有时不切实际地慢），或者评估模型的计算成本很高（例如，偏微分方程或微分方程的大系统）。SGDCT提供了一种计算效率高的方法，用于长时间的每IOD统计学习和复杂模型的统计学习。SGDCT沿观测路径连续跟踪（噪声）下降方向；这将导致更大的ra pid收敛。参数在连续时间内在线更新，参数更新θt满足随机微分方程。考虑一个分歧Xt∈ X=Rm：dXt=f*（Xt）dt+σdWt。（1.1）功能f*（x） 未知，σ是常数矩阵。目标是统计估计f的模型f（x，θ）*（x） 从da ta（Xt）t的连续流≥0.重量∈ Rmis a s标准布朗运动和*伊利诺伊大学厄本那-香槟分校工业与系统工程系，Urbana，电子邮件：jasirign@illinois.edu+波士顿大学数学与统计系，波士顿，电子邮件：kspiliop@math.bu.edu部分由美国国家科学基金会（DMS 1550918）资助的K.S.研究§作者感谢普林斯顿大学和科罗拉多大学博尔德分校的研讨会参与者的评论。我们假设σ是已知的。

差异术语WT表示系统或环境的任何随机行为。函数f（x，θ）和f*（x） 可能是非凸的。参数θ的连续随机梯度下降更新∈ Rksaties the SDE:dθt=αtθf（Xt，θt）（σσ)-1文本- θf（Xt，θt）（σσ)-1f（Xt，θt）dt, （1.2）其中θf（Xt；θt）是矩阵值，α是学习率。例如，αtcould equalCαC+t。Weassumeθ是根据具有紧凑支持的某个分布初始化的。参数更新（1.2）既可用于基于先前观测数据的统计估计，也可用于在线学习（即数据可用时的实时统计估计）。定义函数g（x，θ）=kf（x，θ）- f*（x） kσσ=Df（x，θ）- f*（x） ，则，σσ-1（f（x，θ）- f*（x） ）E，它测量模型f（x，θ）和真实动力学f之间的距离E*（x） 对于一个特定的x，我们假设Xtis是充分遍历的（本文稍后将具体说明），并且它有一些行为良好的π（dx）作为其唯一不变度量。作为一般符号，如果h（x，θ）是一个一般的L（π）函数，那么我们将其在π（dx）上的平均值定义为“h（θ）=ZXh（x，θ）π（dx）。特别是，\'g（θ）=RXg（x，θ）π（dx）是我们分析算法的交感行为时需要考虑的自然目标函数θt。\'g（θ）是f（x，θ）和f之间距离的加权平均值*（x） 。权重由π（dx）给出，这是随着t变大，x趋于的分布。通过在下降方向上移动θ，距离g（x，θ）减小-θg（x，θ），这激发了算法dθt=-αtθg（Xt，θt）dt=αtθf（Xt，θt）（σσ)-1.f*（Xt）- f（Xt，θt）dt。（1.3）f*（x） 未知，因此（1.3）无法在实践中实现。然而，dXt=f*（Xt）dt+σdWtis f的方差估计*（Xt）dt，可用于推导SGDCT算法（1.2）。

特别是，很容易看出SGDCT算法（1.2）是下降方向（1.3）加上噪声项：dθt=αtθf（Xt，θt）（σσ)-1文本- θf（Xt，θt）（σσ)-1f（Xt，θt）dt= αtθf（Xt，θt）（σσ)-1.f*（Xt）-f（Xt，θt）dt+αtθf（Xt，θt）（σσ)-1σdWt=-αtθg（Xt，θt）dt+αtθf（Xt，θt）（σσ)-1σdWt。（1.4）下降方向-αt方程（1.4）中的θf（Xt，θt）取决于Xt，因此如果θt朝着固定点前进，则上述公式中的r是不明确的。为了理解θt的行为，将（1.4）分解为几个项是有帮助的：dθt=-αtθ′g（θt）dt |{z}下降项-αtθg（Xt，θt）-θ′g（θt）dt{z}涨落项+αtθf（Xt，θt）（σσ)-1σdWt |{z}噪声项。（1.5）启发式地，如果αt随时间衰减（例如，αt=CαC+t），则下降项-αtθ′g（θt）将主导大t的波动和噪声项。然后，人们可能会发现θtwill收敛到局部最小值g（θ）。作者在[14]中证明了θt收敛到目标函数'g（θ）：k的临界点\'g（θt）ka。s→ 0作为t→ ∞. （1.6）然而，[14]留下了一个关于θtsatis是否存在任何渐近收敛率的问题。在本文中，我们证明了一个中心极限定理和一个lp收敛速度，这将在本导言的下一小节中介绍。1.1本文的贡献当g（θ）有一个临界点θ时，我们证明了θtw的中心极限定理*:√t型θt- θ*d→ N（0，‘∑）作为t→ ∞. （1.7）对于目标函数'g（θ）（可能是非凸的）和模型f（x；θ）（θ为线性增长，x为多项式增长）证明了该结果；见定理2.13。此外，当'g（θ）为强凸时，我们给出了一个lp收敛速度：Ekθt- θ*kp公司≤K（C+t）p/2，（1.8）对于p≥ 我们证明了模型f（x，θ）的这个结果，其中θ为二次增长，inx为多项式增长。

此外，在这种强凸情况下，我们证明了中心极限定理也适用于θ为二次增长且x为多项式增长的模型f（x，θ）。强凸x情况下的lp收敛速度和CLT分别在定理2.7和2.8中陈述。定理2.7和2.8没有利用[14]中的结果。作为定理2.13证明的一部分，我们还加强了[14]的c-onvergenc-e结果，它不允许f（x，θ）在θ中增长；见定理2.11。定理2.7，2。8和2.13证明了学习率αt=CαC+t。理论2.7、2.8和2.13的类似结果当然适用于一般类别的学习率αt；见第2.14条。第2节介绍了数学结果的精度陈述和所需的技术假设。此外，作为推论，我们的结果证明了在Xt不依赖的情况下，LPT收敛速度和CLT。也就是说，如果θ*是函数g（θ）的唯一临界点，dθt=αt- g（θt）dt+dWt, （1.9）然后θta。s→ θ*和√t型θt- θ*d→ N（0，‘∑）作为t→ ∞. 此外，如果g（θ）是强凸的，则kθt- θ*kp公司≤K（C+t）p/2。这些数学结果之所以重要，有两个原因。首先，他们为算法的收敛速度建立了理论保证。其次，它们可用于分析不同特征的影响，如学习率αt、噪声水平σ和目标函数g（θ）的形状。我们能够精确地描述存在最优收敛速度的区域，以及描述极限协方差∑。该制度完全取决于学习率的选择。由于XT过程的性质，证明中心极限定理具有挑战性。

数据XT将随时间进行关联，这与随机梯度下降的标准离散时间版本不同，在该版本中，数据通常被视为每一步的i.i.d。特别是，函数项αtθg（Xt，θt）- θ′g（θt）必须分析dt，并在某种适当的意义上显示其变小。我们使用泊松偏微分方程评估和控制这些波动率αt。虽然可以启发性地看到，对于大t，下降项在方程（1.5）中的波动和噪声项中占主导地位，但下降项αtθ′g（θt）→ 0作为t→ ∞ s公司限制→∞αt=0。因此，如果渐近αtθ′g（θt）将保持足够大，以保证θt的渐近收敛速度[14]证明了c收敛结果kθ′g（θt）ka。s→ 0使用停止时间周期捕获whenkθ′g（θt）k大或小。然而，这种方法对于证明CLT是无用的。相反，我们推导出一个近似积分来表示√t（θt- θ*) 利用Duhamel原理和随机微分方程dψt=-αtθ′g（|θt）ψtdt，其中|θt位于连接θ的线上*和θt。此随机积分的被积函数包括函数项、噪声项以及ψt。本文中的证明还需要解决其他几个挑战。模型f（x，θ）允许随θ增长。这意味着函数以及其他项可以随θ增长。因此，我们必须证明kθtk的先验稳定性估计。在Orem 2.13中证明非凸的¨g（θ）的中心极限定理并不简单，因为θtca的收敛速度在某些区域会变得任意缓慢，梯度甚至可能指向远离全局最小值θ的地方*.

为了解决这个问题，我们考虑了时间τδ之后的随机积分，该时间τδ被定义为最终时间θ在θ的邻域内*.然而，τδ不是停止时间，因此需要仔细分析以研究随机积分的极限行为。我们在本文中开发的方法可能是研究其他连续时间统计学习方法（例如，[11]、[15]和[6]）的渐近性的通用方法。1.2文献综述绝大多数统计学习、机器学习和随机梯度下降文献都涉及离散时间算法。对比分析了一种连续时间的统计学习算法。我们回顾了与我们的工作最相关的现有文献。我们还评论了开发和分析连续时间算法以处理连续时间模型的重要性。许多学术论文研究了θn的算法，而不考虑X动力学（例如，每一步都带有i.i.d.噪声的随机梯度下降）。X-dynamics的加入使得分析更具挑战性。文[2]给出了离散时间随机梯度下降的收敛速度和中心极限定理结果。我们的设置和假设与[2]不同。我们的证明方法不同于[2]中的方法，并利用了我们设置的连续时间性质，这是对许多工程和金融问题的兴趣公式（见[14]）。[17] 研究了随机梯度搜索算法的连续时间版本的收敛性。他们改进了过程的收敛性，并给出了时间平均过程的中心极限定理。我们的论文与[17]之间存在一些差异。我们的论文包括X动力学，这在文献[17]中没有考虑。

[17] 证明了时间平均过程的中心极限定理，同时研究了过程本身的中心极限定理。此外，我们的假设是不同的。[13] 研究了连续时间随机梯度下降算法的收敛性。然而，[13]不包括X-dynamics。[13] 本文证明了一个中心极限定理和一个收敛速度。[11] 在与我们不同的环境中研究连续时间随机镜像下降。在[11]的框架中，目标函数是已知的。本文考虑随机过程（即满足（1.1）的X过程）未知动力学的统计估计。统计学家和金融工程师积极研究了SDE的参数估计，尽管通常不使用统计学习或机器学习方法。似然函数通常从X的整个观测路径（即批量优化）计算出来，然后最大化以找到最大似然估计量（MLE）。例如，[1]为连续观察到的X的整个病理过程建立了似然函数。与本论文不同的是，通常不分析最大化似然函数的实际优化过程。读者可以参考[3、8、12]对随机微分方程的经典统计推断方法进行粗略回顾。连续时间模型在工程和金融领域很常见。在这些模型中，经常存在不确定或未知的系数或函数；随机梯度下降可以用来从数据中学习这些模型参数。人们自然会问，为什么要使用SGDCT，而不是（1）离散连续时间动力学，然后（2）应用传统随机梯度下降的简单方法。

我们在[14]中详细阐述了这一问题，其中提供了具体示例来展示差异。为了完整起见，让我们简要地讨论出现的问题。SGDCT允许将所选数值格式应用于连续时间模型的理论正确的统计学习方程。这可以导致更准确、更高效的参数更新。数值格式始终适用于连续时间动力学，不同的数值格式对于不同的连续时间模型可能具有不同的特性。先验地对系统动力学进行离散化，然后应用传统的离散时间随机梯度下降方案，可能会导致精度降低，甚至可能不会收敛，参见【14】。例如，无法保证（1）使用更高阶的r ac c urate方案来离散系统动力学，然后（2）应用传统的随机梯度下降将产生时间上更高阶精度的统计学习方案。因此，首先建立连续时间统计学习方程，然后应用高阶精度数值格式是有意义的。除模型估计外，SGDCT还可用于解决连续时间优化问题，如美式期权。在【14】中，SGDCT与dee神经网络相结合，以解决多达100个维度的美国选项。或者，可以将动力学离散化，然后使用QLearn算法（传统的随机梯度下降应用于离散HJBequation的近似值）。然而，正如我们在【14】中所示，Q-le学习是有偏的，而SGDCT是无偏的。