随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用

doi:10.15960/j.cnki.issn.1007-6093.2022.02.002

运筹学学报 ›› 2022, Vol. 26 ›› Issue (2): 16-30.doi: 10.15960/j.cnki.issn.1007-6093.2022.02.002

随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用

吕袈豪¹, 罗洪林¹^,*(), 杨泽华², 彭建文¹

1. 重庆师范大学数学科学学院，重庆 401331
2. 重庆师范大学计算机与信息科学学院，重庆 401331

收稿日期:2021-03-08 出版日期:2022-06-15 发布日期:2022-05-27
通讯作者: 罗洪林 E-mail:luohonglin@cqnu.edu.cn
作者简介:罗洪林 E-mail: luohonglin@cqnu.edu.cn
基金资助:
国家自然科学基金(11991024);国家自然科学基金(11771064);重庆市高校创新研究群体项目(CXQT20014);重庆市创新领军人才项目团队(CQYC20210309536);重庆市科技局(cstc2021jcyj-msx300)

A stochastic Bregman ADMM with its application in training sparse structure SVMs

Jiahao LYU¹, Honglin LUO¹^,*(), Zehua YANG², Jianwen PENG¹

1. School of Mathematical Sciences, Chongqing Normal University, Chongqing 401331, China
2. School of Computer and Information Science, Chongqing Normal University, Chongqing 401331, China

Received:2021-03-08 Online:2022-06-15 Published:2022-05-27
Contact: Honglin LUO E-mail:luohonglin@cqnu.edu.cn

摘要/Abstract

摘要：

针对具有多块可分结构的非凸优化问题提出了一类新的随机Bregman交替方向乘子法，在周期更新规则下, 证明了该算法的渐进收敛性; 在随机更新的规则下, 几乎确定的渐进收敛性得以证明。数值实验结果表明, 该算法可有效训练具有离散结构的支持向量机。

关键词: 多块可分离的非凸优化问题, Bregman度量, 随机交替方向乘子法, 渐进收敛性, 支持向量机

Abstract:

A new stochastic Bregman multiplier alternating direction method (S-B-ADMM) is proposed for non-convex optimization problems with multiple separable blocks. It is shown that the sequence produced by the S-B-ADMM under the periodic update rule converges asymptotically to a stationary solution of the Lagrangian function of the original problem. Under the random update rule, we prove the almost surely convergence of the sequence produced by the S-B-ADMM. Numerical experiments results illustrate the feasibility of the S-B-ADMM for training sparse structural support vector machines.

Key words: non-convex optimization problems with multiple separable blocks, Bregman divergence, stochastic ADMM, asymptotic convergence, support vector machine

中图分类号:

O221.2
O224

吕袈豪, 罗洪林, 杨泽华, 彭建文. 随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用[J]. 运筹学学报, 2022, 26(2): 16-30.

Jiahao LYU, Honglin LUO, Zehua YANG, Jianwen PENG. A stochastic Bregman ADMM with its application in training sparse structure SVMs[J]. Operations Research Transactions, 2022, 26(2): 16-30.

图/表 4

参考文献 24

1	Glowinski R , Marroco A . Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires[J]. Journal of Equine Veterinary Science, 1975, 2 (2): 41- 76.
2	Gabay D , Mercier B . A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J]. Computers and Mathematics with Applications, 1976, 2 (1): 17- 40. doi: 10.1016/0898-1221(76)90003-1
3	Dhar S, Yi C, Ramakrishnan N, et al. ADMM based scalable machine learning on spark[C]//IEEE International Conference on Big Data, 2015: 1174-1182.
4	Huebner N, Rink Y, Suriyah M, et al. Distributed AC-DC optimal power flow in the european transmission grid with ADMM[C]//The 55th International Universities Power Engineering Conference (UPEC), 2020: 1-6.
5	Schizas I , Ribeiro A , Giannakis G . Consensus in ad hoc WSNS with noisy links-parti: Distributed estimation of deterministic signals[J]. IEEE Journal of Selected Topics in Signal Processing, 2008, 56 (3): 350- 364.
6	Yang Q , Chen G , Wang T . ADMM-based distributed algorithm for economic dispatch in power systems with both packet drops and communication delays[J]. IEEE/CAA Journal of Automatica Sinica, 2020, 7 (3): 842- 852. doi: 10.1109/JAS.2020.1003156
7	何炳生. 凸优化和单调变分不等式收缩算法的统一框架[J]. 中国科学, 2018, 48 (02): 4- 21.
8	Yang L , Pong T K , Chen X . An alternating direction method of multipliers for nonconvex background/foreground extraction[J]. Frontiers of Mathematics in China, 2012, 4 (2): 1- 22.
9	Xu Y , Yin W , Wen Z , et al. An alternating direction algorithm for matrix completion with nonnegative factors[J]. Frontiers of Mathematics in China, 2012, 7 (2): 365- 384. doi: 10.1007/s11464-012-0194-5
10	Forero P A , Cano A , Giannakis G B . Distributed clustering using wireless sensor networks[J]. IEEE Journal of Selected Topics in Signal Processing, 2011, 5 (4): 707- 724. doi: 10.1109/JSTSP.2011.2114324
11	Liavas A P , Sidiropoulos N D . Parallel algorithms for constrained tensor factorization via the alternating direction method of multipliers[J]. IEEE Transactions on Signal Processing, 2014, 63 (20): 50- 63.
12	Wen Z , Yang C , Liu X , et al. Alternating direction methods for classical and ptychographic phase retrieval[J]. Inverse Problems, 2012, 28 (11): 115- 132.
13	Xu Y , Yin W , Wen Z , et al. An alternating direction algorithm for matrix completion with nonnegative factors[J]. Frontiers of Mathematics in China, 2012, 7 (2): 365- 384. doi: 10.1007/s11464-012-0194-5
14	Hong M , Luo Z Q , Razaviyayn M . Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems[J]. SIAM Journal on Optimization, 2014, 26 (1): 3836- 3840.
15	Liu M , Jian J . An ADMM-based SQP method for separably smooth nonconvex optimization[J]. Journal of Inequalities and Applications, 2020, 12 (1): 2- 17.
16	Themelis A , Patrinos P . Douglas-Rachford splitting and ADMM for nonconvex optimization: Tight convergence results[J]. SIAM Journal on Optimization, 2020, 30 (1): 149- 181. doi: 10.1137/18M1163993
17	Bai J , Li J , Xu F , et al. Generalized symmetric ADMM for separable convex optimization[J]. Computational Optimization and Applications, 2017, 70 (1): 129- 170.
18	张艳娜, 申远, 孙黎明. 求解结构型优化问题的随机步长ADMM下降算法[J]. 工程数学学报, 2019, 36 (002): 123- 137.
19	Chao M , Deng Z , Jian J . Convergence of Linear Bregman ADMM for Nonconvex and Nonsmooth Problems with Nonseparable Structure[J]. Complexity, 2020, 26 (02): 1- 14.
20	Wang F , Cao W , Xu Z B . Convergence of multi-block Bregman ADMM for nonconvex composite problems[J]. Science China Information Sciences, 2018, 61 (12): 122- 148.
21	Bertsekas D P , Tsitsiklis J N . Neuro-Dynamic Programming[M]. BelBmont: Athena Scientific, 1996.
22	Tsochantaridis I , Joachims T , Hofmann T , et al. Large margin methods for structured and interdependent output variables[J]. Journal of Machine Learning Research, 2006, 6 (2): 1453- 1484.
23	Balamurugan P, Posinasetty A, Shevade S. ADMM for training sparse structural SVMs with augmented l₁ regularizers[C]//SIAM International Conference on Data Mining, 2016: 684-692.
24	Jiang B , Lin T , Ma S , et al. Structured nonconvex and nonsmooth optimization: Algorithms and iteration complexity analysis[J]. Computational Optimization and Applications, 2019, 72, 115- 157. doi: 10.1007/s10589-018-0034-y

训练集	n	n_test	c	m
iris	150	362	3	3 672
Forest Fires	517	120	13	83 643
Student Performance	649	5 350	33	4 744
self Back	26 136	4 353	6	1 802 434

训练集	算法	%NZF	T-A	Time/s
iris	ADMM	0.81	81.3	9.25
	S-B-ADMM	0.77	83.2	11.63
Forest Fires	ADMM	0.96	92.4	4.91
	S-B-ADMM	1.2	91.6	8.31
StudentPerformance	ADMM	12.4	77.2	15.42
	S-B-ADMM	17.8	79.8	18.73
selfBack	ADMM	0.064	94.5	976.3
	S-B-ADMM	0.022	94.8	1 224.7

概率	%NZF	T-A	Time/s
0.1	0.022	94.2	2 545
0.5	0.022	94.8	1 225
0.9	0.024	95.1	1 004
1.0	0.023	94.6	988

Φ(x)	%NZF	T-A	Time/s
\|\|x\|\|²	0.022	94.8	1225
x^TAx	0.027	92.5	1352

[1]	杨琳希, 李国权. 基于DC规划方法的稀疏临近支持向量机[J]. 运筹学学报, 2020, 24(3): 115-126.
[2]	田英杰, 胥栋宽, 张春华. 多示例学习问题研究进展综述[J]. 运筹学学报, 2018, 22(2): 1-17.
[3]	邵元海, 杨凯丽, 刘明增, 等. 从支持向量机到非平行支持向量机[J]. 运筹学学报, 2018, 22(2): 55-65.

随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用

A stochastic Bregman ADMM with its application in training sparse structure SVMs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 24

相关文章 3

编辑推荐

Metrics

本文评价