A Unified Contraction Analysis of a Class of Distributed Algorithms for Composite Optimization

Jinming Xu, Ying Sun, Ye Tian, Gesualdo Scutari

Abstract

We study distributed composite optimization over networks: agents minimize the sum of a smooth (strongly) convex function, the agents' sum-utility, plus a non-smooth (extended-valued) convex one. We propose a general algorithmic framework for such a class of problems and provide a unified convergence analysis leveraging the theory of operator splitting. Our results unify several approaches proposed in the literature of distributed optimization for special instances of our formulation. Distinguishing features of our scheme are: (i) when the agents' functions are strongly convex, the algorithm converges at a linear rate, whose dependencies on the agents' functions and the network topology are decoupled, matching the typical rates of centralized optimization; (ii) the step-size does not depend on the network parameters but only on the optimization ones; and (iii) the algorithm can adjust the ratio between the number of communications and computations to achieve the same rate of the centralized proximal gradient scheme (in terms of computations). This is the first time that a distributed algorithm applicable to composite optimization enjoys such properties.

Introduction

In distributed optimization, a group of agents connected by a network tries to solve a global problem without a central controller. Each agent possesses a local, private cost function ($f_i$), and they often share a common non-smooth objective ($G$), such as a sparsity-inducing penalty ($L_1$ norm) or a set of constraints. Historically, the literature has been fragmented into "bespoke" algorithms like EXTRA, DIGing, and NEXT, each requiring unique proofs and specific parameter settings. Furthermore, these methods often suffer from a "network bottleneck," where the step-size and convergence rate are inextricably linked to the network's connectivity, making them slower and harder to tune than centralized counterparts.

A Unified Algorithmic Framework

The authors propose a General Primal-Dual Proximal Algorithm that reformulates the optimization problem into its Karush-Kuhn-Tucker (KKT) saddle-point conditions. By applying operator splitting theory, they demonstrate that many popular existing algorithms are actually specific instances of a single mathematical family defined by three weight matrices: $A, B,$ and $C$.

Table I: Parameterization of the general framework to recover existing distributed algorithms.

As shown in the table above, by choosing different values for these matrices, the framework "collapses" into well-known algorithms like EXTRA, NIDS, or NEXT. This unification allows for a single convergence analysis that applies to all these methods simultaneously.

Key Insights: Rate Separation and Independence

A major breakthrough of this work is the decoupling of optimization and network parameters. The authors prove that the convergence rate is determined by the maximum of two separate factors: the optimization rate (function properties) and the network rate (communication efficiency).

  • Network-Independent Step-Size: Unlike previous methods, the optimal step-size $\gamma^* = \frac{2}{L+\mu}$ depends only on the smooth functions' Lipschitz constants ($L$) and strong convexity ($\mu$). This allows agents to set local parameters without global knowledge of the network's spectral gap.
  • Matching Centralized Performance: By adjusting the ratio of communications to computations—specifically through multiple consensus rounds or Chebyshev acceleration—the distributed algorithm can match the linear convergence rate of a centralized proximal gradient scheme.

Convergence Results

The algorithm is proven to converge at a linear rate $O(\lambda^k)$ for composite problems with strongly convex local functions. The theoretical analysis explores how the contraction factor ($\rho^2_{opt}$) behaves relative to the connectivity of the graph ($\rho_{com}$).

Figure 1: Comparison of contraction factors across different schemes and communication-to-computation ratios.

As illustrated in the figure above, the proposed scheme (b and c) maintains a lower contraction factor across a wider range of graph connectivity compared to prior benchmarks (a). This demonstrates that the proposed framework is not only more general but also more efficient in utilizing network communication to accelerate convergence.

Conclusion

This research provides a "grand unified theory" for distributed composite optimization. By proving that linear convergence can be achieved with network-independent step-sizes, it bridges the gap between distributed and centralized optimization. Future work may extend this analysis to time-varying or directed graphs, as well as exploring asynchronous update regimes for larger-scale systems.

Summary updated

BibTeX
@inproceedings{xu2019unified,
  author = {Jinming Xu and Ying Sun and Ye Tian and Gesualdo Scutari},
  title = {{A Unified Contraction Analysis of a Class of Distributed Algorithms for Composite Optimization}},
  booktitle = {CAMSAP},
  year = {2019},
  url = {https://openreview.net/forum?id=_x9K3cx3odc},
}
Figure