Median Selection Subset Aggregation for Parallel Inference

Xiangyu Wang, Peichao Peng, David B. DunsonNeurIPS 2014

TL;DR

The "message" algorithm (MEdian Selection Subset AGgregation) is a communication-efficient framework for performing high-dimensional regression and classification on massive datasets. By performing feature selection on data subsets in parallel and then taking the "median" of those selections, it achieves the statistical accuracy of full-dataset analysis with a fraction of the computational cost and almost zero communication overhead.

The Distributed Computing Bottleneck

In the era of "Big Data," we often have more information than a single machine can process. The standard solution is distributed computing, but this introduces a major bottleneck: communication costs.

Most distributed algorithms require machines to "talk" to each other at every iteration of an optimization process (e.g., sharing gradients). This back-and-forth is slow. A faster alternative is to process data subsets completely independently and combine the results at the very end. However, for "sparse" problems (where we want to select only the most important features), simple averaging doesn't work well—it often results in a "noisy" model that includes too many irrelevant variables. The authors seek a method that is "embarrassingly parallel" (minimal communication) but still statistically rigorous and accurate.

The "message" Algorithm

The authors propose the MEdian Selection Subset AGgregation Estimator (message). The algorithm follows a clever two-stage process:

  1. Parallel Selection & Median Voting: The data is split into $m$ subsets. Each machine independently performs feature selection (using Lasso or a Generalized Information Criterion) on its subset. These selections are sent to a central machine, which calculates the "median model"—a feature is included in the final model only if it was selected by more than 50% of the subsets.
  2. Parallel Estimation & Averaging: The "median model" is sent back to the machines. Each machine then estimates the coefficients (weights) for only those selected features using its local data. Finally, these coefficient estimates are averaged to produce the final output.

This approach is novel because it separates the selection of variables (using a robust median) from the estimation of their values (using a simple average), significantly reducing the influence of outliers and "heavy-tailed" noise.

Experimental Validation

The paper evaluates the algorithm using both synthetic simulations and massive real-world datasets:

  • Synthetic Data: Linear and logistic regression models with up to 10,000 features, testing both normal and heavy-tailed (t-distributed) error terms.
  • Individual Household Electric Power Consumption: A regression task involving over 2 million measurements and 74 predictors to predict power usage.
  • HIGGS Classification: A massive particle physics dataset from the UCI repository with 11 million samples and 27 features, used to distinguish between two classes of particles.

Key Insights

  • The Power of the Median: The authors prove that using the median for feature selection isn't just a heuristic; it actually improves the convergence rate. In the presence of heavy-tailed noise (outliers), the median model converges to the "true" model at an exponential rate, whereas standard methods on the full dataset only converge at a polynomial rate.
  • Communication Efficiency: The algorithm only requires two rounds of communication: one to collect feature indicators and one to redistribute the final model. This makes it ideal for distributed systems where network latency is high.
  • Robustness by Design: Because the median ignores the "extremes," a few subsets containing bad data or extreme outliers won't ruin the final model selection.

Key Results

Performance comparison of message against other methods
  • Accuracy: In synthetic tests, message consistently achieved a lower Mean Square Error (MSE) and a higher probability of selecting the correct features compared to simple subset averaging or even full-dataset Lasso in some noisy scenarios.
  • Speed: On the HIGGS dataset (11M samples), message adapted to the prediction bound much faster than competitors. On the power consumption data, it dominated other algorithms in both speed and accuracy.
  • Scalability: Unlike "Bolasso" (Bootstrap Lasso), which is computationally expensive, message scales efficiently as the sample size increases because the workload is distributed and the communication remains constant.

Limitations and Future Work

  • Model Specificity: The current theoretical proofs and experiments focus primarily on linear and logistic regression. While the authors suggest the "geometric median" could extend this to more complex models, those applications aren't explored in detail here.
  • Partitioning Sensitivity: The performance depends on choosing an appropriate number of subsets ($m$). If subsets are too small, the local feature selection might become unreliable.
  • Future Directions: The authors suggest extending the "message" framework to online learning (streaming data) and exploring more general "normed model spaces" for the median calculation.

Summary updated

BibTeX
@inproceedings{wang2014median,
  author = {Xiangyu Wang and Peichao Peng and David B. Dunson},
  title = {{Median Selection Subset Aggregation for Parallel Inference}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure