Outlier-Robust Phase Retrieval in Nearly-Linear Time

We thank the reviewer for their time spent reading our work.

Reviewer: The paper does not explicitly point out any difficulties in terms of theory or technology that the theoretical analysis and algorithm derivation of the proposed algorithm compared with the existing works.

Authors: A key technical contribution of our paper is the robust spectral initialization step, which differs significantly from prior work. Specifically, we design a nonnegative reweighting scheme that ensures the empirical covariance matrix is robust to outliers without explicitly computing the covariance matrix, which would require matrix multiplication time $O(d^{2.37})$. Instead, we introduce a new Ky Fan norm formulation and show that good weights can be computed in nearly-linear time $\tilde O(nd) \approx \tilde O(d^2)$. Note that concurrent work [BR25] (as discussed in Lines 69–71) performs robust spectral initialization in a different way but is much slower than linear time.

Reviewer: This paper lacks numerical simulation experiments, which prevents it from demonstrating the superiority of the proposed algorithm compared to other algorithms.

Authors: We believe our results are substantial even without experiments, and we hope that our theoretical results are judged based on their merits.

Reviewer: The descriptions of some lemmas in this paper are rather vague, for example: 3.1. The description of the parameter in Lemma 3.1 as "sufficiently small" 3.2. The description of the parameter in Lemma 4.1 is insufficient 3.3. The constant corresponding to $O(|z - x|^2_2)$ in Lemma 5.1 is not given.

Authors: We respectfully disagree. Our theorems, lemmas, and proofs are rigorous. A key point is that many constants appear throughout our analysis, and explicitly tracking each of them would introduce notational overhead without providing additional insight. Omitting explicit constants is standard practice in the theory community. As a concrete example, in Appendix B where we prove Lemma 5.1, the constant can be written explicitly as $151 > 16 \cdot 105 \cdot (1/8)^2 \cdot (2+1/8)^2 \cdot (1+1/8)^2$. While it is possible to include this constant in Lemma 5.1 and substitute it into other parts of our proofs, doing so would make the presentation unnecessarily cumbersome without affecting the correctness of our results.

Reviewer: The proofs of some theorems in this article are not rigorous (4.1 - Example in line 254; 4-2, Proof of Lemma 5.2)

Authors: Thank you for pointing this out. The statement can indeed be made more precise here. In Lemma 4.1, we should have stated the inequalities of Line 248 using a value u: e.g., the top eigenvalue is between $3-u$ and $3+u$ for some $u = O(\delta)$, and complete the rest of the proof using $u$.

We should have stated in Line 254 that $(3+u)\alpha_1^2 + (1+u)(1-\alpha_1^2) \le 1 + O(\delta) + 2\alpha_1^2$. We will revise the paper accordingly.

Reviewer: Why is the step size of GD in algorithm 2 set to 1/300?

Authors: Our choice of step size $\eta = 1/300$ is close to the best-possible constant to minimize the expression in Line 654 when $c = 4$.

Reviewer: In line 127, "the corrupted samples can only add directions to Yw but cannot remove directions." What is the meaning of "direction"? Why do corrupted samples add directions to Y_{w}?

Authors: This was explained in Lines 122-126. When there is no corruption, we have $\mathbb{E}[Y_w] = I + 2 x x^\top$, which is a matrix with one eigenvalue $3$ (in the direction of $**x**$) and all other eigenvalues $1$. Corrupted samples may perturb this spectrum, but since each term $y_i **a**_i **a**_i^\top$ is a positive semidefinite matrix, they cannot reduce variance in any direction (that is, the corrupted samples cannot decrease $v^\top Y_w v$ for any direction $v$). We will clarify this.

Reviewer: Why do you compute w that minimizes the sum of the largest "two" eigenvalues of Y_{w}?

Authors: Suppose the adversarial corrupts $Y_w$ to become $M = I + 2 x x^\top + 2.01 y y^\top$ for some arbitrary irrelevant direction $y$. The largest eigenvalue of $M$ is close to $3$, which is the same as what we expect when there is no corruption, but the top eigenvector of $M$ is not a good initialization for converging to the ground truth $x$.

We thank the reviewer for taking the time to read our work and provide their feedback.

Reviewer: Is it possible to remove the sample-splitting requirement by following an approach similar to the SEVER algorithm (https://proceedings.mlr.press/v97/diakonikolas19a.html), Can you expand on how you anticipate attacking the sample-splitting requirement? I suspect that verifying stability conditions without fresh samples is very difficult in general settings.

Authors: This is a good observation. We believe that a covering argument on the stability condition would allow us to remove the sample-splitting (and thus the dependency on $\Delta$). At a high level, proving an $\epsilon$-net plus union bound argument for the stability conditions (i.e., stability of the mean and covariance of individual gradients) to hold uniformly for all $z$ is not straightforward. These conditions only hold when none of the $a_i$'s are close to the current solution $\pm z$. Of course, if the $a_i$'s are chosen after $z$, this holds with high-probability, and this is why we use a fresh set of samples in each iteration. One possible idea is to consider an $\epsilon$-net argument in regions far from all $a_i$'s, and argue that gradient descent never gets close to any of the $a_i$'s. We defer this to future work, as our main technical contribution is in the robust initialization step (via the Ky Fan SDP solver).

Reviewer: What is the relationship between $\epsilon(\delta)$ in Lemma 4.1 and the upper bound $\epsilon_0$ on the contamination level?

Authors: Thank you for asking this. We need Lemma 4.1 to hold for our choice of $\delta$ (from Line 256), and the simplest way to do this is to require $\epsilon_0 \le \epsilon(\delta)$. We will clarify this.

Reviewer: Is there a weaker notion of adversary suitable for some of the corruptions you describe in the introduction (hardware noise + miscalibration)?

Authors: We welcome the study of other adversarial models. We want to emphasize that there is value in studying phase retrieval in the strong contamination model we consider in this paper. Our results show that even against such a strong adversary, phase retrieval can be solved with only logarithmic overhead in both sample and computational complexity.

Reviewer: Appendix C shows that prior "robust" approaches -- focusing on corruption solely in the measurement space -- fail when measurement vectors can be corrupted. However, my understanding is that the argument focuses on the failure of spectral initialization. Is it possible that, given a sufficiently good initial estimate, prior methods (such as optimizing the robust loss a-la Duchi-Ruan) succeed in recovering ? In my opinion, a formal argument ruling this out would considerably strengthen this paper.

Authors: We currently do not have such a formal impossibility result. We agree that proving this formally would strengthen the paper and view it as a promising direction for future work.

Reviewer: How much of the overall analysis depends on Gaussianity? I suspect the robust gradient descent analysis can be easily extended.

Authors: The conditions we require on the (clean) distribution of $a_i$ are: an upper bound on its tail (used in the proof of Lemma 4.2) and bounded first few moments (used in the proof of Lemma 5.1). Therefore, our results directly extend to isotropic sub-Gaussian distributions and other distributions with these properties.

We thank the reviewer for their time and thoughtful comments.

Reviewer: Although the authors claim it is a theoretical paper, the work essentially proposes an algorithm with theoretical justification. The techniques in the theoretical derivations themselves have no novelty.

Authors: We respectfully disagree. Our contribution is both algorithmic and theoretical, and the techniques we introduce are novel in the context of robust phase retrieval. In particular, our main result establishes that one can solve phase retrieval with arbitrary corruption on the pairs $(**a**_i, y_i)$ in nearly-linear time and with near-optimal sample complexity. Prior work typically considers simpler corruption models, such as adversarial perturbations limited to the intensity measurements $y_i$. Handling corruptions in both $(**a**_i, y_i)$ presents new challenges, which we address through novel techniques. A key technical contribution of our paper is the robust spectral initialization step, which differs significantly from prior work. Specifically, we design a nonnegative reweighting scheme that ensures the empirical covariance matrix is robust to outliers without explicitly computing the covariance matrix, which would require matrix multiplication time $O(d^{2.37})$. Instead, we introduce a new Ky Fan norm formulation and show that good weights can be computed in nearly-linear time $\tilde O(nd) \approx \tilde O(d^2)$. Note that concurrent work [BR25] (as discussed in Lines 69–71) performs robust spectral initialization in a different way but is much slower than linear time. To our knowledge, no prior work achieves this level of robustness and efficiency; we would welcome the reviewer pointing us to any such existing result.

Reviewer: The analysis appears to be more incremental in nature compared to prior theoretical works on phase retrieval. Specifically, the main novelty of the spectral initialization step lies in assigning a nonnegative weight to each sample.

Authors: The main novelty is that we can compute good weights in nearly-linear time. We invite the reviewer to point to prior work that achieves this when there is corruption in both $a_i$ and $y_i$. As noted above, our spectral initialization is not merely a reweighting heuristic. It is backed by a rigorous analysis showing how to select these weights efficiently via Ky Fan norm minimization, and how this leads to accurate recovery despite arbitrary corruptions. This represents a departure from existing techniques and is not a straightforward extension of prior methods.

Reviewer: This paper is a resubmission of the work originally submitted to NeurIPS 2024. One of the main concerns previously raised was the lack of numerical experiments; however, this revision fails to address that issue entirely.

Authors: We believe our results are substantial even without experiments, and we hope that our theoretical results are judged based on their merits.

That said, the current version has significantly improved over the NeurIPS24 submission: we have clarified the setting, strengthened the presentation of the results, and expanded the discussion of the techniques.

Reviewer : I do not believe the problem setting studied in this paper has genuine practical value. In phase retrieval, if noise is considered, then all pairs will be corrupted. If outliers are considered, they would correspond to measurements with very large noise levels. The setting proposed in the paper does not make sense in real-world scenarios.

Authors : We respectfully disagree. We welcome the study of other adversarial models. We want to emphasize that there is value in studying phase retrieval in the strong contamination model we consider in this paper. Our results show that even against such a strong adversary, phase retrieval can be solved with only logarithmic overhead in both sample and computational complexity. Extending our work to the setting with noisy observations is an exciting avenue of future work, where our nearly linear-time robust initialization step will remain useful.

We thank the reviewer for their time spent reading and providing feedback on our work.

The reviewer’s main concern is that “the central claim is that the results of this paper are independent of $\epsilon$” is incorrect. We respectfully disagree. Our results indeed hold as stated, and a careful reading of our proofs confirms this.

Below, we address the reviewer's specific doubts in detail.

Reviewer: “It is evident Lemma 2.3 does not hold with high probability when $\epsilon$ is very small”

Authors: This is true. However, in our algorithm, we only need to robustly estimate the gradient up to constant precision (e.g., $c = 4$ in Lemma 5.3), so we never invoke Lemma 2.3 with very small $\epsilon$.

Reviewer: For the statement of Lemma 2.3 to hold with high probability , it is necessary $\epsilon_0 = w(1/n)$. This implies that $\epsilon_0$ cannot be any absolute constant independent of $n$.

Authors: An absolute constant is $\omega(1/n)$.

Reviewer: Similar issues arise elsewhere - for example, in Lemma 5.2, where the choice of m must depend on epsilon_0 for the Lemma 5.2 statement to hold.

Authors: There is nothing wrong with $m$ depending on $\epsilon_0$. We only need a constant approximation when estimating the gradient (e.g., $c = 4$ in Lemma 5.3). This leads to $\mathrm{poly}(1/c)$ dependence in both sample complexity and runtime, but $\mathrm{poly}(1/c) = \Theta(1)$ when $c = 4$.

Our paper provides detailed mathematical proofs for all theorems and lemmas. If there are concerns about correctness, we would appreciate it if the reviewer could point out specific incorrect steps.

In Lemma 5.2, the only place where Lemma 2.3 is actually used, we invoke Lemma 2.3 with $\epsilon = O(c^2) = O(1)$. Therefore, the reviewer's concern about very small $\epsilon$ (e.g., $\epsilon \leq 1/n \log(1/(1 - \tau))$) is irrelevant to our analysis, as we never use Lemma 2.3 in that regime.

In other parts of the paper (e.g., Lemmas 3.1 and 3.2), we only need $\epsilon$ to be at most a universal constant, which is independent of $n$. We kindly ask the reviewer to point out a specific step in our proofs where $\epsilon$ must be at least some function of $n$. To the best of our knowledge, no such dependence is required.