Zona de cercetare putin probabila dezvaluie o rasucire surprinzatoare in optimizarea non-lina – Microsoft Research

Invatarea automata moderna se caracterizeaza prin doua caracteristici cheie: modele cu dimensiuni ridicate si seturi de date foarte mari. Fiecare dintre aceste caracteristici prezinta propriile sale provocari unice, de la probleme de baza, cum ar fi stocarea si accesarea tuturor datelor, la cautari matematice mai complexe, cum ar fi gasirea unor algoritmi buni pentru a cauta prin spatiul de dimensiuni ridicate al modelelor. In lucrarea noastra recenta, despre care suntem bucurosi sa anuntam ca a primit un premiu pentru cea mai buna lucrare la Conferinta din acest an asupra sistemelor de procesare a informatiilor neuronale (NeurIPS), gasim o noua legatura surprinzatoare intre aceste doua aspecte cheie. Am descoperit ca binecunoscutul fenomen de acceleratie pentru o optimizare uniforma poate fi aplicat intotdeauna optimizarii distribuite – chiar si in setari care nu sunt netede – datorita fluiditatii inerente a procesului de comunicare!

Progresul si cautarea necunoscutului

Provocarile calculului si optimizarii distribuite au fost studiate separat de mai bine de jumatate de secol. Luati, de exemplu, provocarea mai usoara, dar inca predominanta, in multe sarcini ale modelelor liniare, cum ar fi regresia logistica. Acolo teoria matematica a tehnicilor locale de cautare – de exemplu, coborarea in gradient – in spatii cu dimensiuni ridicate este aproape completa. Acest lucru se datoreaza in mare parte muncii din scoala de cercetatori si ingineri rusi din anii 1980, inclusiv a figurilor centrale Arkadi Nemirovski si Yurii Nesterov. Au dezvoltat o teorie a metodelor optime de cautare locala, obtinand algoritmi reali, cum ar fi coborarea in gradient accelerat bazata pe impuls, precum si dovezi ca, intr-un anumit sens, nu exista algoritmi mai buni. Aceasta teorie a fost extrem de influenta si a pus invatarea automata moderna pe o baza solida. Un alt exemplu este evaluarea zgomotoasa, care a produs celebra tehnica descendenta stocastica de gradient. Dar cercetarile de astazi in aceste domenii raman foarte active, iar invatarea automata moderna vine cu o serie de alte probleme fundamentale in care metodele optime nu sunt inca cunoscute. Un interes deosebit este intrebarea cum sa proiectam metode optime de cautare locala pentru optimizarea convexa distribuita, luand in considerare atat spatiul cu dimensiuni ridicate, cat si seturile de date imense.

Microsoft Research a fost mult timp investit in gasirea raspunsurilor la aceasta intrebare, inclusiv lucrari fundamentale privind relatia dintre invatarea distribuita si descendenta gradientului mini-lot. Intr-o colaborare recenta intre Microsoft Research AI si Centrul Comun Microsoft Research-Inria din Paris, s-au facut noi progrese in ceea ce priveste metodele optime pentru optimizarea distribuita. O lucrare despre optimizarea fara probleme a fost publicata anul trecut la Conferinta internationala de invatare automata (ICML). Lucrarea noastra NeurIPS 2018, „Algoritmi optimi pentru optimizarea distribuita non-neteda in retele”, exploreaza problema mult mai delicata a optimizarii non-netede.

Un taram complet diferit

Este bine cunoscut faptul ca, pentru optimizarea seriala a convexului neted, tehnicile bazate pe impuls ofera rate de convergenta optime. O constatare usor coplesitoare a lucrarii ICML 2017 este ca, in setarea distribuita, se pot implementa pur si simplu astfel de metode seriale optime impreuna cu protocolul master / slave, iar acest lucru, la randul sau, va produce o metoda distribuita optima. In acest moment, este crucial sa ne amintim ce inseamna de fapt matematic optim. O metoda este „optima” numai in cadrul setului de ipoteze in baza carora este dovedita optimitatea. In special, exista o slabiciune extrem de importanta in protocolul master / slave: nu este robust impotriva defectiunilor masinii, care sunt omniprezente in calculul distribuit. Odata ce se adauga cerinta de robustete – de exemplu, cerand ca comunicarea sa urmeze asa-numitul protocol de barfe – se intra intr-un domeniu cu totul diferit. In acest regim, o metoda mult mai profunda se dovedeste a fi optima, una bazata pe o reprezentare primala-duala a obiectivului distribuit. Astfel de reprezentari sunt cunoscute de mult timp si stau la baza multor algoritmi practici, cum ar fi metoda alternativa de directie a multiplicatorilor (ADMM). Lucrarea ICML demonstreaza ca, intr-o conditie locala de netezime, astfel de tehnici primale-duale sunt de fapt optime.

Descoperirea netezimii ascunse

Pentru expertii in optimizare, optimizarea distribuita in scenariul non-neted ar putea parea o zona de cercetare putin probabila, deoarece este bine cunoscut faptul ca pentru optimizarea seriala non-neteda, descendenta gradientului de vanilie este deja optima. Insa, intorsatura surprinzatoare de aici – si intr-adevar observatia cheie din lucrarea noastra NeurIPS – este ca natura distribuita induce intotdeauna o anumita netezime. Putin mai precis, in timp ce fiecare masina s-ar putea confrunta cu o problema dificila, neteda, procesul de agregare rezultat din comunicare este de fapt un proces lin.

Aceasta netezime ascunsa se dezvaluie in metodele primale-duale, in care acum problema primara este neteda, in timp ce problema duala este neteda. Ideea devine apoi, aproximativ, de a folosi o metoda optima non-neteda in primara impreuna cu o metoda optima neteda in dual. Cu alte cuvinte, optimizarea distribuita neuniforma permite intotdeauna o comunicare accelerata, in ciuda non-netezimii problemei initiale. Cititorul intelept ar fi putut observa ca invocarea metodelor primal-dual inseamna inevitabil ca se ia in considerare regularitatea locala (adica pe fiecare masina) a functiei distribuite, lasand deschisa problema metodelor optime sub o presupunere de regularitate globala. Lucrarea noastra NeurIPS propune, de asemenea, un algoritm pentru acest scenariu bazat pe idei profunde in algoritmi randomizati. In orice caz, dovedirea optimitatii ramane o provocare tehnica dificila. In special, presupunem ca metodele optime sub regularitate globala ar putea suferi inerent de dimensiunea inalta a spatiului. Dovada unei asemenea afirmatii este o problema deschisa interesanta!