Extending Gossip Algorithms to Distributed Estimation of U-statistics

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

16 citations recorded by the source corpus.

Efficient and robust algorithms for decentralized estimation in networks are essential to many distributed systems. Whereas distributed estimation of sample mean statistics has been the subject of a good deal of attention, computation of $U$-statistics, relying on more expensive averaging over pairs of observations, is a less investigated area. Yet, such data functionals are essential to describe global properties of a statistical population, with important examples including Area Under the Curve, empirical variance, Gini mean difference and within-cluster point scatter. This paper proposes new synchronous and asynchronous randomized gossip algorithms which simultaneously propagate data across the network and maintain local estimates of the $U$-statistic of interest. We establish convergence rate bounds of $O(1/t)$ and $O(\log t / t)$ for the synchronous and asynchronous cases respectively, where $t$ is the number of iterations, with explicit data and network dependent terms. Beyond favorable comparisons in terms of rate analysis, numerical experiments provide empirical evidence the proposed algorithms surpasses the previously introduced approach.

Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics

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 Statistical and Nonlinear Physics

Citations in the corpus

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).”
Gossip Dual Averaging for Decentralized Optimization of Pairwise Functions (2016, positive): “Although gossip algorithms have recently been introduced to evaluate such pairwise functions for a fixed θ (Pelckmans & Suykens, 2009; Colin et al., 2015), to the best of our knowledge, efficiently finding the optimal solution θ in a decentralized way remains an open challenge.”
Hiding in the Crowd: A Massively Distributed Algorithm for Private Averaging with Malicious Adversaries (2018, background): “…of Algorithm 1 is: where C G = 1 − λ 2 ( L ) / | E | ∈ (0 , 1) with λ 2 ( L ) the second smallest eigenvalue of the Laplacian matrix L (Boyd et al., 2006; Colin et al., 2015), d max = max u d u is the maximum degree and B X , B δ are upper bounds for the absolute value of private values and…”