Study of the behaviour of Nesterov Accelerated Gradient in a non convex setting: the strongly quasar convex case

2024/05/30 by Hermant, Julien, Aujol, Jean-François, Dossal, Charles +1 · 4 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2405.19809

Abstract

We study the convergence of Nesterov Accelerated Gradient (NAG) minimization algorithmapplied to a class of non convex functions called strongly quasar convex functions. We show thatNAG can achieve an accelerated convergence speed at the cost of a lower curvature assumption.We provide a continuous analysis through high resolution ODEs, where we show that despite thatnegative friction may appear, the solution of the system achieves accelerated rate of convergenceto the minimum. Finally, we identify the key geometrical property that, if dropped, theoreticallycancels the acceleration phenomenon.

Cited by

• Mirror Descent Methods for Quasar Convex Optimization Problems With Non-Smooth Inequality Constraints
• Continuized Nesterov Acceleration for Non-Convex Optimization
• Star Quasiconvexity: an Unified Approach for Linear Convergence of First-Order Methods Beyond Convexity
• Extending Linear Convergence of the Proximal Point Algorithm: The Quasar-Convex Case

Related

• Continuized Acceleration for Quasar Convex Functions in Non-Convex Optimization
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• A geometric alternative to Nesterov's accelerated gradient descent
• Revisiting the acceleration phenomenon via high-resolution differential equations
• Optimal convergence rates for Nesterov acceleration