Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functions

• 成果类型: Article
• 署名作者: Bianchi, Pascal; Hachem, Walid; Schechtman, Sholom
• 署名单位: IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom Paris; Universite Gustave-Eiffel; Centre National de la Recherche Scientifique (CNRS)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.0194
• 发表日期: 2024
• 页码: 1761-1790
• 关键词: algorithms

摘要

In nonsmooth stochastic optimization, we establish the nonconvergence of the stochastic subgradient descent (SGD) to the critical points recently called active strict saddles by Davis and Drusvyatskiy. Such points lie on a manifold M, where the function f has a direction of second-order negative curvature. Off this manifold, the norm of the Clarke subdifferential of f is lower-bounded. We require two conditions on f. The first assumption is a Verdier stratification condition, which is a refinement of the popular Whitney stratification. It allows us to establish a strengthened version of the projection formula of Bolte et al. for Whitney stratifiable functions and which is of independent interest. The second assumption, termed the angle condition, allows us to control the distance of the iterates to M. When f is weakly convex, our assumptions are generic. Consequently, generically, in the class of definable weakly convex functions, SGD converges to a local minimizer.