Exact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development

By Kun Yuan, Bicheng Ying, Xiaochuan Zhao, Ali H. Sayed. 2017

249 citations recorded by the source corpus.

This paper develops a distributed optimization strategy with guaranteed exact convergence for a broad class of left-stochastic combination policies. The resulting exact diffusion strategy is shown in Part II of this paper to have a wider stability range and superior convergence performance than the EXTRA strategy. The exact diffusion method is applicable to locally balanced left-stochastic combination matrices which, compared to the conventional doubly stochastic matrix, are more general and able to endow the algorithm with faster convergence rates, more flexible step-size choices, and improved privacy-preserving properties. The derivation of the exact diffusion strategy relies on reformulating the aggregate optimization problem as a penalized problem and resorting to a diagonally weighted incremental construction. Detailed stability and convergence analyses are pursued in Part II of this paper and are facilitated by examining the evolution of the error dynamics in a transformed domain. Numerical simulations illustrate the theoretical conclusions.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Kun Yuan
2. Hanlin Tang
3. Ali H. Sayed
4. Wotao Yin
5. Ji Liu
6. Ce Zhang
7. Xiangru Lian
8. Sulaiman A. Alghunaim

In Computer Networks and Communications

1. Ali H. Sayed
2. Kun Yuan
3. Ji Liu
4. Wotao Yin
5. Hanlin Tang
6. Ce Zhang
7. Xiangru Lian
8. Angelia Nedić

Citations in the corpus

• D2: Decentralized Training over Decentralized Data (2018, methodology): “This algorithm was simultaneously proposed by Yuan et al. [2017] for the smooth case only using a different approach.”
• Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic Rates. (2018, background): “While we pursue stochastic optimization in this paper, the case of deterministic noiseless distributed optimization has seen much progress ( [3]–[6]) and more recently accelerated methods ( [7], [8]).”
• Linear convergence of primal-dual gradient methods and their performance in distributed optimization (2019, methodology): “Exact diffusion [27].”
• Supervised Learning Under Distributed Features (2018, methodology): “To this end, we can apply the exact diffusion algorithm developed in [18], [51] to solve (22).”
• A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, methodology): “In the line of research of optimization over heterogeneous networks, after the initial work [38] regarding uncoordinated step sizes, references [49] and [50] introduce and analyze a diffusion strategy with corrections that achieves an exact linear convergence with uncoordinated step sizes.”
• Multiagent Fully Decentralized Value Function Learning With Linear Convergence Rates (2018, methodology): “We perform incremental updates in our distributed setting because it provides better stability than regular gradient ascent [30], [31].”
• Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization (2018, methodology): “Exact diffusion [17] O ( ln ( 1 ) · ( m 1−λ2(P) ))”
• Optimization over time-varying directed graphs with row and column-stochastic matrices (2018, background): “networks [5], large-scale machine learning [6], [7], distributed estimation [8], and localization [9].”
• Throughput-Optimal Topology Design for Cross-Silo Federated Learning (2020, methodology): “For particular choices of the matrix A and the number of local updates s, DPASGD reduces to other schemes previously proposed [61, 58, 110], including FedAvg [72], where the orchestrator just performs the averaging step (this corresponds to its local loss function fi(.”