Skvaller är ett effektivt sätt att dela information över stora nätverk och har oväntade tillämpningar för att lösa andra matematiska problem och problem med maskininlärning.

Genom att titta på klassiska skvalleralgoritmer ur ett nytt perspektiv, KAUST Professor Peter Richtarik har hittat ett sätt att avsevärt påskynda skvallerbaserad informationsdelning, och i processen, han upptäckte nya tillämpningar för detta effektiva matematiska tillvägagångssätt.

Skvaller innebär delning av information mellan individer i ett nätverk och kan tillämpas matematiskt i både mänskliga sociala nätverk och datanätverk, såsom distribuerade sensorer.

"Ett nätverk är en samling noder, var och en ansluten till andra noder via länkar, " förklarar Richtarik. "I sociala nätverk, till exempel, individer är kopplade till andra via vänskapslänkar. I sensornätverk, sensorer kan anslutas om de är tillräckligt nära för att kommunicera via en trådlös anslutning."

I många verkliga tillämpningar, det är ofta användbart att utföra beräkningar baserat på data som lagras av alla noder i ett nätverk, som att beräkna medelvärdet av den privata data som lagras av varje nod, vilket är känt som det genomsnittliga konsensusproblemet. Dock, eftersom kommunikation är begränsad till direkta länkar mellan noder, i praktiken, det här är väldigt utmanande.

"Idén med skvalleralgoritmer är att utföra denna beräkning genom parvis kommunikation mellan slumpmässigt utvalda vänner och att upprepa denna process tills alla individer lär sig resultatet, ", säger Richtarik. "Detta härmar hur skvaller fungerar bland människor. Det är förvånande att det är möjligt att matematiskt visa att denna enkla kommunikationsstrategi kan lösa en global, nätverksomfattande problem."

I samarbete med Nicolas Loizou från University of Edinburgh i Skottland, Richtarik har studerat de randomiserade skvalleralgoritmerna och deras kopplingar till andra grenar av matematik och datavetenskap.

Deras teoretiska studie avslöjade ett djupt samband mellan randomiserade skvalleralgoritmer och en gren av matematiken som kallas linjär algebra, som innebär att lösa system av många ekvationer med många okända. De etablerade också en direkt djuplänk med en av de mest kända algoritmerna inom maskininlärning, den stokastiska gradientnedstigningsmetoden, som används för att träna de djupinlärningsmodeller som används i nästan alla industriella tillämpningar. Dessa insikter hjälpte forskarna att utveckla nya och mycket snabbare skvallerprotokoll.

"Vi kunde utveckla en accelererad skvalleralgoritm som behöver många färre skvallerrundor för att nå det genomsnittliga konsensusvärdet, " säger Richtarik. "Vår metod behöver bara kvadratroten av antalet varv som behövs för en klassisk skvalleralgoritm, det är 100 omgångar istället för 10, 000. Vi bevisade detta matematiskt och observerade denna acceleration i praktiken också."