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

Chambolle, Antonin; Pock, Thomas

Journal of computational mathematics, Tome 1 (2015), p. 29-54 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

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.

Publié le : 2015-01-01
DOI : https://doi.org/10.5802/smai-jcm.3
Classification: 65K10, 65B99, 49M27, 49M29, 90C25

@article{SMAI-JCM_2015__1__29_0,
     author = {Chambolle, Antonin and Pock, Thomas},
     title = {A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions},
     journal = {Journal of computational mathematics},
     volume = {1},
     year = {2015},
     pages = {29-54},
     doi = {10.5802/smai-jcm.3},
     language = {en},
     url = {http://dml.mathdoc.fr/item/SMAI-JCM_2015__1__29_0}
}

Chambolle, Antonin; Pock, Thomas. A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions. Journal of computational mathematics, Tome 1 (2015) pp. 29-54. doi : 10.5802/smai-jcm.3. http://gdmltest.u-ga.fr/item/SMAI-JCM_2015__1__29_0/

Bibliographie

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

[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., Tome 137 (2013) no. 1-2, Ser. A, pp. 91-129 | Article | MR 3010421 | Zbl 1260.49048

[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., Tome 74 (2011) no. 18, pp. 7455-7473 | Article | MR 2833727 | Zbl 1228.65100

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

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

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

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

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

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

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

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

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

[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, Tome 26 (2004) no. 9, pp. 1124-1137 | Article | Zbl 1005.68964

[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), Springer, Berlin (Lecture Notes in Statist.) Tome 37 (1986), pp. 28-47 | Article | MR 875647 | Zbl 0603.49024

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

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

[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., Tome 166 (2015) no. 3, pp. 968-982 | Article | MR 3375610

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

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

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

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

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

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

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

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

[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, manuscript (2014)

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

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

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

[31] He, B. S.; Yuan, X. M. Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond, manuscript (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 | Article | MR 3299201

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

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

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

[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, Tome abs/1305.1922 (2013) http://arxiv.org/abs/1305.1922 | MR 3246216

[38] Lin, Q.; Lu, Z.; Xiao, L. An Accelerated Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization, Microsoft Research (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, Tome 9020 (2014), p. 90200P-90200P-9 | Article | MR 3322225

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

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

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

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

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

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

[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., Tome 23 (2013) no. 2, pp. 1126-1153 | Article | MR 3063152 | Zbl 1273.90123

[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) | MR 3297186

[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., Tome 6 (2013) no. 3, pp. 1758-1789 | Article | MR 3105787 | Zbl 1280.49042