Top

Journal of Scientific Computing

Published in:

01-07-2020

Stochastic Primal Dual Fixed Point Method for Composite Optimization

Authors: Ya-Nan Zhu, Xiaoqun Zhang

Published in: Journal of Scientific Computing | Issue 1/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper we propose a stochastic primal dual fixed point method for solving the sum of two proper lower semi-continuous convex function and one of which is composite. The method is based on the primal dual fixed point method proposed in Chen et al. (Inverse Probl 29:025011, 2013) that does not require subproblem solving. Under some mild condition, the convergence is established based on two sets of assumptions: bounded and unbounded gradients and the convergence rate of the expected error of iterate is of the order \({\mathcal {O}}(k^{-\alpha })\) where k is iteration number and \(\alpha \in (0,1]\). Finally, numerical examples on graphic Lasso and logistic regressions are given to demonstrate the effectiveness of the proposed algorithm.

previous article Accurate Numerical Solution for Shifted M-Matrix Algebraic Riccati Equations

next article Relaxation Runge–Kutta Methods for Hamiltonian Problems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

http://www.cs.nyu.edu/~roweis/data.html.

Chen, P., Huang, J., Zhang, X.: A primal–dual fixed point algorithm for convex separable minimization with applications to image restoration. Inverse Probl. 29, 025011 (2013)MathSciNetCrossRef

Tibshirani, R.J.: The Solution Path of the Generalized Lasso. Stanford University, Stanford (2011)CrossRef

Vapnik, V.: The Nature of Statistical Learning Theory. Springer Science & Business Media (2003)

Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward–backward splitting. Multiscale Model. Simul. 4, 1168–1200 (2005)MathSciNetCrossRef

Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009)MathSciNetCrossRef

Nesterov, Y.E.: A method for solving the convex programming problem with convergence rate o (\(1/\text{k}^{2}\)). In: Doklady Akademii Nauk SSSR, vol. 269, pp. 543–547 (1983)

Güler, O.: New proximal point algorithms for convex minimization. SIAM J. Optim. 2, 649–664 (1992)MathSciNetCrossRef

Rosasco, L., Villa, S., Vũ, B.: Convergence of stochastic proximal gradient algorithm (2014). arXiv preprint arXiv:1403.5074

Duchi, J., Singer, Y.: Efficient online and batch learning using forward backward splitting. J. Mach. Learn. Res. 10, 2899–2934 (2009)MathSciNetMATH

10.

Shalev-Shwartz, S., Zhang, T.: Proximal stochastic dual coordinate ascent (2012). arXiv preprint arXiv:1211.2717

11.

Shalev-Shwartz, S., Zhang, T.: Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization. In: International Conference on Machine Learning, pp. 64–72 (2014)

12.

Xiao, L., Zhang, T.: A proximal stochastic gradient method with progressive variance reduction. SIAM J. Optim. 24, 2057–2075 (2014)MathSciNetCrossRef

13.

Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55, 293–318 (1992)MathSciNetCrossRef

14.

Setzer, S.: Split Bregman algorithm, Douglas–Rachford splitting and frame shrinkage. In: International Conference on Scale Space and Variational Methods in Computer Vision, pp. 464–476. Springer (2009)

15.

He, B., Yuan, X.: On the o(1/n) convergence rate of the Douglas–Rachford alternating direction method. SIAM J. Numer. Anal. 50, 700–709 (2012)MathSciNetCrossRef

16.

Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66, 889–916 (2016)MathSciNetCrossRef

17.

Zhu, M., Chan, T.F.: An Efficient Primal–Dual Hybrid Gradient Algorithm for Total Variation Image Restoration, CAM Report 08–34. UCLA, Los Angeles, CA (2008)

18.

Esser, E., Zhang, X., Chan, T.F.: A General Frame Work for a Class of First Order Primal Dual Algorithms for Convex Optimization in Imaging Science, CAM Report 08–34. UCLA, Los Angeles, CA (2008)

19.

Chambolle, A., Pock, T.: A first-order primal–dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120145 (2011)MathSciNetCrossRef

20.

Micchelli, C.A., Shen, L., Yuesheng, X.: Proximity algorithms for image models: denoising. Inverse Probl. 27, 045009 (2011)MathSciNetCrossRef

21.

Ouyang, H., He, N., Tran, L., Gray, A.: Stochastic alternating direction method of multipliers. In: International Conference on Machine Learning, pp. 80–88 (2013)

22.

Xiao, L.: Dual averaging methods for regularized stochastic learning and online optimization. J. Mach. Learn. Res. 11, 2543–2596 (2010)MathSciNetMATH

23.

Duchi, J., Singer, Y.: Efficient online and batch learning using forward backward splitting. J. Mach. Learn. Res. 10, 2873–2908 (2009)MathSciNetMATH

24.

Suzuki, T.: Dual averaging and proximal gradient descent for online alternating direction multiplier method. In: International Conference on Machine Learning, pp. 392–400 (2013)

25.

Zhong, W., Kwok, J.: Fast stochastic alternating direction method of multipliers. In: International Conference on Machine Learning, pp. 46–54 (2014)

26.

Le Roux, N., Schmidt, M., Bach, F.R: A stochastic gradient method with an exponential convergence rate for finite training sets. In: Advances in Neural Information Processing Systems, pp. 2672–2680 (2012)

27.

Zhao, S.-Y., Li, W.-J., Zhou, Z.-H.: Scalable stochastic alternating direction method of multipliers (2015). arXiv preprint arXiv:1502.03529

28.

Suzuki, T.: Stochastic dual coordinate ascent with alternating direction method of multipliers. In: International Conference on Machine Learning, pp. 736–744 (2014)

29.

Zheng, S., Kwok, J.T.: Fast-and-light stochastic ADMM. In: IJCAI, pp. 2407–2613 (2016)

30.

Chambolle, A., Ehrhardt, M.J., Richtarik, P., Schonlieb, C.-B.: Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications. SIAM J. Optimiz. 28(4), 2783–2808 (2018)MathSciNetCrossRef

31.

Chen, Y., Lan, G., Ouyang, Y.: Optimal primal–dual methods for a class of saddle point problems. SIAM J. Optim. 24(4), 1779–1814 (2014)MathSciNetCrossRef

32.

Moulines, E., Bach, F.R: Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In: Advances in Neural Information Processing Systems, pp. 451–459 (2011)

33.

Polyak, B.T.: Introduction to Optimization, vol. 1. Optimization Software, Inc., Publications Division, New York (1987)MATH

34.

Kim, S., Sohn, K.-A., Xing, E.P.: A multivariate regression approach to association analysis of a quantitative trait network. Bioinformatics 25(12), i204–i212 (2009)CrossRef

35.

Chang, C.-C., Lin, C.-J.: LIBSVM: a library for support vector machines. ACM Trans. Intell. Syst. Technol. 2, 27:1–27:27 (2011)CrossRef

36.

Banerjee, O., El Ghaoui, L., dAspremont, A.: Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data. J. Mach. Learn. Res. 9, 485–516 (2008)MathSciNetMATH

37.

Friedman, J., Hastie, T., Tibshirani, R.: Sparse inverse covariance estimation with the graphical lasso. Biostatistics 9, 432–441 (2008)CrossRef

Title: Stochastic Primal Dual Fixed Point Method for Composite Optimization
Authors: Ya-Nan Zhu
Xiaoqun Zhang
Publication date: 01-07-2020
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 1/2020
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-020-01265-2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2020

Barrier Function Local and Global Analysis of an L1 Finite Element Method for a Multiterm Time-Fractional Initial-Boundary Value Problem

Numerical Approximation for Fractional Diffusion Equation Forced by a Tempered Fractional Gaussian Noise

Convergence and Error Estimates for a Finite Difference Scheme for the Multi-dimensional Compressible Navier–Stokes System

Finite Element Methods Based on Two Families of Second-Order Numerical Formulas for the Fractional Cable Model with Smooth Solutions

Two-Level Schwarz Methods for a Discontinuous Galerkin Approximation of Elliptic Problems with Jump Coefficients

Asymptotic Analysis for Overlap in Waveform Relaxation Methods for RC Type Circuits

Premium Partner