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

By Heinz H. Bauschke, Jérôme Bolte, Marc Teboulle. 2017

498 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Mathematical Physics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Mathematical Physics

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, methodology): “Assumption 3.1 The function ω ( ) satisﬁes Since ω ( x ) is convex by the triangle inequality, we de-ﬁne the dual distance Remark 3.2 Usually, extensions of smoothness of a function use Bregman divergences (see e.g. [Lu et al. 2018; Bauschke et al. 2017]).”
Generalized conditional subgradient and generalized mirror descent: duality, convergence, and symmetry (2019, background): “The above concept of relative quadratic curvature is inspired by the concepts of relative smoothness and relative continuity introduced in [2, 17, 18, 22].”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, background): “…proof of mSPS is included in Section D; the proofs for the results in Section 5 are presented in Section E, including Theorem 1 and Theorem 3; proofs for Section 6 are given in Section F, including a non-convex result for preconditioned SGD in Section F.3; experiment details are given in Section G.”