Efficient Algorithm for Extremely Large Multi-task Regression with Massive Structured Sparsity
This work addresses computational bottlenecks for researchers and practitioners dealing with high-dimensional data requiring millions of sparsity patterns, though it is incremental as it builds on existing optimization methods.
The paper tackles the scalability challenge in multi-task regression with massive structured sparsity by proposing a hierarchical group-thresholding algorithm that screens out irrelevant constraints efficiently, achieving significant speed-ups in experiments on simulation datasets and a genetic variant detection application.
We develop a highly scalable optimization method called "hierarchical group-thresholding" for solving a multi-task regression model with complex structured sparsity constraints on both input and output spaces. Despite the recent emergence of several efficient optimization algorithms for tackling complex sparsity-inducing regularizers, true scalability in practical high-dimensional problems where a huge amount (e.g., millions) of sparsity patterns need to be enforced remains an open challenge, because all existing algorithms must deal with ALL such patterns exhaustively in every iteration, which is computationally prohibitive. Our proposed algorithm addresses the scalability problem by screening out multiple groups of coefficients simultaneously and systematically. We employ a hierarchical tree representation of group constraints to accelerate the process of removing irrelevant constraints by taking advantage of the inclusion relationships between group sparsities, thereby avoiding dealing with all constraints in every optimization step, and necessitating optimization operation only on a small number of outstanding coefficients. In our experiments, we demonstrate the efficiency of our method on simulation datasets, and in an application of detecting genetic variants associated with gene expression traits.