×

zbMATH — the first resource for mathematics

Block-proximal methods with spatially adapted acceleration. (English) Zbl 1420.49034
Summary: We study and develop (stochastic) primal-dual block-coordinate descent methods for convex problems based on the method due to Chambolle and Pock. Our methods have known convergence rates for the iterates and the ergodic gap of \(O(1/N^2)\) if each block is strongly convex, \(O(1/N)\) if no convexity is present, and more generally a mixed rate \(O(1/N^2)+O(1/N)\) for strongly convex blocks if only some blocks are strongly convex. Additional novelties of our methods include blockwise-adapted step lengths and acceleration as well as the ability to update both the primal and dual variables randomly in blocks under a very light compatibility condition. In other words, these variants of our methods are doubly-stochastic. We test the proposed methods on various image processing problems, where we employ pixelwise-adapted acceleration.

MSC:
49M29 Numerical methods involving duality
65K10 Numerical optimization and variational techniques
65K15 Numerical methods for variational inequalities and related problems
90C30 Nonlinear programming
90C47 Minimax problems in mathematical programming
Software:
ARock; iPiano
PDF BibTeX XML Cite
Full Text: DOI Link arXiv
References:
[1] A. BECK ANDM. TEBOULLE, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), pp. 183-202. · Zbl 1175.94009
[2] D. P. BERTSEKAS, Incremental aggregated proximal and augmented Lagrangian algorithms, Preprint on arXiv, 2015.https://arxiv.org/abs/1509.09257
[3] P. BIANCHI, W. HACHEM,ANDF. IUTZELER, A stochastic coordinate descent primal-dual algorithm and applications to large-scale composite optimization, Preprint on arXiv, 2015. https://arxiv.org/abs/1407.0898
[4] J. BOLTE, S. SABACH,ANDM. TEBOULLE, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146 (2014), pp. 459-494. · Zbl 1297.90125
[5] A. CHAMBOLLE, An algorithm for mean curvature motion, Interfaces Free Bound., 6 (2004), pp. 195-218. ETNA Kent State University and Johann Radon Institute (RICAM) 48T. VALKONEN · Zbl 1061.35147
[6] A. CHAMBOLLE ANDT. POCK, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision, 40 (2011), pp. 120-145. · Zbl 1255.68217
[7] , On the ergodic convergence rates of a first-order primal-dual algorithm, Math. Program., 159 (2016), pp. 253-287. · Zbl 1350.49035
[8] Y. CHEN, G. LAN,ANDY. OUYANG, Optimal primal-dual methods for a class of saddle point problems, SIAM J. Optim., 24 (2014), pp. 1779-1814. · Zbl 1329.90090
[9] P. L. COMBETTES ANDJ.-C. PESQUET, Stochastic forward-backward and primal-dual approximation algorithms with application to online image restoration, Preprint on arXiv, 2016. https://arxiv.org/abs/1602.08021
[10] L. CONDAT, A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms, J. Optim. Theory Appl., 158 (2013), pp. 460-479. · Zbl 1272.90110
[11] D. CSIBA, Z. QU,ANDP. RICHTÁRIK, Stochastic dual coordinate ascent with adaptive probabilities, Preprint on arXiv, 2015.https://arxiv.org/abs/1502.08053
[12] I. DAUBECHIES, M. DEFRISE,ANDC. DEMOL, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57 (2004), pp. 1413-1457. · Zbl 1077.65055
[13] J. C. DE LOSREYES, C.-B. SCHÖNLIEB,ANDT. VALKONEN, Bilevel parameter learning for higher-order total variation regularisation models, J. Math. Imaging Vision, 57 (2017), pp. 1-25.
[14] E. ESSER, X. ZHANG,ANDT. F. CHAN, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci., 3 (2010), pp. 1015-1046. · Zbl 1206.90117
[15] O. FERCOQ ANDP. BIANCHI, A coordinate descent primal-dual algorithm with large step size and possibly non separable functions, Preprint on arXiv, 2015.https://arxiv.org/abs/1508.04625
[16] O. FERCOQ ANDP. RICHTÁRIK, Optimization in high dimensions via accelerated, parallel, and proximal coordinate descent, SIAM Rev., 58 (2016), pp. 739-771. · Zbl 1353.65053
[17] T. GOLDSTEIN, M. LI,ANDX. YUAN, Adaptive primal-dual splitting methods for statistical learning and image processing, in Advances in Neural Information Processing Systems 28, Vol. 2, C. Cortes, N. D. Lawrence, and D. D. Lee, eds., NIPS, La Jolla, 2015, pp. 2080-2088.
[18] B. HE, Y. YOU,ANDX. YUAN, On the convergence of primal-dual hybrid gradient algorithm, SIAM J. Imaging Sci., 7 (2014), pp. 2526-2537. · Zbl 1308.90129
[19] B. HE ANDX. YUAN, Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective, SIAM J. Imaging Sci., 5 (2012), pp. 119-149. · Zbl 1250.90066
[20] , Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond, SMAI J. Comput. Math., 1 (2015), pp. 145-174. · Zbl 1418.90193
[21] T. MÖLLENHOFF, E. STREKALOVSKIY, M. MOELLER,ANDD. CREMERS, The primal-dual hybrid gradient method for semiconvex splittings, SIAM J. Imaging Sci., 8 (2015), pp. 827-857. · Zbl 1328.68278
[22] Y. NESTEROV, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim., 22 (2012), pp. 341-362. · Zbl 1257.90073
[23] P. OCHS, Y. CHEN, T. BROX,ANDT. POCK, iPiano: inertial proximal algorithm for nonconvex optimization, SIAM J. Imaging Sci., 7 (2014), pp. 1388-1419. · Zbl 1296.90094
[24] Z. PENG, T. WU, Y. XU, M. YAN,ANDW. YIN, Coordinate friendly structures, algorithms and applications, Preprint on arXiv, 2016.https://arxiv.org/abs/1601.00863
[25] Z. PENG, Y. XU, M. YAN,ANDW. YIN, ARock: an algorithmic framework for asynchronous parallel coordinate updates, SIAM J. Sci. Comput., 38 (2016), pp. A2851-A2879. · Zbl 1350.49041
[26] J.-C. PESQUET ANDA. REPETTI, A class of randomized primal-dual algorithms for distributed optimization, J. Nonlinear Convex Anal., 16 (2015), pp. 2453-2490. · Zbl 1336.65113
[27] T. POCK, D. CREMERS, H. BISCHOF,ANDA. CHAMBOLLE, An algorithm for minimizing the MumfordShah functional, in 12th IEEE Int. Conference on Computer Vision, September 2009, IEEE Conference Proceedings, Los Alamitos, pp. 1133-1140.
[28] Z. QU, P. RICHTÁRIK,ANDT. ZHANG, Randomized dual coordinate ascent with arbitrary sampling, Preprint on arXiv, 2014.https://arxiv.org/abs/1411.5873
[29] P. RICHTÁRIK ANDM. TAKÁ ˇC, Distributed coordinate descent method for learning with big data, J. Mach. Learn. Res., 17 (2016), Paper No. 75, (25 pages).
[30] , Parallel coordinate descent methods for big data optimization, Math. Program., 156 (2016), pp. 433- 484. · Zbl 1342.90102
[31] S. SHALEV-SHWARTZ ANDT. ZHANG, Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization, Math. Program., 155 (2016), pp. 105-145. · Zbl 1342.90103
[32] A. N. SHIRYAEV, Probability, Graduate Texts in Mathematics, Springer, 1996.
[33] T. SUZUKI, Stochastic dual coordinate ascent with alternating direction multiplier method, Preprint on arXiv 2013.https://arxiv.org/abs/1311.0622
[34] T. VALKONEN, Inertial, corrected, primal – dual proximal splitting, Preprint on arXiv, 2018. https://arxiv.org/abs/1804.08736
[35] , Testing and non-linear preconditioning of the proximal point method, Appl. Math. Optim, (2018), in press,https://doi.org/10.1007/s00245-018-9541-6 ETNA Kent State University and Johann Radon Institute (RICAM) BLOCK-PROXIMAL METHODS WITH SPATIALLY ADAPTED ACCELERATION49
[36] T. VALKONEN, K. BREDIES,ANDF. KNOLL, Total generalised variation in diffusion tensor imaging, SIAM J. Imaging Sci., 6 (2013), pp. 487-525. · Zbl 1322.94024
[37] T. VALKONEN ANDT. POCK, Acceleration of the PDHGM on partially strongly convex functions, J. Math. Imaging Vision, 59 (2017), pp. 394-414. · Zbl 1382.90080
[38] B. C. VU˜, A splitting algorithm for dual monotone inclusions involving cocoercive operators, Adv. Comput. Math., 38 (2013), pp. 667-681. · Zbl 1284.47045
[39] S. J. WRIGHT, Coordinate descent algorithms, Math. Program., 151 (2015), pp. 3-34. · Zbl 1317.49038
[40] A. W. YU, Q. LIN,ANDT. YANG, Doubly stochastic primal-dual coordinate method for empirical risk minimization and bilinear saddle-point problem, Preprint on arXiv, 2015. https://arxiv.org/abs/1508.03390
[41] Y. ZHANG ANDL. XIAO, Stochastic primal-dual coordinate method for regularized empirical risk minimization, J. Mach. Learn. Res., 18 (2017), Paper No. 84, (42 pages). · Zbl 1440.62314
[42] P. ZHAO ANDT. ZHANG, Stochastic optimization with importance sampling, Preprint on arXiv, 2014. https://arxiv.org/abs/1401.2753
[43] M. ZHU ANDT. CHAN, An efficient primal-dual hybrid gradient algorithm for total variation image restoration, CAM Report 08-34, Dept. of Math., UCLA, Los Angeles, 2008.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.