Inertial Block Proximal Methods for Non-Convex Non-Smooth Optimization

Hien Le, Nicolas Gillis, Panagiotis PatrinosICML 2020 · OpenReview

This paper introduces a more flexible and efficient way to speed up optimization for complex, real-world problems like data mining and image processing. By bringing the power of "momentum" (inertia) to block coordinate descent, the authors propose methods that bypass the computationally expensive "restarting" steps required by previous state-of-the-art algorithms.

The Challenge: Non-Convex, Non-Smooth Optimization

Many machine learning tasks, such as Non-negative Matrix Factorization (NMF) or sparse dictionary learning, involve optimization problems that are both non-convex (having many local minima) and non-smooth (containing "kinks" or constraints).

A common strategy for these problems is Block Coordinate Descent (BCD), where you update one set of variables (a "block") while keeping others fixed. To speed this up, researchers often add "inertia" or momentum—similar to how a ball rolling down a hill gains speed. However, in non-convex settings, adding inertia is risky because it can cause the algorithm to diverge. To prevent this, existing methods usually require a "restarting" step: checking if the objective function actually decreased and resetting the momentum if it didn't. This check is computationally expensive and slows down progress.

Proposed Methods: IBP and IBPG

The authors introduce two main algorithms to solve this bottleneck:

  1. IBP (Inertial Block Proximal): An inertial version of the proximal BCD method using one extrapolation point.
  2. IBPG (Inertial Block Proximal Gradient): An inertial version of the proximal gradient BCD method.

The "Secret Sauce"

  • Two Extrapolation Points: In IBPG, the algorithm can use one point to evaluate the gradient and a different point to add the inertial force. This added flexibility allows the algorithm to take more aggressive, efficient steps.
  • No Restarts: Through rigorous mathematical analysis using the Kurdyka-Łojasiewicz (KL) property, the authors prove that their methods converge to a critical point without needing to check for objective decrease at every step.
  • Bregman Divergence: The methods are formulated using Bregman divergences, a generalization of standard Euclidean distance. This makes the algorithms applicable to a wider variety of geometry-specific constraints.
  • Flexible Updates: Blocks can be updated cyclically or randomly. The algorithm also allows for "accelerated" versions (like IBPG-A) where a single block is updated multiple times before switching to the next.

Experimental Setup

The researchers evaluated their methods on two types of data:

  • Synthetic Data: Randomly generated low-rank matrices used to test convergence speed and accuracy in a controlled environment.
  • Real-World Hyperspectral Images: The Urban and San Diego datasets, which are standard benchmarks in remote sensing where the goal is "unmixing" (identifying the materials present in each pixel of a satellite image).

Key Insights and Results

The empirical results strongly suggest that using two extrapolation points is significantly more effective than the single-point extrapolation used in older methods like iPALM. Furthermore, repeating the update for a specific block significantly reduces the cost of gradient evaluations, leading to much faster wall-clock times.

The authors compared their accelerated method, IBPG-A, against several heavyweights, including A-HALS (a standard NMF workhorse) and iPALM.

  • Superior Speed: On synthetic datasets, IBPG-A reached lower error levels significantly faster than all competitors. It often achieved a relative error of $10^{-7}$ while others were still at $10^{-4}$ or $10^{-5}$ in the same timeframe.
Convergence speed comparison showing IBPG-A outperforming competitors.
  • Better Solutions: In the hyperspectral image tests, IBPG-A consistently found lower final objective values (better reconstructions) than the state-of-the-art E-A-HALS and APGC algorithms.
Table comparing mean error and standard deviation across algorithms, highlighting IBPG-A's superior performance.
  • Robustness: Because it doesn't require restarts, the algorithm's trajectory is smoother and more computationally predictable.

Limitations and Future Work

While highly effective, the performance of these methods still depends on choosing inertial parameters ($\alpha, \beta, \gamma$) effectively. Additionally, while the framework supports various Bregman divergences, the experiments primarily focused on the standard Euclidean case (Frobenius norm). Exploring other divergences, like those suited for Kullback-Leibler loss, is a promising future direction. Finally, further work could explore how these inertial methods scale to massive, "big data" tensor decompositions.

Summary updated

Abstract

We propose inertial versions of block coordinate descent methods for solving non-convex non-smooth composite optimization problems. Our methods possess three main advantages compared to current sta...
BibTeX
@inproceedings{le2020inertial,
  author = {Hien Le and Nicolas Gillis and Panagiotis Patrinos},
  title = {{Inertial Block Proximal Methods for Non-Convex Non-Smooth Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=EeQP3mNjR36},
}
Figure