View article

We study distributed multiagent optimization over graphs. We consider the minimization of subject to convex constraints, where is the smooth strongly convex sum of the agent's losses and is a nonsmooth convex function. We build on the SONATA algorithm: the algorithm employs the use of surrogate objective functions in the agents' subproblems (thus going beyond linearization, such as proximal-gradient) coupled with a perturbed consensus mechanism that aims to locally track the gradient of . SONATA achieves precision on the objective value in gradient computations at each node and communication steps, where is the condition number of and characterizes the connectivity of the network. This is the first linear rate result for distributed composite optimization; it also improves on existing (nonaccelerated) schemes just minimizing , whose rate depends on much larger quantities …