Abstract: Group-Lasso (gLasso) identifies important explanatory factors in predicting the response variable by considering the grouping structure over input variables. However, most existing algorithms for gLasso are not scalable to deal with large-scale datasets, which are becoming a norm in many applications. In this paper, we present a divide-and-conquer based parallel algorithm (DC-gLasso) to scale up gLasso in the tasks of regression with grouping structures. DC-gLasso only needs two iterations to collect and aggregate the local estimates on subsets of the data, and is provably correct to recover the true model under certain conditions. We further extend it to deal with overlappings between groups. Empirical results on a wide range of synthetic and real-world datasets show that DC-gLasso can significantly improve the time efficiency without sacrificing regression accuracy.
Introduction
In high-dimensional regression problems, variables often possess a natural grouping structure—such as dummy variables representing a single categorical factor or multiple sensors in a single EEG device. Group-Lasso (gLasso) is the standard tool for these problems as it encourages "group-wise" sparsity, selecting or discarding entire blocks of variables simultaneously.
However, as datasets grow into the "Big Data" regime, traditional gLasso solvers (like coordinate descent) hit a performance wall. These algorithms are typically designed for single-machine execution; parallelizing their individual iterations requires constant communication between nodes, creating a massive network bottleneck. The authors address this by proposing DC-gLasso (Divide-and-Conquer Group-Lasso), a communication-efficient method designed for distributed systems where network latency is high.
The DC-gLasso Algorithm
DC-gLasso breaks the regression problem into two distinct, communication-efficient stages:
- The Model Selection Stage: The dataset is partitioned into $m$ shards across different machines. Each machine independently runs a standard gLasso solver on its local data to identify important groups. These local results are sent to a master node for majority voting: a group is included in the final model only if at least half of the machines selected it. This voting process acts as a robust filter against local noise.
- The Coefficient Estimation Stage: Once the global sparse pattern is determined, machines perform a simple Ordinary Least Squares (OLS) regression using only the selected variables. The final coefficients are obtained by averaging these local OLS estimates.
The paper also introduces an extension for Overlapping Group-Lasso, utilizing a "select-and-discard" strategy with a "security check" to ensure the final selected features form a valid union of groups consistent with the overlapping structure.
Key Results and Discussion
The researchers evaluated DC-gLasso using synthetic datasets (up to 3,000 features and 1,000 groups) and the real-world MEMset Donor bioinformatics dataset.
As illustrated in Figure 4, DC-gLasso achieves near-constant scaling. While the computation time for the standard "Fullset" gLasso grows significantly with data size, DC-gLasso's time remains nearly flat as more machines are added to handle the load. On the MEMset Donor dataset, this translated to a reduction in training time from 151 seconds to just 50 seconds using 5 machines.
Beyond speed, DC-gLasso often improves accuracy. Standard gLasso estimates are biased because the $L_2$ penalty shrinks coefficients toward zero. By using OLS in the second stage, DC-gLasso "debiases" the estimates. Figure 2 demonstrates that this approach consistently achieves a lower Mean Square Error (MSE) than the full-set gLasso across various scenarios.
Conclusion
DC-gLasso offers a scalable solution for group-structured regression by minimizing communication to just two rounds. While its theoretical consistency relies on each machine having a sufficient sample size ($n/m$), its empirical performance shows it to be a fast and accurate alternative to traditional solvers. Future work may extend this framework to non-linear models, such as Cox proportional hazards or non-parametric models.
Summary updated