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

DOI10.1109/TSP.2018.2875883MaRDI QIDQ4628230zbMATH OpenOpenAlexFDO

Authors Kun Yuan, Bicheng Ying, Xiaochuan Zhao, Ali H. Sayed

Publication date 6 March 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.05142

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Convex programming (90C25) Deterministic network models in operations research (90B10) Stochastic programming (90C15)

Abstract: Part I of this work [2] developed the exact diffusion algorithm to remove the bias that is characteristic of distributed solutions for deterministic optimization problems. The algorithm was shown to be applicable to a larger set of combination policies than earlier approaches in the literature. In particular, the combination matrices are not required to be doubly stochastic, which impose stringent conditions on the graph topology and communications protocol. In this Part II, we examine the convergence and stability properties of exact diffusion in some detail and establish its linear convergence rate. We also show that it has a wider stability range than the EXTRA consensus solution, meaning that it is stable for a wider range of step-sizes and can, therefore, attain faster convergence rates. Analytical examples and numerical simulations illustrate the theoretical findings.

Cited in

(11)

• Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation
• Linear convergence of primal-dual gradient methods and their performance in distributed optimization
• Distributed Learning in Non-Convex Environments— Part II: Polynomial Escape From Saddle-Points
• scientific article; zbMATH DE number 7306853 (Why is no real title available?)
• Convergence of an accelerated distributed optimisation algorithm over time-varying directed networks
• On the linear convergence of two decentralized algorithms
• Decentralized projected Riemannian gradient method for smooth optimization on compact submanifolds embedded in the Euclidean space
• Projected subgradient based distributed convex optimization with transmission noises
• Correction-based diffusion LMS algorithms for distributed estimation
• Distributed Stochastic Optimization via Matrix Exponential Learning
• Exact Diffusion for Distributed Optimization and Learning—Part I: Algorithm Development

This page was built for publication: Exact Diffusion for Distributed Optimization and Learning—Part II: Convergence Analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4628230)