A nearly linearly convergent first-order method for nonsmooth functions with quadratic growth

2022/04/29 by Damek Davis, Liwei Jiang, Davis, Damek +1 · 2 citations
Computer Science · Mathematics · #65K05 #65K10 #90C15 #90C30 #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2205.00064

openalex publication_date 2022/04/29 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28

Abstract

Classical results show that gradient descent converges linearly to minimizers of smooth strongly convex functions. A natural question is whether there exists a locally nearly linearly convergent method for nonsmooth functions with quadratic growth. This work designs such a method for a wide class of nonsmooth and nonconvex locally Lipschitz functions, including max-of-smooth, Shapiro's decomposable class, and generic semialgebraic functions. The algorithm is parameter-free and derives from Goldstein's conceptual subgradient method.

Cited by

• On computing Goldstein approximate second-order stationary points of structured nonsmooth nonconvex programs
• Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Pieces

Related

• A superlinearly convergent subgradient method for sharp semismooth problems
• A nonsmooth nonconvex descent algorithm
• A descent subgradient method using Mifflin line search for nonsmooth nonconvex optimization
• Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity
• Revisiting the Geometrically Decaying Step Size: Linear Convergence for Smooth or Non-Smooth Functions