×

A simple convergence analysis of Bregman proximal gradient algorithm. (English) Zbl 1423.90275

Summary: In this paper, we provide a simple convergence analysis of proximal gradient algorithm with Bregman distance, which provides a tighter bound than existing result. In particular, for the problem of minimizing a class of convex objective functions, we show that proximal gradient algorithm with Bregman distance can be viewed as proximal point algorithm that incorporates another Bregman distance. Consequently, the convergence result of the proximal gradient algorithm with Bregman distance follows directly from that of the proximal point algorithm with Bregman distance, and this leads to a simpler convergence analysis with a tighter convergence bound than existing ones. We further propose and analyze the backtracking line-search variant of the proximal gradient algorithm with Bregman distance.

MSC:

90C52 Methods of reduced gradient type
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Auslender, A., Teboulle, M.: Interior gradient and proximal methods for convex and conic optimization. SIAM J. Optim. 16(3), 697-725 (2006) · Zbl 1113.90118
[2] Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3), 167-175 (2003) · Zbl 1046.90057
[3] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183-202 (2009) · Zbl 1175.94009
[4] Beck, A., Teboulle, M.: Smoothing and first order methods: a unified framework. SIAM J. Optim. 22(2), 557-580 (2012) · Zbl 1251.90304
[5] Bolte, J., Bauschke, H., Teboulle, M.: A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Math. Oper. Res. 42, 330-348 (2016) · Zbl 1364.90251
[6] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1-122 (2011) · Zbl 1229.90122
[7] Bregman, L.M.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7(3), 200-217 (1967) · Zbl 0186.23807
[8] Censor, Y., Zenios, S.A.: Proximal minimization algorithm with d-functions. J. Optim. Theory Appl. 73(3), 451-464 (1992) · Zbl 0794.90058
[9] Chen, G., Teboulle, M.: Convergence analysis of a proximal-like minimization algorithm using Bregman functions. SIAM J. Optim. 3(3), 538-543 (1993) · Zbl 0808.90103
[10] De Pierro, A.R., Iusem, A.N.: A relaxed version of Bregman’s method for convex programming. J. Optim. Theory Appl. 51(3), 421-440 (1986) · Zbl 0581.90069
[11] Eckstein, J.: Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Math. Oper. Res. 18(1), 202-226 (1993) · Zbl 0807.47036
[12] Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55, 293-318 (1992) · Zbl 0765.90073
[13] Fukushima, M., Mine, H.: A generalized proximal point algorithm for certain non-convex minimization problems. Int. J. Syst. Sci. 12(8), 989-1000 (1981) · Zbl 0467.65028
[14] Güler, O.: On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. 29(2), 403-419 (1991) · Zbl 0737.90047
[15] Lions, P., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964-979 (1979) · Zbl 0426.65050
[16] Martinet, B.: Bréve communication: régularisation d’inéquations variationnellespar approximations successives. ESAIM Math. Modell. Numer. Anal. 4(R3), 154-158 (1970) · Zbl 0215.21103
[17] Micchelli, C.A., Shen, L., Xu, Y.: Proximity algorithms for image models: denoising. Inverse Probl. 27, 045009 (2011) · Zbl 1216.94015
[18] Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127-152 (2005) · Zbl 1079.90102
[19] Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471-501 (2010) · Zbl 1198.90321
[20] Rockafellar, R.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5), 877-898 (1976) · Zbl 0358.90053
[21] Teboulle, M.: Entropic proximal mappings with applications to nonlinear programming. Math. Oper. Res. 17(3), 670-690 (1992) · Zbl 0766.90071
[22] Teboulle, M.: Convergence of proximal-like algorithms. SIAM J. Optim. 7(4), 1069-1083 (1997) · Zbl 0890.90151
[23] Tseng, P.: Approximation accuracy, gradient methods, and error bound for structured convex optimization. Math. Program. 125(2), 263-295 (2010) · Zbl 1207.65084
[24] Zhou, Y., Liang, Y., Shen, L.: A new perspective of proximal gradient algorithms. arXiv: 1503.05601 (2015)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.