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

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

8 May 2021arXiv:2105.03678archive 2025-07-28

Fan Wu, Patrick Rebeschini

This paper studies early-stopped mirror descent applied to noisy sparse phase retrieval, which is the problem of recovering a k-sparse signal x^⋆∈ℝⁿ 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 k² (modulo logarithmic term) and the minimum (in modulus) non-zero entry of the signal is on the order of ‖x^⋆‖₂/√(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.

PaperPDFCode

Syntology This paper's arXiv id is not in Syntology's Atlas id list (549,449 ids, as this build read them; the read time is in the build record), so this page links to no Syntology page for it. The list is not the whole graph; Syntology's feed shows papers as they enter the graph.

Code

fawuuu/irmsmd mentioned on GitHubSyntology: no sample linked to this paper (harvested for another paper). Syntology's graph links these samples to Implicit Regularization in Matrix Sensing via Mirror Descent (arXiv:2105.13831; that paper's own run record: 3 ran (of which 0 constructed an object rather than computing a result; 0 with no instrument failure: 0 honoured, 0 violated, 0 with no contract checked; 3 where Syntology's instrument failed) · 0 unverified); nothing checks that they implement this paper's method. report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

A paper named beside a repository with no sample linked to this paper is shown with that paper's own run record, not this paper's: “ran” means executed on a synthesized input, not that the code is correct, and “where Syntology's instrument failed” counts failures of Syntology's instrument, not of the code. Papers are listed in arXiv-id order, at most three per repository.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Retrieval

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Methods

Early Stopping

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections