×

zbMATH — the first resource for mathematics

A coordinate-descent primal-dual algorithm with large step size and possibly nonseparable functions. (English) Zbl 1411.90265

MSC:
90C25 Convex programming
49M25 Discrete approximations in optimal control
90C06 Large-scale problems in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] H. H. Bauschke, J. M. Borwein, and P. L. Combettes, Bregman monotone optimization algorithms, SIAM J. Control Optim, 42 (2003), pp. 596–636. · Zbl 1049.90053
[2] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183–202. · Zbl 1175.94009
[3] A. Beck and L. Tetruashvili, On the convergence of block coordinate descent type methods, SIAM J. Optim., 23 (2013), pp. 2037–2060. · Zbl 1297.90113
[4] D. P. Bertsekas, Incremental proximal methods for large scale convex optimization, Math. Program., 129 (2011), pp. 163–195. · Zbl 1229.90121
[5] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, Englewood Cliffs, NJ, 1989.
[6] P. Bianchi and O. Fercoq, Using big steps in coordinate descent primal-dual algorithms, in Proceedings of 2016 IEEE 55th Conference on Decision and Control, Las Vegas, NV, IEEE Press, Piscataway, NJ, 2016, pp. 1895–1899.
[7] P. Bianchi, W. Hachem, and F. Iutzeler, A Stochastic Coordinate Descent Primal-Dual Algorithm and Applications to Large-Scale Composite Optimization, preprint, , 2014. · Zbl 1359.90090
[8] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends. Mach. Learn., 3 (2011), pp. 1–122. · Zbl 1229.90122
[9] V. Cevher, S. Becker, and M. Schmidt, Convex optimization for big data: Scalable, randomized, and parallel algorithms for big data analytics, IEEE Signal Process. Mag., 31 (2014), pp. 32–43.
[10] A. Chambolle, V. Caselles, D. Cremers, M. Novaga, and T. Pock, An introduction to total variation for image analysis, in Theoretical Foundations and Numerical Methods for Sparse Recovery, Radon Series on Comput. Appl. Math. 9, 2010, Walter De Gruyter, Berlin, pp. 263–340. · Zbl 1209.94004
[11] A. Chambolle and C. Dossal, On the Convergence of the Iterates of the “Fast Iterative Shrinkage/Thresholding Algorithm,” J. Optim. Theory Appl, 166 (2015), pp. 968–982. · Zbl 1371.65047
[12] A. Chambolle, M. J. Ehrhardt, P. Richtárik, and C.-B. Schönlieb, Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Application, preprint, , 2017.
[13] A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40 (2011), pp. 120–145. · Zbl 1255.68217
[14] A. Chambolle and T. Pock, On the ergodic convergence rates of a first-order primal–dual algorithm, Math. Program., 159 (2016), pp. 253–287. · Zbl 1350.49035
[15] C.-C. Chang and C.-J. Lin, LIBSVM: A library for support vector machines, ACM Trans. Intell. Syst. Technol., 2 (2011), 27.
[16] P. L. Combettes and J.-C. Pesquet, Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping, SIAM J. Optim., 25 (2015), pp. 1221–1248. · Zbl 1317.65135
[17] L. Condat, A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optim. Theory Appl., 158 (2013), pp. 460–479. · Zbl 1272.90110
[18] D. Davis and W. Yin, A Three-Operator Splitting Scheme and Its Optimization Applications, preprint, , 2015. · Zbl 06834688
[19] D. Davis and W. Yin, Faster convergence rates of relaxed Peaceman–Rachford and ADMM under regularity assumptions, Math. Oper. Res., 42 (2017), pp. 783–805. · Zbl 1379.65035
[20] E. Dohmatob, A. Gramfort, B. Thirion, and G. Varoquaux, Benchmarking solvers for TV-\(ℓ_1\) least-squares and logistic regression in brain imaging, in Proceedings of the 2014 International Workshop on Pattern Recognition in Neuroimaging, IEEE Press, Piscataway, NJ, 2014, DOI: 10.1109/PRNI.2014.6858516.
[21] O. Fercoq and P. Richtárik, Accelerated, parallel and proximal coordinate descent, SIAM J. Optim., 25 (2015), pp. 1997–2023. · Zbl 1327.65108
[22] J. Friedman, T. Hastie, H. Höfling, and R. Tibshirani, Pathwise coordinate optimization, Ann. Appl. Stat., 1 (2007), pp. 302–332. · Zbl 1378.90064
[23] D. Gabay, Applications of the method of multipliers to variational inequalities, in Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, Stud. Math. Applic. 15, M. Fortin and R. Glowinski, eds., Elsevier, New York, 1983, pp. 299–331.
[24] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2 (1976), pp. 17–40. · Zbl 0352.65034
[25] X. Gao, Y. Xu, and S. Zhang, Randomized Primal-Dual Proximal Block Coordinate Updates, preprint, , 2016.
[26] X. Gao and S.-Z. Zhang, First-order algorithms for convex optimization with nonseparable objective and coupled constraints, J. Oper. Res. Soc. China, 5 (2017), pp. 131–159. · Zbl 1390.90423
[27] R. Glowinski and A. Marroco, 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,RAIRO Analyse Numérique, 9 (1975), pp. 41–76. · Zbl 0368.65053
[28] I. Guyon, V. Lemaire, M. Boullé, G. Dror, and D. Vogel, Analysis of the KDD Cup \(2009\): Fast scoring on a large Orange customer database, Proc. Mach. Learn. Res. 7, pp. 1–22; available at .
[29] B. He and X. Yuan, Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective, SIAM J. Imaging Sci., 5 (2012), pp. 119–149. · Zbl 1250.90066
[30] M. Hong, X. Wang, M. Razaviyayn, and Z.-Q. Luo, Iteration complexity analysis of block coordinate descent methods, Math. Program., 163 (2017), pp. 85–114. · Zbl 1367.49010
[31] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 2012.
[32] F. Iutzeler, P. Bianchi, P. Ciblat, and W. Hachem, Asynchronous distributed optimization using a randomized alternating direction method of multipliers, in Proceedings of IEEE 52nd Annual Conference on Decision and Control, IEEE Press, Piscataway, NJ, 2013, pp. 3671–3676.
[33] D. D. Lewis, Y. Yang, T. G. Rose, and F. Li, RCV1: A new benchmark collection for text categorization research, J. Mach. Learn. Res., 5 (2004), pp. 361–397.
[34] Q. Lin, Z. Lu, and L. Xiao, An accelerated proximal coordinate gradient method, in Adv. Neural Inf. Process. Syst. 27, Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, eds., Curran Associates, Red Hook, NY, 2014, pp. 3059–3067.
[35] Z. Q. Luo and P. Tseng, On the convergence of the coordinate descent method for convex differentiable minimization, J. Optim. Theory Appl., 72 (1992), pp. 7–35. · Zbl 0795.90069
[36] J. Mairal, Incremental majorization-minimization optimization with application to large-scale machine learning, SIAM J. Optim., 25 (2015), pp. 829–855. · Zbl 1320.90047
[37] I. Necoara and A. Patrascu, A Random Coordinate Descent Algorithm for Optimization Problems with Composite Objective Function and Linear Coupled Constraints, Technical report, Politehnica University of Bucharest, 2012. · Zbl 1304.90160
[38] Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 22 (2012), pp. 341–362. · Zbl 1257.90073
[39] Y. Nesterov, Subgradient methods for huge-scale optimization problems, Math. Program., 146 (2014), pp. 275–297. · Zbl 1297.90120
[40] J.-C. Pesquet and A. Repetti, A class of randomized primal-dual algorithms for distributed optimization, J. Nonlinear Convex Anal., 16 (2015), pp. 2453–2490. · Zbl 1336.65113
[41] P. Richtárik and M. Takáč, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function, Math. Program., 144 (2014), pp. 1–38. · Zbl 1301.65051
[42] P. Richtárik and M. Takáč, Parallel coordinate descent methods for big data optimization, Math. Program., 156 (2016), pp. 433–484.
[43] P. Richtárik and M. Takáč, Efficient Serial and Parallel Coordinate Descent Method for Huge-Scale Truss Topology Design, Oper. Res. Proc. 2011, Springer, 2012, pp. 27–32.
[44] H. Robbins and D. Siegmund, A convergence theorem for non negative almost supermartingales and some applications, in Optimizing Methods in Statistics, Academic Press, New York, 1971, pp. 233–257.
[45] S. Shalev-Shwartz and T. Zhang, Stochastic dual coordinate ascent methods for regularized loss minimization, J. Mach. Learn. Res., 14 (2013), pp. 567–599. · Zbl 1307.68073
[46] T. Suzuki, Stochastic dual coordinate ascent with alternating direction method of multipliers, Proc. Mach. Learn. Res. 32, 2014, pp. 736–744; available at .
[47] Q. Tran-Dinh and V. Cevher, A Primal-Dual Algorithmic Framework for Constrained Convex Minimization, preprint, , 2014.
[48] Q. Tran-Dinh, O. Fercoq, and V. Cevher, A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization, preprint, , 2016. · Zbl 1386.90109
[49] P. Tseng, On accelerated proximal gradient methods for convex-concave optimization, SIAM J. Optim., submitted.
[50] P. Tseng and C. O. L. Mangasarian, Convergence of a block coordinate descent method for nondifferentiable minimization, J. Optim. Theory Appl., (2001), pp. 475–494. · Zbl 1006.65062
[51] P. Tseng and S. Yun, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program., 117 (2009), pp. 387–423. · Zbl 1166.90016
[52] P. Tseng and S. Yun, A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training, Comput. Optim. Appl., 47 (2010), pp. 179–206. · Zbl 1226.90062
[53] B. C. Vu͂, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Adv. Comput. Math., 38 (2013), pp. 667–681. · Zbl 1284.47045
[54] J. Warga, Minimizing certain convex functions, J. Soc. Indust. Appl. Math., 11 (1963), pp. 588–593. · Zbl 0128.05801
[55] Y. Zhang and L. Xiao, Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization, preprint, , 2014.
[56] C. Zhu, R. H. Byrd, P. Lu, and J. Nocedal, Algorithm 778: L-BFGS-B: FORTRAN subroutines for large-scale bound-constrained optimization, ACM Trans. Math. Software, 23 (1997), pp. 550–560. · Zbl 0912.65057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.