Source-linked AI summary
An inertial Tseng's type proximal algorithm for nonsmooth and nonconvex optimization problems
Radu Ioan Bot, Ernö Robert Csetnek
TL;DR
The paper addresses convergence of proximal algorithms for minimizing a nonsmooth function plus a smooth one without convexity. It studies an inertial forward-backward-forward method with a Bregman-distance backward step, and establishes convergence when an appropriate regularization satisfies the KL property, including for semi-algebraic objectives.
Problem
The paper studies how to obtain convergence guarantees for proximal-type optimization of a nonsmooth function plus a smooth function without assuming convexity.
Source: §1 · pp. 1–2Method
Results
Convergence is guaranteed under mild assumptions when an appropriate regularization of the objective is a KL function, including the semi-algebraic case.
Source: §1 · p. 2, §3 · pp. 11, 13Takeaways & Limitations
The convergence result covers nonsmooth nonconvex problems with semi-algebraic objectives as a particular instance.
Source: §1 · p. 2
Abstract
from arXiv · showhide
We investigate the convergence of a forward-backward-forward proximal-type algorithm with inertial and memory effects when minimizing the sum of a nonsmooth function with a smooth one in the absence of convexity. The convergence is obtained provided an appropriate regularization of the objective satisfies the Kurdyka-\L{}ojasiewicz inequality, which is for instance fulfilled for semi-algebraic functions.
1 Introduction
Proximal splitting methods are well established in the convex setting, while extending their convergence guarantees to nonconvex problems remains challenging. This paper studies an inertial forward-backward-forward method with a Bregman-based backward step and establishes convergence under a Kurdyka-Lojasiewicz condition on a regularized objective.
1 Introduction
- In the convex setting, forward-backward, forward-backward-forward, and FISTA are among the available proximal-type splitting methods.Splitting evaluates the smooth term through its gradient and the nonsmooth term through its proximal operator.Source: §1 · p. 1
- Nonconvex convergence results for proximal-point and forward-backward schemes use the Kurdyka-Lojasiewicz property, which includes semi-algebraic functions.The motivation includes optimization problems involving the counting norm, which is semi-algebraic.Source: §1 · p. 2
- An inertial forward-backward method had previously been proposed under a KL regularization condition and the additional assumption that the nonsmooth function is convex.The present work investigates the forward-backward-forward algorithm in the full nonconvex setting.Source: §1 · p. 2
- Convergence of the proposed forward-backward-forward algorithm is guaranteed under mild assumptions when an appropriate regularization of the objective satisfies the Kurdyka-Lojasiewicz property.The paper also treats semi-algebraic objectives as a particular instance.Source: §1 · p. 2
- The backward step replaces the squared norm in the standard proximal operator with the Bregman distance of a strongly convex, differentiable function.The scheme also uses the previous two iterates through an inertial term.Source: §1 · p. 2
2 Preliminaries
The preliminaries set out the nonsmooth-analysis tools and sequence results used in the convergence proof. They introduce the limiting subdifferential, the KL property and its uniformized form, and basic convergence lemmas.
2 Preliminaries
- The limiting subdifferential is defined through limits of Fréchet subgradients along sequences whose points and function values converge.For convex functions, the Fréchet and limiting subdifferentials coincide with the convex subdifferential; the limiting subdifferential also has a stated graph-closedness criterion.Source: §2 · p. 3
- The nonsmooth Fermat rule states that a local minimizer has zero in its limiting subdifferential.For a continuously differentiable function, the limiting subdifferential is its gradient, and the sum rule adds that gradient to the subdifferential of the nonsmooth term.Source: §2 · p. 3
- The KL property requires a local inequality involving a concave desingularizing function near points in the domain of the subdifferential.Functions satisfying the property at every such point are called KL functions; the text lists semi-algebraic and real sub-analytic functions among examples.Source: §2 · p. 4
- On a compact set where a function is constant and satisfies the KL property at every point, the uniformized KL result supplies common inequality parameters and a desingularizing function.This is the uniformized property used in the convergence analysis.Source: §2 · p. 4
- A bounded-below sequence whose successive decreases dominate nonnegative terms converges, and the sum of those terms is finite.A second sequence lemma gives summability under a two-step recurrence with summable errors and coefficients whose sum is less than one.Source: §2 · pp. 4–5
3 An inertial forward-backward-forward algorithm
The section develops an inertial forward-backward-forward scheme with a Bregman-distance backward step and analyzes its convergence in the nonconvex setting. Under coercivity, suitable parameter choices, and a KL condition on a regularized objective, both generated sequences converge to a common critical point.
Relations to other algorithms
- If α=0, the scheme extends the classical Tseng-type algorithm to the nonconvex setting.The inertial scheme’s relation to the convex setting is also compared with [13].Source: §3 · p. 6
- When h=0, the scheme becomes an inertial proximal-point algorithm with memory for finding critical points of f.Removing inertia gives the KL-function proximal-point setting considered in.Source: §3 · p. 6
Descent conditions
- The objective-plus-step term obeys a descent inequality, and the objective values along p_n converge.The inequality bounds (f + h)(p_n) + M1∥x_n − p_n∥2 by the preceding iterate’s corresponding term with M2.Source: §3 · pp. 6–8
- The convergence analysis requires parameters for which the descent constants satisfy M1 > M2.Lemma 6 chooses λ and α to ensure this strict inequality.Source: §3 · p. 8
Cluster-point properties
- Under coercivity, (p_n) is bounded and has a nonempty cluster set, and each cluster point is critical for f+h.The objective also takes the same limiting value at every cluster point.Source: §3 · pp. 9–10
- The cluster points of the paired sequence (p_n, x_n) lie on the diagonal and correspond to critical points of f+h.They are characterized as critical points of H.Source: §3 · p. 10
Convergence under the KL property
- With f+h coercive, parameters chosen as in Lemma 6, and H a KL function, both sequences converge to the same critical point.Here H(x, y) = (f + h)(x) + M2∥x − y∥2.Source: §3 · pp. 11, 13