Optimization over time-varying directed graphs with row and column-stochastic matrices
By Fakhteh Saadatniaki, Ran Xin, Usman A. Khan. 2018
41 citations recorded by the source corpus.
In this paper, we provide a distributed optimization algorithm, termed as TV-$\mathcal{AB}$, that minimizes a sum of convex functions over time-varying, random directed graphs. Contrary to the existing work, the algorithm we propose does not require eigenvector estimation to estimate the (non-$\mathbf{1}$) Perron eigenvector of a stochastic matrix. Instead, the proposed approach relies on a novel information mixing approach that exploits both row- and column-stochastic weights to achieve agreement towards the optimal solution when the underlying graph is directed. We show that TV-$\mathcal{AB}$ converges linearly to the optimal solution when the global objective is smooth and strongly-convex, and the underlying time-varying graphs exhibit bounded connectivity, i.e., a union of every $C$ consecutive graphs is strongly-connected. We derive the convergence results based on the stability analysis of a linear system of inequalities along with a matrix perturbation argument. Simulations confirm the findings in this paper.
Subfields: Computer Networks and Communications, Electrical and Electronic Engineering
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
- Sebastian U. Stich
- Martin Jaggi
- Anastasia Koloskova
- Nicolas Loizou
- Ziyang Meng
- Sadra Boreiri
- Zongli Lin
- Xinlei Yi
In Electrical and Electronic Engineering
- Martin Jaggi
- Anastasia Koloskova
- Nicolas Loizou
- Sadra Boreiri
- Sebastian U. Stich
- Karl Henrik Johansson
- Ziyang Meng
- Yiguang Hong
Citations in the corpus
- A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “However, as we require W to be symmetric, our setting is less general than the one considered in (Nedić et al., 2017; Xi & Khan, 2017; Saadatniaki et al., 2018; Assran & Rabbat, 2018; Scutari & Sun, 2019; Assran et al., 2019).”
- A survey of distributed optimization (2019, methodology): “The second class of algorithms is based on the push–pull method (see, e.g., Du, Yao et al., 2018; Pu, Shi, Xu, & Nedi ´ c, 2018; Xin & Khan, 2018; Yang et al., 2013 ).”