Communication-efficient Algorithm for Distributed Sparse Learning via Two-way Truncation
We propose a communicationally and computationally efficient algorithm for high-dimensional distributed sparse learning. At each iteration, local machines compute the gradient on local data and the master machine solves one shifted $l_1$ regularized minimization problem. The communication cost is reduced from constant times of the dimension number for the state-of-the-art algorithm to constant times of the sparsity number via Two-way Truncation procedure. Theoretically, we prove that the estimation error of the proposed algorithm decreases exponentially and matches that of the centralized method under mild assumptions. Extensive experiments on both simulated data and real data verify that the proposed algorithm is efficient and has performance comparable with the centralized method on solving high-dimensional sparse learning problems.
Code (0)
등록된 구현이 없습니다.
Tasks
Sparse LearningVocal Bursts Valence PredictionSimilar Papers 제목 키워드 기반
Truncated Non-Uniform Quantization for Distributed SGD
To address the communication bottleneck challenge in distributed learning, our work introduces a novel two-stage quantization strategy designed to enhance the communication efficiency of distributed Stochastic Gradient D…
QuantizationImproved Quantization Strategies for Managing Heavy-tailed Gradients in Distributed Learning
Gradient compression has surfaced as a key technique to address the challenge of communication efficiency in distributed learning. In distributed deep learning, however, it is observed that gradient distributions are hea…
QuantizationOptimal Sparsity-Sensitive Bounds for Distributed Mean Estimation
We consider the problem of estimating the mean of a set of vectors, which are stored in a distributed system. This is a fundamental task with applications in distributed SGD and many other distributed problems, where com…
Estimate Exchange over Network is Good for Distributed Hard Thresholding Pursuit
We investigate an existing distributed algorithm for learning sparse signals or data over networks. The algorithm is iterative and exchanges intermediate estimates of a sparse signal over a network. This learning strateg…
Distributed Sparse Normal Means Estimation with Sublinear Communication
We consider the problem of sparse normal means estimation in a distributed setting with communication constraints. We assume there are $M$ machines, each holding $d$-dimensional observations of a $K$-sparse vector $\mu$ …