  This work concerns the analysis and design of distributed first-order
optimization algorithms over time-varying graphs. The goal of such algorithms
is to optimize a global function that is the average of local functions using
only local computations and communications. Several different algorithms have
been proposed that achieve linear convergence to the global optimum when the
local functions are strongly convex. We provide a unified analysis that yields
the worst-case linear convergence rate as a function of the condition number of
the local functions, the spectral gap of the graph, and the parameters of the
algorithm. The framework requires solving a small semidefinite program whose
size is fixed; it does not depend on the number of local functions or the
dimension of their domain. The result is a computationally efficient method for
distributed algorithm analysis that enables the rapid comparison, selection,
and tuning of algorithms. Finally, we propose a new algorithm, which we call
SVL, that is easily implementable and achieves a faster worst-case convergence
rate than all other known algorithms.
