| Summary: | This paper studies early-stopped mirror descent applied to noisy sparse phase retrieval, which is the problem of recovering a k-sparse signal x
? ∈ R
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 hypentropy mirror map and proper
initialization, achieves a nearly minimax-optimal rate of convergence, provided the sample size is at least
of order k
2
(modulo logarithmic term) and the minimum (in modulus) non-zero entry of the signal is
on the order of kx
?k2/
√
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.
|
|---|