DEXTRA: A Fast Algorithm for Optimization Over Directed Graphs

By Chenguang Xi, Usman A. Khan. 2017

182 citations recorded by the source corpus.

Subfields: 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 Computer Networks and Communications

1. Ali H. Sayed
2. Angelia Nedić
3. Wei Shi
4. Kun Yuan
5. Wotao Yin
6. Martin Jaggi
7. Shi Pu
8. Sebastian U. Stich

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´c et al., 2017; Xi & Khan, 2017; Saadatniaki et al., 2018; Assran & Rabbat, 2018; Scutari & Sun, 2019; Assran et al., 2019).”
• Anytime Minibatch: Exploiting Stragglers in Online Distributed Optimization (2020, background): “A large body of work elaborates on these ideas, considering differences in topology, communications models, data models, etc. Duchi et al. (2012); Tsianos et al. (2012); Shi et al. (2015); Xi & Khan (2017).”
• Optimal Convergence Rates for Convex Distributed Optimization in Networks (2019, unknown): “We refer the reader to Nedic and Olshevsky (2015); Xi and Khan (2017); Nedic and Olshevsky (2016); Nedic et al. (2016) for asymmetric decentralized optimization algorithms.”
• A survey of distributed optimization (2019, methodology): “To accelerate the convergence process, distributed algorithms with fixed step-sizes by using the push-sum method have been proposed in Nedi ´c et al. (2017a , 2017b) ; Xi and Khan (2017) ; Zeng and Yin (2017) .”
• Asynchronous Gradient Push (2018, unknown): “Xi and Khan [22] propose DEXTRA and Zeng and Yin [23] propose Extra-Push, both of which use the Push-Sum protocol in conjunction with gradient tracking to achieve geometric convergence for smooth, strongly convex objectives over directed graphs.”
• Optimization over time-varying directed graphs with row and column-stochastic matrices (2018, background): “Related work along these lines also include [31] over undirected graphs and [32] over directed graphs that are related to [26], [28].”
• 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]).”
• Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization (2018, methodology): “Among them, Push-Sum [24], DEXTRA [25], EXTRAPUSH [26], subgradient-push [27], and Push-Pull methods [20], [21] are designed for directed graphs, while DIGing is for timevarying graphs.”
• Multiagent Fully Decentralized Value Function Learning With Linear Convergence Rates (2018, background): “EXTRA and DEXTRA [29] can also converge linearly to the global minimizer while maintaining the same computational efficiency as consensus and diffusion.”
• Push–Pull Gradient Methods for Distributed Optimization in Networks (2018, methodology): “Directed graphs were discussed in [10], [11], [12], [9], [13], [14].”