Communication-Efficient distributed optimization for sparse learning via two-way truncation

Jineng Ren, Xingguo Li, Jarvis Haupt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

We propose a communication and computation efficient algorithm for high-dimensional distributed sparse learning, motivated by the approach of (Wang et al., 2016). At each iteration, local machines compute local gradients on their own local data and using these, a master machine solves a shifted l\ regularized minimization problem. Here, our contribution reduces the communication cost per transmission from the order of the parameter dimension to the order of the number of nonzero entries in the parameter via a 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 conditions. Extensive experiments on both simulated data and real data support that the proposed algorithm is efficient and has statistical performance comparable with the centralized method.

Original languageEnglish (US)
Title of host publication2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-5
Number of pages5
ISBN (Electronic)9781538612514
DOIs
StatePublished - Mar 9 2018
Event7th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2017 - Curacao
Duration: Dec 10 2017Dec 13 2017

Publication series

Name2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2017
Volume2017-December

Conference

Conference7th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, CAMSAP 2017
CityCuracao
Period12/10/1712/13/17

Bibliographical note

Funding Information:
ACKNOWLEDGMENT The authors graciously acknowledge support from DARPA Young Faculty Award N66001-14-1-4047 and thank Jialei Wang for very useful suggestions.

Fingerprint Dive into the research topics of 'Communication-Efficient distributed optimization for sparse learning via two-way truncation'. Together they form a unique fingerprint.

Cite this