使用Nesterov步长策略投影次梯度方法的个体收敛性 被引量：16

1

作者 陶蔚 潘志松 +1 位作者 储德军 陶卿 《计算机学报》 EI CSCD 北大核心 2018年第1期164-176,共13页

很多机器学习问题都可以最终转换为优化问题来进行求解,凸优化算法已经被成功用于各种机器学习优化问题中,而在优化算法的研究中是否能获得最优的收敛速率是一个最基本问题.此外,稀疏性是稀疏学习问题中关注的另一个目标.目前,人们已经... 很多机器学习问题都可以最终转换为优化问题来进行求解,凸优化算法已经被成功用于各种机器学习优化问题中,而在优化算法的研究中是否能获得最优的收敛速率是一个最基本问题.此外,稀疏性是稀疏学习问题中关注的另一个目标.目前,人们已经提出了大量的随机优化方法求解大规模机器学习优化问题,但大部分的研究只是针对平均输出方式获得了最优收敛速率.个体输出方式显然比平均方式的输出具有更好的稀疏性,但使个体收敛速率获得最优具有一定的难度,人们已经将强凸情形下的最优个体收敛性作为公开问题进行广泛研究.对于光滑目标函数的优化问题,著名学者Nesterov提出了一种步长策略,使得梯度方法的收敛速率获得了数量级形式的加速,并且获得了最优的个体收敛速率.目前,Nesterov加速算法已经应用于各种具有光滑损失函数机器学习优化问题中,研究者基于该加速策略提出了大量的随机优化算法.能否将这种技巧推广至非光滑情形获得最优的个体收敛速率显然是有意义的问题.文中考虑在非光滑优化算法中引入这种步长策略.特别地,我们聚焦经典的一阶梯度方法,提出了一种嵌入加速算法步长策略的投影次梯度算法,证明了这种算法在求解非光滑损失函数学习问题时具有最优的个体收敛速率.这是比标准投影次梯度方法只有在平均输出方式下才具有最优收敛速率更强的结论,也是一阶梯度方法在个体最优收敛速率方面比较接近于大家期待的研究成果.与平均方式输出以及线性插值的投影次梯度方法相比,该文所提方法的梯度运算在插值策略之后,因此在求解l1范数约束的hinge损失函数学习问题时具有更好的稀疏性.人工数据集上的实验验证了所提方法的正确性,基准数据集上验证了该方法在保持稀疏性方面具有良好的性能. 展开更多

关键词 机器学习 非光滑损失函数问题 投影次梯度方法 Nesterov步长策略 个体收敛速率 稀疏学习

下载PDF 职称材料

Heavy-Ball型动量方法的最优个体收敛速率 被引量：10

2

作者 程禹嘉 陶蔚 +1 位作者 刘宇翔 陶卿 《计算机研究与发展》 EI CSCD 北大核心 2019年第8期1686-1694,共9页

动量方法作为一种加速技巧被广泛用于提高一阶梯度优化算法的收敛速率.目前,大多数文献所讨论的动量方法仅限于Nesterov提出的加速方法,而对Polyak提出的Heavy-ball型动量方法的研究却较少.特别,在目标函数非光滑的情形下,Nesterov加速... 动量方法作为一种加速技巧被广泛用于提高一阶梯度优化算法的收敛速率.目前,大多数文献所讨论的动量方法仅限于Nesterov提出的加速方法,而对Polyak提出的Heavy-ball型动量方法的研究却较少.特别,在目标函数非光滑的情形下,Nesterov加速方法具有最优的个体收敛性,并在稀疏优化问题的求解中具有很好的效果.但对于Heavy-ball型动量方法,目前仅仅获得了平均输出形式的最优收敛速率,个体收敛是否具有最优性仍然未知.对于非光滑优化问题,通过巧妙地设置步长,证明了Heavy-ball型动量方法具有最优的个体收敛速率,从而说明了Heavy-ball型动量方法可以将投影次梯度方法的个体收敛速率加速至最优.作为应用,考虑了l1范数约束的hinge损失函数优化问题.通过与同类的优化算法相比,实验验证了该理论分析的正确性以及所提算法在保持稀疏性方面的良好性能. 展开更多

关键词 一阶梯度方法 动量方法 个体收敛速率 Heavy-ball方法 稀疏性

下载PDF 职称材料

基于反向学习的布谷鸟算法优化搜索仿真 被引量：7

3

作者 胡安明 李伟 《计算机仿真》 北大核心 2021年第12期276-280,共5页

针对布谷鸟算法求解复杂的问题时收敛速度过低、全局效果不理想等问题,提出基于反向学习的布谷鸟算法优化搜索方法。对当前布谷鸟群体加入反向学习策略,从全局中找出精英个体,并对个体求反向解,在所得的可行解与反向解中找出最优个体作... 针对布谷鸟算法求解复杂的问题时收敛速度过低、全局效果不理想等问题,提出基于反向学习的布谷鸟算法优化搜索方法。对当前布谷鸟群体加入反向学习策略,从全局中找出精英个体,并对个体求反向解,在所得的可行解与反向解中找出最优个体作为下一次迭代的个体。将混沌扰动策略引入鸟巢位置的确定过程,扩大布谷鸟种群的多样性,提高算法整体的收敛精度和搜索能力。最后进行仿真,运用不同方法对四个函数测试的结果中可以看出,所提方法具有更优的搜索能力和收敛速度。 展开更多

关键词 反向学习 精英个体 混沌扰动策略 收敛速度 寻优能力

下载PDF 职称材料

非光滑凸情形Adam 型算法的最优个体收敛速率 被引量：5

4

作者 黄鉴之 丁成诚 +1 位作者 陶蔚 陶卿 《智能系统学报》 CSCD 北大核心 2020年第6期1140-1146,共7页

Adam是目前深度神经网络训练中广泛采用的一种优化算法框架,同时使用了自适应步长和动量技巧,克服了SGD的一些固有缺陷。但即使对于凸优化问题,目前Adam也只是在线学习框架下给出了和梯度下降法一样的regret界,动量的加速特性并没有得... Adam是目前深度神经网络训练中广泛采用的一种优化算法框架,同时使用了自适应步长和动量技巧,克服了SGD的一些固有缺陷。但即使对于凸优化问题,目前Adam也只是在线学习框架下给出了和梯度下降法一样的regret界,动量的加速特性并没有得到体现。这里针对非光滑凸优化问题,通过巧妙选取动量和步长参数,证明了Adam的改进型具有最优的个体收敛速率,从而说明了Adam同时具有自适应和加速的优点。通过求解l_(1)范数约束下的hinge损失问题,实验验证了理论分析的正确性和在算法保持稀疏性方面的良好性能。 展开更多

关键词 机器学习 AdaGrad算法 RMSProp算法 动量方法 Adam算法 AMSGrad算法 个体收敛速率 稀疏性

下载PDF 职称材料

线性插值投影次梯度方法的最优个体收敛速率 被引量：5

5

作者 陶蔚 潘志松 +1 位作者 朱小辉 陶卿 《计算机研究与发展》 EI CSCD 北大核心 2017年第3期529-536,共8页

投影次梯度算法(projected subgradient method,PSM)是求解非光滑约束优化问题最简单的一阶梯度方法,目前只是对所有迭代进行加权平均的输出方式得到最优收敛速率,其个体收敛速率问题甚至作为open问题被提及.最近,Nesterov和Shikhman在... 投影次梯度算法(projected subgradient method,PSM)是求解非光滑约束优化问题最简单的一阶梯度方法,目前只是对所有迭代进行加权平均的输出方式得到最优收敛速率,其个体收敛速率问题甚至作为open问题被提及.最近,Nesterov和Shikhman在对偶平均方法(dual averaging method,DAM)的迭代中嵌入一种线性插值操作,得到一种拟单调的求解非光滑问题的次梯度方法,并证明了在一般凸情形下具有个体最优收敛速率,但其讨论仅限于对偶平均方法.通过使用相同技巧,提出了一种嵌入线性插值操作的投影次梯度方法,与线性插值对偶平均方法不同的是,所提方法还对投影次梯度方法本身进行了适当的修改以确保个体收敛性.同时证明了该方法在一般凸情形下可以获得个体最优收敛速率,并进一步将所获结论推广至随机方法情形.实验验证了理论分析的正确性以及所提算法在保持实时稳定性方面的良好性能. 展开更多

关键词 一阶梯度方法 个体收敛速率 投影次梯度方法 线性插值操作 对偶平均方法

下载PDF 职称材料

基于双重更新策略的粒子群算法 被引量：4

6

作者 宋锦 高浩 +1 位作者 胡海东 王保云 《南京邮电大学学报（自然科学版）》 北大核心 2015年第6期84-88,共5页

粒子群算法由于其简单易实现以及快速寻优的特点引起了研究者的广泛兴趣,但却存在着在搜索过程中无法跳出局部最小点的缺陷。文中提出了一种基于双重更新策略粒子群算法。当群体的聚集度达到设定的条件时,首先在具有较差成绩的个体历史... 粒子群算法由于其简单易实现以及快速寻优的特点引起了研究者的广泛兴趣,但却存在着在搜索过程中无法跳出局部最小点的缺陷。文中提出了一种基于双重更新策略粒子群算法。当群体的聚集度达到设定的条件时,首先在具有较差成绩的个体历史最优解(personal best,pbest)中任意选择一个更新,使它具有在全局范围内进行搜索的能力,同时从获得较好成绩的pbest中选择一个,在它和全局最优位置之间进行局部搜索,从而引导个体向有价值的区域寻优。标准测试函数的仿真结果表明,该算法有效提高了粒子的全局搜索能力,同时提升了算法的局部搜索能力,因此可以应用在实际生产领域。 展开更多

关键词 粒子群优化算法 全局搜索 个体历史最优 收敛速度

下载PDF 职称材料

基于AdaGrad的自适应NAG方法及其最优个体收敛性 被引量：3

7

作者 陇盛 陶蔚 +1 位作者 张泽东 陶卿 《软件学报》 EI CSCD 北大核心 2022年第4期1231-1243,共13页

与梯度下降法相比,自适应梯度下降方法(AdaGrad)利用过往平方梯度的算数平均保存了历史数据的几何信息,在处理稀疏数据时获得了更紧的收敛界.另一方面,Nesterov加速梯度方法(Nesterov’saccelerated gradient,NAG)在梯度下降法的基础上... 与梯度下降法相比,自适应梯度下降方法(AdaGrad)利用过往平方梯度的算数平均保存了历史数据的几何信息,在处理稀疏数据时获得了更紧的收敛界.另一方面,Nesterov加速梯度方法(Nesterov’saccelerated gradient,NAG)在梯度下降法的基础上添加了动量运算,在求解光滑凸优化问题时具有数量级加速收敛的性能,在处理非光滑凸问题时也获得了最优的个体收敛速率.最近,已经出现了自适应策略与NAG相结合的研究,但现有代表性的自适应NAG方法AcceleGrad由于采取的自适应方式与AdaGrad不同,步长未能在不同维度上体现差异性,仅得到了加权平均方式的收敛速率,个体收敛速率的理论分析尚存在缺失.提出了一种自适应NAG方法,继承了AdaGrad的步长设置方式,证明了所提算法在解决约束非光滑凸优化问题时具有最优的个体收敛速率.在L1范数约束下,通过求解典型的hinge损失函数分类和L1损失函数回归优化问题.实验验证了理论分析的正确性,也表明了所提算法的性能优于AcceleGrad. 展开更多

关键词 机器学习 凸优化 自适应算法 NAG方法 个体收敛速率

下载PDF 职称材料

基于改进加速遗传算法的作物灌水率图修正研究 被引量：3

8

作者 张宇亮 张礼兵 +2 位作者 周玉良 张明 吴成国 《灌溉排水学报》 CSCD 北大核心 2015年第11期80-83,共4页

提出了基于改进加速遗传算法的作物灌水率图修正方案。首先确定停水次数、块内均匀度和灌水率极差的3个子目标函数,再将多目标优化问题转化为单目标优化问题,最后执行基于个体修正模型的改进加速遗传算法的智能优化,关键对每代个体利用... 提出了基于改进加速遗传算法的作物灌水率图修正方案。首先确定停水次数、块内均匀度和灌水率极差的3个子目标函数,再将多目标优化问题转化为单目标优化问题,最后执行基于个体修正模型的改进加速遗传算法的智能优化,关键对每代个体利用个体修正模型局部调整各次灌水起止时间。实例表明,灌水率图修正过程中,总目标函数从1.00降低到0.05,比相关文献低0.23,同时与无个体修正模型相比,有个体修正模型的142代以后的总目标函数值降低了近1个数量级。基于改进加速遗传算法的作物灌水率图修正方案是有效可行的,且其修正质量、修正速度和自动化水平较现有方法得到提高。 展开更多

关键词 作物灌水率图 个体修正模型 加速遗传算法 收敛速度 层次分析法

下载PDF 职称材料

基于AdaBelief的Heavy-Ball动量方法 被引量：1

9

作者 张泽东 陇盛 +1 位作者 鲍蕾 陶卿 《模式识别与人工智能》 EI CSCD 北大核心 2022年第2期106-115,共10页

同时使用动量和自适应步长技巧的自适应矩估计(Adaptive Moment Estimation,Adam)型算法广泛应用于深度学习中.针对此方法不能同时在理论和实验上达到最优这一问题,文中结合AdaBelief灵活调整步长提高实验性能的技巧,以及仅采用指数移... 同时使用动量和自适应步长技巧的自适应矩估计(Adaptive Moment Estimation,Adam)型算法广泛应用于深度学习中.针对此方法不能同时在理论和实验上达到最优这一问题,文中结合AdaBelief灵活调整步长提高实验性能的技巧,以及仅采用指数移动平均(Exponential Moving Average,EMA)策略调整步长的Heavy-Ball动量方法加速收敛的优点,提出基于AdaBelief的Heavy-Ball动量方法.借鉴AdaBelief和Heavy-Ball动量方法收敛性分析的技巧,巧妙选取时变步长、动量系数,并利用添加动量项和自适应矩阵的方法,证明文中方法对于非光滑一般凸优化问题具有最优的个体收敛速率.最后,在凸优化问题和深度神经网络上的实验验证理论分析的正确性,并且证实文中方法可在理论上达到最优收敛性的同时提高性能. 展开更多

关键词 AdaBelief Heavy-Ball动量方法 个体收敛速率 深度神经网络

下载PDF 职称材料

自适应策略下Heavy-Ball型动量法的最优个体收敛速率 被引量：1

10

作者 黄鉴之 陇盛 陶卿 《模式识别与人工智能》 EI CSCD 北大核心 2021年第2期137-145,共9页

同时使用自适应步长和动量两种优化技巧的AMSGrad在收敛性分析方面存在比自适应步长算法增加一个对数因子的问题.为了解决该问题,文中在非光滑凸情形下,巧妙选取动量和步长参数,证明自适应策略下Heavy-Ball型动量法具有最优的个体收敛速... 同时使用自适应步长和动量两种优化技巧的AMSGrad在收敛性分析方面存在比自适应步长算法增加一个对数因子的问题.为了解决该问题,文中在非光滑凸情形下,巧妙选取动量和步长参数,证明自适应策略下Heavy-Ball型动量法具有最优的个体收敛速率,说明自适应策略下Heavy-Ball型动量法兼具动量的加速特性和自适应步长对超参数的低依赖性.求解l 1范数约束下的Hinge损失问题,验证理论分析的正确性. 展开更多

关键词 自适应步长算法 动量算法 AMSGrad 个体收敛速率

下载PDF 职称材料

基于对偶平均的动量方法研究综述

11

作者 曲军谊 《计算机与数字工程》 2022年第11期2443-2448,共6页

对偶平均(dual averaging)方法是一种颇具潜力的优化算法,它巧妙地利用过往所有梯度的信息,克服了传统一阶梯度算法无法摆脱的梯度消失的弊端,并得到稳定的收敛速率。而恰恰类似的是,动量方法同样是利用过往的梯度信息,目的在于在非凸... 对偶平均(dual averaging)方法是一种颇具潜力的优化算法,它巧妙地利用过往所有梯度的信息,克服了传统一阶梯度算法无法摆脱的梯度消失的弊端,并得到稳定的收敛速率。而恰恰类似的是,动量方法同样是利用过往的梯度信息,目的在于在非凸优化问题中能够有效地逃离局部最小点和鞍点,而今年来动量方法也广泛活跃在凸优化领域,不单对一般的梯度下降算法起到加速作用,同时在没有光滑性条件的情况下,得到最优个体收敛速率。论文对对偶平均方法和动量方法的研究现状和存在的问题进行综述,分析两者的联系和区别,并在此基础上指出一些值得研究的问题。 展开更多

关键词 机器学习 对偶平均 动量方法 个体收敛性 稀疏性

下载PDF 职称材料

随机COMID的瞬时收敛速率分析 被引量：1

12

作者 姜纪远 陶卿 +1 位作者 邵言剑 汪群山 《电子学报》 EI CAS CSCD 北大核心 2015年第9期1850-1858,共9页

COMID(Composite Objective MIrror Descent)是一种能够保证L1正则化结构的在线算法,其随机收敛速率可由在线算法的regret界直接得到,但其最终解是T次迭代平均的形式,稀疏性很差.瞬时解具有很好的稀疏性,因此分析算法的瞬时收敛速率在... COMID(Composite Objective MIrror Descent)是一种能够保证L1正则化结构的在线算法,其随机收敛速率可由在线算法的regret界直接得到,但其最终解是T次迭代平均的形式,稀疏性很差.瞬时解具有很好的稀疏性,因此分析算法的瞬时收敛速率在随机学习中变得越来越重要.本文讨论正则化非光滑损失的随机优化问题,当正则化项为L1和L1+L2时,分别证明了COMID的瞬时收敛速率.大规模数据库上的实验表明,在保证几乎相同正确率的同时,瞬时解一致地提高了稀疏性,尤其是对稀疏性较差的数据库,稀疏度甚至能够提升4倍以上. 展开更多

关键词 机器学习 随机优化 非光滑优化 L1正则化 COMID 瞬时收敛速率

下载PDF 职称材料

非光滑凸问题投影型对偶平均优化方法的个体收敛性 被引量：1

13

作者 曲军谊 鲍蕾 陶卿 《模式识别与人工智能》 EI CSCD 北大核心 2021年第1期25-32,共8页

对于一般凸问题,对偶平均方法的收敛性分析需要在对偶空间进行转换,难以得到个体收敛性结果.对此,文中首先给出对偶平均方法的简单收敛性分析,证明对偶平均方法具有与梯度下降法相同的最优个体收敛速率Ο(ln t√t).不同于梯度下降法,讨... 对于一般凸问题,对偶平均方法的收敛性分析需要在对偶空间进行转换,难以得到个体收敛性结果.对此,文中首先给出对偶平均方法的简单收敛性分析,证明对偶平均方法具有与梯度下降法相同的最优个体收敛速率Ο(ln t√t).不同于梯度下降法,讨论2种典型的步长策略,验证对偶平均方法在个体收敛分析中具有步长策略灵活的特性.进一步,将个体收敛结果推广至随机形式,确保对偶平均方法可有效处理大规模机器学习问题.最后,在L1范数约束的hinge损失问题上验证理论分析的正确性. 展开更多

关键词 对偶平均 个体收敛速率 稀疏性 非光滑

下载PDF 职称材料

梯度有偏随机DA优化方法的个体收敛界分析

14

作者 张梦晗 汪海 +1 位作者 刘欣 鲍蕾 《计算机工程》 CAS CSCD 北大核心 2019年第10期203-207,214,共6页

样本不满足独立同分布会使梯度估计在迭代过程中存在偏差,且最优的个体收敛界在噪声的干扰下无法确定。为此,提出一种线性插值随机对偶平均(DA)优化方法。给出DA方法收敛性的证明,在梯度估计有偏的基础上,求解得到一种线性插值DA随机优... 样本不满足独立同分布会使梯度估计在迭代过程中存在偏差,且最优的个体收敛界在噪声的干扰下无法确定。为此,提出一种线性插值随机对偶平均(DA)优化方法。给出DA方法收敛性的证明,在梯度估计有偏的基础上,求解得到一种线性插值DA随机优化方法不产生累积偏差的个体收敛界,以保证正则化损失函数结构下优化方法的个体收敛精度。实验结果表明,与随机加速方法相比,该方法具有较快的个体收敛速率与较高的收敛精度。 展开更多

关键词 对偶平均方法 随机优化 个体收敛性 梯度有偏估计 最优收敛速率

下载PDF 职称材料

基于随机步长具有最优瞬时收敛速率的稀疏随机优化算法

15

作者 周柏 陶卿 储德军 《模式识别与人工智能》 EI CSCD 北大核心 2015年第10期876-885,共10页

几乎所有的稀疏随机算法都来源于在线形式,只能获得平均输出方式的收敛速率,对于强凸优化问题无法达到最优的瞬时收敛速率.文中避开在线形式转到随机模式,直接研究随机优化算法.首先在含有L1正则化项的稀疏优化问题中加入L2正则化项,使... 几乎所有的稀疏随机算法都来源于在线形式,只能获得平均输出方式的收敛速率,对于强凸优化问题无法达到最优的瞬时收敛速率.文中避开在线形式转到随机模式,直接研究随机优化算法.首先在含有L1正则化项的稀疏优化问题中加入L2正则化项,使之具有强凸特性.然后将黑箱优化方法中的随机步长策略引入到当前通用的结构优化算法COMID中,得到基于随机步长的混合正则化镜面下降稀疏随机优化算法.最后通过分析L1正则化问题中软阈值方法的求解特点,证明算法具有最优的瞬时收敛速率.实验表明,文中算法的稀疏性优于COMID. 展开更多

关键词 机器学习 随机优化 最优瞬时收敛速率 稀疏性

下载PDF 职称材料