Research

Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization

May 15, 2018

Abstract

In decentralized optimization, nodes cooperate to minimize an overall objective function that is the sum (or average) of per-node private objective functions. Algorithms interleave local computations with communication among all or a subset of the nodes. Motivated by a variety of applications—decentralized estimation in sensor networks, fitting models to massive datasets, and decentralized control of multi-robot systems, to name a few—significant advances have been made towards the development of robust, practical algorithms with theoretical performance guarantees. This paper presents an overview of recent work in this area. In general, rates of convergence depend not only on the number of nodes involved and the desired level of accuracy, but also on the structure and nature of the network over which nodes communicate (e.g., whether links are directed or undirected, static or time-varying). We survey the state-of-the-art algorithms and their analyses tailored to these different scenarios, highlighting the role of the network topology.

Download the Paper

Related Publications

April 08, 2021

Responsible AI

Integrity

Towards measuring fairness in AI: the Casual Conversations dataset

Caner Hazirbas, Joanna Bitton, Brian Dolhansky, Jacqueline Pan, Albert Gordo, Cristian Canton Ferrer

April 08, 2021

February 07, 2020

Integrity

Generate, Segment and Refine: Towards Generic Manipulation Segmentation | Facebook AI Research

Peng Zhou, Bor-Chun Chen, Xintong Han, Mahyar Najibi, Abhinav Shrivastava, Ser-Nam Lim, Larry S. Davis

February 07, 2020

February 24, 2018

Speech & Audio

Computer Vision

Applied Machine Learning at Facebook: A Datacenter Infrastructure Perspective | Facebook AI Research

Kim Hazelwood, Sarah Bird, David Brooks, Soumith Chintala, Utku Diril, Dmytro Dzhulgakov, Mohamed Fawzy, Bill Jia, Yangqing Jia, Aditya Kalro, James Law, Kevin Lee, Jason Lu, Pieter Noordhuis, Misha Smelyanskiy, Liang Xiong, Xiaodong Wang

February 24, 2018

April 30, 2018

Computer Vision

Integrity

Countering Adversarial Images Using Input Transformations | Facebook AI Research

Chuan Guo, Mayank Rana, Moustapha Cisse, Laurens van der Maaten

April 30, 2018

November 02, 2019

NLP

Speech & Audio

Build it Break it Fix it for Dialogue Safety: Robustness from Adversarial Human Attack | Facebook AI Research

Emily Dinan, Samuel Humeau, Bharath Chintagunta, Jason Weston

November 02, 2019

May 31, 2019

Integrity

Abusive Language Detection with Graph Convolutional Networks | Facebook AI Research

Pushkar Mishra, Marco Del Tredici, Helen Yannakoudakis, Ekaterina Shutova

May 31, 2019

June 15, 2019

Computer Vision

Integrity

Feature Denoising for Improving Adversarial Robustness | Facebook AI Research

Kaiming He, Yuxin Wu, Laurens van der Maaten, Alan Yuille, Cihang Xie

June 15, 2019

Help Us Pioneer The Future of AI

We share our open source frameworks, tools, libraries, and models for everything from research exploration to large-scale production deployment.