A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions
The SMAI journal of computational mathematics, Volume 1 (2015) , pp. 29-54.

We analyze alternating descent algorithms for minimizing the sum of a quadratic function and block separable non-smooth functions. In case the quadratic interactions between the blocks are pairwise, we show that the schemes can be accelerated, leading to improved convergence rates with respect to related accelerated parallel proximal descent. As an application we obtain very fast algorithms for computing the proximity operator of the 2D and 3D total variation.

Published online:
DOI: https://doi.org/10.5802/smai-jcm.3
Classification: 65K10,  65B99,  49M27,  49M29,  90C25
Keywords: block coordinate descent, Dykstra’s algorithms, first order methods, acceleration, FISTA
@article{SMAI-JCM_2015__1__29_0,
     author = {Antonin Chambolle and Thomas Pock},
     title = {A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions},
     journal = {The SMAI journal of computational mathematics},
     pages = {29--54},
     publisher = {Soci\'et\'e de Math\'ematiques Appliqu\'ees et Industrielles},
     volume = {1},
     year = {2015},
     doi = {10.5802/smai-jcm.3},
     mrnumber = {3620369},
     zbl = {1416.65170},
     language = {en},
     url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.3/}
}
Antonin Chambolle; Thomas Pock. A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions. The SMAI journal of computational mathematics, Volume 1 (2015) , pp. 29-54. doi : 10.5802/smai-jcm.3. https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.3/

[1] H. Attouch; J. Bolte On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., Volume 116 (2009) no. 1-2, Ser. B, pp. 5-16 | Article | MR 2421270 | Zbl 1165.90018

[2] H. Attouch; J. Bolte; B. Svaiter Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., Volume 137 (2013) no. 1-2, Ser. A, pp. 91-129 | Article | MR 3010421 | Zbl 1260.49048

[3] H. Attouch; A. Cabot; P. Frankel; J. Peypouquet Alternating proximal algorithms for linearly constrained variational inequalities: application to domain decomposition for PDE’s, Nonlinear Anal., Volume 74 (2011) no. 18, pp. 7455-7473 | Article | MR 2833727 | Zbl 1228.65100

[4] A. Auslender Asymptotic properties of the Fenchel dual functional and applications to decomposition problems, J. Optim. Theory Appl., Volume 73 (1992) no. 3, pp. 427-449 | Article | MR 1164802 | Zbl 0794.49026

[5] Á. Barbero; S. Sra Modular proximal optimization for multidimensional total-variation regularization (2014) (Technical report) | Zbl 1411.90314

[6] H. H. Bauschke; P. L. Combettes A Dykstra-like algorithm for two monotone operators, Pac. J. Optim., Volume 4 (2008) no. 3, pp. 383-391 | MR 2541251 | Zbl 1176.47051

[7] H. H. Bauschke; P. L. Combettes Convex analysis and monotone operator theory in Hilbert spaces, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, Springer, New York, 2011, xvi+468 pages (With a foreword by Hédy Attouch) | Article | MR 2798533 | Zbl 1218.47001

[8] A. Beck On the Convergence of Alternating Minimization with Applications to Iteratively Reweighted Least Squares and Decomposition Schemes (2013) no. 4154 (Technical report)

[9] A. Beck; M. Teboulle A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., Volume 2 (2009) no. 1, pp. 183-202 | Article | MR 2486527 | Zbl 1175.94009

[10] A. Beck; L. Tetruashvili On the convergence of block coordinate descent type methods, SIAM J. Optim., Volume 23 (2013) no. 4, pp. 2037-2060 | Article | MR 3116649 | Zbl 1297.90113

[11] J. Bect; L. Blanc-Féraud; G. Aubert; A. Chambolle A l 1 -unified framework for image restoration, Proceedings ECCV 2004 (Prague) (Lecture Notes in Computer Science) (2004) no. 3024, pp. 1-13 | Zbl 1098.68728

[12] J. Bolte; S. Sabach; M. Teboulle Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., Volume 146 (2014) no. 1-2, Ser. A, pp. 459-494 | Article | MR 3232623 | Zbl 1297.90125

[13] Y. Boykov; V. Kolmogorov An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision, IEEE Trans. Pattern Analysis and Machine Intelligence, Volume 26 (2004) no. 9, pp. 1124-1137 | Article

[14] J. P. Boyle; R. L. Dykstra A method for finding projections onto the intersection of convex sets in Hilbert spaces, Advances in order restricted statistical inference (Iowa City, Iowa, 1985) (Lecture Notes in Statist.) Volume 37, Springer, Berlin, 1986, pp. 28-47 | Article | MR 875647 | Zbl 0603.49024

[15] A. Cabot; P. Frankel Alternating proximal algorithms with asymptotically vanishing coupling. Application to domain decomposition for PDE’s, Optimization, Volume 61 (2012) no. 3, pp. 307-325 | Article | MR 2879338 | Zbl 1238.65051

[16] P. Cannarsa; C. Sinestrari Semiconcave functions, Hamilton-Jacobi equations, and optimal control, Progress in Nonlinear Differential Equations and their Applications, 58, Birkhäuser Boston, Inc., Boston, MA, 2004, xiv+304 pages | Article | MR 2041617 | Zbl 1095.49003

[17] A. Chambolle; J. Darbon A parametric maximul flow approach to discrete total variation minimization, Image Processing and Analysis with Graphs: Theory and Practice (2012)

[18] A. Chambolle; Ch. Dossal On the Convergence of the Iterates of the “Fast Iterative Shrinkage/Thresholding Algorithm”, J. Optim. Theory Appl., Volume 166 (2015) no. 3, pp. 968-982 | Article | MR 3375610 | Zbl 1371.65047

[19] E. Chouzenoux; J.-C. Pesquet; A. Repetti A block coordinate variable metric forward-backward algorithm (2013) https://hal-upec-upem.archives-ouvertes.fr/hal-00945918 (Preprint hal-00945918) | Zbl 1351.90128

[20] P. L. Combettes Iterative construction of the resolvent of a sum of maximal monotone operators, J. Convex Anal., Volume 16 (2009) no. 3-4, pp. 727-748 | MR 2583892 | Zbl 1193.47067

[21] P. L. Combettes; J.-C. Pesquet Proximal splitting methods in signal processing, Fixed-point algorithms for inverse problems in science and engineering (Springer Optim. Appl.) Volume 49, Springer, New York, 2011, pp. 185-212 | Article | MR 2858838 | Zbl 1242.90160

[22] P. L. Combettes; V. R. Wajs Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., Volume 4 (2005) no. 4, pp. 1168-1200 | Article | MR 2203849 | Zbl 1179.94031

[23] L. Condat A Direct Algorithm for 1-D Total Variation Denoising, IEEE Signal Processing Letters, Volume 20 (2013), pp. 1054-1057 | Article

[24] R. L. Dykstra An algorithm for restricted least squares regression, J. Amer. Statist. Assoc., Volume 78 (1983) no. 384, pp. 837-842 | Article | MR 727568 | Zbl 0535.62063

[25] O. Fercoq; P. Richtárik Accelerated, parallel and proximal coordinate descent, arXiv preprint arXiv:1312.5799 (2013) | Zbl 1327.65108

[26] P. Frankel; G. Garrigos; J. Peypouquet Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates, J. Optim. Theory Appl., Volume 165 (2015) no. 3, pp. 874-900 | Article | MR 3341671 | Zbl 1316.49039

[27] X. L. Fu; B. S. He; X. F. Wang; X. M. Yuan Block-wise alternating direction method of multipliers with Gaussian back substitution for multiple-block convex programming, 2014

[28] N. Gaffke; R. Mathar A cyclic projection algorithm via duality, Metrika, Volume 36 (1989) no. 1, pp. 29-54 | Article | MR 985010 | Zbl 0676.90054

[29] L. Grippo; M. Sciandrone On the convergence of the block nonlinear Gauss-Seidel method under convex constraints, Oper. Res. Lett., Volume 26 (2000) no. 3, pp. 127-136 | Article | MR 1746833 | Zbl 0955.90128

[30] O. Güler New proximal point algorithms for convex minimization, SIAM J. Optim., Volume 2 (1992) no. 4, pp. 649-664 | Article | MR 1186167 | Zbl 0778.90052

[31] B. S. He; X. M. Yuan Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond, 2014

[32] M. Hintermüller; A. Langer Non-Overlapping Domain Decomposition Methods For Dual Total Variation Based Image Denoising, Journal of Scientific Computing (2014), pp. 1-26 | Article | Zbl 1323.65016

[33] D. Hochbaum An efficient algorithm for image segmentation, Markov random fields and related problems, J. ACM, Volume 48 (2001) no. 4, p. 686-701 (electronic) | Article | MR 2144926 | Zbl 1127.68474

[34] H. Ishikawa Exact optimization for Markov random fields with convex priors, IEEE Trans. Pattern Analysis and Machine Intelligence, Volume 25 (2003) no. 10, pp. 1333-1336 | Article

[35] N. A. Johnson A dynamic programming algorithm for the fused lasso and L 0 -segmentation, J. Comput. Graph. Statist., Volume 22 (2013) no. 2, pp. 246-260 | Article | MR 3173713

[36] V. Kolmogorov; T. Pock; M. Rolinek Total variation on a tree (2015) (arXiv preprint 1502.07770)

[37] Y. Lee; A. Sidford Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems, CoRR, Volume abs/1305.1922 (2013) http://arxiv.org/abs/1305.1922

[38] Q. Lin; Z. Lu; L. Xiao An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization (2014) no. MSR-TR-2014-94 (Technical report)

[39] M. G. McGaffin; J. A. Fessler Fast edge-preserving image denoising via group coordinate descent on the GPU, Proc. SPIE, Volume 9020 (2014), p. 90200P-90200P-9 | Article

[40] A. Nemirovski; D. Yudin Problem complexity and method efficiency in optimization, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1983, xv+388 pages (Translated from the Russian and with a preface by E. R. Dawson, Wiley-Interscience Series in Discrete Mathematics) | MR 702836

[41] Yu. Nesterov A method for solving the convex programming problem with convergence rate O(1/k 2 ), Dokl. Akad. Nauk SSSR, Volume 269 (1983) no. 3, pp. 543-547 | MR 701288 | Zbl 0535.90071

[42] Yu. Nesterov Introductory lectures on convex optimization, Applied Optimization, Volume 87, Kluwer Academic Publishers, Boston, MA, 2004, xviii+236 pages (A basic course) | Article | MR 2142598 | Zbl 1086.90045

[43] Yu. Nesterov Smooth minimization of non-smooth functions, Math. Program., Volume 103 (2005) no. 1, Ser. A, pp. 127-152 | Article | MR 2166537 | Zbl 1079.90102

[44] Yu. Nesterov Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., Volume 22 (2012) no. 2, pp. 341-362 | Article | MR 2968857 | Zbl 1257.90073

[45] B. O’Donoghue; E. Candès Adaptive Restart for Accelerated Gradient Schemes, Foundations of Computational Mathematics (2013) | Zbl 1320.90061

[46] T. Pock; T. Schoenemann; G. Graber; H. Bischof; D. Cremers A Convex Formulation of Continuous Multi-Label Problems, European Conference on Computer Vision (ECCV) (2008)

[47] M. Razaviyayn; M. Hong; Z.-Q. Luo A unified convergence analysis of block successive minimization methods for nonsmooth optimization, SIAM J. Optim., Volume 23 (2013) no. 2, pp. 1126-1153 | Article | MR 3063152 | Zbl 1273.90123

[48] D. Scharstein; H. Hirschmüller; Y. Kitajima; G. Krathwohl; N. Nesic; X. Wang; P. Westling High-resolution stereo datasets with subpixel-accurate ground truth, German Conference on Pattern Recognition (GCPR 2014) (2014)

[49] P. Tseng On accelerated proximal gradient methods for convex-concave optimization, 2008 (Submitted to SIAM J. Optim.)

[50] Y. Xu; W. Yin A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion, SIAM J. Imaging Sci., Volume 6 (2013) no. 3, pp. 1758-1789 | Article | MR 3105787 | Zbl 1280.49042