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.

DOI: 10.5802/smai-jcm.3
Classification: 65K10, 65B99, 49M27, 49M29, 90C25
Keywords: block coordinate descent, Dykstra’s algorithms, first order methods, acceleration, FISTA
Antonin Chambolle 1; Thomas Pock 2

1 CMAP, Ecole Polytechnique, CNRS, 91128 Palaiseau, France
2 Institute for Computer Graphics and Vision, Graz University of Technology, 8010 Graz, Austria and Digital Safety & Security Department, AIT Austrian Institute of Technology GmbH, 1220 Vienna, Austria
@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},
     language = {en},
     url = {https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.3/}
}
TY  - JOUR
AU  - Antonin Chambolle
AU  - Thomas Pock
TI  - A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions
JO  - The SMAI Journal of computational mathematics
PY  - 2015
SP  - 29
EP  - 54
VL  - 1
PB  - Société de Mathématiques Appliquées et Industrielles
UR  - https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.3/
DO  - 10.5802/smai-jcm.3
LA  - en
ID  - SMAI-JCM_2015__1__29_0
ER  - 
%0 Journal Article
%A Antonin Chambolle
%A Thomas Pock
%T A remark on accelerated block coordinate descent for computing the proximity operators of a sum of convex functions
%J The SMAI Journal of computational mathematics
%D 2015
%P 29-54
%V 1
%I Société de Mathématiques Appliquées et Industrielles
%U https://smai-jcm.centre-mersenne.org/articles/10.5802/smai-jcm.3/
%R 10.5802/smai-jcm.3
%G en
%F SMAI-JCM_2015__1__29_0
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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | Zbl

[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, pp. xvi+468 (With a foreword by Hédy Attouch) | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[11] J. Bect; L. Blanc-Féraud; G. Aubert; A. Chambolle; T. Pajdla; J. Matas, Proceedings ECCV 2004 (Prague) (Lecture Notes in Computer Science) (2004) no. 3024, pp. 1-13 | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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, pp. xiv+304 | MR | Zbl

[17] A. Chambolle; J. Darbon A parametric maximul flow approach to discrete total variation minimization, Image Processing and Analysis with Graphs: Theory and Practice, CRC Press (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 | DOI | MR

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

[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 | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

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

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

[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 | DOI | MR

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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 | DOI | MR

[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) | DOI | MR | Zbl

[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 | DOI

[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 | DOI | MR

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

[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, Proc. SPIE, Volume 9020 (2014), p. 90200P-90200P-9 | DOI | MR

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

[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 | Zbl

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

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

[44] Yu. Nesterov 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] B. O’Donoghue; E. Candès Adaptive Restart for Accelerated Gradient Schemes, Foundations of Computational Mathematics (2013)

[46] T. Pock; T. Schoenemann; G. Graber; H. Bischof; D. Cremers, 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 | DOI | MR | Zbl

[48] D. Scharstein; H. Hirschmüller; Y. Kitajima; G. Krathwohl; N. Nesic; X. Wang; P. Westling, German Conference on Pattern Recognition (GCPR 2014) (2014) | MR

[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 | DOI | MR | Zbl

Cited by Sources: