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

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

Abstract

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

CLC Number:

O221.2
O224

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.

Figures/Tables 4

References 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]	Wenjie LIU, Dongmei ZHANG, Peng ZHANG, Juan ZOU. The seeding algorithm for $\mu$-similar Bregman divergences $k$-means problem with penalties [J]. Operations Research Transactions, 2022, 26(1): 99-112.
[2]	YANG Linxi, LI Guoquan. Sparse proximal support vector machines via DC programming [J]. Operations Research Transactions, 2020, 24(3): 115-126.
[3]	TIAN Yingjie, XU Dongkuan, ZHANG Chunhua. A review of multi-instance learning research [J]. Operations Research Transactions, 2018, 22(2): 1-17.
[4]	SHAO Yuanhai, YANG Kaili, LIU Mingzeng, et al.. From support vector machine to nonparallel support vector machine [J]. Operations Research Transactions, 2018, 22(2): 55-65.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 24

Related Articles 4

Recommended Articles

Metrics

Comments