acceptodds
Under review as a conference paper at ICLR 2027

Benign population landscapes do not transfer to empirical risk minimization in nonsmooth optimization

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: establish benign geometry for the population objective—which is often easier to analyze—and 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.

Primary area:
optimization
Keywords:
Nonsmooth optimization, Landscape analysis, Robust phase retrieval, active strict saddle property

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_FByfOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the critical points of finite-sample and population robust phase retrieval. The population objective is shown to be benign: all critical points that are not global minimizers are (smooth) strict saddles, and therefore not traps for first order optimization methods. In contrast, the finite sample objective admits strict local minimizers away from the global minimizers as well as (nonsmooth) strict saddle points. The strict local minimizers are not benign, as they can trap optimization methods. Authors then count a subset of local minimizers, those such that the objective function grows away sharply in all directions, showing that their number grows polynomially in observation number in expectation, and that the probability of having at least one such minimizer be spurious is above 0.136. The proofs combine involved techniques and notions from nonsmooth analysis and probability theory. The general message is that nonsmooth per-sample losses may provide benign population risk, but still cause spurious local minima in the empirical risk.

Critical strengths
  • the paper is well motivated -- existence of spurious local minimizers and benign landscapes are relevant in both optimization and ML; the nonsmooth analysis approach is sound and builds on well established foundations and prior works.

  • the paper is clearly written and easy to follow. In particular, the main body provides a clear and insightful sketch of the proofs in appendix. In addition, the main body of the paper is technically sound. I have not checked the appendix entirely.

Critical weaknesses

None.

Questions for authors
  • l. 329: the matrix AI−1A_I^{-1} has size n×dn \times d. Rather than inverse, do you mean pseudo-inverse?

  • You use the notion of "strict local minimizer" three times (l. 97, 256, 272) without defining this notion. The last occurrence is crucial to understand theorem 3.2. What do you mean by "strict local minimizer"?

  • Your analysis focuses on sharp local minimizers, which are the worse traps for first-order methods in some sense. Other traps could be local minimizers that are not sharp in all directions, but have an active manifold of positive dimension and a positive definite riemannian hessian. Such points would also be traps for 1st order methods. Do such points exists for robust phase retrieval? Could the techniques developed in this work be applied to count their number?

  • Can you please clarify why the critical points captured by Nn,dN_{n, d} are spurious and cannot share the objective value Fn(x⋆)F_n(x^\star)?

1 comment

Thank you for the valuable feedback and thoughtful questions. We first address Questions 1, 2, and 4, and then offer a few insights on Question 3, which points to an interesting direction that we believe is worth exploring further.

Q1

Here II has cardinality dd, so AI∈Rd×dA_I\in\mathbb{R}^{d\times d}, We will revise the notation around this line to make the dimensions explicit.

Q2

Thank you for pointing this out. By a strict local minimizer, we mean a point whose function value is strictly smaller than the value at every other point in some neighborhood. We have added this definition at the end of the preliminaries (Section 2).

Q4

It comes from two facts. For a point xx captured by Nn,dN_{n,d}, first, we can show x≠±x⋆x\neq \pm x^\star. The sign pattern we choose (see l. 342) contains both +1+1 and −1-1, so there exist distinct i,j∈Ii,j\in I such that ai⊤x=ai⊤x⋆a_i^\top x= a_i^\top x^\star and aj⊤x=−aj⊤x⋆a_j^\top x = -a_j^\top x^\star. Note that almost surely, ai⊤x⋆≠0a_i^\top x^\star\neq 0. It follows that x≠±x⋆x\neq \pm x^\star.

Second, for Gaussian measurements with n≥2dn\ge 2d, the only global minimizers are ±x⋆\pm x^\star, almost surely (Balan, Casazza, and Edidin, "On Signal Reconstruction Without Phase," 2006, Corollary 2.6). Therefore, the counted local minima are spurious.

Q3

This is an interesting and important question that we had not considered in the current work. Those non-sharp local minimizers would have k<dk<d active constraints. For a candidate point to be a local minimum, we would additionally need the Riemannian Hessian on the corresponding (d−kd-k)-dimensional active manifold to be positive definite. Our current counting argument for sharp local minima does not directly extend to this setting because, in the sharp case, the active manifold is a singleton, and we don’t need to consider the Riemannian Hessian.

Nevertheless, our current analysis provides some ingredients that may be useful for studying this case. In Appendix B.3, we show that the Riemannian Hessian takes the form V⊤HVV^\top H V, where VV is an orthonormal basis for the tangent space and HH is the Hessian of a smooth function whose restriction to the active manifold coincides with FnF_n. In addition, the result by Feng Ruan (“On the Uniform Convergence of Subdifferentials in Stochastic Optimization and Learning,” 2025, Corollary 1) suggests that the local minimizers should lie near population critical points. We think a possible approach to locating the non-sharp local minimizers is to analyze the expectation of HH in neighborhoods of the population critical points and determine where its restriction V⊤HVV^\top H V can be positive definite. We view this as an important open question for understanding the landscape of robust phase retrieval. As discussed in our response to Reviewer 2, Question 1, a qualitative characterization of local minima alone does not fully explain the algorithm’s behavior, and new tools are needed to understand why iterative algorithms barely reach those spurious local minima.

Reviewer_vhxAOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates whether benign population landscapes transfer to empirical risk minimization in nonsmooth nonconvex optimization. Using robust phase retrieval with Gaussian measurements as a canonical example, the authors establish that the population objective has a benign landscape: its only local minima are the ground-truth solutions, while all other critical points are strict saddles.

For the empirical objective, the authors first establish an active strict saddle property. However, they show that this property does not preclude spurious sharp local minima. Specifically, for any fixed dimension (d \geq 4), the expected number of such minima grows at least as (\Omega(n^{d/2-1})), and the asymptotic probability of their existence admits a dimension-independent lower bound of 0.136.

The analysis uses active-set characterization, Kac–Rice formulas, local limit arguments, and second-moment estimates. Numerical experiments further demonstrate the prevalence of spurious minima and investigate the recovery behavior of a perturbed subgradient method.

Critical strengths
  1. A theoretically important counterexample in a well-established optimization problem.

The paper addresses a fundamental question concerning the transfer of benign population geometry to nonsmooth empirical objectives. Rather than relying on an artificially constructed objective, it establishes the obstruction in Gaussian robust phase retrieval, a structured problem extensively studied in nonsmooth optimization. This makes the negative result both meaningful and relevant to existing landscape theory.

  1. A nontrivial quantitative characterization of spurious local minima.

The contribution goes beyond establishing the possibility of spurious local minima. The authors derive a polynomial lower bound on their expected number and, more importantly, a nonvanishing asymptotic probability lower bound independent of dimension. The latter is particularly significant because a diverging expectation alone does not establish that spurious minima occur with appreciable probability.

Critical weaknesses
  1. Limited understanding of the algorithmic consequences of spurious minima.

While the paper establishes a meaningful geometric obstruction to population-to-empirical landscape transfer, its practical consequences for optimization remain less clear. The authors partially investigate this issue in Figure 2(b), where the tested perturbed subgradient method frequently achieves successful recovery despite the existence of spurious local minima, but lack theoretical proof.

  1. Limited characterization of the finite-sample and high-dimensional regimes.

The main probability guarantee is established in an asymptotic setting where the dimension is fixed and the sample size tends to infinity. Although the resulting lower bound is independent of dimension, the analysis does not quantify how large the sample size must be relative to the dimension for the phenomenon to become observable. This limits the direct applicability of the result to high-dimensional optimization problems where both the sample size and dimension increase. The authors acknowledge this limitation, but a more explicit discussion of its implications would strengthen the paper.

Questions for authors

Q1. Geometry and algorithmic relevance of spurious minima.

Can the authors provide further insight into how the local sharpness constants or attraction regions of the constructed spurious minima scale with the sample size? Is it possible that these minima become increasingly difficult for optimization algorithms to encounter as the sample size grows? Even a qualitative discussion would help reconcile the theoretical existence results with the successful recovery behavior observed in Figure 2(b).

Q2. Finite-sample and dimensional dependence.

Although the asymptotic probability lower bound is independent of dimension, the analysis fixes the dimension before taking the sample size to infinity. Does the proof provide any indication of how the required sample size depends on dimension? A qualitative discussion of this dependence would help clarify the applicability of the theoretical result to finite-sample and high-dimensional settings.

1 comment

Thank you for pointing out the two main limitations of our work and for providing constructive suggestions for addressing them. We agree that these concerns are important.

Weakness 1 and Question 1: Geometry and algorithmic relevance of spurious minima.

Indeed, our results show that active strict saddles are not the final answer for understanding the behavior of first-order methods for nonsmooth losses arising from learning problems. We agree that understanding how these spurious local minima affect optimization algorithms is important. Our current results establish their existence but do not quantify their attraction regions or how their local sharpness constants scale with n. Our experiments nevertheless show that the algorithm frequently recovers the global solution. We conjecture that the attraction regions of these minima shrink rapidly as nn grows, which could help explain this behavior, and that their local sharpness constants may also decrease. As an illustration, consider the one-dimensional toy example from our paper, Hn(t)=−t2+1n∑i=1nai∣t∣,H_n(t)=-t^2+\frac{1}{n}\sum_{i=1}^n a_i |t|, where ai∼N(0,1)a_i\sim N(0,1). Let cn=1n∑i=1naic_n=\frac{1}{n}\sum_{i=1}^n a_i. Conditioned on {cn>0}\{c_n>0\}, t=0t=0 is a sharp spurious local minimum with local sharpness governed by cnc_n, while the negative-gradient direction points toward 00 precisely when ∣t∣<cn/2|t|<c_n/2. Since $c_n\sim N(0,1/n) $, both the sharpness and the radius of this contraction region are of order n−1/2n^{-1/2}. We believe this toy example therefore illustrates the behavior we see in practice where spurious minima have smaller attraction regions as the sample size grows. We will state our conjecture more explicitly in the paper.

More broadly, this behavior suggests that the classical notion of a benign landscape—typically formulated through the absence of spurious local minima—may not fully capture the algorithmic behavior of nonsmooth problems. In our setting, many spurious local minima may coexist with highly successful optimization. This motivates new approaches to algorithmic analysis. We leave this as an interesting direction for future work.

Weakness 2 and Question 2: Finite-sample and dimensional dependence.

We agree that the absence of a finite-sample characterization is a limitation of our main result. Our analysis requires $n\to \infty $ because the local limit theorem used in our proof provides convergence but no explicit finite-sample error bounds. Such bounds would require additional quantitative control of the non-Gaussian random sums in the Kac-Rice formulas. We believe this is a worthwhile but technically challenging extension. We can, however, establish a complementary finite-sample result using a different and substantially simpler argument. Under the same Gaussian measurement model, there exist universal constants C,c>0C,c>0 such that, for every d≥2d\ge 2 and n≥d+1n\ge d+1,

\ge e^{-Cd^2}\left(\frac{c}{n-d}\right)^{n-d}.$$ This bound is positive for every admissible pair $(d,n)$ but goes to zero as $n\to\infty$, so it does not recover the positive asymptotic constant in our main theorem. This complements our main theorem: the finite-sample result gives strictly positive probability for every admissible $d,n$, while the asymptotic result shows that, for every fixed $d\ge 4$, this probability remains bounded below by a positive constant as $n\to\infty$. If the reviewer feels strongly about this, we can include this result and its proof in the appendix.
Reviewer_wZwHOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies whether a benign population landscape transfers to the empirical objective in nonsmooth weakly convex optimization, using noiseless real phase retrieval with Gaussian measurements and the absolute residual loss as a case study. The population objective has only the two ground-truth global minimizers, while the origin and an orthogonal sphere are strict saddles. For the empirical objective, the authors establish that, when n >= 2d, almost surely every critical point is either a strict local minimizer or an active strict saddle. Their main theorem states that, for every fixed d >= 4, the liminf as n tends to infinity of the probability of a sharp spurious local minimum is at least 0.136. The same lower bound applies to every fixed d >= 4; no joint limit in n and d is asserted. The expected number of such minima grows at least on the order of n^(d/2-1), with a positive constant that may depend on d. The proof counts a selected family of minima in a shrinking tube around the population saddle sphere and combines Kac-Rice calculations, a uniform local limit theorem, a second-moment argument using the Paley-Zygmund inequality, and certified numerical bounds. Experiments at d = 4 estimate the incidence of sharp spurious minima, while an experiment at d = 100 studies recovery by a perturbed subgradient method initialized from perturbations of the saddle sphere.

Critical strengths
  1. The paper identifies a conceptually important obstruction in a canonical structured model. Demonstrating that a benign population landscape can coexist with sharp spurious empirical minima challenges a common population-to-empirical transfer intuition in nonsmooth statistical optimization.
  2. The stated contribution goes beyond an expected-count result: it gives a positive asymptotic probability bound that is the same for every fixed d >= 4, using a second-moment argument. The experiments also illustrate that the existence of spurious minima can coexist with high recovery rates for a perturbed subgradient method. Together, these results distinguish a geometric obstruction from its algorithmic consequences.
Critical weaknesses
  1. Verification of the central technical contribution remains incomplete based on the version available for review. Theorem 3.3 depends on uniform local asymptotics, control of dependence between candidate pairs in the second moment, and certified numerical calculations. Section 4 gives a useful roadmap, but the precise hypotheses and certification procedure are deferred to appendices not included in this file. If these appendices are available separately as part of the submission, this concern should be reassessed after consulting them.
  2. The quantitative scope and algorithmic implications remain only partially characterized. As acknowledged in Section 6, the theorem takes n to infinity for each fixed d and provides no finite-sample rate, threshold n(d), or regime in which n and d grow jointly. These limitations do not invalidate the qualitative counterexample, but they restrict what can be inferred for practical sample sizes. The incidence experiment is restricted to d = 4. The experiment at d = 100 measures recovery from perturbations centered on the population saddle sphere, so it does not directly quantify the prevalence or attraction regions of spurious minima under a more general initialization distribution. In the reported d = 4 experiment, with 100 instances per setting, the estimated probabilities are approximately 0.66-0.83. These finite-sample estimates are qualitatively consistent with the existence result, but do not establish the tightness of the asymptotic lower bound. The manuscript suggests that counting a restricted candidate family may contribute to the gap, but does not separate this effect from losses in the moment bounds or the relaxation used to obtain a bound independent of d.
Questions for authors

1.How is the certified bound c_* >= 0.1361 in Appendix C.5 obtained? Please specify the validation method, such as interval or ball arithmetic, the precision settings, and how numerical errors are controlled. Providing the certification code, reproduction instructions, and any machine-checkable certificate would help verify the bound. 2.The counted family excludes near-degenerate candidates by imposing positive lower bounds on |det A_I| and |det Q_I(x_I)|, together with bounds on the selected measurement norms. How are these thresholds chosen as functions of d, and how do they ensure positive first-moment constants and the uniform estimates needed for the Kac-Rice identity in (9)? Clarifying how the truncation enters the first- and second-moment calculations would also help explain the probability bound. 3.Can the authors give any quantitative indication, even a partial estimate, of how large n must be relative to d? If computationally feasible, incidence measurements at a few dimensions d > 4 would help assess the relevance of the result beyond the reported d = 4 experiment. A joint growth regime for n and d would be a useful extension, rather than a prerequisite for the qualitative non-transfer claim. 4.How sensitive is Figure 2(a) to the criticality tolerances specified in Appendix G? How are exact duplicates or numerically near-duplicate candidates generated by different pairs (I,s) handled, and what checks ensure that a candidate declared critical satisfies the strict interior condition in (7)? Reporting objective gaps and empirical sharpness measures for representative detected minima would help assess numerical reliability. 5.Under a specified initialization distribution that does not depend on the population saddle sphere, what fractions of runs recover the ground truth or fail to recover within the computational budget? Where feasible, distinguishing runs that approach a detected spurious minimum from other non-recovering runs would clarify whether these minima have algorithmically significant attraction regions.

1 comment

Thank you for your careful review and constructive questions. We address each concern you raised below.

Weakness 1

The supplementary material contains complete proofs of the main results. Specifically, Proposition 3.1 and Theorems 3.2-3.3 are proved in Appendices A-C, respectively. We devoted substantial time to checking and polishing these proofs before submission, and we would appreciate your reassessment after reading the supplementary material.

Weakness 2

As we understand it, the second weakness raises three main concerns: (i) Tightness of the asymptotic lower bound, (ii) absence of finite-sample rates, and (iii) the choice of initialization. For (i), we agree that our lower bound is not tight. That said, the main goal of the paper is to establish a positive asymptotic probability lower bound that is independent of dimension, rather than to obtain a tight characterization of the probability itself. We find that, by itself, this is surprising and provides a new insight for the community (see also comments by Reviewers vhxA and FByf, which called it “particularly significant” and “relevant in both optimization and ML”). We respectfully decided not to pursue a tighter analysis, since we expect it to be significantly harder and have diminishing returns. Regarding (ii) and (iii), please see our responses to questions 3 and 5.

Q1

We first derive upper and lower bounds for the integrals, accounting for the error from truncating the series. We then evaluate these bounds in Python using interval arithmetic with 100 decimal digits of precision. Appendix C.5 now provides further details. We also added a Lean formalization in the repository linked in the paper. The Lean formalization verifies the supporting analytic results, while the numerical interval evaluations are performed separately in Python.

Q2

The answer to this question appears explicitly in Lemma D.1, which shows that these thresholds can be chosen as functions of dd and also provides a permissible range for each threshold. The precise choices are not insightful, so we did not include them in the body of the paper. Our probability bound is obtained from the squared first moment divided by the second moment, and the threshold-dependent factor cancels as n→∞n\to\infty. Therefore, the resulting limiting ratio remains independent of dd.

Q3

Our current proof relies on a local limit theorem, which does not provide explicit finite-sample error bounds. Such bounds would require quantitative control of the non-Gaussian random sums in the Kac-Rice formulas. We believe this is a worthwhile but technically challenging extension. Meanwhile, we can provide a substantially simpler argument that yields the following finite-sample guarantee: there exist universal constants C,c>0C,c>0 such that, for every d≥2d\ge 2 and n≥d+1n\ge d+1,

\ge e^{-Cd^2}\left(\frac{c}{n-d}\right)^{n-d}.$$ This bound is positive for every admissible pair $(d,n)$ but goes to zero as $n\to \infty$, so it does not recover the dimension-independent asymptotic bound. If the reviewer feels strongly about this, we will include this result and its proof in the appendix. We also ran new experiments for $d=5,6,7$ and $n/d=2,\ldots,7$, which we haven’t included in the paper yet. The results of the new experiments are consistent with those of the experiment appearing in the paper. If the reviewer feels that the new experiments would add value to the paper, we can include this larger suite of numerics in the appendix. ## Q4 Figure 2(a) estimates the probability that an instance has at least one sharp spurious local minimum, so duplicate candidates do not affect the estimate. We recompute selected candidates and their multipliers using 60-digit decimal arithmetic. A candidate is accepted only if $1-\|\lambda\|_\infty>10^{-30}$ and every inactive residual has magnitude greater than $10^{-30}$. These checks verify numerically that the multiplier lies strictly inside $(-1,1)^d$ and that no additional measurement is active. By Lemma 4.1, each accepted candidate with $d$ active constraints is a spurious sharp local minimum, so a separate estimate of its sharpness constant or objective gaps is not needed for this test. ## Q5 We are running additional experiments with initialization uniform inside the unit ball. The results so far are consistent with our existing experiments: for larger $n/d$, the perturbed subgradient method recovers the global solution with high frequency. Most other runs remain unresolved within the computational budget. Only a few end near a numerically verified spurious local minimum. These observations are consistent with our conjecture that, as the sample size increases, regions of attraction of spurious local minima shrink. Proving this conjecture would require analyzing the algorithm’s dynamics beyond the landscape analysis used in smooth optimization. So, we leave it as an important open question.

Comments on the paper

1 comment

Thank you for the constructive comments.

First of all, thank you for pointing out these two references. The form of the Riemannian Hessian is indeed a standard result, and we'll add them to the final version. To prove the active strict saddle property, we take a step further and show that the Riemannian Hessian is almost surely nonsingular at a critical point. Under this property, positive definiteness is indeed a sufficient and necessary condition to determine whether a critical point is a local minimizer.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.