On the Influence of Bias-Correction on Distributed Stochastic Optimization

Various bias-correction methods such as EXTRA, gradient tracking methods, and exact diffusion have been proposed recently to solve distributed deterministic optimization problems. These methods employ constant step-sizes and converge linearly to the exact solution under proper conditions. However, t...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on signal processing 2020, Vol.68, p.4352-4367
Main Authors: Yuan, Kun, Alghunaim, Sulaiman A., Ying, Bicheng, Sayed, Ali H.
Format: Article
Language:English
Subjects:
Adaptation models
adaptive networks
Algorithms
Bias
Computer simulation
consensus
Convergence
Diffusion
Distributed optimization
exact diffusion
Exact solutions
EXTRA
gradient tracking
Indexes
Network topologies
Network topology
Noise measurement
Optimization
Performance degradation
Steady-state
stochastic gradient descent
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Various bias-correction methods such as EXTRA, gradient tracking methods, and exact diffusion have been proposed recently to solve distributed deterministic optimization problems. These methods employ constant step-sizes and converge linearly to the exact solution under proper conditions. However, their performance under stochastic and adaptive settings is less explored. It is still unknown whether , when and why these bias-correction methods can outperform their traditional counterparts with noisy gradient and constant step-sizes. This work studies the performance of exact diffusion under the stochastic and adaptive setting, and provides conditions under which exact diffusion has superior steady-state mean-square deviation (MSD) performance than traditional algorithms without bias-correction. In particular, it is proven that this superiority is more evident over sparsely-connected network topologies such as lines, cycles, or grids. Conditions are also provided under which exact diffusion method can or degrade the performance of traditional methods. Simulations are provided to validate the theoretical findings.
ISSN:1053-587X
1941-0476
DOI:10.1109/TSP.2020.3008605