Benign population landscapes do not transfer to empirical risk minimization in nonsmooth optimization
math.OC, cs.LG
Submitted: 2026-11-01
Updated: 2026-11-01
Comments: 71 pages, 2 figures, 1 table
Code: https://github.com/PenghaoWang1225/Phase-Retrieval
License: http://creativecommons.org/licenses/by/4.0/
The gist: Benign landscapes provide a geometric explanation for the success of iterative methods on nonconvex problems arising in data science.
Abstract
Benign landscapes provide a geometric explanation for the success of iterative methods on nonconvex problems arising in data science. The landscape is benign if every local minimizer is global and every other critical point is a strict saddle. For methods that avoid strict saddles, convergence to a critical point therefore implies convergence to a global minimizer. For smooth stochastic optimization, a common strategy for establishing such landscapes proceeds in two steps: (i) establish benign geometry for the population objective---which is often easier to analyze---and (ii) transfer this geometry to the empirical objective using concentration of gradients and Hessians. Recent work has extended saddle-point avoidance guarantees to weakly convex nonsmooth optimization through the notion of active strict saddles. We show, however, that benign population geometry need not transfer to empirical objectives in this setting. Specifically, for robust phase retrieval with Gaussian measurements---a well-studied and highly structured problem---the population objective is benign. Nevertheless, the empirical objective has sharp spurious local minima with probability bounded away from zero as the sample size tends to infinity. This asymptotic probability lower bound is independent of the dimension.
Sources
- $\ell_1$-norm rank-one symmetric matrix factorization has no spurious second-order stationary points
- Gradient descent avoids strict saddles with a simple line-search method too
- Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework
- Failure of uniform laws of large numbers for subdifferentials and beyond
- Lipschitzian SLLNs for random functions
- Smoothed Robust Phase Retrieval
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise