Active manifolds, stratifications, and convergence to local minima in nonsmooth optimization
Authors:
- Damek DavisDDDamek Davis
- Dmitriy DrusvyatskiyDDDmitriy Drusvyatskiy
- Liwei JiangLJLiwei Jiang
Preprint
Abstract
We show that the subgradient method converges only to local minimizers when applied to generic Lipschitz continuous and subdifferentially regular functions that are definable in an o-minimal structure. At a high level, the argument we present is appealingly transparent: we interpret the nonsmooth dynamics as an approximate Riemannian gradient method on a certain distinguished submanifold that captures the nonsmooth activity of the function. In the process, we develop new regularity conditions in nonsmooth analysis that parallel the stratification conditions of Whitney, Kuo, and Verdier and extend stochastic processes techniques of Pemantle.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Stochastic algorithms with geometric step decay converge linearly on sharp functionsMathematical Programming, 2023
- Proximal Methods Avoid Active Strict Saddles of Weakly Convex FunctionsFoundations of Computational Mathematics, 2021
- First-order methods almost always avoid strict saddle pointsMathematical Programming, 2019
- A Geometric Analysis of Phase RetrievalFoundations of Computational Mathematics, 2017
- Proximal alternating linearized minimization for nonconvex and nonsmooth problemsMathematical Programming, 2013
- Calculus Without Derivatives2013
- Nonsmooth Analysis of Singular Values. Part I: TheorySet-Valued Analysis, 2005
- Lipschitz functions with maximal Clarke subdifferentials are genericProceedings of the American Mathematical Society, 2000
- Prox-regular functions in variational analysisTransactions of the American Mathematical Society, 1996
- All convex invariant functions of hermitian matricesArchiv der Mathematik, 1957