I detta papper studeras en klass av adaptiva gradientbaserade momentumalgoritmer som uppdaterar sökriktningar och inlärningshastigheter samtidigt med hjälp av tidigare gradienter. Denna klass, som vi kallar "Adam-typen", omfattar de populära algoritmerna såsom Adam [1], AMSGrad [2] och AdaGrad [3]. Trots sin popularitet i utbildning djupa neurala nätverk, konvergensen av dessa algoritmer för att lösa icke konvexa problem är fortfarande en öppen fråga. Detta dokument ger en uppsättning milda villkor som garanterar konvergensen för Adam-liknande metoder. Vi bevisar att under våra härledda förhållanden, dessa metoder kan uppnå konvergensen klass O (log T / ε T ) för icke konvex stokastisk optimering. Vi visar att villkoren är nödvändiga i den meningen att brott mot dem kan göra algoritmen divergera. Dessutom föreslår och analyserar vi en klass av (deterministiska) inkrementella adaptiva gradientalgoritmer, som har samma O(log T / ε T ) konvergenshastighet. Vår studie skulle också kunna utvidgas till en bredare klass av adaptiva gradientmetoder inom maskininlärning och optimering. Nya produktioner har föreslagit en mängd olika påskyndade versioner av GD och SGD [6, [10] [11] [12] [13] [15] [16] [17] [18] [19] [20], [21] [23] [24], [26]. Dessa resultat kan delas in i tre kategorier: a) momentummetoder [6, [10] [11] [12] [13] [15] [17] [17] [18] [19] som noggrant utformar nedstigningsriktningen  och t; b) adaptiva inlärningshastighetsmetoder [20, 3, 21, 22] som bestämmer goda inlärningshastigheter α t, och c) adaptiva gradientmetoder [23, 24, 1, 2] som har dubbla fördelar med a) och b). I synnerhet Adam [1], som tillhör den tredje typen av metoder, har blivit mycket populär för att lösa djupa inlärningsproblem, t.ex. att träna djupa neurala nätverk. Trots sin överlägsna prestation i praktiken saknas fortfarande en teoretisk undersökning av Adam-liknande metoder för icke konvex optimering. Mycket nyligen pekade arbetet [2] på Adams konvergensfrågor även i konvexa sammanhang, och föreslog AMSGrad, en korrigerad version av Adam. Även om AMSGrad har gjort ett positivt steg mot att förstå det teoretiska beteendet hos adaptiva gradientmetoder, var konvergensanalysen av [2] fortfarande mycket restriktiv eftersom den bara fungerar för konvexa problem, trots att de mest framgångsrika tillämpningarna är för icke konvexa problem. Tydligen finns det fortfarande en stor klyfta mellan teori och praktik. Såvitt vi vet är frågan om adaptiva gradientmetoder som Adam, AMSGrad, AdaGrad konvergerar för icke konvexa problem fortfarande öppen i teorin. Närbesläktat arbete Momentum metoder tar hänsyn till historien om första ordningen information [6, [10] [11] [12] [13] [14] [15] [16] [17] [18] [19]. En välkänd metod, som kallas Nesterovs accelererade lutning (NAG) ursprungligen utformad för konvex deterministisk optimering [6, 10, 11], konstruerar nedstigningsriktningen  på t med hjälp av skillnaden mellan det nuvarande iteratet och det föregående iteratet. I ett nyligen utfört arbete [12] studerades en generalisering av NAG för icke konvex stokastisk programmering. Liknar NAG-metoderna (HB) [13] [14] [15] [16] bildar nedstigningsriktningens vektor genom en sönderfallande summa av den tidigare gradientinformationen. Utöver NAG- och HB-metoderna integrerar stokastisk varians reducerad gradient (SVRG) metoder SGD med GD för att förvärva en hybrid nedstigningsriktning av reducerad varians [17] [18] [19]. Nyligen, vissa accelererade versionen av perturbed lutning nedstigning (PAGD) algoritm föreslås också i [25], som visar den snabbaste konvergensen bland alla hessiska fria algoritmer. Adaptive Learning Rate Methods accelererar vanliga SGD genom att använda kunskap om tidigare gradienter eller andra ordningen information i den nuvarande inlärningshastigheten α t [20, 3, 21, 22]. I [20], de diagonala elementen i den hessiska matrisen användes för att bestraffa en konstant inlärningshastighet. Att förvärva den andra ordningens information är dock beräkningsmässigt oöverkomligt. På senare tid har en adaptiv subgradientmetod (dvs. AdaGrad) bestraffat den nuvarande lutningen genom att dividera kvadratroten av medelvärdet av kvadratgradientkoordinaterna i tidigare iterationer [3]. Även om AdaGrad fungerar bra när lutningarna är glesa, analyseras dess konvergens endast i den konvexa världen. Andra adaptiva inlärnings metoder inkluderar Adadelta [21] och ESGD [22], som saknade teoretisk undersökning även om vissa konvergensförbättringar visades i praktiken. adaptiva gradientmetoder uppdaterar nedstigningsriktningen och inlärningshastigheten samtidigt genom att använda kunskap i det förflutna, och därmed åtnjuta dubbla fördelar med momentum och adaptiva inlärningshastighetsmetoder. Algoritmer i denna familj omfattar RMSProp [23], Nadam [24] och Adam [1]. Bland dessa har Adam blivit den mest använda metoden för att träna djupa neurala nätverk (DNN). Speciellt, Adam antar exponentiella rörliga medelvärden (med sönderfallande / glömska faktorer) av de tidigare gradienterna för att uppdatera nedstigningsriktningen. Den använder också invers av exponentiellt glidande medelvärde av kvadrat förflutna gradienter för att justera inlärningshastigheten. Arbetet [1] visade att Adam konvergerar med som mest O(1/ T ) hastighet för konvexa problem. Det senaste arbetet [2] pekade dock på Adams konvergensfrågor även i konvexa sammanhang och föreslog en modifierad version av Adam (dvs. AMSGrad), som använder en icke-ökande quadratisk normalisering och undviker Adams fallgropar. Även om AMSGrad har gjort ett betydande framsteg mot att förstå det teoretiska beteendet hos adaptiva gradientmetoder, fungerar konvergensanalysen av [2] endast för konvexa problem. Efter att icke-konvergens frågan om Adam har tagits upp i [2], Det finns några senaste arbeten på att föreslå nya varianter av Adam-typ algoritmer. Vid konvexa förhållanden föreslogs referens [26] för att stabilisera den koordinatvisa viktningsfaktorn för att säkerställa konvergens. Referens [27] utvecklade en algoritm som ändrar den koordinatvisa viktningsfaktorn för att uppnå bättre generaliseringsprestanda. Parallellt med detta arbete försöker flera verk förstå Adams prestanda i icke konvexa optimeringsproblem. Referens [28] gav konvergensgraden för den ursprungliga Adam och RMSprop under full batch (deterministisk) inställning, och [29] visade konvergensfrekvensen för en modifierad version av AdaGrad där koordinatvis viktning tas bort. Bidrag Annorlunda från ovan nämnda arbeten syftar vårt arbete till att bygga teorin för att förstå konvergensfrågor för en generisk klass av adaptiva gradientmetoder för icke konvex optimering. I synnerhet erbjuder vi en uppsättning milda villkor som garanterar konvergensen för Adam-liknande metoder. Vi sammanfattar vårt bidrag enligt följande. • Vi anser både stokastisk version och deterministisk inkrementell version av en klass av generaliserade Adam, kallad "Adam-typ", som inkluderar den nyligen föreslagna AMSGrad [2], AdaGrad [3], och stokastiska tungbollsmetoder som specialfall. Vi visar för första gången att under lämpliga förhållanden om stegen och algoritmparametrar, ovan nämnda algoritmer alla konvergera till första ordningen stationära lösningar av de ursprungliga icke konvexa problem, vilket ger O(log T / ε T ) konvergenshastighet.
Det senaste dokumentet REF ger ett liknande resultat i den stokastiska inställningen och för en allmän klass av adaptiva algoritmer.
On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}