An Iterative Smoothing Algorithm for Regression with Structured Sparsity

Fouad Hadj‐Selem, Tommy Löfstedt, Vincent Frouin, Vincent Guillemot, Édouard Duchesnay

Abstract

High-dimensional prediction models are increasingly used to analyze biological data such as neuroimaging of genetic data sets. However, classical penalized algorithms yield to dense solutions that are difficult to interpret without arbitrary thresholding. Alternatives based on sparsity-inducing penalties suffer from coefficient instability. Complex structured sparsity-inducing penalties are a promising approach to force the solution to adhere to some domain-specific constraints and thus offering new perspectives in biomarker identification. We propose a generic optimization framework that can combine any smooth convex loss function with: (i) penalties whose proximal operator is known and (ii) with a large range of complex, non-smooth convex structured penalties such as total variation, or overlapping group lasso. The proposed continuation algorithm, called CONESTA, dynamically smooths the complex penalties to avoid the computation of proximal operators. The decreasing sequence of smoothing parameters is dynamically adapted, using the duality gap, in order to maintain the optimal convergence speed towards any globally desired precision with duality gap guarantee.

Introduction

In neuroimaging, researchers often face the challenge of identifying predictive biomarkers within high-dimensional datasets, such as MRI scans containing hundreds of thousands of voxels. While standard regularization techniques like the Lasso ($\ell_1$ penalty) can induce sparsity, they often produce unstable and scattered results that lack biological interpretability. Structured sparsity-inducing penalties, such as Total Variation (TV), offer a solution by encouraging contiguous, smooth regions of activity. However, these penalties are non-smooth and computationally demanding, especially at the scale required for modern medical imaging.

The CONESTA Algorithm: Dynamic Smoothing via Duality Gap

The paper introduces CONESTA (COntinuation with NEsterov smoothing in a Shrinkage Thresholding Algorithm), a novel optimization framework designed to handle complex, non-smooth penalties efficiently. The core innovation lies in its continuation strategy. Instead of using a fixed smoothing parameter ($\mu$), which leads to a trade-off between speed and precision, CONESTA employs a dynamic approach:

  1. Nesterov’s Smoothing: The non-smooth penalty is approximated by a smooth version.
  2. Duality Gap Monitoring: The algorithm calculates the duality gap—a rigorous measure of the distance to the global optimum.
  3. Adaptive Continuation: As the duality gap decreases, the algorithm automatically reduces the smoothing parameter $\mu$. This "sharpening" allows the algorithm to maintain optimal convergence speed throughout the optimization process.
Convergence performance on simulated datasets of size 200x200.

Experimental Validation and Key Results

The authors evaluated CONESTA against several state-of-the-art solvers, including the Excessive Gap Method (EGM), ADMM, and Inexact FISTA, using both simulated data and structural MRI data from the Alzheimer’s Disease Neuroimaging Initiative (ADNI).

Speed and Precision

CONESTA demonstrates a significant advantage in reaching high-precision solutions. On high-dimensional datasets, it was found to be approximately four times faster than Inexact FISTA in reaching a precision of $10^{-3}$. Unlike other methods that may plateau or slow down significantly as they approach the optimum, CONESTA's adaptive smoothing ensures a steady path to high accuracy.

Comparison of convergence speed (time) and iteration count for CONESTA versus competing algorithms.

Biological Stability

Beyond computational efficiency, the use of structured sparsity (TV + $\ell_1$) via CONESTA yielded more stable and interpretable brain maps. In the ADNI dataset, the algorithm successfully identified consistent clusters in the hippocampus and areas of ventricular enlargement—well-known biomarkers for Alzheimer's disease. These regions remained stable across cross-validation folds, whereas non-structured methods produced fragmented and inconsistent signatures.

Conclusion

CONESTA provides a robust and generic framework for high-dimensional regression with structured sparsity. By leveraging the duality gap to drive a continuation strategy, it bridges the gap between computational feasibility and the high precision required for reliable biomarker identification in clinical neuroimaging.

Reference: Hadj-Selem, F., Löfstedt, T., et al. (2018). Continuation of Nesterov’s Smoothing for Regression with Structured Sparsity in High-Dimensional Neuroimaging. IEEE Transactions on Medical Imaging.

Summary updated

Abstract

High-dimensional prediction models are increasingly used to analyze biological data such as neuroimaging of genetic data sets. However, classical penalized algorithms yield to dense solutions that are difficult to interpret without arbitrary thresholding. Alternatives based on sparsity-inducing penalties suffer from coefficient instability. Complex structured sparsity-inducing penalties are a promising approach to force the solution to adhere to some domain-specific constraints and thus offering new perspectives in biomarker identification. We propose a generic optimization framework that can combine any smooth convex loss function with: (i) penalties whose proximal operator is known and (ii) with a large range of complex, non-smooth convex structured penalties such as total variation, or overlapping group lasso. Although many papers have addressed a similar goal, few have tackled it in such a generic way and in the context of high-dimensional data. The proposed continuation algorithm, called \textit{CONESTA}, dynamically smooths the complex penalties to avoid the computation of proximal operators, that are either not known or expensive to compute. The decreasing sequence of smoothing parameters is dynamically adapted, using the duality gap, in order to maintain the optimal convergence speed towards any globally desired precision with duality gap guarantee. First, we demonstrate, on both simulated data and on experimental MRI data, that CONESTA outperforms the excessive gap method, ADMM, proximal gradient smoothing (without continuation) and inexact FISTA in terms of convergence speed and/or precision of the solution. Second, on the experimental MRI data set, we establish the superiority of structured sparsity-inducing penalties ($\ell_1$ and total variation) over non-structured methods in terms of the recovery of meaningful and stable groups of predictive variables.
BibTeX
@misc{hadjselem2016iterative,
  author = {Fouad Hadj‐Selem and Tommy Löfstedt and Vincent Frouin and Vincent Guillemot and Édouard Duchesnay},
  title = {{An Iterative Smoothing Algorithm for Regression with Structured Sparsity}},
  year = {2016},
  eprint = {1605.09658},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1605.09658},
}
Figure