%0 Conference Proceedings
%B Neural Information Processing Systems
%D 2012
%T Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization
%A Konstantinos I Tsianos
%A Sean Lawlor
%A Michael G. Rabbat
%C Lake Tahoe, NV, USA
%X 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.
%8 12/2012
%> http://networks.ece.mcgill.ca/sites/default/files/1209.1076v1.pdf