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.

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] 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] 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] 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] 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] Modular proximal optimization for multidimensional total-variation regularization (2014) (Technical report) | Zbl 1411.90314

[6] 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] 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] On the Convergence of Alternating Minimization with Applications to Iteratively Reweighted Least Squares and Decomposition Schemes (2013) no. 4154 (Technical report)

[9] 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] 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] 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] 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] 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] 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] 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] 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 parametric maximul flow approach to discrete total variation minimization, Image Processing and Analysis with Graphs: Theory and Practice (2012)

[18] 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] 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] 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] 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] 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] A Direct Algorithm for 1-D Total Variation Denoising, IEEE Signal Processing Letters, Volume 20 (2013), pp. 1054-1057 | Article

[24] 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] Accelerated, parallel and proximal coordinate descent, arXiv preprint arXiv:1312.5799 (2013) | Zbl 1327.65108

[26] 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] Block-wise alternating direction method of multipliers with Gaussian back substitution for multiple-block convex programming, 2014

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

[29] 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] 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] Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond, 2014

[32] 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] 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] 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] 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] Total variation on a tree (2015) (arXiv preprint 1502.07770)

[37] 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] An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization (2014) no. MSR-TR-2014-94 (Technical report)

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

[40] 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] 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] 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] 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] 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] Adaptive Restart for Accelerated Gradient Schemes, Foundations of Computational Mathematics (2013) | Zbl 1320.90061

[46] A Convex Formulation of Continuous Multi-Label Problems, European Conference on Computer Vision (ECCV) (2008)

[47] 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] High-resolution stereo datasets with subpixel-accurate ground truth, German Conference on Pattern Recognition (GCPR 2014) (2014)

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

[50] 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