Extending Gossip Algorithms to Distributed Estimation of U-statistics

Igor Colin 1 Aurélien Bellet 2 Joseph Salmon 1 Stéphan Clémençon 1
2 MAGNET - Machine Learning in Information Networks
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : 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.
Type de document :
Communication dans un congrès
Annual Conference on Neural Information Processing Systems (NIPS), Dec 2015, Montréal, Canada. 〈https://nips.cc/Conferences/2015〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01214665
Contributeur : Aurélien Bellet <>
Soumis le : jeudi 5 novembre 2015 - 13:37:10
Dernière modification le : jeudi 11 janvier 2018 - 06:27:32
Document(s) archivé(s) le : vendredi 28 avril 2017 - 08:32:14

Fichiers

nips15_gossip.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01214665, version 1

Citation

Igor Colin, Aurélien Bellet, Joseph Salmon, Stéphan Clémençon. Extending Gossip Algorithms to Distributed Estimation of U-statistics. Annual Conference on Neural Information Processing Systems (NIPS), Dec 2015, Montréal, Canada. 〈https://nips.cc/Conferences/2015〉. 〈hal-01214665〉

Partager

Métriques

Consultations de la notice

319

Téléchargements de fichiers

124