Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems

Thomas Pock, Shoham SabachSIAM J. Imaging sci 2016 · DOI

TL;DR

This paper introduces iPALM, an "inertial" extension of an existing algorithm (PALM) for solving a challenging class of optimization problems that are both nonconvex and nonsmooth. The authors prove that iPALM guarantees convergence to a critical point, and demonstrate its effectiveness on real-world problems like image deconvolution and dictionary learning, often outperforming previous methods.

What Problem Does This Paper Address?

Many real-world problems in machine learning and image processing are modeled by optimization problems that are "nonconvex" and "nonsmooth." This means the objective function we want to minimize has multiple local minima (nonconvex) and may have sharp corners or discontinuities (nonsmooth). Traditional optimization methods often struggle with these properties, getting stuck in suboptimal solutions or failing to converge. While algorithms like Proximal Alternating Linearized Minimization (PALM) have been developed to handle these issues, this paper aims to improve their performance by incorporating an "inertial" component, inspired by the heavy-ball method. This inertial term allows the algorithm to "remember" previous steps, potentially accelerating convergence and helping it escape shallow local minima.

Methods

The core contribution is the Inertial Proximal Alternating Linearized Minimization (iPALM) algorithm. It's an extension of the Proximal Alternating Linearized Minimization (PALM) method. The key innovation is the addition of an "inertial term" to the update steps, which is a weighted combination of the current and previous steps. This is motivated by the heavy-ball method, known for its acceleration properties.

The algorithm works by iteratively updating blocks of variables. For each block, it performs a linearized minimization step with respect to a smooth part of the objective function and a proximal step with respect to a nonsmooth part. The paper provides a rigorous convergence analysis, proving that under certain conditions (specifically, the Kurdyka-Łojasiewicz property), iPALM converges to a critical point of the objective function.

Datasets

The paper evaluates iPALM on three standard datasets/problem settings:

  • ORL database: Used for Non-Negative Matrix Factorization (NMF) experiments, consisting of 400 normalized facial images.
  • Books image: Used for Blind Image Deconvolution (BID) experiments, a 495x323 pixel image.
  • Barbara image: Used for Convolutional LASSO (sparse approximation) experiments, a 512x512 pixel image.

No new datasets were introduced.

Key Insights and Ideas

  • Inertia for Nonconvexity: The paper demonstrates that adding an inertial term, inspired by methods for convex optimization, can be beneficial even for nonconvex and nonsmooth problems. This suggests that inertia can help navigate complex objective landscapes.
  • Block-wise Approach: The algorithm's effectiveness stems from its ability to exploit the block structure of the problem, allowing for tailored step-sizes and potentially faster convergence compared to methods that treat the problem as a whole.
  • Dynamic Parameter Tuning: Numerical experiments suggest that dynamically adjusting the inertial parameters (rather than keeping them fixed) can lead to significant performance improvements, though the theoretical convergence analysis for this dynamic setting is left for future work.
  • Convergence Guarantees: The theoretical analysis provides strong convergence guarantees to a critical point, which is a significant achievement for nonconvex optimization.

Key Results

  • Convergence Proof: The paper provides a theoretical proof of global convergence for iPALM to a critical point of the objective function, provided the problem satisfies the Kurdyka-Łojasiewicz property.
  • Numerical Performance:
    • NMF: iPALM showed competitive performance, with a dynamic choice of inertial parameters yielding good results.
  • Blind Image Deconvolution (BID): iPALM significantly outperformed the version without inertial terms (PALM). The best results were achieved with a dynamic choice of inertial parameters.
  • Convolutional LASSO: Similar to BID, dynamic inertial parameters led to the best performance.
  • Comparison to iPiano: iPALM generally performed better than the iPiano algorithm (a related single-block inertial method), especially in terms of CPU time, due to iPALM's ability to leverage block structure and avoid computationally expensive backtracking for Lipschitz constant estimation.

Limitations and Future Work

  • Theoretical Support for Dynamic Parameters: The current convergence theory does not fully support the observed benefits of dynamically chosen inertial parameters. The authors suggest that developing a more general convergence theory for this setting is an interesting direction for future research.
  • Choice of Inertial Parameters: While dynamic parameter selection showed promise, the paper doesn't offer a definitive method for choosing these parameters a priori.
  • "Bad" Stationary Points: The paper notes that for highly nonconvex problems, the final value of the objective function can be misleading, potentially corresponding to a "bad" stationary point. While iPALM converges to a critical point, it doesn't guarantee convergence to the global minimum.

Summary updated

BibTeX
@article{pock2016inertial,
  author = {Thomas Pock and Shoham Sabach},
  title = {{Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems}},
  journal = {SIAM J. Imaging sci},
  year = {2016},
  doi = {10.1137/16m1064064},
}
Figure