2021/05/08 by Fan Wu, Wu, Fan, Patrick Rebeschini +1
Computer Science · Engineering · Physics and Astronomy · #Advanced X-ray Imaging Techniques #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Signal Processing (eess.SP) #Sparse and Compressive Sensing Techniques #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2105.03678
openalex publication_date 2021/05/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper studies early-stopped mirror descent applied to noisy sparse phase retrieval, which is the problem of recovering a k-sparse signal x^⋆∈ℝ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^⋆‖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.