Il pettegolezzo è un modo efficiente per condividere informazioni su reti di grandi dimensioni e ha applicazioni inaspettate nella risoluzione di altri problemi matematici e di apprendimento automatico.

Osservando gli algoritmi classici del gossip da una prospettiva nuova, Il professor KAUST Peter Richtarik ha trovato un modo per accelerare significativamente la condivisione delle informazioni basata sul gossip, e nel processo, scoprì nuove applicazioni per questo efficiente approccio matematico.

Il pettegolezzo implica la condivisione di informazioni tra individui in una rete e può essere applicato matematicamente sia nei social network umani che nelle reti di dati, come sensori distribuiti.

"Una rete è un insieme di nodi, ciascuno connesso ad altri nodi tramite link, " spiega Richtarik. "Nei social network, ad esempio, gli individui sono collegati agli altri tramite legami di amicizia. Nelle reti di sensori, i sensori potrebbero essere collegati se sono abbastanza vicini da comunicare tramite una connessione wireless."

In molte applicazioni del mondo reale, è spesso utile eseguire calcoli basati sui dati memorizzati da tutti i nodi in una rete, come calcolare la media dei dati privati ​​archiviati da ciascun nodo, noto come problema del consenso medio. Però, perché la comunicazione è limitata ai collegamenti diretti tra i nodi, in pratica, questo è molto impegnativo.

"L'idea degli algoritmi di gossip è di eseguire questo calcolo tramite una comunicazione a coppie tra amici selezionati casualmente e di ripetere questo processo finché tutti gli individui non apprendono il risultato, " dice Richtarik. "Questo imita il modo in cui funzionano i pettegolezzi tra gli umani. È sorprendente che sia possibile dimostrare matematicamente che questa semplice strategia di comunicazione può risolvere un problema globale, problema a livello di rete."

In collaborazione con Nicolas Loizou dell'Università di Edimburgo in Scozia, Richtarik ha studiato gli algoritmi di gossip randomizzati e le loro connessioni con altri rami della matematica e dell'informatica.

Il loro studio teorico ha rivelato una profonda connessione tra gli algoritmi di gossip randomizzati e una branca della matematica chiamata algebra lineare, che implica la risoluzione di sistemi di molte equazioni con molte incognite. Hanno anche stabilito un legame profondo diretto con uno degli algoritmi più famosi nell'apprendimento automatico, il metodo stocastico di discesa del gradiente, che viene utilizzato per addestrare i modelli di deep learning impiegati in quasi tutte le applicazioni industriali. Queste intuizioni hanno aiutato i ricercatori a sviluppare protocolli di gossip nuovi e molto più veloci.

"Siamo stati in grado di sviluppare un algoritmo di gossip accelerato che ha bisogno di molti meno giri di gossip per raggiungere il valore di consenso medio, " dice Richtarik. "Il nostro metodo ha bisogno solo della radice quadrata del numero di round necessari per un classico algoritmo di gossip, sono 100 colpi invece di 10, 000. Lo abbiamo dimostrato matematicamente e abbiamo osservato questa accelerazione anche nella pratica."