Phase retrieval: Global convergence of gradient descent with optimal sample complexity
Phase Retrieval;Gradient Descent;Global Convergence;Benign Landscape;Sample Complexity;Random Initialization
This manuscript proposes a sample complexity which relies on a tensor concentration inequality Theorem 3 in

M. Even and L. Massoulié. Concentration of non-isotropic random tensors with applications to learning and empirical risk minimization. In Conference on Learning Theory, pages 1847–1886. PMLR, 2021.

which is false. Since COLT did not publish an erratum, we did not know.
I have read and agree with the venue's withdrawal policy on behalf of myself and my co-authors.
This paper proves the global convergence of gradient descent with random initialization for phase retrieval under optimal sample complexity
@misc{
fougereux2024phase,
title={Phase retrieval: Global convergence of gradient descent with optimal sample complexity},
author={Th{\'e}odore Fougereux and C{\'e}dric Josz and Xiaopeng Li},
year={2024},
url={https://openreview.net/forum?id=T0MLnjav7P}
}
This paper addresses the phase retrieval problem, which aims to recover a signal vector $x^{\natural}$ from $m$ measurements $y_i=|\langle a_i,x^{\natural}\rangle|^2$, $i=1,\ldots,m$. A standard approach is to solve a nonconvex least squares problem using gradient descent with random initialization, which is known to work efficiently given a sufficient number of measurements. However, whether $O(n)$ measurements suffice for gradient descent to recover the ground truth efficiently has remained an open question. Prior work has established that $O(n{\rm poly}(\log n))$ measurements are sufficient. In this paper, we resolve this open problem by proving that $m=O(n)$ Gaussian random measurements are sufficient to guarantee, with high probability, that the objective function has a benign global landscape. This sample complexity is optimal because at least $\Omega(n)$ measurements are required for exact recovery. The landscape result allows us to further show that gradient descent with a constant step size converges to the ground truth from almost any initial point.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
~Théodore_Fougereux1 ~Cédric_Josz1 ~Xiaopeng_Li6
Théodore Fougereux Cédric Josz Xiaopeng Li
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Phase Retrieval Gradient Descent Global Convergence Benign Landscape Sample Complexity Random Initialization
I certify that there is no acknowledgement section in this submission for double blind review.
fougereux|phase_retrieval_global_convergence_of_gradient_descent_with_optimal_sample_complexity
/pdf/bbf09d73ae4c49c02b0d632b81e48175b294b623.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/60933542182f5c79b8073fb3d4230027019cd97b.zip
Phase retrieval: Global convergence of gradient descent with optimal sample complexity
ICLR 2025 Conference Withdrawn Submission
ICLR.cc/2025/Conference/Withdrawn_Submission