Gossip Dual Averaging pour l'optimisation décentralisée de fonctions par paires.

Résumé Dans les réseaux décentralisés (de capteurs, d'objets connectés, etc.), il existe un besoin important d'algorithmes efficaces pour optimiser une fonction de coût globale, par exemple pour apprendre un modèle global à partir des données locales collectées par chaque unité de calcul. Dans cet article, nous abordons le problème de la minimisation décentralisée de fonctions par paires de points de données, où ces points sont distribués sur les nœuds d'un graphe définissant la topologie de communication du réseau. Ce problème général trouve des applications dans le classement, l'apprentissage métrique de la distance et l'inférence de graphes, entre autres. Nous proposons de nouveaux algorithmes de commérage basés sur la moyenne double qui visent à résoudre de tels problèmes à la fois dans des contextes synchrones et asynchrones. Le cadre proposé est suffisamment flexible pour traiter les variantes contraintes et régularisées du problème d'optimisation. Notre analyse théorique révèle que les algorithmes proposés préservent le taux de convergence de la double moyenne centralisée jusqu'à un terme de biais additif. Nous présentons des simulations numériques sur des problèmes de maximisation de l'aire sous la courbe ROC (AUC) et d'apprentissage métrique qui illustrent l'intérêt pratique de notre approche.