Protocols for Distributed Classication and Optimization
Hal Daum, Matthew D. Phillips, Avishek Saha, Suresh Venkatasubramanian · 2012
In distributed learning, the goal is to perform a learning task over data distributed across multiple nodes with minimal (expensive) communication. Prior work (Daum e III et al., 2012) proposes a general model that bounds the communication required for learning classiers while allowing for training error on linearly separable data adversarially distributed across nodes. In this work, we develop key improvements and extensions to this basic model. Our rst result is a two-party multiplicative-weight-update based protocol that uses O(d 2 log 1=) words of communication to classify distributed data in arbitrary dimension d, -optimally. This readily extends to classication overk nodes withO(kd 2 log 1=) words of communication. Our proposed protocol is simple to implement and is considerably more ecient than baselines compared, as demonstrated by our empirical results. In addition, we illustrate general algorithm design paradigms for doing ecient learning over distributed data. We show how to solve xed-dimensional and high dimensional linear programming eciently 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.