Efficient Protocols for Distributed Classification and Optimization

By Hal Daumé Iii, Jeff M. Phillips, Avishek Saha, Suresh Venkatasubramanian. 2012

41 citations recorded by the source corpus.

A recent paper [1] proposes a general model for distributed learning that bounds the communication required for learning classifiers with e error on linearly separable data adversarially distributed across nodes. In this work, we develop key improvements and extensions to this basic model. Our first result is a two-party multiplicative-weight-update based protocol that uses O(d2 log1/e) words of communication to classify distributed data in arbitrary dimension d, e-optimally. This extends to classification over k nodes with O(kd2 log1/e) words of communication. Our proposed protocol is simple to implement and is considerably more efficient than baselines compared, as demonstrated by our empirical results. In addition, we show how to solve fixed-dimensional and high-dimensional linear programming with small communication in a distributed setting where constraints may be distributed across nodes. Our techniques make use of a novel connection from multipass streaming, as well as adapting the multiplicative- weight-update framework more generally to a distributed setting.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints (2018, background): “…also an increasing number of applications in which data is generated in a distributed manner and it (or features of it) are communicated over bandwidth-limited links to central processors Boyd et al. (2011); Balcan et al. (2012); Daume III et al. (2012); Daumé et al. (2012); Dekel et al. (2012).”
Communication-Efficient Distributed Learning of Discrete Probability Distributions (2017, background): “In recent years, a number of statistical estimation problems have been algorithmically studied in the distributed setting [3, 16, 15, 40, 21, 30, 24, 33, 5, 29].”
Communication-Efficient Distributed Online Prediction by Dynamic Model Synchronization (2014, background): “In contrast to work on the communication complexity of batch learning [3, 17, 2, 7], we consider the online in-place performance of a streaming distributed prediction system.”