Gossip est un moyen efficace de partager des informations sur de grands réseaux et a des applications inattendues dans la résolution d'autres problèmes mathématiques et d'apprentissage automatique.

En examinant les algorithmes de potins classiques sous un nouvel angle, Le professeur KAUST Peter Richtarik a trouvé un moyen d'accélérer considérablement le partage d'informations basées sur les potins, et dans le processus, il a découvert de nouvelles applications pour cette approche mathématique efficace.

Gossip implique le partage d'informations entre les individus dans un réseau et peut être appliqué mathématiquement à la fois dans les réseaux sociaux humains et les réseaux de données, tels que les capteurs distribués.

"Un réseau est un ensemble de nœuds, chacun connecté à d'autres nœuds via des liens, " explique Richtarik. " Dans les réseaux sociaux, par exemple, les individus sont connectés aux autres via des liens d'amitié. Dans les réseaux de capteurs, les capteurs pourraient être connectés s'ils sont suffisamment proches pour communiquer via une connexion sans fil.

Dans de nombreuses applications du monde réel, il est souvent utile d'effectuer des calculs basés sur les données stockées par tous les nœuds d'un réseau, comme le calcul de la moyenne des données privées stockées par chaque nœud, qui est connu comme le problème de consensus moyen. Cependant, car la communication se limite à des liens directs entre les nœuds, en pratique, c'est très difficile.

"L'idée des algorithmes de potins est d'effectuer ce calcul par communication par paires entre amis sélectionnés au hasard et de répéter ce processus jusqu'à ce que tous les individus connaissent le résultat, " dit Richtarik. " Cela imite la façon dont fonctionnent les commérages parmi les humains. Il est surprenant qu'il soit possible de montrer mathématiquement que cette simple stratégie de communication peut résoudre un problème global, problème à l'échelle du réseau."

En collaboration avec Nicolas Loizou de l'Université d'Edimbourg en Ecosse, Richtarik a étudié les algorithmes de potins aléatoires et leurs liens avec d'autres branches des mathématiques et de l'informatique.

Leur étude théorique a révélé un lien profond entre les algorithmes de potins aléatoires et une branche des mathématiques appelée algèbre linéaire, ce qui implique la résolution de systèmes de nombreuses équations avec de nombreuses inconnues. Ils ont également établi un lien direct et profond avec l'un des algorithmes les plus célèbres de l'apprentissage automatique, la méthode de descente de gradient stochastique, qui est utilisé pour former les modèles d'apprentissage en profondeur utilisés dans presque toutes les applications industrielles. Ces informations ont aidé les chercheurs à développer de nouveaux protocoles de potins beaucoup plus rapides.

« Nous avons pu développer un algorithme de potins accéléré qui a besoin de beaucoup moins de tours de potins pour atteindre la valeur moyenne du consensus, " dit Richtarik. " Notre méthode n'a besoin que de la racine carrée du nombre de tours nécessaires pour un algorithme de potins classique, c'est 100 tours au lieu de 10, 000. Nous l'avons prouvé mathématiquement et observé cette accélération dans la pratique également."