Source-linked AI summary
First Order Methods beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems
Jérôme Bolte, Shoham Sabach, Marc Teboulle, Yakov Vaisbourd
TL;DR
The paper addresses nonconvex nonsmooth composite optimization when the differentiable term lacks a globally Lipschitz gradient. It extends geometry-adapted Bregman methods through smooth adaptability and proves global convergence, including for sparse quadratic inverse problems under stated assumptions.
Problem
Global Lipschitz continuity of the smooth term’s gradient is a restrictive assumption in first-order methods, motivating methods for nonconvex composite problems that avoid it.
Method
The paper introduces smooth adaptable functions and an extended descent lemma, then develops a Bregman proximal-gradient method for nonconvex composite minimization.
Results
The Bregman proximal-gradient schemes globally converge to critical points under natural assumptions and yield new globally convergent schemes for sparse quadratic inverse problems.
Takeaways & Limitations
The framework removes the global Lipschitz-gradient requirement while retaining a global critical-point convergence result for the supported problem class.
Takeaways & Limitations
The convergence analysis relies on assumptions including coercivity or boundedness conditions, and technical qualification conditions may be required outside settings where they hold automatically.
Abstract
from arXiv · showhide
We focus on nonconvex and nonsmooth minimization problems with a composite objective, where the differentiable part of the objective is freed from the usual and restrictive global Lipschitz gradient continuity assumption. This longstanding smoothness restriction is pervasive in first order methods (FOM), and was recently circumvent for convex composite optimization by Bauschke, Bolte and Teboulle, through a simple and elegant framework which captures, all at once, the geometry of the function and of the feasible set. Building on this work, we tackle genuine nonconvex problems. We first complement and extend their approach to derive a full extended descent lemma by introducing the notion of smooth adaptable functions. We then consider a Bregman-based proximal gradient methods for the nonconvex composite model with smooth adaptable functions, which is proven to globally converge to a critical point under natural assumptions on the problem's data. To illustrate the power and potential of our general framework and results, we consider a broad class of quadratic inverse problems with sparsity constraints which arises in many fundamental applications, and we apply our approach to derive new globally convergent schemes for this class.
1 Introduction
The paper extends Bregman-based first-order optimization from convex composite problems to genuinely nonconvex, nonsmooth settings without requiring globally Lipschitz gradients. It develops a convergent proximal-gradient framework and applies it to sparse quadratic inverse problems.
- Motivation: Global Lipschitz continuity of the smooth component’s gradient is a restrictive assumption common to most first-order methods.Linesearches and complex inner loops have been used to circumvent it, but may distort efficiency and complexity.
- Contribution: The paper extends the Bauschke–Bolte–Teboulle framework to nonconvex composite minimization using geometry-adapted Bregman distances.Both objective components may be nonconvex, and the smooth component need not have a globally Lipschitz continuous gradient.
- Contribution: The proposed Bregman proximal-gradient algorithms are proven to globally converge to a critical point under stated assumptions, including semi-algebraic data when C = R^d.The framework covers standard proximal-gradient methods as a special case.
- Application: New simple, provably convergent schemes are derived for a broad class of sparse quadratic inverse problems arising in fundamental applications.The paper identifies them as, to the authors’ knowledge, the first globally convergent algorithms for this class.
- Organization: The paper first develops smooth adaptable functions and an extended descent lemma, then analyzes the nonconvex proximal-gradient method and its applications.The paper’s organization follows this progression through the theoretical and application sections.
2 Smooth Adaptable Functions and a Descent Lemma
The paper introduces smooth adaptability to replace Euclidean quadratic smoothness by geometry-sensitive Bregman proximity measures. This yields a two-sided extended descent lemma for differentiable functions that need not be convex.
- Smooth Adaptability: Smooth adaptable functions generalize the convex framework by accommodating differentiable functions that are not necessarily convex.The construction derives a natural two-sided descent lemma rather than only a one-sided bound.
- Proximity Measures: A kernel-generating distance is induced by a proper lower-semicontinuous convex function that is continuously differentiable on the interior of its domain.The associated class is denoted G(C).
- Proximity Measures: The Bregman distance measures the discrepancy between a kernel value and its linear approximation at a reference point.For convex kernels it is nonnegative, while symmetry generally does not hold.
- Extended Descent Lemma: L-smooth adaptability requires Lh − g and Lh + g to be convex, which is equivalent to bounding the absolute linearization error by L times the Bregman distance.The resulting inequality is |g(x) − g(y) − ⟨∇g(y), x − y⟩| ≤ L D_h(x,y).
- Extended Descent Lemma: The extended descent lemma recovers classical quadratic descent when h is the Euclidean energy kernel and g has an L-smooth gradient.More generally, it exploits the geometry of both the function and the feasible set through h and D_h.
3 The Problem and a Bregman Proximal Gradient Algorithm
The paper formulates a nonconvex composite problem and solves it with a Bregman proximal-gradient mapping that linearizes the smooth term and regularizes the step using a non-Euclidean distance. Under coercivity and regularity assumptions, the mapping is well-defined and the algorithm is globally convergent under later conditions.
- Problem Formulation: The target problem minimizes a nonconvex composite objective over C = int dom h, with a proper lower-semicontinuous nonsmooth term and a continuously differentiable smooth term.The feasible-set geometry is encoded through the kernel h.
- Algorithm: The Bregman proximal-gradient mapping minimizes a linearization of g plus λf and the Bregman distance from the current iterate.With the Euclidean energy kernel, it reduces to the classical set-valued proximal-gradient mapping.
- Algorithm: Because f may be nonconvex, the proximal mapping is generally set-valued; when f is convex, it becomes single-valued under the stated assumptions.The overall composite problem can remain nonconvex because g may still be nonconvex.
- Well-Posedness: Supercoercivity of h + λf ensures the proximal subproblem has a nonempty compact solution set.The proof combines level boundedness with properness and lower semicontinuity.
- Algorithm: The Bregman proximal-gradient algorithm is well-defined under the standing assumptions and is analyzed for global convergence to a critical point.The convergence statement is established in the following analysis section.
4 Convergence Analysis of BPG
The convergence analysis establishes sufficient decrease and criticality of limit points for BPG, then uses the KL property to obtain finite-length global convergence to a critical point. The results require bounded iterates and a step size satisfying 0 < λL < 1.
- Descent Properties: 0 < λL < 1 ensures sufficient decrease in the composite objective along BPG iterates.The descent estimate is the key basis for the subsequent convergence analysis.
- Descent Properties: Under the step-size condition, the objective sequence is nonincreasing and successive-iterate gaps satisfy the stated vanishing estimates.These properties are collected in Proposition 4.1.
- Global Convergence: If the generated sequence is bounded, every limit point is a critical point of the composite objective.This is the subsequential convergence part of Theorem 4.1.
- Global Convergence: If the objective satisfies the KL property, the BPG sequence has finite length and converges globally to a critical point.The proof treats the iterates as a gradient-like descent sequence and invokes the KL-based convergence theorem.
- Rates: When f and g are semi-algebraic, convergence rates for the generated sequence follow from the corresponding KL rate theorem.The paper states this as a consequence of semi-algebraicity rather than giving the rate in the supplied passage.
5 Application to Quadratic Inverse Problems
The paper applies its Bregman proximal-gradient framework to sparse quadratic inverse problems, including ℓ1 regularization and ℓ0 constraints. It establishes suitable geometry and derives explicit globally convergent update formulas for both models.
- Problem setting: Quadratic inverse problems generalize linear inverse problems through quadratic measurements and include phase retrieval as a special case.The model uses symmetric matrices and possibly noisy measurements to recover x from a quadratic system.
- Problem setting: The proposed application addresses an underdetermined nonconvex model with least-squares data fidelity and a possibly nonsmooth regularizer encoding prior information or constraints.The regularizer may be nonconvex, nonsmooth, and extended valued; θ controls the trade-off between data fidelity and regularization.
- Adapted geometry: The quadratic loss is continuously differentiable but lacks a globally Lipschitz continuous gradient, so classical proximal-gradient methods do not apply directly.The paper instead identifies a function h such that Lh − g is convex, providing the required smooth-adaptable geometry.
- Algorithmic outcome: The resulting algorithms are explicit, straightforward to implement, and presented as globally convergent schemes for the unconstrained ℓ1 and sparsity-constrained ℓ0 models.The paper states that these are, to its knowledge, the first globally convergent schemes for this class of problems; a thorough computational study is deferred to separate work.
- Explicit updates: For the ℓ1-regularized model, the Bregman proximal update combines soft thresholding with a uniquely determined positive scalar t* obtained from a cubic equation.The scalar admits an explicit closed-form formula, making the update explicit.
6 Appendix: Global Convergence for KL Functions
The appendix establishes a general convergence mechanism for bounded gradient-like descent sequences and shows how the KL property upgrades subsequential convergence to convergence of the whole sequence. It also records rate regimes determined by the KL desingularizing exponent.
- Descent framework: The gradient-like descent conditions require sufficient decrease and a subgradient bound linked to the iterates' successive differences.These conditions are presented as the basic ingredients for subsequential convergence.
- Subsequential convergence: A bounded gradient-like descent sequence has a nonempty compact limit set contained in crit F, with F finite and constant on that set.The subsequential convergence result also identifies criticality of limit points.
- KL property: The nonsmooth KL property is the additional assumption used to establish global convergence of the whole sequence.Semi-algebraic functions satisfy the KL property at every point of their domain.
- Global convergence: Under boundedness and the KL property, the sequence has finite length and converges to a critical point of F.Finite length means the sum of successive iterate differences is finite, making the sequence Cauchy.