Timezone: »

Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization
Konstantinos Tsianos · Sean Lawlor · Michael Rabbat

Thu Dec 06 02:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor #None
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 communication among nodes as a $k$-regular expander graph~\cite{kRegExpanders} yields speedups, while when all pairs of nodes communicate (as in a complete graph), there is an optimal number 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.

Author Information

Konstantinos Tsianos (Amazon)
Sean Lawlor (Genetec Inc)
Michael Rabbat (University of Wisconsin-Madison)

More from the Same Authors