Efficient protocols for distributed classification and optimization

DOI10.1007/978-3-642-34106-9_15MaRDI QIDQ3164818zbMATH OpenOpenAlexFDO

Authors Hal Daumé, Jeff M. Phillips, Avishek Saha, Suresh Venkatasubramanian

Publication date 16 October 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.3523

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Distributed algorithms (68W15) Network protocols (68M12)

Abstract: In distributed learning, the goal is to perform a learning task over data distributed across multiple nodes with minimal (expensive) communication. Prior work (Daume III et al., 2012) proposes a general model that bounds the communication required for learning classifiers while allowing for $eps$ training 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(d^{2}log1/eps)$ words of communication to classify distributed data in arbitrary dimension $d$, $eps$-optimally. This readily extends to classification over $k$ nodes with $O(k{d}^{2}log1/eps)$ 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 illustrate general algorithm design paradigms for doing efficient learning over distributed data. We show how to solve fixed-dimensional and high dimensional linear programming efficiently in a distributed setting where constraints may be distributed across nodes. Since many learning problems can be viewed as convex optimization problems where constraints are generated by individual points, this models many typical distributed learning scenarios. 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. As a consequence, our methods extend to the wide range of problems solvable using these techniques.

Recommendations

• An efficient distributed learning algorithm based on effective local functional approximations
• Communication-efficient distributed optimization of self-concordant empirical loss
• Communication-efficient algorithms for statistical optimization

Cited in

(7)

• Communication-Efficient Distributed Linear Discriminant Analysis for Binary Classification
• Over-the-Air computation for distributed machine learning and consensus in large wireless networks
• scientific article; zbMATH DE number 5375437 (Why is no real title available?)
• Distributed Deep Learning on Heterogeneous Computing Resources Using Gossip Communication
• An efficient distributed learning algorithm based on effective local functional approximations
• Communication-efficient distributed optimization of self-concordant empirical loss
• Distributed and robust support vector machine

Describes a project that uses

Uses Software

• bmrm

This page was built for publication: Efficient protocols for distributed classification and optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3164818)