非光滑强凸情形Adam型算法的最优收敛速率

doi:10.12263/DZXB.20210589

电子学报 ›› 2022, Vol. 50 ›› Issue (9): 2049-2059.DOI: 10.12263/DZXB.20210589

• 学术论文 • 下一篇

非光滑强凸情形Adam型算法的最优收敛速率

陇盛¹^,³, 陶蔚², 张泽东³, 陶卿³

^1.国防科技大学信息系统工程重点实验室, 湖南长沙 410073
^2.军事科学院战略评估咨询中心, 北京 100091
^3.陆军炮兵防空兵学院信息工程系, 安徽合肥 230031

收稿日期:2021-05-09 修回日期:2021-11-02 出版日期:2022-09-25
- 通讯作者:
- 陶蔚
- 作者简介:
- 陇　盛　男，1998年1月出生于贵州省盘州市.硕士研究生.主要研究领域为机器学习，模式识别.E-mail: ls15186322349@163.com
  陶　蔚　男，1991年出生于安徽省合肥市.博士，助理研究员，主要研究领域为机器学习.
  张泽东　男，1994年出生于山东省临清市.硕士研究生，主要研究领域为机器学习，模式识别.E-mail: l632783823@qq.com
  陶　卿　男，1965年出生于安徽省合肥市.博士，教授，博士生导师，CCF高级会员，主要研究领域为机器学习，模式识别，应用数学.E-mail: qing.tao@ia.ac.cn
- 基金资助:
- 国家自然科学基金 (62076252)

The Optimal Convergence Rate of Adam-Type Algorithms for Non-Smooth Strongly Convex Cases

LONG Sheng¹^,³, TAO Wei², ZHANG Ze-dong³, TAO Qing³

^1.Science and Technology on Information Systems Engineering Laboratory，National University of Defense Technology，Changsha，Hunan 410073，China
^2.Center for Strategic Assessment and Consulting，Academy of Military Science，Beijing 100091，China
^3.Department of Information Engineering，Army Academy of Artillery and Air Defense，Hefei，Anhui 230031，China

Received:2021-05-09 Revised:2021-11-02 Online:2022-09-25 Published:2022-10-26
- Corresponding author:
- TAO Wei

摘要/Abstract

摘要：

对于非光滑强凸问题，在线梯度下降（Online Gradient Decent，OGD）取适当步长参数可以得到对数阶后悔界.然而，这并不能使一阶随机优化算法达到最优收敛速率.为解决这一问题，研究者通常采取两种方案：其一是改进算法本身，另一种是修改算法输出方式.典型的Adam（Adaptive moment estimation）型算法SAdam（Strongly convex Adaptive moment estimation）采用了改进算法的方式，并添加了自适应步长策略和动量技巧，虽然得到更好的数据依赖的后悔界，但在随机情形仍然达不到最优.针对这个问题，本文改用加权平均的算法输出方式，并且重新设计与以往算法同阶的步长超参数，提出了一种名为WSAdam（Weighted average Strongly convex Adaptive moment estimation）的Adam型算法.证明了WSAdam达到了非光滑强凸问题的最优收敛速率.经过Reddi问题的测试和在非光滑强凸函数优化中的实验，验证了所提方法的有效性.

关键词: 非光滑, 强凸优化, 自适应步长, 动量方法, Adam型算法, 加权平均, 收敛速率

Abstract:

For non-smooth strongly convex problems, the logarithmic regret bound can be obtained by online gradient descent with the appropriate step size parameter. However, it cannot make the first order stochastic optimization algorithm achieve the optimal convergence rate. To solve this problem, researchers usually adopt two schemes: one is to modify the iterate of the algorithm, the other is to change the output mode of the algorithm. SAdam, a typical Adam-type algorithm, modify the algorithm by adding adaptive step size strategy and momentum technique. Although it obtains a tighter data dependent regret bound, it still cannot reach the optimal bound in the stochastic case. To solve this problem, this paper redesigns the step size scheme which is the same order as the previous algorithm, uses the weighted average algorithm output mode, and proposes an Adam-type algorithm named WSAdam. It is proved that WSAdam achieves the optimal convergence rate for non-smooth strongly convex problems. The validity of the proposed method is verified by the test of Reddi's problem and the experiment in the optimization of non-smooth strongly convex functions.

Key words: non-smooth, strongly convex, adaptive step size, momentum methods, Adam-type algorithms, weighted average, convergence rate

中图分类号:

TP301

陇盛, 陶蔚, 张泽东, 陶卿. 非光滑强凸情形Adam型算法的最优收敛速率[J]. 电子学报, 2022, 50(9): 2049-2059.

LONG Sheng, TAO Wei, ZHANG Ze-dong, TAO Qing. The Optimal Convergence Rate of Adam-Type Algorithms for Non-Smooth Strongly Convex Cases[J]. Acta Electronica Sinica, 2022, 50(9): 2049-2059.

图/表 6

表1 常见Adam型算法对比

算法	$α t, m t, V t$	后悔界	收敛速率
Adam	$α t = α / t$ $m t = β 1 m t - 1 + 1 - β 1 g ̂ t$ $V t = d i a g v t + δ I d / t$ $v t = β 2 v t - 1 + 1 - β 2 g ̂ t 2$	$Ο (T)$	$Ο (1 / T)$
AMSGrad	$α t = α / t$ $m t = β 1 m t - 1 + 1 - β 1 g ̂ t$ $V t = m a x V t - 1, V ̂ t$ $V ̂ t = d i a g v t + δ I d / t$ $v t = β 2 v t - 1 + 1 - β 2 g ̂ t 2$	$Ο (T)$	$Ο (1 / T)$
AdamNC	$α t = α / t$ $m t = β 1 m t - 1 + 1 - β 1 g ̂ t$ $V t = d i a g v t + δ I d / t$ $v t = β 2, t v t - 1 + 1 - β 2, t g ̂ t 2$ $1 - 1 / t ≤ β 2, t ≤ 1 - γ / t$ $γ ∈ 0,1$	$Ο (T)$	$Ο (1 / T)$
SC-Adagrad	$α t = α$ $m t = g ̂ t$ $V t = d i a g v t 2 + δ I d$ $v t = v t - 1 + g ̂ t 2$	$Ο (l o g T)$	$Ο (l o g T / T)$
SC-RMSProp	$α t = α / t$ $m t = g ̂ t$ $V t = d i a g v t 2 + δ I d / t 2$ $v t = β 2, t v t - 1 + 1 - β 2, t g ̂ t 2$ $1 - 1 / t ≤ β t ≤ 1 - γ / t$ $γ ∈ 0,1$	$Ο (l o g T)$	$Ο (l o g T / T)$
SAdam	$α t = α / t$ $m t = β 1 m t - 1 + 1 - β 1 g ̂ t$ $V t = d i a g v t 2 + δ I d / t 2$ $v t = β 2, t v t - 1 + 1 - β 2, t g ̂ t 2$ $1 - 1 / t ≤ β t ≤ 1 - γ / t$ $γ ∈ 0,1$	$Ο (l o g T)$	$Ο (l o g T / T)$

表1 常见Adam型算法对比

算法	$α t, m t, V t$	后悔界	收敛速率
Adam	$α t = α / t$ $m t = β 1 m t - 1 + 1 - β 1 g ̂ t$ $V t = d i a g v t + δ I d / t$ $v t = β 2 v t - 1 + 1 - β 2 g ̂ t 2$	$Ο (T)$	$Ο (1 / T)$
AMSGrad	$α t = α / t$ $m t = β 1 m t - 1 + 1 - β 1 g ̂ t$ $V t = m a x V t - 1, V ̂ t$ $V ̂ t = d i a g v t + δ I d / t$ $v t = β 2 v t - 1 + 1 - β 2 g ̂ t 2$	$Ο (T)$	$Ο (1 / T)$
AdamNC	$α t = α / t$ $m t = β 1 m t - 1 + 1 - β 1 g ̂ t$ $V t = d i a g v t + δ I d / t$ $v t = β 2, t v t - 1 + 1 - β 2, t g ̂ t 2$ $1 - 1 / t ≤ β 2, t ≤ 1 - γ / t$ $γ ∈ 0,1$	$Ο (T)$	$Ο (1 / T)$
SC-Adagrad	$α t = α$ $m t = g ̂ t$ $V t = d i a g v t 2 + δ I d$ $v t = v t - 1 + g ̂ t 2$	$Ο (l o g T)$	$Ο (l o g T / T)$
SC-RMSProp	$α t = α / t$ $m t = g ̂ t$ $V t = d i a g v t 2 + δ I d / t 2$ $v t = β 2, t v t - 1 + 1 - β 2, t g ̂ t 2$ $1 - 1 / t ≤ β t ≤ 1 - γ / t$ $γ ∈ 0,1$	$Ο (l o g T)$	$Ο (l o g T / T)$
SAdam	$α t = α / t$ $m t = β 1 m t - 1 + 1 - β 1 g ̂ t$ $V t = d i a g v t 2 + δ I d / t 2$ $v t = β 2, t v t - 1 + 1 - β 2, t g ̂ t 2$ $1 - 1 / t ≤ β t ≤ 1 - γ / t$ $γ ∈ 0,1$	$Ο (l o g T)$	$Ο (l o g T / T)$

图1 Reddi问题实验结果

表2 标准数据库描述

Datasets	Training Samples	Test Samples	Dimensions
cod-rna	59535	271617	8
ijcnn1	49990	91701	22
gisette	6000	1000	5000
madelon	2000	600	500
a9a	32561	16281	123
liver-disorders	145	200	5

图2 目标函数收敛速率比较图

表3 训练准确率和方差比较

数据库/算法	Pegasos	SAdam	WSAdam	SC-Adagrad	SC-RMSProp
cod-rna	0.5994 $±$ 0.1737	0.8575 $±$ 0.0165	0.8846 $±$ 0.0011	0.8099 $±$ 0.1468	0.8260 $±$ 0.0881
ijcnn1	0.9024 $±$ 0.0000	0.9024 $±$ 0.0000	0.9024 $±$ 0.0000	0.9024 $±$ 0.0000	0.9024 $±$ 0.0000
gisette	0.9795 $±$ 0.0367	0.9792 $±$ 0.0148	0.9861 $±$ 0.0118	0.9800 $±$ 0.0236	0.9850 $±$ 0.0071
madelon	0.5000 $±$ 0.0000	0.5681 $±$ 0.0507	0.5760 $±$ 0.0569	0.5545 $±$ 0.0573	0.5340 $±$ 0.0436
a9a	0.8425 $±$ 0.0016	0.8423 $±$ 0.0008	0.8428 $±$ 0.0005	0.8420 $±$ 0.0006	0.8423 $±$ 0.0009
liver-disorders	0.6228 $±$ 0.1216	0.6897 $±$ 0.0065	0.6979 $±$ 0.0121	0.6648 $±$ 0.0732	0.6531 $±$ 0.0758

表3 训练准确率和方差比较

数据库/算法	Pegasos	SAdam	WSAdam	SC-Adagrad	SC-RMSProp
cod-rna	0.5994 $±$ 0.1737	0.8575 $±$ 0.0165	0.8846 $±$ 0.0011	0.8099 $±$ 0.1468	0.8260 $±$ 0.0881
ijcnn1	0.9024 $±$ 0.0000	0.9024 $±$ 0.0000	0.9024 $±$ 0.0000	0.9024 $±$ 0.0000	0.9024 $±$ 0.0000
gisette	0.9795 $±$ 0.0367	0.9792 $±$ 0.0148	0.9861 $±$ 0.0118	0.9800 $±$ 0.0236	0.9850 $±$ 0.0071
madelon	0.5000 $±$ 0.0000	0.5681 $±$ 0.0507	0.5760 $±$ 0.0569	0.5545 $±$ 0.0573	0.5340 $±$ 0.0436
a9a	0.8425 $±$ 0.0016	0.8423 $±$ 0.0008	0.8428 $±$ 0.0005	0.8420 $±$ 0.0006	0.8423 $±$ 0.0009
liver-disorders	0.6228 $±$ 0.1216	0.6897 $±$ 0.0065	0.6979 $±$ 0.0121	0.6648 $±$ 0.0732	0.6531 $±$ 0.0758

表4 测试准确率和方差比较

数据库/算法	Pegasos	SAdam	WSAdam	SC-Adagrad	SC-RMSProp
cod-rna	0.6374 $±$ 0.3886	0.9495 $±$ 0.0017	0.9460 $±$ 0.0015	0.9142 $±$ 0.0965	0.9387 $±$ 0.0178
ijcnn1	0.9050 $±$ 0.0000	0.9050 $±$ 0.0000	0.9050 $±$ 0.0000	0.9050 $±$ 0.0000	0.9050 $±$ 0.0000
gisette	0.9626 $±$ 0.0320	0.9568 $±$ 0.0152	0.9642 $±$ 0.0125	0.9578 $±$ 0.0238	0.9617 $±$ 0.0097
madelon	0.5000 $±$ 0.0000	0.5612 $±$ 0.0459	0.5620 $±$ 0.0569	0.5450 $±$ 0.0657	0.5220 $±$ 0.0395
a9a	0.8462 $±$ 0.0023	0.8454 $±$ 0.0009	0.8460 $±$ 0.0013	0.8452 $±$ 0.0013	0.8458 $±$ 0.0016
liver-disorders	0.5335 $±$ 0.0231	0.5360 $±$ 0.0084	0.5410 $±$ 0.0097	0.5280 $±$ 0.0289	0.5190 $±$ 0.0281

表4 测试准确率和方差比较

数据库/算法	Pegasos	SAdam	WSAdam	SC-Adagrad	SC-RMSProp
cod-rna	0.6374 $±$ 0.3886	0.9495 $±$ 0.0017	0.9460 $±$ 0.0015	0.9142 $±$ 0.0965	0.9387 $±$ 0.0178
ijcnn1	0.9050 $±$ 0.0000	0.9050 $±$ 0.0000	0.9050 $±$ 0.0000	0.9050 $±$ 0.0000	0.9050 $±$ 0.0000
gisette	0.9626 $±$ 0.0320	0.9568 $±$ 0.0152	0.9642 $±$ 0.0125	0.9578 $±$ 0.0238	0.9617 $±$ 0.0097
madelon	0.5000 $±$ 0.0000	0.5612 $±$ 0.0459	0.5620 $±$ 0.0569	0.5450 $±$ 0.0657	0.5220 $±$ 0.0395
a9a	0.8462 $±$ 0.0023	0.8454 $±$ 0.0009	0.8460 $±$ 0.0013	0.8452 $±$ 0.0013	0.8458 $±$ 0.0016
liver-disorders	0.5335 $±$ 0.0231	0.5360 $±$ 0.0084	0.5410 $±$ 0.0097	0.5280 $±$ 0.0289	0.5190 $±$ 0.0281

参考文献 25

1	CUTKOSKY A. Parameter-free, dynamic, and strongly-adaptive online learning[C]//Proceedings of the 37th International Conference on Machine Learning. Virtual Event: ICML, 2020: 2250-2259.
2	ZINKEVICH M. Online convex programming and generalized infinitesimal gradient ascent[C]//Proceedings of the Twentieth International Conference on International Conference on Machine Learning. Washington DC: ICML,2003: 928-935.
3	HAZAN E, KALAI A, KALE S, et al. Logarithmic regret algorithms for online convex optimization[C]//Proceedings of 19th Annual Conference on Learning Theory(COLT). Berlin, Heidelberg: Springer, 2006: 499-513.
4	SHAMIR O, ZHANG T. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes[C]//Proceedings of the 30th International Conference on International Conference on Machine Learning - Volume 28. Atlanta: ICML, 2013: I-71-I-79.
5	AGARWAL A, BARTLETT P L, RAVIKUMAR P, et al. Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization[J]. IEEE Transactions on Information Theory, 2012, 58(5): 3235-3249.
6	陶卿, 朱烨雷, 罗强, 等. 一种基于Comid的非光滑损失随机坐标下降方法[J]. 电子学报, 2013, 41(4): 768-775.
	TAO Q, ZHU Y L, LUO Q, et al. A new comid-based stochastic coordinate descent method for non-smooth losses[J]. Acta Electronica Sinica, 2013, 41(4): 768-775. (in Chinese)
7	HAZAN E, KALE S. Beyond the regret minimization barrier: Optimal algorithms for stochastic strongly-convex optimization[J]. Journal of Machine Learning Research, 2011: 421-436.
8	RAKHLIN A, SHAMIR O, SRIDHARAN K. Making gradient descent optimal for strongly convex stochastic optimization[C]//Proceedings of the 29th International Conference on Machine Learning(ICML). Edinburgh: ICML, 2012: 1571-1578.
9	LACOSTE-JULIEN S, SCHMIDT M, BATCH F. A Simpler Approach to Obtaining an convergence rate for projected stochastic subgradient descent[EB/OL].(2012-12-10). .
10	邵言剑, 陶卿, 姜纪远, 等. 一种求解强凸优化问题的最优随机算法[J]. 软件学报, 2014, 25(9): 2160-2171.
	SHAO Y J, TAO Q, JIANG J Y, et al. Stochastic algorithm with optimal convergence rate for strongly convex optimization problems[J]. Journal of Software, 2014, 25(9): 2160-2171. (in Chinese)
11	CUTKOSKY A. Anytime online-to-batch, optimism and acceleration[C]//Proceedings of the 36th International Conference on Machine Learning(ICML). Long Beach: ICML, 2019: 1446-1454.
12	KINGMA D P, BA J. Adam: A method for stochastic optimization[C]//Proceedings of the 3th International Conference on Learning Representations(ICLR). San Diego: ICLR, 2015: 1-13.
13	TIMOTHY D. Incorporating Nesterov momentum into Adam[EB/OL].(2015-12-12)..
14	CHEN J H, ZHOU D R, TANG Y Q, et al. Closing the generalization gap of adaptive gradient methods in training deep neural networks[C]//Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 2020: 3267-3275.
15	TAO Wei, LONG Sheng, WU Gao-wei, et al. The role of momentum parameters in the optimal convergence of adaptive Polyak's heavy-ball methods[EB/OL].(2021-02-15). .
16	REDDI S J, KALE S, KUMAR S. On the convergence of Adam and Beyond[EB/OL].(2019-04-19). .
17	MUKKAMALA M C, HEIN M. Variants of RMSProp and Adagrad with logarithmic regret bounds[C]//Proceedings of the 34th International Conference on Machine Learning. Sydney: ICML, 2017: 2545-2553.
18	DUCHI J, HAZAN E, SINGER Y. Adaptive subgradient methods for online learning and stochastic optimization[J]. Journal of Machine Learning Research, 2011, 12(7): 257-269.
19	CHEN Zai-yi, XU Yi, CHEN En-hong, et al. SADAGRAD: Strongly adaptive stochastic gradient methods[C]//Proceedings of the 35th International Conference on Machine Learning(ICML). Stockholm: ICML, 2018: 912-920.
20	WANG Guang-hui, LU Shi-yin, et al. SAdam: A variant of Adam for strongly convex functions[EB/OL].(2019-05-08). .
21	SHALEV-SHWARTZ S, SINGER Y, SREBRO N, et al. Pegasos: primal estimated sub-gradient solver for SVM[J]. Mathematical Programming, 2011, 127(1): 3-30.
22	沈卉卉, 李宏伟. 基于动量方法的受限玻尔兹曼机的一种有效算法[J]. 电子学报, 2019, 47(1): 176-182.
	SHEN H H, LI H W. An effective algorithm of restricted boltzmann machine based on momentum method[J]. Acta Electronica Sinica, 2019, 47(1): 176-182. (in Chinese)
23	姜纪远, 陶卿, 邵言剑, 等. 随机COMID的瞬时收敛速率分析[J]. 电子学报, 2015, 43(9): 1850-1858.
	JIANG J Y, TAO Q, SHAO Y J, et al. The analysis of convergence rate of individual COMID iterates[J]. Acta Electronica Sinica, 2015, 43(9): 1850-1858. (in Chinese)
24	邹军华, 段晔鑫, 任传伦, 等. 基于噪声初始化、Adam-Nesterov方法和准双曲动量方法的对抗样本生成方法[J]. 电子学报, 2022, 50(1): 207-216.
	ZOU J H, DUAN Y X, REN C L, et al. Perturbation initialization, Adam-Nesterov and quasi-hyperbolic momentum for adversarial examples[J]. Acta Electronica Sinica, 2022, 50(1): 207-216. (in Chinese)
25	罗会兰, 袁璞, 童康. 基于深度学习的显著性目标检测方法综述[J]. 电子学报, 2021, 49(7): 1417-1427.
	LUO H L, YUAN P, TONG K. Review of the methods for salient object detection based on deep learning[J]. Acta Electronica Sinica, 2021, 49(7): 1417-1427. (in Chinese)

[1]	董明, 李敬, 索永录, 唐恩贤, 马宏伟, 陈渊, 张广明, 万翔. 基于改进果蝇优化算法正交匹配追踪的超声信号降噪方法[J]. 电子学报, 2022, 50(2): 493-501.
[2]	邹军华, 段晔鑫, 任传伦, 邱俊洋, 周星宇, 潘志松. 基于噪声初始化、Adam-Nesterov方法和准双曲动量方法的对抗样本生成方法[J]. 电子学报, 2022, 50(1): 207-216.
[3]	孔德阳, 彭华, 马金全. 基于人工鱼群算法的自适应随机共振方法研究[J]. 电子学报, 2017, 45(8): 1864-1872.
[4]	姜纪远, 陶卿, 邵言剑, 汪群山. 随机COMID的瞬时收敛速率分析[J]. 电子学报, 2015, 43(9): 1850-1858.
[5]	刘晓光, 高兴宝. 一种基于GNC和增广拉格朗日对偶的非凸非光滑图像恢复方法[J]. 电子学报, 2014, 42(2): 264-271.
[6]	陶卿, 朱烨雷, 罗强, 孔康. 一种基于Comid的非光滑损失随机坐标下降方法[J]. 电子学报, 2013, 41(4): 768-775.

非光滑强凸情形Adam型算法的最优收敛速率

The Optimal Convergence Rate of Adam-Type Algorithms for Non-Smooth Strongly Convex Cases

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 25

相关文章 6

编辑推荐

Metrics