Journal of the Operations Research Society of China >

2023 , Vol. 11 >Issue 4: 783 - 807

DOI: https://doi.org/10.1007/s40305-023-00470-8

Accelerated Stochastic Peaceman-Rachford Method for Empirical Risk Minimization

Expand
  • 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 date: 2022-06-22

  Revised date: 2022-12-15

  Online published: 2023-12-26

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).

Fold

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

Cite this article

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 . DOI: 10.1007/s40305-023-00470-8

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)
Options
Outlines

/

〈 〉

Copyright © Operations Research Society of China, The Periodicals Agency of Shanghai University , and Springer-Verlag Berlin Heidelberg 2016