Extension des algorithmes de commérage à l'estimation distribuée des statistiques U.

Résumé Des algorithmes efficaces et robustes pour l'estimation décentralisée dans les réseaux sont essentiels pour de nombreux systèmes distribués. Alors que l'estimation distribuée des statistiques de la moyenne de l'échantillon a fait l'objet d'une grande attention, le calcul des statistiques U, qui repose sur le calcul plus coûteux de la moyenne sur des paires d'observations, est un domaine moins étudié. Pourtant, de telles fonctions de données sont essentielles pour décrire les propriétés globales d'une population statistique, avec des exemples importants comme l'aire sous la courbe, la variance empirique, la différence de moyenne de Gini et la dispersion ponctuelle au sein d'un cluster. Cet article propose de nouveaux algorithmes de commérage aléatoires synchrones et asynchrones qui propagent simultanément les données à travers le réseau et maintiennent les estimations locales de la statistique U d'intérêt. Nous établissons des limites de taux de convergence de O(1 / t) et O(log t / t) pour les cas synchrones et asynchrones respectivement, où t est le nombre d'itérations, avec des termes explicites dépendant des données et du réseau. Au-delà des comparaisons favorables en termes d'analyse de taux, les expériences numériques fournissent des preuves empiriques que les algorithmes proposés surpassent l'approche introduite précédemment.