A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications

Heinz H. Bauschke (), Jérôme Bolte and Marc Teboulle ()
Additional contact information
Heinz H. Bauschke: Mathematics, University of British Columbia, Kelowna, British Columbia V1V 1V7, Canada
Marc Teboulle: School of Mathematical Sciences, Tel Aviv University, Ramat Aviv 69978, Israel

Mathematics of Operations Research, 2017, vol. 42, issue 2, 330-348

Abstract: The proximal gradient and its variants is one of the most attractive first-order algorithm for minimizing the sum of two convex functions, with one being nonsmooth. However, it requires the differentiable part of the objective to have a Lipschitz continuous gradient, thus precluding its use in many applications. In this paper we introduce a framework which allows to circumvent the intricate question of Lipschitz continuity of gradients by using an elegant and easy to check convexity condition which captures the geometry of the constraints. This condition translates into a new descent lemma which in turn leads to a natural derivation of the proximal-gradient scheme with Bregman distances. We then identify a new notion of asymmetry measure for Bregman distances, which is central in determining the relevant step-size. These novelties allow to prove a global sublinear rate of convergence, and as a by-product, global pointwise convergence is obtained. This provides a new path to a broad spectrum of problems arising in key applications which were, until now, considered as out of reach via proximal gradient methods. We illustrate this potential by showing how our results can be applied to build new and simple schemes for Poisson inverse problems.

Keywords: first-order methods; composite nonsmooth convex minimization; descent lemma; proximal-gradient algorithms; complexity; Bregman distance; multiplicative Poisson linear inverse problems (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (37)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0817 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:2:p:330-348

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().