Source-linked AI summary
iPiano: Inertial Proximal Algorithm for Non-Convex Optimization
Peter Ochs, Yunjin Chen, Thomas Brox, Thomas Pock
TL;DR
The paper addresses minimization of a smooth, possibly non-convex function plus a convex, possibly non-smooth function. It proposes iPiano, combining forward-backward splitting with inertia, and proves convergence under the Kurdyka-Lojasiewicz property, with applications to denoising and image compression.
Problem
The paper studies how to efficiently solve non-convex, non-smooth composite optimization problems.
Method
iPiano combines forward-backward splitting with an inertial force for objectives consisting of smooth f and convex g.
Results
The analysis proves convergence of the whole iPiano sequence to a unique stationary point under the Kurdyka-Lojasiewicz property, with experimental applications to denoising and image compression.
Takeaways & Limitations
iPiano provides a convergence-analyzed inertial method for the proposed non-convex composite problems and achieves state-of-the-art performance in the reported experiments.
Takeaways & Limitations
The inertial term prevents monotonically decreasing function values, and the objective is assumed to have a smooth-plus-convex composite structure.
Abstract
from arXiv · showhide
In this paper we study an algorithm for solving a minimization problem composed of a differentiable (possibly non-convex) and a convex (possibly non-differentiable) function. The algorithm iPiano combines forward-backward splitting with an inertial force. It can be seen as a non-smooth split version of the Heavy-ball method from Polyak. A rigorous analysis of the algorithm for the proposed class of problems yields global convergence of the function values and the arguments. This makes the algorithm robust for usage on non-convex problems. The convergence result is obtained based on the \KL inequality. This is a very weak restriction, which was used to prove convergence for several other gradient methods. First, an abstract convergence theorem for a generic algorithm is proved, and, then iPiano is shown to satisfy the requirements of this theorem. Furthermore, a convergence rate is established for the general problem class. We demonstrate iPiano on computer vision problems: image denoising with learned priors and diffusion based image compression.
1. Introduction.
The paper introduces iPiano for non-convex, non-smooth objectives formed by a smooth function and a convex function. It combines forward-backward splitting with inertia and establishes convergence under the Kurdyka-Lojasiewicz property.
- iPiano targets objectives f + g where f is smooth and possibly non-convex, while g is convex and possibly non-smooth.
- The method combines a forward gradient step, an inertial term, and a backward proximal step.
- The inertial term prevents monotonically decreasing function values, unlike forward-backward splitting with β = 0.
- The convergence analysis establishes convergence of function values, a converging subsequence of arguments, and criticality of every limit point.
- Under the Kurdyka-Lojasiewicz inequality, the whole sequence converges to a unique limit point.
- The experiments apply iPiano to computer-vision tasks including denoising and image compression.
2. Related Work.
The related work connects iPiano to forward-backward splitting and inertial optimization methods. It emphasizes extensions of these approaches from convex or smooth settings toward non-convex and nonsmooth problems.
- Forward-backward splitting: Forward-backward splitting is a simple splitting approach that separates a gradient-like forward step from a proximal backward step.
- Forward-backward splitting: Its appeal for non-convex problems comes from its simplicity and special cases such as gradient projection.
- Forward-backward splitting: Prior inexact forward-backward analyses require explicit decrease of function values, whereas this paper does not consider erroneous estimates.
- Optimization with inertial forces: Polyak’s Heavy-ball method accelerates gradient descent through a two-step scheme with an inertial term.
- Optimization with inertial forces: Heavy-ball and Nesterov acceleration differ in where gradients are evaluated, despite similar behavior on strongly convex functions.
- Optimization with inertial forces: Heavy-ball methods have been generalized to smooth non-convex functions and maximal monotone operators.
3. An abstract convergence result.
The paper develops an abstract convergence theorem for two-step descent sequences under sufficient decrease, relative error, continuity, and the Kurdyka–Łojasiewicz property. Under these conditions, the sequence has finite length and converges to a critical point.
- Framework: The Kurdyka–Łojasiewicz property bounds subgradients below through a function-value reparametrization and includes real semi-algebraic functions as a broad class.In smooth settings, the condition corresponds to a reparametrized sharpness property.
- Framework: The abstract framework studies sequences z_n=(x_n,x_{n−1}) generated in R^2N for proper lower-semicontinuous functions, targeting critical points satisfying 0 ∈ ∂F(x*).The limiting subdifferential generalizes the convex subdifferential to non-convex, non-smooth problems.
- Convergence theorem: Under the abstract theorem, the sequence converges to a diagonal point (x̄,x̄), and its limit is critical for F when the continuity condition H3 holds.The theorem is obtained from the preceding lemmas and corollaries for sequences satisfying H1–H3.
- Caveat: Without H3, the limit point need not be critical because the limiting subdifferential requires F(z_n) → F(z̄).With H3, the function values converge to the limit value and criticality follows.
- Conditions: The convergence theorem assumes H1 sufficient decrease, H2 relative error, and H3 continuity, with a KL property at the relevant cluster point.The conditions are formulated for a two-step sequence and differ from earlier one-step descent conditions.
4. The proposed algorithm - iPiano.
iPiano targets structured non-smooth non-convex objectives by combining forward-backward splitting with an inertial force. Under suitable step-size and regularity conditions, its iterates converge to critical points, including for semi-algebraic objectives.
- Problem: The problem minimizes h = f + g, where f is C1-smooth with Lipschitz gradient and g is proper, lower semi-continuous, convex, and proximable.The objective h is also required to be coercive and bounded below.
- Algorithm: iPiano combines a gradient forward step, an inertial term weighted by β_n, and a proximal backward step weighted by α_n.The forward step uses ∇f, while the backward step applies the proximity operator of g.
- Step-size rules: Step sizes may be fixed or adapted through backtracking, with parameter rules constrained by the Lipschitz estimates and inertial weights.The constant-parameter scheme requires β ∈ [0, 1) and α < 2(1 − β)/L; variable-step rules adapt parameters when L_n changes.
- Convergence analysis: A majorizing function decreases monotonically even though iPiano's objective values need not, providing the Lyapunov-style mechanism for convergence analysis.The inertial term prevents monotonic decrease of the function values, but the constructed majorizing function retains descent.
- Convergence analysis: Under the stated theorem and the Kurdyka-Lojasiewicz property, the iterates have finite length, converge to x∗, and x∗ is a critical point of h.For semi-algebraic h, the required Kurdyka-Lojasiewicz property holds and the same finite-length convergence conclusion follows.
5. Numerical experiments.
The experiments evaluate iPiano on non-convex optimization examples, learned-prior image denoising, and diffusion-based image compression. Across these settings, inertia helps avoid spurious stationary points and reduce iterations, while performance varies by model and accuracy target.
- Ability to overcome spurious stationary points: In a two-dimensional non-convex example, β = 0 is attracted to nearby stationary points, whereas inertia helps iPiano overcome spurious ones.The objective has four stationary points, and the inertial term can remain effective when the gradient vanishes.
- Student-t regularized image denoising: With a proper inertial term, iPiano takes significantly fewer iterations than without inertia, with β ≈ 0.8 generally effective in practice.For MRF-ℓ2, L-BFGS is slightly faster at moderate accuracy, while iPiano's gap increases at high accuracy; for MRF-ℓ1, the comparison reverses.
- Linear diffusion based image compression: In diffusion-based image compression, iPiano reaches lower energy in 1000 iterations, compared with 200 × 4000 iterations required by Successive PD.The lower energy indicates better minimization of the stated non-convex problem, while final compression results trade slightly lower density for slightly worse MSE.
- Overview: The paper proposes iPiano for objectives formed by a smooth possibly non-convex term and a convex possibly non-smooth term, combining forward-backward splitting with Heavy-ball ideas.The experiments demonstrate applicability to learned-prior denoising and diffusion-based image compression.
6. Conclusions.
The analysis establishes convergence properties for iPiano, including whole-sequence convergence under the Kurdyka–Łojasiewicz property and a rough convergence-rate bound. Experiments demonstrate applicability to denoising and diffusion-based image compression, including optimal-mask computation.
- Theoretical convergence: Under the Kurdyka–Łojasiewicz property, the whole iPiano sequence converges to a unique stationary point.Without this property, the analysis establishes convergence of function values, boundedness of the argument subsequence, and criticality of every limit point.
- Convergence rate: O(1/n) is a rough upper bound for the squared proximal residual, while experiments show a much faster convergence rate.
- Applications: iPiano achieved state-of-the-art performance in denoising and image compression experiments.For image compression, it computed an optimal mask for a Laplacian PDE-based compression method.
- Conclusion: The paper characterizes iPiano as having favorable theoretical properties while being simple and efficient.