A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions

Chambolle, Antonin; Pock, Thomas

The SMAI Journal of computational mathematics, Tome 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.

Classification : 65K10, 65B99, 49M27, 49M29, 90C25
Mots clés : block coordinate descent, Dykstra’s algorithms, first order methods, acceleration, FISTA

[1] Attouch, H.; Bolte, J. 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 | DOI | MR | Zbl

[2] Attouch, H.; Bolte, J.; Svaiter, B. 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 | DOI | MR | Zbl

[3] Attouch, H.; Cabot, A.; Frankel, P.; Peypouquet, J. 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 | DOI | MR | Zbl

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

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

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

[7] Bauschke, H. H.; Combettes, P. L. 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) | DOI | MR | Zbl

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

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

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

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

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

[13] Boykov, Y.; Kolmogorov, V. 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 | DOI

[14] Boyle, J. P.; Dykstra, R. L. 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 | DOI | MR | Zbl

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

[16] Cannarsa, P.; Sinestrari, C. 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 | DOI | MR | Zbl

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

[18] Chambolle, A.; Dossal, Ch. 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 | DOI | MR | Zbl

[19] Chouzenoux, E.; Pesquet, J.-C.; Repetti, A. A block coordinate variable metric forward-backward algorithm (2013) (Preprint hal-00945918) | HAL | Zbl

[20] Combettes, P. L. 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 | Zbl

[21] Combettes, P. L.; Pesquet, J.-C. 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 | DOI | MR | Zbl

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

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

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

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

[26] Frankel, P.; Garrigos, G.; Peypouquet, J. 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 | DOI | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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

[40] Nemirovski, A.; Yudin, D. 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

[41] Nesterov, Yu. 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 | Zbl

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

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

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

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

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

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

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

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

[50] Xu, Y.; Yin, W. 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 | DOI | MR | Zbl