Vi utvecklar och analyserar en variant av Nesterovs accelererade lutningsnedstigning (AGD) för minimering av smidiga icke-konvexa funktioner. Vi bevisar att ett av två fall inträffar: antingen konvergerar vår AGD variant snabbt, som om funktionen var konvex, eller så producerar vi ett intyg om att funktionen är "skyldig" att vara icke-konvex. Detta icke-konvexitet certifikat gör det möjligt för oss att utnyttja negativ krökning och få deterministisk, dimensionsfri acceleration av konvergens för icke-konvexa funktioner. För en funktion f med Lipschitz kontinuerlig lutning och Hessian, beräknar vi en punkt x med  skaf (x) ≤ i O( −7/4 log(1/)) gradient och funktionsutvärderingar. Om man dessutom antar att det tredje derivatet är Lipschitz, kräver vi endast O( −5/3 log(1/ )) utvärderingar.
Nyligen har det visat sig att GD kan påskyndas för att hitta en sådan punkt i O( −7/4 log( −1 )) REF.
"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
{'venue': 'ICML', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}