Accelerated Stochastic Peaceman-Rachford Method for Empirical Risk Minimization

doi:10.1007/s40305-023-00470-8

Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (4): 783-807.doi: 10.1007/s40305-023-00470-8

Previous Articles Next Articles

Accelerated Stochastic Peaceman-Rachford Method for Empirical Risk Minimization

Jian-Chao Bai^1,2, Feng-Miao Bian³, Xiao-Kai Chang⁴, Lin Du⁵

1. Research & Development Institute of Northwestern Polytechnical University in Shenzhen, Shenzhen, 518057, Guangdong, China;
2. School of Mathematics and Statistics, Northwestern Polytechnical University, Xi'an 710129, Shaanxi, China;
3. Department of Mathematics, The Hong Kong University of Science and Technology, Hong Kong, China;
4. School of Science, Lanzhou University of Technology, Lanzhou, 730050, Gansu, China;
5. School of Mathematics and Statistics, the MIIT Key Laboratory of Dynamics and Control of Complex Systems, Northwestern Polytechnical University, Xi'an 710129, Shaanxi, China

Received:2022-06-22 Revised:2022-12-15 Online:2023-12-30 Published:2023-12-26
Contact: Jian-Chao Bai, Feng-Miao Bian, Xiao-Kai Chang, Lin Du E-mail:jianchaobai@nwpu.edu.cn;mafmbian@ust.hk;xkchang@lut.cn;lindu@nwpu.edu.cn
Supported by:
This research was supported by the National Natural Science Foundation of China (Nos. 12001430, 11972292 and 12161053), the China Postdoctoral Science Foundation (No. 2020M683545) and the Guangdong Basic and Applied Basic Research Foundation (No. 2023A1515012405).

Abstract

Abstract: This work is devoted to studying an accelerated stochastic Peaceman-Rachford splitting method (AS-PRSM) for solving a family of structural empirical risk minimization problems. The objective function to be optimized is the sum of a possibly nonsmooth convex function and a finite sum of smooth convex component functions. The smooth subproblem in AS-PRSM is solved by a stochastic gradient method using variance reduction technique and accelerated techniques, while the possibly nonsmooth subproblem is solved by introducing an indefinite proximal term to transform its solution into a proximity operator. By a proper choice for the involved parameters, we show that AS-PRSM converges in a sublinear convergence rate measured by the function value residual and constraint violation in the sense of expectation and ergodic. Preliminary experiments on testing the popular graph-guided fused lasso problem in machine learning and the 3D CT reconstruction problem in medical image processing show that the proposed AS-PRSM is very efficient.

Key words: Empirical risk minimization, Convex optimization, Stochastic Peaceman-Rachford method, Indefinite proximal term, Complexity

CLC Number:

Jian-Chao Bai, Feng-Miao Bian, Xiao-Kai Chang, Lin Du. Accelerated Stochastic Peaceman-Rachford Method for Empirical Risk Minimization[J]. Journal of the Operations Research Society of China, 2023, 11(4): 783-807.

TrendMD

References

[1] Bai, J., Han, D., Sun, H., Zhang, H.: Convergence on a symmetric accelerated stochastic ADMM with larger stepsizes. CSIAM Trans. Appl. Math. 3, 448-479 (2022)
[2] Bai, J., Hager, W., Zhang, H.: An inexact accelerated stochastic ADMM for separable convex optimization. Comput. Optim. Appl. 81, 479-518 (2022)
[3] Bian, F., Liang, J., Zhang, X.: A stochastic alternating direction method of multipliers for non-smooth and non-convex optimization. Inverse Probl. 37, 075009 (2021)
[4] Kim, S., Xing, E.: Statistical estimation of correlated genome associations to a quantitative trait network. PLOS Genet. 5, 1-18 (2009)
[5] Li, H., Liu, N., Ma, X. et al.: ADMM-based weight pruning for real-time deep learning acceleration on mobile devices. In: Proceedings of the 2019 on great lakes symposium on VLSI, pp. 501-506 (2019)
[6] Zhu, Y., Zhang, X.: Stochastic primal dual fixed point method for composite optimization. J. Sci. Comput. 84, 1-25 (2020)
[7] Glowinski, R., Marrocco, A.: Approximation paréléments finis d’rdre un et résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires. Rev. Fr. Autom. Inform. Rech. Opér. Anal. Numér 2, 41-76 (1975)
[8] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3, 1-122 (2010)
[9] Yan, M., Yin, W.: Self equivalence of the alternating direction method of multipliers. In: Glowinski, R., et al. (Ed) Splitting Methods in Communication, Imaging, Science, and Engineering, Scientific Computation, In Chapter 5, 165-194 (2016)
[10] Eckstein, J., Bertsekas, D.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Prog. 55, 293-318 (1992)
[11] Fang, E., He, B., Liu, H., Yuan, X.M.: Generalized alternating direction method of multipliers: new theoretical insights and applications. Math. Prog. Comput. 7, 149-187 (2015)
[12] He, B., Ma, F., Yuan, X.: Convergence study on the symmetric version of ADMM with larger step sizes. SIAM J. Imag. Sci. 9, 1467-1501 (2016)
[13] Bai, J., Li, J., Xu, F., Zhang, H.: Generalized symmetric ADMM for separable convex optimization. Comput. Optim. Appl. 70, 129-170 (2018)
[14] Wu, Z., Li, M.: An LQP-based symmetric alternating direction method of multipliers with larger step sizes. J. Oper. Res. Soc. China 7, 365-383 (2019)
[15] Bai, J., Ma, Y., Sun, H., Zhang, M.: Iteration complexity analysis of a partial LQP-based alternating direction method of multipliers. Appl. Numer. Math. 165, 500-518 (2021)
[16] Adona, V., Goncalves, M.: An inexact version of the symmetric proximal ADMM for solving separable convex optimization. arXiv:2006.02815 (2020)
[17] Gu, Y., Jiang, B., Han, D.: A semi-proximal-based strictly contractive Peaceman-Rachford splitting method. arXiv:1506.02221 (2015)
[18] He, B., Ma, F., Yuan, X.: Optimally linearizing the alternating direction method of multipliers for convex programming. Comput. Optim. Appl. 75, 361-388 (2020)
[19] He, B., Ma, F., Yuan, X.: Optimal proximal augmented Lagrangian method and its application to full Jacobian splitting for multi-block separable convex minimization problems. IMA J. Numer. Anal. 40, 1188-1216 (2020)
[20] Jiang, F., Wu, Z., Cai, X.: Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. J. Ind. Manag. Optim. 13(5), 1-22 (2017)
[21] Peaceman, D., Rachford, H.: The numerical solution of parabolic and elliptic differential equations. J. Soc. Ind. Appl. Math. 3, 28-41 (1955)
[22] Gao, B., Ma, F.: Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization. J. Optim. Theory Appl. 176, 178-204 (2018)
[23] Deng, Z., Liu, S.: Generalized Peaceman-Rachford splitting method with substitution for convex programming. Optim. Lett. 14, 1781-1802 (2020)
[24] Chang, X., Bai, J., Song, D., Liu, S.: Linearized symmetric multi-block ADMM with indefinite proximal regularization and optimal proximal parameter. Calcolo 57, 1-36 (2020)
[25] Chen, J., Wang, Y., He, H., Lv, Y.: Convergence analysis of positive-indefinite proximal ADMM with a Glowinski’s relaxation factor. Numer. Algor. 83, 1415-1440 (2020)
[26] Li, M., Wu, Z.: On the convergence rate of inexact majorized sGS ADMM with indefinite proximal terms for convex composite programming. Asia Pac. J. Oper. Res. 38, 2050035 (2021)
[27] Tao, M.: Convergence study of indefinite proximal ADMM with a relaxation factor. Comput. Optim. Appl. 77, 91-123 (2020)
[28] Gao, H.: Fast parallel algorithms for the X-ray transform an its adjoint. Med. Phys. 39, 7110-7120 (2012)
[29] Huang, F., Chen, S.: Mini-batch stochastic ADMMs for nonconvex nonsmooth optimization. arXiv:1802.03284 (2019)

Accelerated Stochastic Peaceman-Rachford Method for Empirical Risk Minimization

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Xin-Xin Li, Xiao-Ya Zhang. A New Stopping Criterion for Eckstein and Bertsekas’s Generalized Alternating Direction Method of Multipliers [J]. Journal of the Operations Research Society of China, 2023, 11(4): 941-955.
[2]	Ru-Jun Jiang, Zhi-Shuo Zhou, Zi-Rui Zhou. Cubic Regularization Methods with Second-Order Complexity Guarantee Based on a New Subproblem Reformulation [J]. Journal of the Operations Research Society of China, 2022, 10(3): 471-506.
[3]	De-Ren Han. A Survey on Some Recent Developments of Alternating Direction Method of Multipliers [J]. Journal of the Operations Research Society of China, 2022, 10(1): 1-52.
[4]	Julien Collonge. Necessary Optimality Conditions for Semi-vectorial Bi-level Optimization with Convex Lower Level: Theoretical Results and Applications to the Quadratic Case [J]. Journal of the Operations Research Society of China, 2021, 9(3): 691-712.
[5]	Huynh Duc Quoc, Nguyen Chi Tam, Tran Hoai Ngoc Nhan. The Continuous Knapsack Problem with Capacities [J]. Journal of the Operations Research Society of China, 2021, 9(3): 713-721.
[6]	Esmaeil Afrashteh, Behrooz Alizadeh, Fahimeh Baroughi. Optimal Algorithms for Integer Inverse Undesirable p-Median Location Problems on Weighted Extended Star Networks [J]. Journal of the Operations Research Society of China, 2021, 9(1): 99-117.
[7]	Ruo-Yu Sun. Optimization for Deep Learning: An Overview [J]. Journal of the Operations Research Society of China, 2020, 8(2): 249-294.
[8]	Yan Li, Sheng-Long Hu, Jie Wang, Zheng-Hai Huang. An Introduction to the Computational Complexity of Matrix Multiplication [J]. Journal of the Operations Research Society of China, 2020, 8(1): 29-43.
[9]	Mohammad Pirhaji, Maryam Zangiabadi, Hossien Mansouri, Ali Nakhaei, Ali Shojaeifard. A Wide Neighborhood Interior-Point Algorithm for Convex Quadratic Semidefinite Optimization [J]. Journal of the Operations Research Society of China, 2020, 8(1): 145-164.
[10]	Xiang Gao, Yang-Yang Xu, Shu-Zhong Zhang. Randomized Primal–Dual Proximal Block Coordinate Updates [J]. Journal of the Operations Research Society of China, 2019, 7(2): 205-250.
[11]	Zhong-Ming Wu, Min Li. An LQP-Based Symmetric Alternating Direction Method of Multipliers with Larger Step Sizes [J]. Journal of the Operations Research Society of China, 2019, 7(2): 365-383.
[12]	Qi Qi, Wen-Wei Wang, Ling-Fei Yu. Competitive and Collaborative Influence in Social Networks [J]. Journal of the Operations Research Society of China, 2019, 7(1): 169-182.
[13]	Mohammad Pirhaji,Hossein Mansouri,Maryam Zangiabadi. A Wide-Neighborhood Predictor-Corrector Interior-Point Algorithm for Linear Complementarity Problems [J]. Journal of the Operations Research Society of China, 2018, 6(4): 529-544.
[14]	Jian-Chao Huang, Jin-Yan Fan. Global Complexity Bound of the Inexact Levenberg–Marquardt Method [J]. Journal of the Operations Research Society of China, 2018, 6(3): 417-428.
[15]	Yurii Nesterov, Vladimir Shikhman. Computation of Fisher–Gale Equilibrium by Auction [J]. Journal of the Operations Research Society of China, 2018, 6(3): 349-390.