×

Cyclic coordinate-update algorithms for fixed-point problems: analysis and applications. (English) Zbl 1368.90104

Summary: Many problems reduce to the fixed-point problem of solving \(x=T(x)\), where \(T\) is a mapping from a Hilbert space to itself. To this problem we apply the coordinate-update algorithms, which update only one or a few components of \(x\) at each step. When each step is cheap, these algorithms are faster than the full fixed-point iteration (which updates all the components). In this paper, we focus on cyclic coordinate selection rules, where the ordering of coordinates in each cycle is arbitrary. The corresponding algorithms are fast, but their convergence is unknown in the fixed-point setting. When \(T\) is a nonexpansive operator and has a fixed point, we show that the sequence of coordinate-update iterates converges to a fixed point under proper step sizes. This result applies to the primal-dual coordinate-update algorithms, which have wide applications to optimization problems with nonseparable nonsmooth objectives, and/or global linear constraints. Numerically, we apply coordinate-update algorithms with cyclic, shuffled cyclic, and random selection rules to \(\ell_1\)-robust least squares, total variation minimization, and nonnegative matrix factorization. These algorithms converge much faster than the standard fixed-point iteration. Among the three rules, cyclic and shuffled cyclic rules are overall faster than the random rule.

MSC:

90C06 Large-scale problems in mathematical programming
90C25 Convex programming
65K05 Numerical mathematical programming methods

Software:

TVAL3; glmnet; NeNMF; ARock
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] H. H. Bauschke and P. L. Combettes, {\it Convex Analysis and Monotone Operator Theory in Hilbert Spaces}, CMS Books in Math., Springer, New York, 2011. · Zbl 1218.47001
[2] A. Beck and L. Tetruashvili, {\it On the convergence of block coordinate descent type methods}, SIAM J. Optim., 23 (2013), pp. 2037-2060, . · Zbl 1297.90113
[3] D. P. Bertsekas, {\it Distributed asynchronous computation of fixed points}, Math. Programming, 27 (1983), pp. 107-120. · Zbl 0521.90089
[4] D. P. Bertsekas and J. N. Tsitsiklis, {\it Parallel and Distributed Computation: Numerical Methods}, Prentice Hall, Englewood Cliffs, NJ, 1989. · Zbl 0743.65107
[5] A. Chambolle and T. Pock, {\it 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
[6] C. Chen, M. Li, X. Liu, and Y. Ye, {\it Extended ADMM and BCD for Nonseparable Convex Minimization Models with Quadratic Coupling Terms: Convergence Analysis and Insights}, preprint, , 2015. · Zbl 1415.90079
[7] E. C. Chi and T. G. Kolda, {\it On tensors, sparsity, and nonnegative factorizations}, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 1272-1299, . · Zbl 1262.15029
[8] P. L. Combettes, L. Condat, J.-C. Pesquet, and B. C. Vu, {\it A forward-backward view of some primal-dual optimization methods in image recovery}, in Proceedings of the 2014 IEEE International Conference on Image Processing (ICIP), IEEE Press, Piscataway, NJ, 2014, pp. 4141-4145.
[9] P. L. Combettes and J.-C. Pesquet, {\it Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping}, SIAM J. Optim., 25 (2015), pp. 1221-1248, . · Zbl 1317.65135
[10] L. Condat, {\it 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
[11] A. P. Da Costa and A. Seeger, {\it Cone-constrained eigenvalue problems: Theory and algorithms}, Comput. Optim. Appl., 45 (2010), pp. 25-57. · Zbl 1193.65039
[12] M. E. Daube-Witherspoon and G. Muehllehner, {\it An iterative image space reconstruction algorithm suitable for volume ECT}, IEEE Trans. Medical Imaging, 5 (1986), pp. 61-66.
[13] D. Davis and W. Yin, {\it A Three-Operator Splitting Scheme and Its Optimization Applications}, UCLA CAM Report 15-13, 2015. · Zbl 1464.47041
[14] D. Davis and W. Yin, {\it Convergence rate analysis of several splitting schemes}, in Splitting Methods in Communication, Imaging, Science, and Engineering, R. Glowinski, S. Osher, and W. Yin, eds., Springer International Publishing, Switzerland, 2016, pp. 115-163. · Zbl 1372.65168
[15] O. Fercoq and P. Bianchi, {\it A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions}, preprint, , 2015. · Zbl 1411.90265
[16] J. Friedman, T. Hastie, H. Höfling, and R. Tibshirani, {\it Pathwise coordinate optimization}, Ann. Appl. Stat., 1 (2007), pp. 302-332. · Zbl 1378.90064
[17] J. Friedman, T. Hastie, and R. Tibshirani, {\it Regularization paths for generalized linear models via coordinate descent}, J. Stat. Software, 33 (2010), pp. 1-22.
[18] D. Gabay and B. Mercier, {\it 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
[19] N. Gillis, {\it The why and how of nonnegative matrix factorization}, in Regularization, Optimization, Kernels, and Support Vector Machines, Chapman and Hall/CRC, Boca Raton, FL, 2014, pp. 257-291.
[20] R. Glowinski and A. Marroco, {\it 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}, ESAIM Math. Model. Numer. Anal., 9 (1975), pp. 41-76. · Zbl 0368.65053
[21] N. Guan, D. Tao, Z. Luo, and B. Yuan, {\it Nenmf: An optimal gradient method for nonnegative matrix factorization}, IEEE Trans. Signal Process., 60 (2012), pp. 2882-2898. · Zbl 1391.65115
[22] J. Han, L. Han, M. Neumann, and U. Prasad, {\it On the rate of convergence of the image space reconstruction algorithm}, Operators and Matrices, 3 (2009), pp. 41-58. · Zbl 1179.65044
[23] M. Hanke, A. Neubauer, and O. Scherzer, {\it A convergence analysis of the Landweber iteration for nonlinear ill-posed problems}, Numer. Math., 72 (1995), pp. 21-37. · Zbl 0840.65049
[24] N.-D. Ho, P. Van Dooren, and V. D. Blondel, {\it Descent methods for nonnegative matrix factorization}, in Numerical Linear Algebra in Signals, Systems and Control, Springer, New York, 2011, pp. 251-293. · Zbl 1251.65049
[25] M. Hong, X. Wang, M. Razaviyayn, and Z.-Q. Luo, {\it Iteration complexity analysis of block coordinate descent methods}, Math. Program., 163 (2017), Ser. A, pp. 85-114. · Zbl 1367.49010
[26] A. N. Iusem and W. Sosa, {\it On the proximal point method for equilibrium problems in Hilbert spaces}, Optimization, 59 (2010), pp. 1259-1274. · Zbl 1206.90212
[27] H. Kim and H. Park, {\it Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis}, Bioinformatics, 23 (2007), pp. 1495-1502.
[28] J. Kim, Y. He, and H. Park, {\it Algorithms for nonnegative matrix and tensor factorizations: A unified view based on block coordinate descent framework}, J. Global Optim., 58 (2014), pp. 285-319. · Zbl 1321.90129
[29] J. Kim and H. Park, {\it Fast nonnegative matrix factorization: An active-set-like method and comparisons}, SIAM J. Sci. Comput., 33 (2011), pp. 3261-3281, . · Zbl 1232.65068
[30] M. Krasnosel’skiĭ, {\it Two remarks on the method of successive approximations}, Uspehi Mat. Nauk (N.S.), 10 (1955), pp. 123-127 (in Russian).
[31] D. D. Lee and H. S. Seung, {\it Algorithms for non-negative matrix factorization}, in Advances in Neural Information Processing Systems 13 (NIPS 2000), MIT Press, Cambridge, MA, 2001, pp. 556-562.
[32] C. Li, W. Yin, H. Jiang, and Y. Zhang, {\it An efficient augmented Lagrangian method with applications to total variation minimization}, Comput. Optim. Appl., 56 (2013), pp. 507-530. · Zbl 1287.90066
[33] C.-J. Lin, {\it Projected gradient methods for nonnegative matrix factorization}, Neural Comput., 19 (2007), pp. 2756-2779. · Zbl 1173.90583
[34] P. L. Lions and B. Mercier, {\it Splitting algorithms for the sum of two nonlinear operators}, SIAM J. Numer. Anal., 16 (1979), pp. 964-979, . · Zbl 0426.65050
[35] Z. Lu and L. Xiao, {\it On the complexity analysis of randomized block-coordinate descent methods}, Math. Programming, 152 (2015), pp. 615-642. · Zbl 1321.65100
[36] Z.-Q. Luo and P. Tseng, {\it On the convergence of the coordinate descent method for convex differentiable minimization}, J. Optim. Theory Appl., 72 (1992), pp. 7-35. · Zbl 0795.90069
[37] W. R. Mann, {\it Mean value methods in iteration}, Proc. Amer. Math. Soc., 4 (1953), pp. 506-510. · Zbl 0050.11603
[38] Yu. Nesterov, {\it Efficiency of coordinate descent methods on huge-scale optimization problems}, SIAM J. Optim., 22 (2012), pp. 341-362, . · Zbl 1257.90073
[39] Z. Peng, T. Wu, Y. Xu, M. Yan, and W. Yin, {\it Coordinate friendly-structures, algorithms and applications}, Ann. Math. Sci. Appl., 1 (2016), pp. 57-119. · Zbl 1432.65076
[40] Z. Peng, Y. Xu, M. Yan, and W. Yin, {\it ARock: An algorithmic framework for asynchronous parallel coordinate updates}, SIAM J. Sci. Comput., 38 (2016), pp. A2851-A2879, . · Zbl 1350.49041
[41] J.-C. Pesquet and A. Repetti, {\it A class of randomized primal-dual algorithms for distributed optimization}, J. Nonlinear Convex Anal., 16 (2015), pp. 2453-2490. · Zbl 1336.65113
[42] T. Pock and A. Chambolle, {\it Diagonal preconditioning for first order primal-dual algorithms in convex optimization}, in Proceedings of the 2011 IEEE International Conference on Computer Vision, IEEE Press, Piscataway, NJ, 2011, pp. 1762-1769.
[43] M. Razaviyayn, M. Hong, and Z.-Q. Luo, {\it A unified convergence analysis of block successive minimization methods for nonsmooth optimization}, SIAM J. Optim., 23 (2013), pp. 1126-1153, . · Zbl 1273.90123
[44] P. Richtárik and M. Takáč, {\it Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function}, Math. Programming, 144 (2014), pp. 1-38. · Zbl 1301.65051
[45] H.-J. M. Shi, S. Tu, Y. Xu, and W. Yin, {\it A Primer on Coordinate Descent Algorithms}, preprint, , 2016.
[46] R. L. Siddon, {\it Fast calculation of the exact radiological path for a three-dimensional CT array}, Med. Phys., 12 (1985), pp. 252-255.
[47] D. C. Sorensen, {\it A parameter free ADI-like method for the numerical solution of large scale Lyapunov equations}, in Splitting Methods in Communication, Imaging, Science, and Engineering, Springer, New York, 2016, pp. 409-425. · Zbl 1372.65131
[48] P. Tseng, {\it Convergence of a block coordinate descent method for nondifferentiable minimization}, J. Optim. Theory Appl., 109 (2001), pp. 475-494. · Zbl 1006.65062
[49] B. C. Vu͂, {\it A splitting algorithm for dual monotone inclusions involving cocoercive operators}, Adv. Comput. Math., 38 (2013), pp. 667-681. · Zbl 1284.47045
[50] J. Warga, {\it Minimizing certain convex functions}, J. Soc. Indust. Appl. Math., 11 (1963), pp. 588-593, . · Zbl 0128.05801
[51] S. J. Wright, {\it Coordinate descent algorithms}, Math. Programming, 151 (2015), pp. 3-34. · Zbl 1317.49038
[52] F.-Q. Xia and N.-J. Huang, {\it A projection-proximal point algorithm for solving generalized variational inequalities}, J. Optim. Theory Appl., 150 (2011), pp. 98-117. · Zbl 1242.90267
[53] Y. Xu and W. Yin, {\it A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion}, SIAM J. Imaging Sci., 6 (2013), pp. 1758-1789, . · Zbl 1280.49042
[54] Y. Xu and W. Yin, {\it A globally convergent algorithm for nonconvex optimization based on block coordinate update}, J. Sci. Comput., to appear, . · Zbl 1378.65126
[55] G.-X. Yuan, K.-W. Chang, C.-J. Hsieh, and C.-J. Lin, {\it A comparison of optimization methods and software for large-scale L1-regularized linear classification}, J. Mach. Learn. Res., 11 (2010), pp. 3183-3234. · Zbl 1242.62065
[56] R. Zdunek and A. Cichocki, {\it Non-negative matrix factorization with quasi-Newton optimization}, in Proceedings of the International Conference on Artificial Intelligence and Soft Computing, Springer-Verlag, Berlin, 2006, pp. 870-879.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.