# Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descent

arXiv: https://arxiv.org/abs/2105.03678 · HTML: https://mlsanity.com/paper/2105.03678/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 52 references that are in the map.
- First posted on arXiv 8 May 2021.

## Builds on (most cited first, 10 of 10)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [A Geometric Analysis of Phase Retrieval](https://mlsanity.com/paper/1602.06664/) (2016)
- [Phase Retrieval using Alternating Minimization](https://mlsanity.com/paper/1306.0160/) (2013)
- [High-Dimensional Linear Regression via Implicit Regularization](https://mlsanity.com/paper/1903.09367/) (2019)
- [Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming](https://mlsanity.com/paper/1310.0807/) (2013)
- [A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval](https://mlsanity.com/paper/2010.10168/) (2020)
- [Hadamard Wirtinger Flow for Sparse Phase Retrieval](https://mlsanity.com/paper/2006.01065/) (2020)
- [Compressed Sensing from Phaseless Gaussian Measurements via Linear Programming in the Natural Parameter Space](https://mlsanity.com/paper/1611.05985/) (2016)
- [On the convergence of mirror descent beyond stochastic convex programming](https://mlsanity.com/paper/1706.05681/) (2017)

## Built on by (most cited first, 5 of 5)

- [Implicit Regularization in Matrix Sensing via Mirror Descent](https://mlsanity.com/paper/2105.13831/) (2021)
- [Optimal sparse phase retrieval via a quasi-Bayesian approach](https://mlsanity.com/paper/2504.09509/) (2025)
- [Robust Gradient Descent for Phase Retrieval](https://mlsanity.com/paper/2410.10623/) (2024)
- [Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity](https://mlsanity.com/paper/2601.18245/) (2026)
- [Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts](https://mlsanity.com/paper/2606.14929/) (2026)

## Abstract (arXiv)

This paper studies early-stopped mirror descent applied to noisy sparse phase retrieval, which is the problem of recovering a k-sparse signal x^star∈ℝn from a set of quadratic Gaussian measurements corrupted by sub-exponential noise. We consider the (non-convex) unregularized empirical risk minimization problem and show that early-stopped mirror descent, when equipped with the hyperbolic entropy mirror map and proper initialization, achieves a nearly minimax-optimal rate of convergence, provided the sample size is at least of order k2 (modulo logarithmic term) and the minimum (in modulus) non-zero entry of the signal is on the order of |x^star|2/√k. Our theory leads to a simple algorithm that does not rely on explicit regularization or thresholding steps to promote sparsity. More generally, our results establish a connection between mirror descent and sparsity in the non-convex problem of noisy sparse phase retrieval, adding to the literature on early stopping that has mostly focused on non-sparse, Euclidean, and convex settings via gradient descent. Our proof combines a potential-based analysis of mirror descent with a quantitative control on a variational coherence property that we establish along the path of mirror descent, up to a prescribed stopping time.