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

Abstract

This work 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 to have a wider stability range and superior convergence performance than the EXTRA strategy. The exact diffusion solution is applicable to non-symmetric left-stochastic combination matrices, while many earlier developments on exact consensus implementations are limited to doubly-stochastic matrices; these latter matrices impose stringent constraints on the network topology. The derivation of the exact diffusion strategy in this work 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 and are facilitated by examining the evolution of the error dynamics in a transformed domain. Numerical simulations illustrate the theoretical conclusions.

15 pages; 12 figures; Submitted for publication

References in corpus (1)

• Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis

Cited by in corpus (8)

• D${}^2$: Decentralized Training over Decentralized Data
• Supervised Learning Under Distributed Features
• Communication-Efficient Distributed Strongly Convex Stochastic Optimization: Non-Asymptotic Rates
• Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking
• Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis
• A Unification and Generalization of Exact Distributed First Order Methods
• Dynamic Average Diffusion with randomized Coordinate Updates
• Variance-Reduced Stochastic Learning by Networked Agents under Random Reshuffling