On Linear Convergence of Non-Euclidean Gradient Methods without Strong Convexity and Lipschitz Gradient Continuity

Heinz H. Bauschke (), Jérôme Bolte, Jiawei Chen (), Marc Teboulle () and Xianfu Wang ()
Additional contact information
Heinz H. Bauschke: University of British Columbia Okanagan
Jiawei Chen: Southwest University
Marc Teboulle: Tel Aviv University
Xianfu Wang: University of British Columbia Okanagan

Journal of Optimization Theory and Applications, 2019, vol. 182, issue 3, No 11, 1068-1087

Abstract: Abstract The gradient method is well known to globally converge linearly when the objective function is strongly convex and admits a Lipschitz continuous gradient. In many applications, both assumptions are often too stringent, precluding the use of gradient methods. In the early 1960s, after the amazing breakthrough of Łojasiewicz on gradient inequalities, it was observed that uniform convexity assumptions could be relaxed and replaced by these inequalities. On the other hand, very recently, it has been shown that the Lipschitz gradient continuity can be lifted and replaced by a class of functions satisfying a non-Euclidean descent property expressed in terms of a Bregman distance. In this note, we combine these two ideas to introduce a class of non-Euclidean gradient-like inequalities, allowing to prove linear convergence of a Bregman gradient method for nonconvex minimization, even when neither strong convexity nor Lipschitz gradient continuity holds.

Keywords: Non-Euclidean gradient methods; Nonconvex minimization; Bregman distance; Lipschitz-like convexity condition; Descent lemma without Lipschitz gradient; Gradient dominated inequality; Łojasiewicz gradient inequality; Linear rate of convergence; 65K05; 49M10; 90C26; 90C30; 65K10 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-019-01516-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joptap:v:182:y:2019:i:3:d:10.1007_s10957-019-01516-9

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-019-01516-9

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().