Source-linked AI summary
Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems
Thomas Pock, Shoham Sabach
TL;DR
The paper addresses nonconvex and nonsmooth optimization with block-separable nonsmooth terms and a smooth coupling function whose gradient may not be globally Lipschitz. It develops inertial PALM, proves convergence to critical points under the KL property, and demonstrates the method on several imaging and factorization problems. The conclusion reports finite-length iterates and numerical viability, while BID modeling remains limited for textured images.
Problem
Nonconvex and nonsmooth problems with block structure require methods that handle block-wise smoothness when the full coupling gradient is not globally Lipschitz.
Method
iPALM extends PALM with Heavy Ball-inspired inertia for block-separable nonsmooth terms and a smooth coupling function with block-Lipschitz gradients.
Results
Under the KL property, iPALM converges to a critical point, has finite-length iterates, and shows viability in numerical experiments on the reported applications.
Takeaways & Limitations
The method provides a convergent inertial block algorithm for the paper’s structured nonconvex problems and is reported to perform better than iPiano in sparse NMF experiments.
Takeaways & Limitations
The BID sparsity-promoting regularizer can be unsuitable for textured images and may make the trivial identity-kernel solution lower-energy than the true solution.
Abstract
from arXiv · showhide
In this paper we study nonconvex and nonsmooth optimization problems with semi-algebraic data, where the variables vector is split into several blocks of variables. The problem consists of one smooth function of the entire variables vector and the sum of nonsmooth functions for each block separately. We analyze an inertial version of the Proximal Alternating Linearized Minimization (PALM) algorithm and prove its global convergence to a critical point of the objective function at hand. We illustrate our theoretical findings by presenting numerical experiments on blind image deconvolution, on sparse non-negative matrix factorization and on dictionary learning, which demonstrate the viability and effectiveness of the proposed method.
1 Introduction
The paper targets structured nonconvex, nonsmooth problems arising in image processing and machine learning, and proposes an inertial PALM variant with convergence guarantees under the KL property. It motivates the method through NMF and blind deconvolution, where block structure and partial Lipschitz continuity support specialized algorithms.
- Motivation: Nonconvex models such as blind image deconvolution motivate efficient algorithms beyond restrictive convex optimization frameworks.The paper identifies blind image deconvolution as inherently nonconvex and emphasizes the need for efficient, simple methods.
- Problem class: The target class minimizes block-separable nonsmooth, nonconvex terms plus a smooth coupling function with block-wise Lipschitz gradients.The coupling gradient need not be globally Lipschitz, although each block gradient is partially Lipschitz continuous.
- Applications: NMF and blind image deconvolution exemplify applications with nonnegativity, sparsity, convolution, and image-regularization constraints.The paper describes sparse NMF for facial-image decomposition and a variational BID model involving an unknown image and blur kernel.
- Prior method: PALM applies proximal forward-backward updates blockwise and, under the KL property, guarantees convergence of the whole sequence to a critical point.This establishes the relevant convergence baseline for the proposed inertial extension.
- Contribution: iPALM adds a Heavy Ball-inspired inertial term to PALM and proves convergence without assuming monotonic objective values.The inertial update incorporates part of the previous direction, while the paper addresses the usual need to restart or remove inertia when function values increase.
- Context: Inertial and accelerated methods connect momentum-based updates with dynamical systems, multistep schemes, conjugate gradients, and improved convex convergence rates.The paper relates Heavy Ball dynamics to friction, multistep gradient combinations, and accelerated-gradient rate improvements from O(1/k) to O(1/k^2).
2 Problem Formulation and Algorithm
The paper formulates block-structured nonconvex, nonsmooth optimization with a smooth coupling term and proposes iPALM, an inertial proximal alternating linearization method. Its blockwise step sizes exploit partial Lipschitz continuity, while inertial parameters connect the method to PALM and iPiano.
- Problem formulation: The objective minimizes F(x)=f1(x1)+f2(x2)+H(x), with extended-valued block functions and a smooth coupling function.The formulation permits separate constraints or regularizers on the variable blocks and extends to any finite number of blocks.
- Problem formulation: Assumption A requires proper lower-semicontinuous block functions, a differentiable coupling function, blockwise C1,1 regularity, and bounded-subset Lipschitz continuity of ∇H.The framework assumes the objective is bounded below and allows constraints through extended-valued functions.
- Algorithm: The proposed iPALM algorithm alternates proximal linearized updates for the two blocks while incorporating inertial extrapolation.Each block uses inertial parameters, step-size parameters, and a proximal update based on the corresponding partial gradient.
- Algorithm: Step sizes are proportional to partial Lipschitz moduli, so larger moduli produce smaller steps and slower iterations.When the moduli are unavailable or difficult to compute, backtracking can estimate them while preserving the convergence results.
- Algorithm: Block-optimized step sizes are reported to yield better numerical performance than non-block-specific choices.The stated advantage is attributed to optimizing step sizes separately for each variable block.
- Algorithm: iPALM recovers PALM when inertial parameters vanish and relates to iPiano in the single-block case.The inertial term is motivated by the Heavy Ball method and adds part of the previous direction to the new direction.
3 Mathematical Preliminaries and Proof Methodology
The convergence analysis uses nonsmooth-analysis tools, proximal-map properties, and the Kurdyka–Łojasiewicz framework. A generic convergence theorem links bounded sequences satisfying descent, subgradient, and criticality conditions to convergence behavior.
- Nonsmooth analysis: Critical points are defined through the limiting subdifferential, with zero belonging to the subdifferential of the objective.This accommodates proper lower-semicontinuous nonsmooth functions that may take the value ∞.
- KL framework: The KL property is expressed using a desingularizing function and provides the central regularity condition for the convergence proof.The paper uses a uniformized KL property on compact sets where the function is constant.
- Proximal mappings: The proximal mapping is nonempty and compact under proper lower-semicontinuity and a finite lower bound, but may be multivalued for nonconvex functions.Indicator functions recover multivalued projection onto closed sets.
- Proximal mappings: The proximal inequality combines Lipschitz-gradient descent with a proximal step to support the analysis of nonconvex nonsmooth updates.A tighter upper bound is available when the nonsmooth term is convex.
- Abstract convergence theorem: For a proper lower-semicontinuous semi-algebraic function, a bounded algorithmic sequence satisfying three abstract conditions has critical limit points and supports convergence analysis.The conditions include a descent relation, a subgradient bound, and criticality of every limit point.
4 Convergence Analysis of iPALM
The convergence proof addresses iPALM’s nonmonotone objective values by introducing an auxiliary function over consecutive iterates. Under assumptions on the functions, boundedness, and inertial parameters, the generated sequence converges to a critical point.
- Proof strategy: iPALM’s objective values need not decrease between successive iterates, so the proof cannot directly verify the abstract descent condition for F.The analysis therefore introduces an auxiliary function whose values decrease along an auxiliary sequence.
- Proof strategy: The auxiliary-function construction enables verification of the abstract descent, subgradient, and criticality conditions required by the KL-based convergence theorem.The proof first establishes these properties for the auxiliary sequence and then transfers convergence to the original sequence.
- Parameter conditions: Assumption B restricts inertial parameters to bounds below one-half of 1−ε in the nonconvex setting.These restrictions are used to obtain positive constants in the descent estimates.
- Parameter conditions: In the convex case, smaller τ parameters and larger step sizes are allowed, with inertial parameters extending to [0,1).This improvement follows from a tighter proximal bound available for convex nonsmooth terms.
- Convergence result: Under Assumptions A and B and boundedness of the generated sequence, every limit point of the auxiliary sequence is critical.The proof uses the closedness of the subdifferential together with the subgradient estimates.
- Convergence result: Theorem 4.1 states that the entire sequence generated by iPALM converges to a critical point of F.This is the paper’s principal theoretical convergence guarantee.
5 Numerical Results
Numerical experiments apply iPALM to sparse NMF, blind image deconvolution, and convolutional LASSO, examining sparsity, inertial parameters, and step-size choices. Across these applications, inertial and dynamically selected parameters often improve convergence or solution quality, although excessive inertia can degrade performance and one BID regularizer has a texture-related limitation.
- 5.1 Non-Negative Matrix Factorization: The sparse NMF experiment decomposes 400 facial images into 25 nonnegative sparse basis faces using an ℓ0 constraint on each basis vector.The two variable blocks are B and C, with nonnegativity and sparsity constraints imposed through efficiently computable proximal mappings.
- 5.1 Non-Negative Matrix Factorization: Smaller sparsity settings produce more compact basis-face representations and might improve the representation’s generalization capabilities.Figure 2 illustrates basis faces under different sparsity settings.
- 5.1 Non-Negative Matrix Factorization: In sparse NMF, inertia can speed convergence, but too-large inertial parameters yield inferior results, while convexity in one nonsmooth block permits twice larger steps.The final objective value can be misleading because the problem is highly nonconvex and may reach a poor stationary point.
- 5.1 Non-Negative Matrix Factorization: Dynamic inertial parameters with block-specific step sizes outperform the other tested NMF settings by a large margin, although this setting is outside the current convergence analysis.The authors identify investigation of convergence for this setting as future work.
- 5.2 Blind Image Deconvolution: For blind image deconvolution, inertial forces produce better recovered images and blur kernels, with dynamic parameters giving the best overall performance.The recovered blur kernel is close to the true kernel, while the recovered image is slightly more piecewise constant than the original.
- 5.3 Convolutional LASSO: In convolutional LASSO, larger inertial parameters consistently improve convergence speed, and dynamic parameter selection clearly outperforms the other tested settings.The experiment learns convolution filters containing stripe-like structures and applies the learned dictionary to denoising.
6 Conclusion
The paper proposes iPALM, an inertial PALM variant for broad nonconvex, nonsmooth problems, and establishes conditions ensuring convergence to a critical point. Under the KL property, the generated iterates have finite length, while experiments report benefits from dynamically chosen parameters.
- iPALM extends PALM with inertia for block-separable nonsmooth, nonconvex functions coupled through a smooth function.
- The analysis gives inertial and step-size bounds that ensure convergence to a critical point.
- Under the Kurdyka-Lojasiewicz property, the generated sequence of iterates has finite length.
- Dynamic inertial and step-size parameters significantly improve convergence speed and convergence to a better critical point in the experiments.
7 Appendix A: Proof of Lemma 4.1
The appendix proves Lemma 7.1 by establishing algebraic conditions under which g equals εδ* and h is at least εδ*. The proof proceeds through direct substitution, simplification, and parameter bounds.
- Lemma 7.1 defines g and h as functions of α, β, δ, τ, and L.
- The lemma assumes bounded α, β, and L, with α constrained below 0.5(1−ε).
- Under the lemma’s conditions, g(α, β, δ*, τ*, L) equals εδ* and h(α, β, δ*, τ*, L) is at least εδ*.
- The proof verifies the equality for g by substituting its definition and simplifying the resulting expression.
- The remaining inequality is obtained through equivalent algebraic manipulation and the stated parameter bounds.