Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization

TitleCommunication/Computation Tradeoffs in Consensus-Based Distributed Optimization
Publication TypeConference Proceedings
Year of Publication2012
AuthorsTsianos, K. I., S. Lawlor, and M. G. Rabbat
Conference NameNeural Information Processing Systems
Date Published12/2012
Conference LocationLake Tahoe, NV, USA

We study the scalability of consensus-based distributed optimization algorithms by considering two questions: How many processors should we use for a given problem, and how often should they communicate when communication is not free? Central to our analysis is a problem-specific value r which quantifies the communication/computation tradeoff. We show that organizing the communica- tion among nodes as a k-regular expander graph [1] yields speedups, while when all pairs of nodes communicate (as in a complete graph), there is an optimal num- ber of processors that depends on r. Surprisingly, a speedup can be obtained, in terms of the time to reach a fixed level of accuracy, by communicating less and less frequently as the computation progresses. Experiments on a real cluster solving metric learning and non-smooth convex minimization tasks demonstrate strong agreement between theory and practice.

Refereed DesignationRefereed
1209.1076v1.pdf437.66 KB