- 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 has size . 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 are spurious and cannot share the objective value ?
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 I has cardinality d, so AI∈Rd×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 x captured by Nn,d, first, we can show x=±x⋆. The sign pattern we choose (see l. 342) contains both +1 and −1, so there exist distinct i,j∈I such that ai⊤x=ai⊤x⋆ and aj⊤x=−aj⊤x⋆. Note that almost surely, ai⊤x⋆=0. It follows that x=±x⋆.
Second, for Gaussian measurements with n≥2d, the only global minimizers are ±x⋆, 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<d active constraints. For a candidate point to be a local minimum, we would additionally need the Riemannian Hessian on the corresponding (d−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⊤HV, where V is an orthonormal basis for the tangent space and H is the Hessian of a smooth function whose restriction to the active manifold coincides with Fn. 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 H in neighborhoods of the population critical points and determine where its restriction V⊤HV 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.