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:
- Nesterov’s Smoothing: The non-smooth penalty is approximated by a smooth version.
- Duality Gap Monitoring: The algorithm calculates the duality gap—a rigorous measure of the distance to the global optimum.
- 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.
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.
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