Nesterov's accelererade lutning nedstigning (AGD), ett exempel på den allmänna familjen av "momentum metoder," tydligt uppnår snabbare konvergens än lutning nedstigning (GD) i konvex inställning. Om dessa metoder är överlägsna GD i den icke konvexa inställningen förblir dock öppna. I detta dokument studeras en enkel variant av AGD, och det visar att den undgår sadelpunkter och finner en andra ordningens stationär punkt i Õ(1/ på 7/4 ) iterationer, snabbare än de Õ(1/ på 2 ) iterationer som krävs av GD. Såvitt vi vet är detta den första hessiska fria algoritmen att hitta en andra ordningens stationär punkt snabbare än GD, och även den första singel-loop algoritmen med en snabbare hastighet än GD även i inställningen av att hitta en första ordningen stationär punkt. Vår analys bygger på två nyckelidéer: (1) användningen av en enkel Hamilton-funktion, inspirerad av ett kontinuerligt tidsperspektiv, som AGD monotont minskar per steg även för icke konvexa funktioner, och (2) en ny ram som kallas förbättring eller lokalisering, vilket är användbart för att spåra det långsiktiga beteendet hos gradientbaserade optimeringsalgoritmer. Vi tror att dessa tekniker kan fördjupa vår förståelse av både accelerationsalgoritmer och icke-konvex optimering.
Den mest kända runtime komplexiteten av dessa metoder är O −7/4 vid inställning H = ε, som föreslås i REF.
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}