Tight convergence rates of the gradient method on smooth hypoconvex functions

Rotaru, Teodor
Glineur, François
Patrinos, Panagiotis

Publication date

June 2022

Abstract

We perform the first tight convergence analysis of the gradient method with varying step sizes when applied to smooth hypoconvex (weakly convex) functions. Hypoconvex functions are smooth nonconvex functions whose curvature is bounded and assumed to belong to the interval $[\mu, L]$, with $\mu<0$. Our convergence rates improve and extend the existing analysis for smooth nonconvex functions with $L$-Lipschitz gradient (which corresponds to the case $\mu=-L$), and smoothly interpolates between that class and the class of smooth convex functions. We obtain our results using the performance estimation framework adapted to hypoconvex functions, for which new interpolation conditions are derived. We derive explicit upper bounds on the minimum gra...

Extracted data

We use cookies to provide a better user experience.

Data Protection

Tight convergence rates of the gradient method on smooth hypoconvex functions

Abstract

Extracted data

Tight convergence rates of the gradient method on smooth hypoconvex functions

Abstract

Extracted data

Related items

Related items