基于随机采样的方差缩减优化算法

1

作者 郭振华 闫瑞栋 +2 位作者 邱志勇 赵雅倩 李仁刚 《计算机科学与探索》 北大核心 2025年第3期667-681,共15页

随机梯度下降(SGD)算法因其性能优异而引起了机器学习和深度学习等领域研究人员的广泛关注。然而,SGD使用单样本随机梯度近似样本全梯度导致算法在迭代过程中引入了额外的方差,使得算法的收敛曲线震荡甚至发散,导致其收敛速率缓慢。因此... 随机梯度下降(SGD)算法因其性能优异而引起了机器学习和深度学习等领域研究人员的广泛关注。然而,SGD使用单样本随机梯度近似样本全梯度导致算法在迭代过程中引入了额外的方差,使得算法的收敛曲线震荡甚至发散,导致其收敛速率缓慢。因此,有效减小方差成为当前关键挑战。提出了一种基于小批量随机采样的方差缩减优化算法(DM-SRG),并应用于求解凸优化及非凸优化问题。算法主要特征在于设计了内外双循环结构:外循环结构采用小批量随机样本计算梯度近似全梯度,以达到减少梯度计算开销的目的;内循环结构采用小批量随机样本计算梯度并代替单样本随机梯度,提升算法收敛稳定性。针对非凸目标函数与凸目标函数,理论分析证明了DMSRG算法具有次线性收敛速率。此外,设计了基于计算单元性能评估模型的动态样本容量调整策略,以提高系统训练效率。为评估算法的有效性,分别在不同规模的真实数据集上开展了数值模拟实验。实验结果表明算法较对比算法损失函数减少18.1%并且平均耗时降低8.22%。 展开更多

关键词 随机梯度下降 方差缩减 凸优化 非凸优化 收敛速率

在线阅读 下载PDF 职称材料

求解一类随机变分不等式问题的带方差缩减的近端镜像滑动算法

2

作者 王子玲 王丽平 《曲阜师范大学学报（自然科学版）》 CAS 2024年第4期1-12,F0002,共13页

考虑了一类具有特殊结构的随机单调变分不等式(Stochastic Monotone Variational Inequalities,SMVI)问题的求解算法.所考虑的SMVI问题涉及到一个梯度算子与单调算子的和,其中梯度算子的精确信息是可知的,而单调算子的信息通过随机样本... 考虑了一类具有特殊结构的随机单调变分不等式(Stochastic Monotone Variational Inequalities,SMVI)问题的求解算法.所考虑的SMVI问题涉及到一个梯度算子与单调算子的和,其中梯度算子的精确信息是可知的,而单调算子的信息通过随机样本估计得到,这使得求解问题的算法具有不确定性.随机近端镜像滑动(Stochastic Mirror-Prox Sliding,SMPS)算法是求解SMVI问题的一种有效算法,但SMPS使用随机信息引入的扰动破坏了单调算子的最优计算复杂度.该文在SMPS的基础上对随机单调算子使用方差缩减技术,提出了带有方差缩减的随机近端镜像滑动(Vraiance Reduced Stochastic Mirror-Prox Sliding,VRSMPS)算法.并且,在一般性的方差可控假设下证明与SMPS相比,使用VRSMPS求解SMVI,获得梯度算子最优计算复杂度O(√L/ε)的同时,把H的计算复杂度从O(√L/ε+M/ε+σ^(2)/ε^(2))降低到O(√L/ε+√(α+M^(2))^(2)/Lε^(3)). 展开更多

关键词 随机变分不等式 近端镜像滑动算法 方差缩减 计算复杂度

在线阅读 下载PDF 职称材料

基于Polyak步长的加速临近随机方差缩减算法

3

作者 王福胜 史鲁玉 《运筹学学报（中英文）》 CSCD 北大核心 2024年第2期131-142,共12页

针对大规模机器学习中随机复合优化问题,本文将加速临近随机方差缩减算法(Acc-Prox-SVRG)和Polyak步长方法相结合,提出了一种新的加速临近随机方差缩减算法(Acc-Prox-SVRG-Polyak)。相比于已有算法,新算法充分利用加速技术和Polyak步长... 针对大规模机器学习中随机复合优化问题,本文将加速临近随机方差缩减算法(Acc-Prox-SVRG)和Polyak步长方法相结合,提出了一种新的加速临近随机方差缩减算法(Acc-Prox-SVRG-Polyak)。相比于已有算法,新算法充分利用加速技术和Polyak步长的优越性,提高了准确率。在通常的假定下论证了算法的收敛性,并分析了复杂度。最后,数值实验验证了新算法的有效性。 展开更多

关键词 Polyak步长 方差缩减 机器学习 随机梯度

在线阅读 下载PDF 职称材料

带消极动量的自适应步长随机方差缩减方法

4

作者 刘海 郭田德 韩丛英 《中国科学院大学学报（中英文）》 CAS CSCD 北大核心 2024年第5期577-588,共12页

近年来,随机方差缩减类方法在解决大规模机器学习问题中取得很大成功,自适应步长技术的引入减轻了该类方法的调参负担。针对自适应步长的方差缩减算法SVRG-BB,指出其算法设计带来了“进展-自适应步长有效性”的权衡问题。因此引入Katyu... 近年来,随机方差缩减类方法在解决大规模机器学习问题中取得很大成功,自适应步长技术的引入减轻了该类方法的调参负担。针对自适应步长的方差缩减算法SVRG-BB,指出其算法设计带来了“进展-自适应步长有效性”的权衡问题。因此引入Katyusha动量以更好地处理该权衡问题,并且在强凸假设下证明由此得到的SVRG-BB-Katyusha算法的线性收敛性质。之后基于“贪婪”思想,提出稀疏地使用Katyusha动量的SVRG-BB-Katyusha-SPARSE算法。在公开数据集上的数值实验结果表明,提出的2个改进算法较SVRG-BB有较稳定的优势,即在达到一定外循环数时优化间隙有若干个数量级的减小。 展开更多

关键词 自适应步长机制 随机方差缩减类方法 Barzilai-Borwein方法 Katyusha动量

在线阅读 下载PDF 职称材料

基于方差缩减的高维美式期权Monte Carlo模拟定价 被引量：2

5

作者 陈金飚 林荣斐 《浙江大学学报（理学版）》 CAS CSCD 北大核心 2017年第5期542-547,共6页

美式期权给予持有者在到期日之前任何时刻的权利,因涉及最佳执行时刻问题定价较为复杂.Monte Carlo方法其估计误差及收敛速度与问题的维数独立,可较好地处理高维衍生证券问题,且方法灵活易于实现.利用最小二乘蒙特卡洛方法(LSM),结合存... 美式期权给予持有者在到期日之前任何时刻的权利,因涉及最佳执行时刻问题定价较为复杂.Monte Carlo方法其估计误差及收敛速度与问题的维数独立,可较好地处理高维衍生证券问题,且方法灵活易于实现.利用最小二乘蒙特卡洛方法(LSM),结合存储量减小技术与方差缩减技术,将Monte Carlo模拟方法应用于多标的资产的美式期权定价,并比较、分析了不同方差缩减技术的效果及适用范围. 展开更多

关键词 MONTE CARLO方法 美式期权 方差缩减技术 定价

在线阅读 下载PDF 职称材料

期权定价的蒙特卡罗模拟方差缩减技术研究 被引量：13

6

作者 陈辉 《统计与信息论坛》 CSSCI 2008年第7期86-96,共11页

蒙特卡罗模拟的方差缩减技术作为模拟效率改进的重要途径,在金融衍生证券的定价分析中得到了广泛的应用和发展,特别是在控制变量、对偶变量、分层抽样、拉丁超立方抽样、矩匹配和重要性抽样技术方面。从方差缩减的效率来看,所有的蒙特... 蒙特卡罗模拟的方差缩减技术作为模拟效率改进的重要途径,在金融衍生证券的定价分析中得到了广泛的应用和发展,特别是在控制变量、对偶变量、分层抽样、拉丁超立方抽样、矩匹配和重要性抽样技术方面。从方差缩减的效率来看,所有的蒙特卡罗模拟方差缩减技术都能显著地提高期权定价的模拟效率,其中基于最优漂移率的重要性抽样技术与沿着最优分层抽样方向进行的分层抽样技术的组合,要比普通的蒙特卡罗模拟具有极其明显的效率提高效果。 展开更多

关键词 期权 蒙特卡罗模拟 方差缩减技术 控制变量 对偶变量 分层抽样 拉丁超立方抽样 矩匹配 重要性抽样

在线阅读 下载PDF 职称材料

批量减数更新方差缩减梯度下降算法BSUG 被引量：6

7

作者 宋杰 朱勇 许冰 《计算机工程与应用》 CSCD 北大核心 2020年第22期117-123,共7页

机器学习问题通常会转换成求解一个目标函数问题。继随机梯度下降(Stochastic Gradient Descent,SGD)之后,随机方差缩减梯度法(Stochastic Variance Reduction Gradient,SVRG)成为如今优化目标函数参数的主流算法,它由于不受方差影响达... 机器学习问题通常会转换成求解一个目标函数问题。继随机梯度下降(Stochastic Gradient Descent,SGD)之后,随机方差缩减梯度法(Stochastic Variance Reduction Gradient,SVRG)成为如今优化目标函数参数的主流算法,它由于不受方差影响达到线性收敛而被人们广泛研究。它的提出导致陆续出现如SAGA(Stochastic Average Gradient Average)和SCSG(Stochastically Controlled Stochastic Gradient)等新型方差缩减算法,它们有着过量消耗内存、迭代缓慢等问题。为了实现小成本存储以及快速迭代的目的,设计了一种以SVRG为基础的新型变异方差缩减算法BSUG(Batch Subtraction Update Gradient)。改进在于:使用小批量样本代替全部样本进行平均梯度计算,同时对平均梯度进行减数更新。每轮迭代中,随机抽取一批小样本进行平均梯度计算,同时在内部迭代时通过对过去模型梯度的舍去来达到更新平均梯度的目的。通过合适地降低批大小B,可以减少内存存储以及迭代次数。理论分析算法的收敛性,并基于Python进行算法实现,通过与Mini-Batch SGD、AdaGrad、RMSProp、SVRG和SCSG等算法进行比较证明了BSUG算法的有效性,并且通过对超参数进行探究证明了算法的稳定性。 展开更多

关键词 机器学习 优化 小批量 减数更新 随机方差缩减梯度法(SVRG)

在线阅读 下载PDF 职称材料

系统可靠性数字仿真中方差缩减技术的分析及其应用 被引量：1

8

作者 金光 周经伦 《系统工程》 CSCD 1998年第3期60-65,共6页

本文通过对几种典型方差缩减技术在系统可靠性数字仿真应用中的研究,分析比较了它们各自的性能和优缺点,并在此基础上构造了一个更稳定和有效的算法——限制的序贯破坏法.

关键词 方差缩减 系统可靠性 数字仿真

在线阅读 下载PDF 职称材料

方差缩减技巧与拟蒙特卡罗方法(英文) 被引量：2

9

作者 王小群 《应用数学》 CSCD 1999年第2期90-96,共7页

"拟蒙特卡罗方法"是蒙特卡罗方法的确定性变形。方差缩减技巧被广泛用于提高蒙特卡罗方法的效率。本文探讨这此些技巧的确定性变形用于"拟随机"情形以减小变差（提高"拟蒙特卡罗方法"的效率的）的可能性... "拟蒙特卡罗方法"是蒙特卡罗方法的确定性变形。方差缩减技巧被广泛用于提高蒙特卡罗方法的效率。本文探讨这此些技巧的确定性变形用于"拟随机"情形以减小变差（提高"拟蒙特卡罗方法"的效率的）的可能性。构造了一系列对某一函数集会精确成立的"拟随机"积分公式。 展开更多

关键词 方差缩减 数值积分 拟蒙特卡罗法 蒙特卡罗法

在线阅读 下载PDF 职称材料

模拟退火方差缩减的FastSLAM算法在AUV导航定位中的应用

10

作者 王宏健 王晶 +1 位作者 曲丽萍 刘振业 《哈尔滨工程大学学报》 EI CAS CSCD 北大核心 2013年第3期338-344,共7页

由于标准FastSLAM中存在粒子退化及重采样引起的粒子贫化,导致自主水下航行器(AUV)位置估计精度严重下降的问题,提出了一种基于粒子权值方差缩减的FastSLAM算法.利用模拟退火的降温函数产生自适应指数渐消因子来降低粒子权值的方差,进... 由于标准FastSLAM中存在粒子退化及重采样引起的粒子贫化,导致自主水下航行器(AUV)位置估计精度严重下降的问题,提出了一种基于粒子权值方差缩减的FastSLAM算法.利用模拟退火的降温函数产生自适应指数渐消因子来降低粒子权值的方差,进而增加有效粒子数,以此取代标准FastSLAM中的重采样步骤.建立AUV的运动学模型、特征模型及传感器的测量模型,通过霍夫变换进行特征提取.利用方差缩减FastSLAM算法,基于海试数据进行了AUV同步定位与构图仿真试验,结果表明所提方法能够保证粒子的多样性,并且降低粒子的退化程度,提高了AUV定位与地图构建系统的准确性及稳定性. 展开更多

关键词 FASTSLAM 权值方差缩减 样本退化 样本贫化 霍夫变换

在线阅读 下载PDF 职称材料

几种方差缩减方法效率的实证比较

11

作者 智冬晓 《统计教育》 2008年第10期20-23,共4页

在蒙特卡罗模拟中,方差缩减方法是提高模拟效率的重要手段。本文对几种常见的方差缩减方法进行了对比,结果发现,控制变量法不论是在计算精度还是在收敛速度上均优于其他方法,而且该方法操作简单,易于编程,是一种首选的计算方法。

关键词 蒙特卡罗模拟 方差缩减 效率

在线阅读 下载PDF 职称材料

方差缩减中的控制变量方法研究 被引量：2

12

作者 时蓬 杨明 刘飞 《科学技术与工程》 2011年第22期5323-5327,共5页

方差缩减方法是提高仿真效率的重要手段。针对方差缩减中广泛应用的控制变量法,在国内外研究基础上,综合考虑对仿真变量进行估计所需的样本量和对控制变量进行估计所需的样本量,给出了控制变量均值未知并且有偏时的估计,以及控制变量方... 方差缩减方法是提高仿真效率的重要手段。针对方差缩减中广泛应用的控制变量法,在国内外研究基础上,综合考虑对仿真变量进行估计所需的样本量和对控制变量进行估计所需的样本量,给出了控制变量均值未知并且有偏时的估计,以及控制变量方差已知时依赖于样本量和样本协方差的复合估计。引入控制变量的计算效率比,综合考虑各种估计方法的方差及其仿真样本量。 展开更多

关键词 仿真 方差缩减 控制变量 计算效率

在线阅读 下载PDF 职称材料

基于历史梯度平均方差缩减的协同参数更新方法 被引量：6

13

作者 谢涛 张春炯 徐永健 《电子与信息学报》 EI CSCD 北大核心 2021年第4期956-964,共9页

随机梯度下降算法(SGD)随机使用一个样本估计梯度,造成较大的方差,使机器学习模型收敛减慢且训练不稳定。该文提出一种基于方差缩减的分布式SGD,命名为DisSAGD。该方法采用历史梯度平均方差缩减来更新机器学习模型中的参数,不需要完全... 随机梯度下降算法(SGD)随机使用一个样本估计梯度,造成较大的方差,使机器学习模型收敛减慢且训练不稳定。该文提出一种基于方差缩减的分布式SGD,命名为DisSAGD。该方法采用历史梯度平均方差缩减来更新机器学习模型中的参数,不需要完全梯度计算或额外存储,而是通过使用异步通信协议来共享跨节点的参数。为了解决全局参数分发存在的“更新滞后”问题,该文采用具有加速因子的学习速率和自适应采样策略:一方面当参数偏离最优值时,增大加速因子,加快收敛速度;另一方面,当一个工作节点比其他工作节点快时,为下一次迭代采样更多样本,使工作节点有更多时间来计算局部梯度。实验表明:DisSAGD显著减少了循环迭代的等待时间,加速了算法的收敛,其收敛速度比对照方法更快,在分布式集群中可以获得近似线性的加速。 展开更多

关键词 梯度下降 机器学习 分布式集群 自适应采样 方差缩减

在线阅读 下载PDF 职称材料

机器学习中随机方差缩减梯度算法的一种新的步长规则 被引量：1

14

作者 杨一名 王福胜 《太原师范学院学报（自然科学版）》 2021年第4期37-42,共6页

针对大规模机器学习中常见的经验风险最小化问题,提出一种新的随机方差缩减梯度算法(SVRG-CABB).新算法结合了SVRG和复合BB步长的优势,对于初始步长的选取不敏感,在运算过程中通过动态调节步长,提高算法的运算效率.在标准数据集上的数... 针对大规模机器学习中常见的经验风险最小化问题,提出一种新的随机方差缩减梯度算法(SVRG-CABB).新算法结合了SVRG和复合BB步长的优势,对于初始步长的选取不敏感,在运算过程中通过动态调节步长,提高算法的运算效率.在标准数据集上的数值实验结果表明新算法是可行有效的. 展开更多

关键词 机器学习 随机梯度 方差缩减 复合BB步长

在线阅读 下载PDF 职称材料

带有随机改进Barzilai-Borwein步长的小批量稀疏随机方差缩减梯度法 被引量：1

15

作者 秦传东 杨旭 《计算机应用研究》 CSCD 北大核心 2023年第12期3655-3659,3665,共6页

为了更好地应对当今时代的大规模高维稀疏数据集,融合BB方法、小批量算法与随机方差缩减梯度法(SVRG)优势,提出一种带有随机改进Barzilai-Borwein步长的小批量稀疏随机方差缩减梯度法(MSSVRG-R2BB)。首先,在SVRG外循环中全梯度计算的基... 为了更好地应对当今时代的大规模高维稀疏数据集,融合BB方法、小批量算法与随机方差缩减梯度法(SVRG)优势,提出一种带有随机改进Barzilai-Borwein步长的小批量稀疏随机方差缩减梯度法(MSSVRG-R2BB)。首先,在SVRG外循环中全梯度计算的基础上加入L_1范数次梯度设计出一种稀疏近似梯度用于内循环,得到一种稀疏的SVRG算法(SSVRG)。在此基础上,在小批量的稀疏随机方差缩减梯度法中使用随机选取的改进BB方法自动计算、更新步长,解决了小批量算法的步长选取问题,拓展得到MSSVRG-R2BB算法。数值实验表明,在求解大规模高维稀疏数据的线性支持向量机(SVM)问题时,MSSVRG-R2BB算法不仅可以减小运算成本、更快达到收敛上界,同时能达到与其他先进的小批量算法相同的优化水平,并且对于不同的初始参数选取表现稳定且良好。 展开更多

关键词 随机梯度下降法 小批量算法 Barzilai-Borwein方法 方差缩减 凸优化

在线阅读 下载PDF 职称材料

非负Tucker分解的随机方差缩减乘性更新算法

16

作者 白姗姗 史加荣 《南京理工大学学报》 EI CAS CSCD 北大核心 2021年第2期197-204,共8页

为了降低乘性迭代算法在求解非负Tucker分解时的计算复杂度,该文在乘性迭代的基础上,提出了一种随机方差缩减乘性更新方法。该方法先将待分解的非负张量n-模式矩阵化,再运用随机方差缩减乘性更新算法对矩阵进行非负分解,得到模式矩阵,... 为了降低乘性迭代算法在求解非负Tucker分解时的计算复杂度,该文在乘性迭代的基础上,提出了一种随机方差缩减乘性更新方法。该方法先将待分解的非负张量n-模式矩阵化,再运用随机方差缩减乘性更新算法对矩阵进行非负分解,得到模式矩阵,最后通过梯度下降思想来更新核心张量。对高维数据进行非负Tucker分解时,加快收敛速度且降低计算复杂度,提高了张量分解性能。在人工合成数据集及真实数据集上进行数值实验,结果验证了所提算法的可行性和有效性。 展开更多

关键词 非负Tucker分解 随机方差缩减梯度算法 乘性更新 梯度下降

在线阅读 下载PDF 职称材料

Monte Carlo方法在Black-Scholes模型上的应用及方差缩减概述

17

作者 梁克垚 《现代信息科技》 2017年第6期65-68,共4页

在欧式期权模型中Black-Scholes公式拥有性质较好的解析解,然而,在很多衍生模型(例如亚式期权)中,Black-Scholes公式的解析解难以求得。Monte Carlo方法作为一种典型的统计模拟算法,在物理学、经济学等多种领域中起到了十分重要的作用... 在欧式期权模型中Black-Scholes公式拥有性质较好的解析解,然而,在很多衍生模型(例如亚式期权)中,Black-Scholes公式的解析解难以求得。Monte Carlo方法作为一种典型的统计模拟算法,在物理学、经济学等多种领域中起到了十分重要的作用。本文对Black-Scholes模型进行修正使其更加适应Monte Carlo方法并进行计算,并对对偶抽样、控制变量方法缩小Monte Carlo方法的方差的可行性和效果进行分析,使其更少的模拟次数得到更精确的计算结果。这种计算方法避免了使用计算机多次进行解微分方程运算,从而提高了用计算机进行大规模定价运算的效率,为高频交易中的期权价格预测提供了可能。 展开更多

关键词 MONTE CARLO方法 BLACK-SCHOLES模型 方差缩减

在线阅读 下载PDF 职称材料

基于Polyak步长的方差缩减算法 被引量：1

18

作者 李蝶 《科技资讯》 2021年第16期174-177,共4页

方差缩减算法的主要问题之一是如何选取一个合适的步长。在实践中,手动调整一个最佳的固定步长是很耗时的,所以该文提出将Polya k步长用于随机方差缩减梯度算法(SV RG),得到了一种新的SV RGPolyak算法。对于光滑强凸的目标函数我们证明... 方差缩减算法的主要问题之一是如何选取一个合适的步长。在实践中,手动调整一个最佳的固定步长是很耗时的,所以该文提出将Polya k步长用于随机方差缩减梯度算法(SV RG),得到了一种新的SV RGPolyak算法。对于光滑强凸的目标函数我们证明了SVRG-Polyak算法的线性收敛性。数值实验对比了SVRGPolyak、SVRG和带有BB步长的SVRG(SVRG-BB)3种算法,结果表明SVRG-Polyak算法的有效性。 展开更多

关键词 Polyak步长 方差缩减 强凸 线性收敛

在线阅读 下载PDF 职称材料

一种基于方差缩减的临近随机牛顿算法

19

作者 杜康乐 《应用数学进展》 2022年第7期4708-4717,共10页

本文研究了优化问题中的一类复合优化问题。 对于凸非光滑的目标函数,在临近牛顿算法的基础上,引入方差缩减的方法,提出了一种新的一一基于方差缩减的随机牛顿算法(SN V R),并进行了 收敛性分析。 与ProxSGD, ProxGD, ProxSV RG方法相比... 本文研究了优化问题中的一类复合优化问题。 对于凸非光滑的目标函数,在临近牛顿算法的基础上,引入方差缩减的方法,提出了一种新的一一基于方差缩减的随机牛顿算法(SN V R),并进行了 收敛性分析。 与ProxSGD, ProxGD, ProxSV RG方法相比,SN V R有更快的收敛速度。 展开更多

关键词 复合优化问题 机器学习 方差缩减 临近随机算法 牛顿算法

在线阅读 下载PDF 职称材料

求解非凸优化问题的一类带动量步的随机方差缩减算法

20

作者 谢小磊 杨毅 《科技创新导报》 2021年第17期78-81,共4页

本文研究一类非凸有限和问题,求解该类问题比较常用的方法是随机方差缩减算法。在随机方差缩减算法的基础上,考虑到动量步能够提升算法的求解效率,将动量步与随机方差缩减算法相结合,提出了一类带动量步的随机方差缩减算法。给出了该算... 本文研究一类非凸有限和问题,求解该类问题比较常用的方法是随机方差缩减算法。在随机方差缩减算法的基础上,考虑到动量步能够提升算法的求解效率,将动量步与随机方差缩减算法相结合,提出了一类带动量步的随机方差缩减算法。给出了该算法的具体迭代格式,并对该算法进行收敛性分析,证明了该算法在非凸情况下的次线性收敛率。 展开更多

关键词 方差缩减 经典动量 非凸优化 小批量

在线阅读 下载PDF 职称材料