Convergence Rates of Zeroth Order Gradient Descent for Łojasiewicz Functions

Tianyu Wang () and Yasong Feng ()
Additional contact information
Tianyu Wang: Shanghai Center for Mathematical Sciences, Fudan University, Shanghai 200437, China; Shanghai Artificial Intelligence Laboratory, Shanghai 200232, China
Yasong Feng: Shanghai Center for Mathematical Sciences, Fudan University, Shanghai 200437, China

INFORMS Journal on Computing, 2024, vol. 36, issue 6, 1611-1633

Abstract: We prove convergence rates of Zeroth-order Gradient Descent (ZGD) algorithms for Łojasiewicz functions. Our results show that for smooth Łojasiewicz functions with Łojasiewicz exponent larger than 0.5 and smaller than 1, the functions values can converge much faster than the (zeroth-order) gradient descent trajectory. Similar results hold for convex nonsmooth Łojasiewicz functions.

Keywords: optimization; zeroth order optimization; Łojasiewicz functions (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0247 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:6:p:1611-1633

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().