Efficient Distributed Learning with Sparsity

Abstract

We propose a novel, efficient approach for distributed sparse learning in high-dimensions, where observations are randomly partitioned across machines. Computationally, at each round our method only requires the master machine to solve a shifted ell_1 regularized M-estimation problem, and other workers to compute the gradient. In respect of communication, the proposed approach provably matches the estimation error bound of centralized methods within constant rounds of communications (ignoring logarithmic factors). We conduct extensive experiments on both simulated and real world datasets, and demonstrate encouraging performances on high-dimensional regression and classification tasks.

References in corpus (16)

• Confidence Intervals and Hypothesis Testing for High-Dimensional Regression
• High-dimensional Ising model selection using ${\ell }_1$-regularized logistic regression
• Optimal Distributed Online Prediction using Mini-Batches
• Communication Efficient Distributed Optimization using an Approximate Newton-type Method
• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• Communication Complexity of Distributed Convex Learning and Optimization
• Distributed Estimation and Inference with Statistical Guarantees
• Optimality guarantees for distributed statistical estimation
• Communication-efficient sparse regression: a one-shot approach
• Distributed Stochastic Variance Reduced Gradient Methods and A Lower Bound for Communication Complexity
• A General Framework for Robust Testing and Confidence Regions in High-Dimensional Quantile Regression
• Computational Limits of A Distributed Algorithm For Smoothing Spline
• Nonparametric Heterogeneity Testing For Massive Data
• A Distributed One-Step Estimator
• A Partially Linear Framework for Massive Heterogeneous Data
• Distributed Multitask Learning

Cited by in corpus (8)

• Quantile Regression Under Memory Constraint
• A review of distributed statistical inference
• Communication-Efficient Distributed Statistical Inference
• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• Fast and Robust Sparsity Learning over Networks: A Decentralized Surrogate Median Regression Approach
• Distributed Estimation and Inference for Semi-parametric Binary Response Models
• A Provably Communication-Efficient Asynchronous Distributed Inference Method for Convex and Nonconvex Problems
• Compressed Distributed Gradient Descent: Communication-Efficient Consensus over Networks