Roddels is een efficiënte manier om informatie over grote netwerken te delen en heeft onverwachte toepassingen bij het oplossen van andere wiskundige en machine learning-problemen.

Door te kijken naar klassieke roddelalgoritmen vanuit een nieuw perspectief, KAUST-professor Peter Richtarik heeft een manier gevonden om het delen van informatie op basis van roddels aanzienlijk te versnellen. en in het proces, hij ontdekte nieuwe toepassingen voor deze efficiënte wiskundige benadering.

Roddels omvat het delen van informatie tussen individuen in een netwerk en kan wiskundig worden toegepast in zowel menselijke sociale netwerken als datanetwerken, zoals gedistribueerde sensoren.

"Een netwerk is een verzameling knooppunten, elk verbonden met andere knooppunten via links, " legt Richtarik uit. "In sociale netwerken, bijvoorbeeld, individuen zijn verbonden met anderen via vriendschapsbanden. In sensornetwerken sensoren kunnen worden aangesloten als ze dichtbij genoeg zijn om via een draadloze verbinding te communiceren."

In veel real-world toepassingen, het is vaak handig om berekeningen uit te voeren op basis van de gegevens die zijn opgeslagen door alle knooppunten in een netwerk, zoals het berekenen van het gemiddelde van de privégegevens die door elk knooppunt zijn opgeslagen, wat bekend staat als het gemiddelde consensusprobleem. Echter, omdat communicatie beperkt is tot directe verbindingen tussen knooppunten, in praktijk, dit is erg uitdagend.

"Het idee van roddelalgoritmen is om deze berekening uit te voeren door paarsgewijze communicatie tussen willekeurig geselecteerde vrienden en dit proces te herhalen totdat alle individuen het resultaat kennen, ", zegt Richtarik. "Dit bootst de manier na waarop roddels onder mensen werken. Het is verrassend dat het mogelijk is om wiskundig aan te tonen dat deze eenvoudige communicatiestrategie een globale, netwerkbreed probleem."

In samenwerking met Nicolas Loizou van de Universiteit van Edinburgh in Schotland, Richtarik heeft de gerandomiseerde roddelalgoritmen en hun connecties met andere takken van wiskunde en informatica bestudeerd.

Hun theoretische studie onthulde een diep verband tussen gerandomiseerde roddelalgoritmen en een tak van wiskunde die lineaire algebra wordt genoemd. waarbij stelsels van veel vergelijkingen met veel onbekenden worden opgelost. Ze hebben ook een directe diepe link gelegd met een van de beroemdste algoritmen in machine learning, de stochastische gradiëntafdalingsmethode, die wordt gebruikt om de deep-learningmodellen te trainen die in bijna alle industriële toepassingen worden gebruikt. Deze inzichten hielpen de onderzoekers om nieuwe en veel snellere roddelprotocollen te ontwikkelen.

"We hebben een versneld roddelalgoritme kunnen ontwikkelen dat veel minder roddelrondes nodig heeft om de gemiddelde consensuswaarde te bereiken. " zegt Richtarik. "Onze methode heeft alleen de vierkantswortel nodig van het aantal rondes dat nodig is voor een klassiek roddelalgoritme, dat zijn 100 ronden in plaats van 10, 000. We hebben dit wiskundig bewezen en deze versnelling ook in de praktijk waargenomen."