关于相关数据流的随机梯度哈密尔顿蒙特卡罗算法的非渐近估计.pdf
《关于相关数据流的随机梯度哈密尔顿蒙特卡罗算法的非渐近估计.pdf》由会员分享,可在线阅读,更多相关《关于相关数据流的随机梯度哈密尔顿蒙特卡罗算法的非渐近估计.pdf(15页珍藏版)》请在咨信网上搜索。
1、Advances in Applied Mathematics 应用数学进展应用数学进展,2024,13(2),569-583 Published Online February 2024 in Hans.https:/www.hanspub.org/journal/aam https:/doi.org/10.12677/aam.2024.132055 文章引用文章引用:杨金圆,胡良剑.关于相关数据流的随机梯度哈密尔顿蒙特卡罗算法的非渐近估计J.应用数学进展,2024,13(2):569-583.DOI:10.12677/aam.2024.132055 关于相关数据流的随机梯度哈密尔顿蒙特卡罗
2、关于相关数据流的随机梯度哈密尔顿蒙特卡罗算法的非渐近估计算法的非渐近估计 杨金圆杨金圆,胡良剑胡良剑*东华大学理学院,上海 收稿日期:2024年1月26日;录用日期:2024年2月21日;发布日期:2024年2月28日 摘摘 要要 近年来,基于朗之万蒙特卡罗方法的随机梯度下降算法得到了广泛应用。这些算法通过在梯度的估计中近年来,基于朗之万蒙特卡罗方法的随机梯度下降算法得到了广泛应用。这些算法通过在梯度的估计中注入适当的高斯噪声以实现在非凸优化问题中的全局收敛。随机梯度哈密尔顿蒙特卡罗注入适当的高斯噪声以实现在非凸优化问题中的全局收敛。随机梯度哈密尔顿蒙特卡罗(SGHMC)是随机是随机梯度下降带
3、有动量的一种变体,通常的研究以样本数据相互独立的假设为前提来分析梯度下降带有动量的一种变体,通常的研究以样本数据相互独立的假设为前提来分析SGHMC算法的收敛算法的收敛性,然而实际中的样本数据往往存在相关性。本文在数据流具有相关性性,然而实际中的样本数据往往存在相关性。本文在数据流具有相关性(满足一定的条件混合特性满足一定的条件混合特性)的条的条件下,给出了件下,给出了SGHMC算法的非渐进估计,建立了全局算法的非渐进估计,建立了全局Lipschtiz条件下条件下SGHMC算法的收敛性定理,得到算法的收敛性定理,得到了迭代分布与目标分布之间了迭代分布与目标分布之间Wasserstein距离的上
4、界距离的上界。关键词关键词 随机梯度哈密尔顿蒙特卡罗,非渐进估计,随机梯度哈密尔顿蒙特卡罗,非渐进估计,非凸优化,非凸优化,相关数据流相关数据流 Non-Asymptotic Estimates for Stochastic Gradient Hamiltonian Monte Carlo Algorithm with Dependent Data Streams Jinyuan Yang,Liangjian Hu*College of Science,Donghua University,Shanghai Received:Jan.26th,2024;accepted:Feb.21st,20
5、24;published:Feb.28th,2024 Abstract In recent years,stochastic gradient descent algorithms based on the Langevin Monte Carlo method have been widely applied,which achieve global convergence in non-convex optimization problems *通讯作者。杨金圆,胡良剑 DOI:10.12677/aam.2024.132055 570 应用数学进展 by injecting appropr
6、iate Gaussian noise into the gradient estimates.Stochastic gradient Hamilto-nian Monte Carlo(SGHMC)is a variant of stochastic gradient descent with momentum.Usually,studies analyze the convergence of algorithm based on the assumption that the sample data are i.i.d.However,in practice,sample data may
7、 be dependent.This paper provides non-asymptotic es-timates for SGHMC algorithm under the condition that the data streams are dependent(satisfying a certain conditional mixing property),establishes a convergence theorem for SGHMC algorithm un-der the global Lipschitz condition,and obtains an upper b
8、ound of the Wasserstein distance between the law of algorithms iterates and the target distribution.Keywords Stochastic Gradient Hamiltonian Monte Carlo,Non-Asymptotic Estimates,Non-Convex Optimization,Dependent Data Streams Copyright 2024 by author(s)and Hans Publishers Inc.This work is licensed un
9、der the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 随机梯度下降算法在解决非凸优化问题中有着广泛应用。考虑一个随机优化问题:最小化()():,UuX=其中 U 可能是非凸损失函数,d,X 是随机数据。我们希望得到的估计量使超额期望风险()()infdUU达到最小。Raginsky 等1阐述了最小化超额期望风险与从一个集中在损失函数 U 的 极小值附近的目标分布()()()expdU 中采样之间的密切联系,其中为
10、逆温度系数。当足够大时,目标分布集中在损失函数 U 的极小值附近2,且在适当的假设下,目标分布是过阻尼郎之万随机微分方程()1dd2dttthtB=+(1)的唯一平稳分布3,其中:hU=,0ttB为 d 维布朗运动。在非凸情形下损失函数 U 可能具有多个极小值,为算法收敛带来挑战。为了从目标分布中采样,基于朗之万蒙特卡罗(Langevin Monte Carlo,LMC)方法的随机梯度下降(Stochastic Gradient Descent,SGD)算法备受关注,这些算法通过在梯度的估计中注入噪声保证全局收敛。考虑使用欧拉离散化方法近似模拟方程(1),同时由于精确梯度 h 难以获得,故使用
11、其以观测数据驱动的无偏估计代替,即得到随机梯度郎之万动力学(Stochastic Gradient Langevin Dynamics,SGLD)算法4()1111:,2nnnnnHX+=+其中0为步长,:dmdH为满足()(),nHXh=的可测函数,nnX为适应于给定流 nn的m值数据序列,nn为独立的标准 d 维高斯噪声。另一方面,本文所考虑的随机梯度哈密尔顿蒙特卡罗(Stochastic Gradient Hamiltonian Monte Carlo,SGHMC)算法5基于欠阻尼朗之万随机微分方程 Open AccessOpen Access杨金圆,胡良剑 DOI:10.12677/a
12、am.2024.132055 571 应用数学进展 ()1ddd2dddttttttVV thtBV t=+=(2)其中 0tt,0ttV分别为位置和动量过程,为摩擦系数。在梯度的适当假设下,马尔可夫过程()0,tttV具有唯一平稳分布6()()21d,dexpd d2vvUv+与 SGLD 算法类似,精确梯度 h 难以获得,但可以有效获得其无偏估计,即得到 SGHMC 算法()11111,2nnnnnnnnnVVVHXV+=+=+(3)Eberle等7证明了在某些假设条件下欠阻尼随机微分方程在Wasserstein 距离下收敛到其平稳分布的速度比过阻尼情形快,许多实验也印证了 SGHMC 算
13、法表现出比 SGLD 算法更快的收敛速度5。近年来,损失函数 U 为凸情形下的近似采样算法的收敛速度得到了深入研究,放宽凸假设是一个更具挑战的问题。对于 U 非凸的情形,通常考虑两种路径:(i)考虑耗散条件1 8;(ii)假设损失函数 U在无穷远处具有凸性9。此外,大多数研究假设样本数据序列相互独立,然而事实上数据可能相关而非独立。如金融市场价格分析问题中,资产收益在适当的时间尺度上保持平稳,但独立性失效10。在下达交易订单以最大化投资组合效益、最小化交易成本等金融问题中,随机梯度下降算法往往在相关数据流的基础上进行8。Chau 等8在相关数据流(样本数据满足条件 L 混合特性)假设下研究了非
14、凸情形下SGLD 算法的收敛性。对于 SGHMC 算法,在观测数据独立同分布的假设下,Chau 等6和 Gao 等11研究了 SGHMC 算法在全局 Lipschitz 条件下的收敛性。本文将考虑的数据样本nnX是相关的,在数据序列满足条件 L 混合特性的条件下,得到 SGHMC 算法的非渐近估计,并由此得到 SGHMC 算法收敛到其目标分布的速度。2.符号与假设符号与假设 2.1.符号符号 设(),P 为一个概率空间。记随机变量 X 的期望为X,用pL表示 p 阶矩可积的实值随机变量的空间。给定整数1d,记d上 Borel代数为()d,随机变量 X 在()d上的分布用()X表示。记内积为,,
15、相应的范数用表示。对于+r,用Br表示中心为 0,半径为 r 的闭球。可测空间()(),dd上的概率测度的集合记为()d。对(),d,用(),表示()dd上的概率测度的集合,其边际分布分别为,。Wasserstein 距离定义为()()()()1 222,:infd,.dddW =2.2.假设假设 假设假设 2.1 损失函数 U 取非负值,即()0U。假设假设 2.2 0,01ppvL。假设假设 2.3 设,nn为代表过去信息的给定流,且0,=,():=nn。设*,nn为一 个递减的代数族,使得对所有n,n和*n相互独立。过程nnX关于*,nnn 是条件 L 混合的,且满足对任意d和1n,杨金
16、圆,胡良剑 DOI:10.12677/aam.2024.132055 572 应用数学进展 ()(),.nHXh=(4)假设假设 2.4 存在正常数1L,2L,使得对所有,d 和,mx x,有()12(,),.HxHxLL xx+(5)假设假设 2.5 存在正常数 a,b 使得对所有d和mx,()2,.Hxab 注注 2.6 由假设 2.4,得到以下性质:(i)对所有,dx,()12*,HxLL xH+(6)其中()*:0,0HH=。(ii)对所有d,()10hLh+(7)其中()0:0hh=。3.主要结果主要结果 3.1.条件条件 L 混合混合 Gerencsr 12介绍了 L 混合过程,L
17、 混合表示随机序列中相邻元素间相关性快速减小。Chau 等13在随机梯度方法的背景下引入了条件 L 混合的概念,条件 L 混合表示在给定一些信息或条件下序列的混 合性质仍然成立。考虑概率空间(),,具有离散时间流 nn和一个递减的域序列*nn,使得对所有n,n和*n相互独立。当1r 时,若1sup,设ttW+为rL有界,且设()().rrMWWa s+。假设对t+,00.tWa s=。设:0,fT 为()0,T可测,且有20 d Ttft,则存在一个常数()Cr使得()()()()1 2120000,supd,.d.rsTrtttrrsTfW tCrftMWWa s+这里可以取()()11 2
18、11 22rCrr=。引理引理 3.3 若假设 2.4 成立,则对每个j,(),BjtHWt+满足()()()()()()12*2,2.rrrrMHWLL MWHjHWLW+引理引理 3.4 若假设 2.4 成立,且设j。令()0ssZ为Bj值随机变量族,满足:dZ+是()0+可测的。对t+,定义过程(),tttYH Z W=,则()()()()12*2,2.rrrrMYLL MWHjYLW+3.2.收敛定理收敛定理 首先定义 3max21142min 1,224KKKKK=其中常数 K1,K2,K3将在引理 4.2 的证明中给出,常数1K和 K4将在引理 4.3 的证明中给出,参数在(9)中
19、引入。下面给出 SGHMC 算法到目标分布的收敛性的主要结果。定理定理 3.5 若假设 2.12.5 成立且max0,使得()()41 21 42123,eCnnnWVCCC+其中 C1,C2依赖于,d,L1,L2和数据流()nnX,具体形式分别在定理 4.6 和定理 4.8 的证明中给出,C3,C4依赖于,d,L1,具体形式在定理 3.5 的证明中给出。本文在数据流存在相关性的假设下给出了 SGHMC 算法的非渐近估计,阐明了 SGHMC 算法在有限迭代次数 n 下的性能。定理 3.5 表明算法的误差在迭代次数 n 上一致有界且选择足够小的步长0可以使误差达到任意小,从而保证了算法的收敛性在
20、相关数据流情形下依然成立。与独立数据流的情形相比,本文在定理证明过程中采用与文献6不同的证明路线。本文将 SGHMC 算法与依赖于条件 L 混合的辅助过程进行比较,得到相关数据流情形下二者之间的 Wasserstein 距离。此外,本文在算法的误差估计中得到不同的系数表达式,条件 L 混合特性为这些系数的有界性提供了保证。4.证明证明 4.1.辅助过程辅助过程 证明主要结果的中心思想是引入合适的Lyapunov函数及SGHMC算法的连续时间插值过程等辅助过程,该连续时间插值过程在离散时间下的分布与SGHMC算法相同。不同于SGLD算法中经典的Lyapunov函数()()221=+p,本文使用
21、Eberle 7定义的 Lyapunov 函数:()()()222211,4vUvv=+(9)其中(0,1 4,该函数依赖于目标函数()U。杨金圆,胡良剑 DOI:10.12677/aam.2024.132055 574 应用数学进展 下面定义(),ttV的缩放过程()(),:,ttttZV=,()()1dd2dddttttttZZhtBZt=+=(10)其中:,0ttBBt=。记 0ttB自然流为 0tt,且 0tt与()00,v 相互独立,则0ttB自然流记为0tt且:tt=,0tt也与()00,v 相互独立。此外,记()0:tt=。然后定义 SGHMC 算法(3)的连续时间插值过程:()
22、()11d,d2dddtttttttVVHXtBVt+=+=(11)注意到,插值过程(11)与 SGHMC 算法在格点上具有相同的分布,即()(),nnnnVV=。此外,考虑一个初值条件为,s u vsu=和,s u vsVv=连续时间过程(),x u vs u vttZ:()(),1,dd2ddds u vs u vs u vtttts u vs u vttZZhtBZt=+=(12)定义定义 4.1 给定n且对:1T=,定义过程,nTnTnTnTnTVnTVnnttttZZ=(13)直观看来,过程(),nnttZtnT是一个开始于时间nT且初值为(),nTnTV的欠阻尼 Langevin
23、过程。最后,对t+定义一个含样本数据nnX信息流和布朗运动 0ttB随机性的连续时间流0tt:*:,:.tttt =4.2.引理准备引理准备 引理引理 4.2 若假设 2.12.5 成立。则对0max,()()11211202110sup:8 12sup:4 12kkkvkCCVCC=其中()()()21110:,d,d4=+dcCvvAd。证明证明 设对0,1,k=,()()()()222211,4kkkkkkkVL kUVV=+(14)类似文献15中引理 3.2 的证明,由(3)和注 2.6 的(6)得到()()()22121,222kkkkkkL kL khVVdM+(15)其中 222
24、2220111124442222kkkhLLLCMV+=(16)杨金圆,胡良剑 DOI:10.12677/aam.2024.132055 575 应用数学进展 且2112LL=,()22122*44CLXH=+。注意到对01 4,由假设 2.1,()()()222,max121284,vv (17)由(14)中()L k的定义及不等式()max,2+a bab,得到()()()222111212168kkL kV+(18)因此,由和,得到()12kMK L kK+其中()()222111201122222444max,11221212168LLLhCKK +=+由参考文献15中的引理 B.5,
25、选择()211 0min 1 4,22=+aLL h,可得到对所有dx,有()()222,24cAhU+(19)其中()01 0222cAbuL h=+。故将(19)代入(15),得到()()()()()3222112121,422kkckkkL kL kUAVVdK L kK +(20)又01 4时,由(14)得到()()2221,422kkkkkL kUVV+(21)则对32120min,2KKK,由(20)和(21),得到()()()33112240L kL kKLK+(22)其中()13:cKAd=+。结合(17),最终得证。引理引理 4.3 设max0,且假设 2.12.5 成立,则
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关于 相关 数据流 随机 梯度 哈密尔顿 蒙特卡罗 算法 渐近 估计
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。