Median Selection Subset Aggregation for Parallel Inference

Abstract

For massive data sets, efficient computation commonly relies on distributed algorithms that store and process subsets of the data on different machines, minimizing communication costs. Our focus is on regression and classification problems involving many features. A variety of distributed algorithms have been proposed in this context, but challenges arise in defining an algorithm with low communication, theoretical guarantees and excellent practical performance in general settings. We propose a MEdian Selection Subset AGgregation Estimator (message) algorithm, which attempts to solve these problems. The algorithm applies feature selection in parallel for each subset using Lasso or another method, calculates the `median' feature inclusion index, estimates coefficients for the selected features in parallel for each subset, and then averages these estimates. The algorithm is simple, involves very minimal communication, scales efficiently in both sample and feature size, and has theoretical guarantees. In particular, we show model selection consistency and coefficient estimation efficiency. Extensive experiments show excellent performance in variable selection, estimation, prediction, and computation time relative to usual competitors.

References in corpus (6)

• Searching for Exotic Particles in High-Energy Physics with Deep Learning
• Optimal Distributed Online Prediction using Mini-Batches
• Geometric median and robust estimation in Banach spaces
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• Parallelizing MCMC via Weierstrass Sampler
• Comunication-Efficient Algorithms for Statistical Optimization

Cited by in corpus (7)

• Communication-efficient sparse regression: a one-shot approach
• A Distributed One-Step Estimator
• Randomized maximum-contrast selection: subagging for large-scale regression
• Individual Data Protected Integrative Regression Analysis of High-dimensional Heterogeneous Data
• Distributed Bayesian Matrix Factorization with Limited Communication
• Nonparametric Bayesian Aggregation for Massive Data
• Distributed Bayesian Piecewise Sparse Linear Models