Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions

By Igor Colin, Aurélien Bellet, Joseph Salmon, Stéphan Clemencon. 2016

113 citations recorded by the source corpus.

In decentralized networks (of sensors, connected objects, etc.), there is an important need for efficient algorithms to optimize a global cost function, for instance to learn a global model from the local data collected by each computing unit. In this paper, we address the problem of decentralized minimization of pairwise functions of the data points, where these points are distributed over the nodes of a graph defining the communication topology of the network. This general problem finds applications in ranking, distance metric learning and graph inference, among others. We propose new gossip algorithms based on dual averaging which aims at solving such problems both in synchronous and asynchronous settings. The proposed framework is flexible enough to deal with constrained and regularized variants of the optimization problem. Our theoretical analysis reveals that the proposed algorithms preserve the convergence rate of centralized dual averaging up to an additive bias term. We present numerical simulations on Area Under the ROC Curve (AUC) maximization and metric learning problems which illustrate the practical interest of our approach.

Subfields: Computer Networks and Communications, Public Health, Environmental and Occupational Health, Optimization & Training

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

In Public Health, Environmental and Occupational Health

In Optimization & Training

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “While multi-agent optimization has a long history in the control community, fully decentralized variants of SGD and other optimization algorithms have recently been considered in machine learning both for improved scalability in datacenters [30] as well as for decentralized networks of devices [110,”
Communication Efficient Decentralized Training with Multiple Local Updates (2019, background): “In recent years, many decentralized algorithms have been proposed for solving the problem (1) [1, 50, 36, 3, 20, 15, 41].”
Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, background): “In this work, we focus on fully decentralized learning, which has recently attracted a lot of interest (Duchi et al., 2012; Wei and Ozdaglar, 2012; Colin et al., 2016; Lian et al., 2017; Jiang et al., 2017; Tang et al., 2018; Lian et al., 2018).”
Distributed Learning over Unreliable Networks (2018, background): “2 Related Work There has been a significant work on distributing deep learning, e.g. Seide and Agarwal (2016); Abadi et al. (2016); Goyal et al. (2017); Colin et al. (2016).”
DJAM: Distributed Jacobi Asynchronous Method for Learning Personal Models (2018, methodology): “They use techniques ranging from distributed (sub)gradient descent [4], [5] to more elaborate techniques such as EXTRA [6], distributed ADMM [7], [8], dual averaging [9], and distributed augmented Lagrangean [10].”
D2: Decentralized Training over Decentralized Data (2018, methodology): “Training machine learning models in a decentralized way has attracted intensive interests recently Colin et al. [2016], Lian et al. [2017a], Yuan et al. [2016].”
Personalized and Private Peer-to-Peer Machine Learning (2017, background): “Most of the work in fully decentralized learning and optimization has focused on the distributed consensus problem, where the goal is to find a single global model which minimizes the sum of the local loss functions (Nedic and Ozdaglar, 2009; Ram et al., 2010; Duchi et al., 2012; Wei and Ozdaglar, 2”
Decentralized Collaborative Learning of Personalized Models over Networks (2016, methodology): “Several peer-to-peer algorithms have been developed for decentralized averaging (Kempe et al., 2003; Boyd et al., 2006; Colin et al., 2015) and optimization (Nedic and Ozdaglar, 2009; Ram et al., 2010; Duchi et al., 2012; Wei and Ozdaglar, 2012, 2013; Iutzeler et al., 2013; Colin et al., 2016).”
Communication Compression for Decentralized Training (2018, methodology): “The decentralized algorithm (also named gossip algorithm in some literature under certain scenarios [Colin et al., 2016]) only assume a connect computational network, without using the central node to collect information from all nodes.”
Towards More Efficient Stochastic Decentralized Learning: Faster Convergence and Sparse Communication (2018, methodology): “As discussed in (Colin et al., 2016), minimizing (9) in a decentralized manner remains a challenging task.”
Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols (2019, unknown): “They are a basic building block to propagate and aggregate information in distributed databases [5, 6] and social networks [7, 8], to model the spread of infectious diseases [9], as well as to train machine learning models on distributed datasets [10, 11, 12, 13].”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, unknown): “Recently there has been an increasing interest in applying mulitagent optimization methods to solve convex and non-convex optimization problems arising in machine learning [80, 39, 1, 2, 9, 36, 32].”
Projection-free Distributed Online Learning in Networks (2017, background): “, 2012) (Colin et al., 2016): the better the connectivity of a graph is, the larger the spectral gap value will be, it is easy to verify that this theorem captures the intuition that the D-OCG’s regret bound will be larger on larger graphs (the regret bound will be larger when the node size n is lar”
A Survey on Federated Learning for Resource-Constrained IoT Devices (2021, unknown): “Fully decentralized SGD and other optimization algorithms are recently getting popular for scalability in large-scale systems [74] and decentralization of networks devices [71], [75]–[82].”
Asynchronous Decentralized Online Learning (2021, background): “Results in Figure 2 show that symmetric gossiping will make the algorithm much less effective as message delays increase, which verifies the effectiveness of asymmetric gossiping.”
Towards Decentralized Deep Learning with Differential Privacy (2019, background): “Many decentralized algorithms aim at solving distributed consensus problems [15][16][17], which is also the goal of our paper.”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, unknown): “Recently there has been an increasing interest in applying mulitagent optimization methods to solve convex and non-convex optimization problems arising in machine learning [189, 105, 4, 5, 25, 95, 83].”
Gossip training for deep learning (2016, methodology): “Gossip averaging has already been adapted to other machine learning algorithms such as kernel methods [4] or PCA [7].”