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

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.

75 pages, 8 figures. Revised intro. New experiments. Simplified proofs. PyTorch code available here: https://github.com/COR-OPT/ntd.py/