Abstract-Vi analyserar konvergensen av gradient-baserade optimeringsalgoritmer som baserar sina uppdateringar på fördröjd stokastisk gradient information. Den huvudsakliga tillämpningen av våra resultat är att gradient-baserade distribuerade optimeringsalgoritmer där en master nod utför parameteruppdateringar medan arbetarnoder beräkna stokastiska gradienter baserat på lokal information parallellt, vilket kan ge upphov till förseningar på grund av asynkroni. Vi tar motivationen från statistiska problem där datans storlek är så stor att den inte får plats på en dator; med tillkomsten av enorma datamängder inom biologi, astronomi och internet är sådana problem nu vanliga. Vårt huvudsakliga bidrag är att visa att för smidiga stokastiska problem är förseningarna asymptotiskt försumbara och vi kan uppnå orderoptimala konvergensresultat. Vi visar n-node arkitekturer vars optimeringsfel i stokastiska problem- trots asynkrona fördröjningar-skalor asymptotiskt som O(1/ ε nT ) efter T iterationer. Denna hastighet är känd för att vara optimal för ett distribuerat system med n noder även i frånvaro av förseningar. Vi kompletterar dessutom våra teoretiska resultat med numeriska experiment på en logistisk regressionsuppgift. Vi fokuserar på stokastisk konvex optimering problem av formen min x.X f (x) för där X  på R d är en sluten konvex uppsättning, P är en sannolikhetsfördelning över  på, och F (· ;  på) är konvexa för alla  på, så att f är konvex. Klassiska stokastiska gradientalgoritmer [7, 6] iterativt uppdatera en parameter x(t)  på X genom provtagning  på P, beräkning g(t) =  på F (x(t); och utföra uppdateringen x(t + 1) = Π X (x(t) − α(t)g(t)), där Π X betecknar projektion på uppsättningen X och α(t) R är en stegvis. I detta papper analyserar vi asynkrona gradientmetoder, där i stället för att ta emot aktuell information g(t), förfarandet får ut av datum gradienter g(t − τ (t)) =  och F (x(t − τ (t)), där τ (t) är den (potentiellt slumpmässiga) fördröjningen vid tiden t. Det centrala bidraget av detta papper är att utveckla algoritmer som-under naturliga antaganden om funktionerna F i målet (1)-uppnå asymptotiskt optimala konvergenshastigheter för stokastisk konvex optimering trots förseningar. Vår modell av information om fördröjd gradient är särskilt relevant i distribuerade optimeringsscenarier, där en master upprätthåller parametrarna x medan arbetstagare beräknar stokastiska gradienter av målet (1) med hjälp av en lokal delmängd av data.  gn(t − 1) Bild 1................................................................ Cyklisk försenad arkitektur. Arbetare beräknar lutningar i parallella, passerar ut-of-date (stokastiska) gradienter g i (t − τ ) =  på i (x(t − τ )) för att bemästra. Befälhavaren svarar med aktuella parametrar. Diagram visar parametrar och gradienter som kommuniceras mellan v t och t + n − 1.
REF visar att begränsad fördröjning kan tolereras samtidigt som linjär upptrappning för konvexa optimeringsproblem bibehålls.
Distributed delayed stochastic optimization
{'venue': '2012 IEEE 51st IEEE Conference on Decision and Control (CDC)', 'journal': '2012 IEEE 51st IEEE Conference on Decision and Control (CDC)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}