A Highly-Efficient Group Elastic Net Algorithm with an Application to Function-On-Scalar Regression

Tobia Boschi, Matthew Reimherr, Francesca ChiaromonteNeurIPS 2021 · OpenReview

In the era of "big data," researchers frequently encounter datasets where the number of features ($p$) vastly exceeds the number of observations ($n$). This challenge is especially pronounced in fields like genomics, where a single study might track millions of genetic markers. To make matters more complex, the collected data is often "functional"—such as a child's growth curve over several years, rather than a single static height measurement.

To address these challenges, researchers have introduced fgen (Functional Group Elastic Net), a novel optimization algorithm designed to handle massive, complex datasets with unprecedented speed.

The Challenge: High Dimensionality Meets Functional Data

Traditional regression models often struggle with two specific hurdles:

  1. Ultra-High Dimensionality: When analyzing millions of potential predictors (like SNPs in a genome), standard optimization algorithms become prohibitively slow.
  2. Functional Responses: In many modern applications, the outcome is a curve or a function rather than a single number. Analyzing how scalar predictors affect an entire curve is known as function-on-scalar regression.

Existing methods either cannot scale to millions of features or remain computationally inefficient because they fail to fully exploit the underlying mathematical structure of the problem.

A Highly-Efficient Solution

The core innovation of fgen is the Semi-smooth Newton Augmented Lagrangian (SsNAL) algorithm. It tackles the problem through several key mechanisms:

  • Group Elastic Net: The model utilizes a penalty that combines the "Group Lasso" (which selects or discards entire groups of variables together) and "Ridge Regression" (which handles highly correlated features).
  • Exploiting Sparsity: The algorithm capitalizes on the fact that the second-order information (the Hessian matrix) used during optimization is extremely sparse. By solving the resulting linear systems using Cholesky factorization and the Sherman-Morrison-Woodbury formula, fgen drastically reduces the required calculations.
  • Functional Principal Components (FPC): To handle curves, the algorithm projects the functional data into a lower-dimensional space using FPC. This transforms a complex curve-fitting problem into a structured group-selection problem that the SsNAL algorithm can solve efficiently.
True vs. Estimated Coefficient Curves
A Highly-Efficient Group Elastic Net Algorithm with an Application to Function-On-Scalar Regression, page 8 This figure illustrates the algorithm's ability to recover true underlying signals. The right panel shows how the 'estimated' coefficient curves (dashed lines) closely match the 'true' curves (solid lines) even in noisy settings.

Key Insights and Performance Gains

The performance gains achieved by fgen are substantial, particularly in sparse, high-dimensional scenarios. The authors evaluated their method using both large-scale synthetic data (with up to $10^5$ features) and real-world data from the INSIGHT study, a Genome-Wide Association Study (GWAS) on childhood obesity.

  • Second-Order Efficiency: While popular solvers like glmnet use first-order coordinate descent, fgen successfully implements a second-order (Newton-type) method that exploits sparsity. This allows it to achieve "super-linear" convergence, reaching the correct answer in far fewer iterations.
  • Speed and Scalability: fgen consistently proved to be the fastest solver. It was approximately 6 times faster than glmnet (which is written in highly optimized Fortran) and more than 30 times faster than sklearn. Furthermore, while other functional regression methods often fail when $p > 10^4$, fgen easily handled $p = 10^5$ and beyond.
  • Biological Discovery: In the INSIGHT study, fgen successfully identified a specific SNP (rs79187646) associated with childhood obesity growth trajectories. This result aligns with previous medical literature but was achieved without the need for heavy pre-screening of variables.
CPU Time Comparisons
A Highly-Efficient Group Elastic Net Algorithm with an Application to Function-On-Scalar Regression, page 8 CPU time comparisons across different solvers. Note how column 'a' (fgen) consistently outperforms 'b' (sklearn) and 'c' (glmnet), especially as the number of features ($p$) and observations ($n$) increase.

Limitations and Future Directions

While fgen represents a significant leap forward, the authors note a few limitations. The current implementation assumes all groups of variables have the same size ($k$), whereas real-world data often features varying group sizes. Additionally, the model is currently restricted to "function-on-scalar" regression; future work aims to extend this to "function-on-function" regression, where the predictors themselves are also curves. Finally, the advanced mathematics behind SsNAL are more complex to implement than standard coordinate descent, which may present a learning curve for integration into simpler software packages.

Summary updated

Abstract

Feature Selection and Functional Data Analysis are two dynamic areas of research, with important applications in the analysis of large and complex data sets. Straddling these two areas, we propose a new highly efficient algorithm to perform Group Elastic Net with application to function-on-scalar feature selection, where a functional response is modeled against a very large number of potential scalar predictors. First, we introduce a new algorithm to solve Group Elastic Net in ultra-high dimensional settings, which exploits the sparsity structure of the Augmented Lagrangian to greatly reduce the computational burden. Next, taking advantage of the properties of Functional Principal Components, we extend our algorithm to the function-on-scalar regression framework. We use simulations to demonstrate the CPU time gains afforded by our approach compared to its best existing competitors, and present an application to data from a Genome-Wide Association Study on childhood obesity.
BibTeX
@inproceedings{boschi2021highly,
  author = {Tobia Boschi and Matthew Reimherr and Francesca Chiaromonte},
  title = {{A Highly-Efficient Group Elastic Net Algorithm with an Application to Function-On-Scalar Regression}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=U7M1yp1vJ8},
}
Figure