mlsanityData to 7 Oct 2026

Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms

arXiv 2102.02837 ↗First posted 4 Feb 2021cs.LG math.OCcited by 4

Not on the map. Why?

Abstract (arXiv)

We propose perturbed proximal algorithms that can provably escape strict saddles for nonsmooth weakly convex functions. The main results are based on a novel characterization of ε-approximate local minimum for nonsmooth functions, and recent developments on perturbed gradient methods for escaping saddle points for smooth problems. Specifically, we show that under standard assumptions, the perturbed proximal point, perturbed proximal gradient and perturbed proximal linear algorithms find ε-approximate local minimum for nonsmooth weakly convex functions in O(ε-2log(d)4) iterations, where d is the dimension of the problem.

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

Builds on

31 of 48 references.

References · 31

  1. 2014Identifying and attacking the saddle point problem in high-dimensional non-convex optimizationcited by 286
  2. 2017How to Escape Saddle Points Efficientlycited by 284
  3. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  4. 2014The Loss Surfaces of Multilayer Networkscited by 278
  5. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  6. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  7. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  8. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  9. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  10. 2016A Geometric Analysis of Phase Retrievalcited by 92
  11. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 81
  12. 2017Gradient Descent Can Take Exponential Time to Escape Saddle Pointscited by 74
19 more
  1. 2017Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descentcited by 66
  2. 2018Escaping Saddles with Stochastic Gradientscited by 66
  3. 2017"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functionscited by 46
  4. 2016The non-convex Burer-Monteiro approach works on smooth semidefinite programscited by 44
  5. 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
  6. 2016Fast Algorithms for Robust PCA via Gradient Descentcited by 39
  7. 2019Escaping from saddle points on Riemannian manifoldscited by 33
  8. 2017Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrievalcited by 24
  9. 2019Efficiently escaping saddle points on manifoldscited by 24
  10. 2016Accelerated Methods for Non-Convex Optimizationcited by 20
  11. 2015Complete Dictionary Recovery over the Spherecited by 19
  12. 2016On the low-rank approach for semidefinite programs arising in synchronization and community detectioncited by 17
  13. 2017The nonsmooth landscape of phase retrievalcited by 16
  14. 2018Escaping Saddle Points in Constrained Optimizationcited by 14
  15. 2019Short-and-Sparse Deconvolution -- A Geometric Approachcited by 9
  16. 2017Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequalitycited by 8
  17. 2019On the Global Geometry of Sphere-Constrained Sparse Blind Deconvolutioncited by 5
  18. 2019Perturbed Proximal Descent to Escape Saddle Points for Non-convex and Non-smooth Objective Functionscited by 4
  19. 2019Proximal methods avoid active strict saddles of weakly convex functionscited by 2

Built on by

Cited by year

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

4 papers.

  1. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  2. 2021Escaping strict saddle points of the Moreau envelope in nonsmooth optimizationcited by 7
  3. 2025PnP-CM: Consistency Models as Plug-and-Play Priors for Inverse Problemscited by 4
  4. 2024On the Hardness of Meaningful Local Guarantees in Nonsmooth Nonconvex Optimizationcited by 0