The complexity of first-order optimization methods from a metric perspective

• 成果类型: Article
• 署名作者: Lewis, A. S.; Tian, Tonghua
• 署名单位: Cornell University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02091-2
• 发表日期: 2025
• 页码: 49-78
• 关键词: proximal point algorithm; descent methods; error-bounds; lojasiewicz inequalities; gradient flows; CONVERGENCE; minimization; SPACES

摘要

A central tool for understanding first-order optimization algorithms is the Kurdyka-& Lstrok;ojasiewicz inequality. Standard approaches to such methods rely crucially on this inequality to leverage sufficient decrease conditions involving gradients or subgradients. However, the KL property fundamentally concerns not subgradients but rather slope, a purely metric notion. By highlighting this view, and avoiding any use of subgradients, we present a simple and concise complexity analysis for first-order optimization algorithms on metric spaces. This subgradient-free perspective also frames a short and focused proof of the KL property for nonsmooth semi-algebraic functions.