Titre :

Extending Gossip Algorithms to Distributed Estimation of U -Statistics

Auteur(s) :

Colin, Igor [Auteur]
Laboratoire Traitement et Communication de l'Information [LTCI]
Salmon, Joseph [Auteur]
Institut Montpelliérain Alexander Grothendieck [IMAG]
Clémençon, Stéphan [Auteur]
Département Images, Données, Signal [IDS]
Laboratoire Traitement et Communication de l'Information [LTCI]
Bellet, Aurelien [Auteur]
Machine Learning in Information Networks [MAGNET]

Titre de l’ouvrage :

Extending Gossip Algorithms to Distributed Estimation of U -Statistics

Date de publication :

2015

Discipline(s) HAL :

Mathématiques [math]
Statistiques [stat]/Machine Learning [stat.ML]
Mathématiques [math]/Statistiques [math.ST]
Mathématiques [math]/Probabilités [math.PR]

Résumé en anglais : [en]

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, ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL