mlsanityData to 14 Oct 2026

Escaping strict saddle points of the Moreau envelope in nonsmooth optimization

arXiv 2106.09815 ↗First posted 17 Jun 2021math.OC cs.LG stat.MLcited by 7

Not on the map. Why?

Abstract (arXiv)

Recent work has shown that stochastically perturbed gradient methods can efficiently escape strict saddle points of smooth functions. We extend this body of work to nonsmooth optimization, by analyzing an inexact analogue of a stochastically perturbed gradient method applied to the Moreau envelope. The main conclusion is that a variety of algorithms for nonsmooth optimization can escape strict saddle points of the Moreau envelope at a controlled rate. The main technical insight is that typical algorithms applied to the proximal subproblem yield directions that approximate the gradient of the Moreau envelope in relative terms.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 27 of its 48 references that are in the map. First posted on arXiv 17 Jun 2021.

Builds on

27 of 48 references.

References · 27

  1. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 243
  2. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  3. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 129
  4. 2016Matrix Completion has No Spurious Local Minimumcited by 125
  5. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
  6. 2016A Geometric Analysis of Phase Retrievalcited by 92
  7. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 82
  8. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
  9. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  10. 2018Escaping Saddles with Stochastic Gradientscited by 66
  11. 2019Escaping from saddle points on Riemannian manifoldscited by 33
  12. 2015When Are Nonconvex Problems Not Scary?cited by 28
15 more
  1. 2019Simple and optimal high-probability bounds for strongly-convex stochastic gradient descentcited by 27
  2. 2017The Global Optimization Geometry of Low-Rank Matrix Optimizationcited by 25
  3. 2019Efficiently escaping saddle points on manifoldscited by 24
  4. 2018A Newton-CG Algorithm with Complexity Guarantees for Smooth Unconstrained Optimizationcited by 23
  5. 2018Adaptive regularization with cubics on manifoldscited by 17
  6. 2017Complexity analysis of second-order line-search algorithms for smooth nonconvex optimizationcited by 16
  7. 2018Escaping Saddle Points in Constrained Optimizationcited by 14
  8. 2018On the Local Minima of the Empirical Riskcited by 12
  9. 2019Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimizationcited by 10
  10. 2019A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guaranteescited by 7
  11. 2020Efficient Clustering for Stretched Mixtures: Landscape and Optimalitycited by 6
  12. 2015Generic minimizing behavior in semi-algebraic optimizationcited by 5
  13. 2018Convergence to Second-Order Stationarity for Constrained Non-Convex Optimizationcited by 5
  14. 2021Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithmscited by 4
  15. 2020A Line-Search Descent Algorithm for Strict Saddle Functions with Complexity Guaranteescited by 2

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 1; 2024: 4; 2025: 1.

7 papers.

  1. 2024Adam with model exponential moving average is effective for nonconvex optimizationcited by 23
  2. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  3. 2024General framework for online-to-nonconvex conversion: Schedule-free SGD is also effective for nonconvex optimizationcited by 15
  4. 2023Can Learning Be Explained By Local Optimality In Robust Low-rank Matrix Recovery?cited by 2
  5. 2024Avoiding strict saddle points of nonconvex regularized problemscited by 1
  6. 2024On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimizationcited by 0
  7. 2025Binarizing Physics-Inspired GNNs for Combinatorial Optimizationcited by 0