mlsanityData to 14 Oct 2026

ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary points

arXiv 2410.05025 ↗First posted 7 Oct 2024math.OC stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

This paper studies the nonsmooth optimization landscape of the ℓ1-norm rank-one symmetric matrix factorization problem using tools from second-order variational analysis. Specifically, as the main finding of this paper, we show that any second-order stationary point (and thus local minimizer) of the problem is actually globally optimal. Besides, some other results concerning the landscape of the problem, such as a complete characterization of the set of stationary points, are also developed, which should be interesting in their own rights. Furthermore, with the above theories, we revisit existing results on the generic minimizing behavior of simple algorithms for nonsmooth optimization and showcase the potential risk of their applications to our problem through several examples. Our techniques can potentially be applied to analyze the optimization landscapes of a variety of other more sophisticated nonsmooth learning problems, such as robust low-rank matrix recovery.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 38 of its 70 references that are in the map. First posted on arXiv 7 Oct 2024.

Builds on

38 of 70 references.

References · 38

  1. 2017How to Escape Saddle Points Efficientlycited by 285
  2. 2021A Geometric Analysis of Neural Collapse with Unconstrained Featurescited by 227
  3. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 160
  4. 2018Stochastic model-based minimization of weakly convex functionscited by 159
  5. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 129
  6. 2016Matrix Completion has No Spurious Local Minimumcited by 125
  7. 2022On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Featurescited by 97
  8. 2016Global Optimality of Local Search for Low Rank Matrix Recoverycited by 82
  9. 2022Are All Losses Created Equal: A Neural Collapse Perspectivecited by 78
  10. 2022Neural Collapse with Normalized Features: A Geometric Analysis over the Riemannian Manifoldcited by 50
  11. 2016Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methodscited by 35
  12. 2018Subgradient methods for sharp weakly convex functionscited by 33
26 more
  1. 2021On the Finite-Time Complexity and Practical Computation of Approximate Stationarity Concepts of Lipschitz Functionscited by 31
  2. 2017The Global Optimization Geometry of Low-Rank Matrix Optimizationcited by 25
  3. 2017Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrievalcited by 24
  4. 2015A Unified Approach to Error Bounds for Structured Convex Optimization Problemscited by 21
  5. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  6. 2020Understanding Notions of Stationarity in Non-Smooth Optimizationcited by 18
  7. 2016On the Estimation Performance and Convergence Rate of the Generalized Power Method for Phase Synchronizationcited by 17
  8. 2017The nonsmooth landscape of phase retrievalcited by 16
  9. 2022No Dimension-Free Deterministic Algorithm Computes Approximate Stationarities of Lipschitzianscited by 16
  10. 2020A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Groupcited by 15
  11. 2019Stochastic algorithms with geometric step decay converge linearly on sharp functionscited by 14
  12. 2023Neural Collapse in Multi-label Learning with Pick-all-label Losscited by 14
  13. 2018Exact Guarantees on the Absence of Spurious Local Minima for Non-negative Rank-1 Robust Principal Component Analysiscited by 13
  14. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
  15. 2022Universal Gradient Descent Ascent Method for Nonconvex-Nonconcave Minimax Optimizationcited by 12
  16. 2021Active manifolds, stratifications, and convergence to local minima in nonsmooth optimizationcited by 11
  17. 2021Stochastic Subgradient Descent Escapes Active Strict Saddles on Weakly Convex Functionscited by 9
  18. 2016A Family of Inexact SQA Methods for Non-Smooth Convex Minimization with Provable Convergence Guarantees Based on the Luo-Tseng Error Bound Propertycited by 7
  19. 2018On the Quadratic Convergence of the Cubic Regularization Method under a Local Error Bound Conditioncited by 7
  20. 2023Fast convergence to non-isolated minima: four equivalent conditions for C2 functionscited by 6
  21. 2021Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Methodcited by 4
  22. 2023ReSync: Riemannian Subgradient-based Robust Rotation Synchronizationcited by 3
  23. 2019Hybrid Inexact BCD for Coupled Structured Matrix Factorization in Hyperspectral Super-Resolutioncited by 2
  24. 2022A Linearly Convergent Algorithm for Rotationally Invariant ℓ1-Norm Principal Component Analysiscited by 2
  25. 2023Testing Stationarity Concepts for ReLU Networks: Hardness, Regularity, and Robust Algorithmscited by 2
  26. 2017A Study of Piecewise Linear-Quadratic Programscited by 1

Built on by

Not cited yet.