Accelererer vineffekten

Sladder er en effektiv måde at dele information på tværs af store netværk og har uventede anvendelser til at løse andre matematiske og maskinlæringsproblemer.

Ved at se på klassiske sladderalgoritmer fra et nyt perspektiv, KAUST Professor Peter Richtarik har fundet en måde at fremskynde sladderbaseret informationsdeling markant, og i processen, han opdagede nye anvendelser for denne effektive matematiske tilgang.

Sladder involverer deling af information mellem individer i et netværk og kan anvendes matematisk i både menneskelige sociale netværk og datanetværk, såsom distribuerede sensorer.

"Et netværk er en samling af noder, hver forbundet til andre noder via links, " forklarer Richtarik. "I sociale netværk, for eksempel, enkeltpersoner er forbundet med andre via venskabslinks. I sensornetværk, sensorer kan tilsluttes, hvis de er tæt nok på til at kommunikere via en trådløs forbindelse."

I mange applikationer i den virkelige verden, det er ofte nyttigt at udføre beregninger baseret på de data, der er lagret af alle noder på tværs af et netværk, såsom at beregne gennemsnittet af de private data, der er lagret af hver node, som er kendt som det gennemsnitlige konsensusproblem. Imidlertid, fordi kommunikation er begrænset til direkte forbindelser mellem noder, i praksis, dette er meget udfordrende.

"Idéen med sladderalgoritmer er at udføre denne beregning ved parvis kommunikation mellem tilfældigt udvalgte venner og at gentage denne proces, indtil alle individer lærer resultatet, " siger Richtarik. "Dette efterligner den måde, sladder fungerer på blandt mennesker. Det er overraskende, at det er muligt matematisk at vise, at denne simple kommunikationsstrategi kan løse en global, netværksdækkende problem."

I samarbejde med Nicolas Loizou fra University of Edinburgh i Skotland, Richtarik har studeret de randomiserede sladderalgoritmer og deres forbindelser til andre grene af matematik og datalogi.

Deres teoretiske undersøgelse afslørede en dyb forbindelse mellem randomiserede sladderalgoritmer og en gren af ​​matematik kaldet lineær algebra, som involverer løsning af systemer af mange ligninger med mange ukendte. De etablerede også en direkte dyb forbindelse med en af ​​de mest berømte algoritmer inden for maskinlæring, den stokastiske gradientnedstigningsmetode, som bruges til at træne de dybe læringsmodeller, der anvendes i næsten alle industrielle applikationer. Disse indsigter hjalp forskerne med at udvikle nye og meget hurtigere sladderprotokoller.

"Vi var i stand til at udvikle en accelereret sladderalgoritme, der har brug for mange færre sladderrunder for at nå den gennemsnitlige konsensusværdi, " siger Richtarik. "Vores metode behøver kun kvadratroden af ​​det antal runder, der er nødvendige for en klassisk sladderalgoritme, det er 100 runder i stedet for 10, 000. Vi beviste dette matematisk og observerede også denne acceleration i praksis."