Nearly minimax-optimal rates for noisy sparse phase retrieval via early-stopped mirror descent
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 minimiza...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Oxford University Press
2022
|
| _version_ | 1797109536851492864 |
|---|---|
| author | Wu, F Rebeschini, P |
| author_facet | Wu, F Rebeschini, P |
| author_sort | Wu, F |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T07:43:08Z |
| format | Journal article |
| id | oxford-uuid:dcda711f-ed78-4078-8981-31bb0b73fb57 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:43:08Z |
| publishDate | 2022 |
| publisher | Oxford University Press |
| record_format | dspace |
| spelling | oxford-uuid:dcda711f-ed78-4078-8981-31bb0b73fb572023-05-03T08:37:13ZNearly minimax-optimal rates for noisy sparse phase retrieval via early-stopped mirror descentJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:dcda711f-ed78-4078-8981-31bb0b73fb57EnglishSymplectic ElementsOxford University Press2022Wu, FRebeschini, PThis 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. |
| spellingShingle | Wu, F Rebeschini, P Nearly minimax-optimal rates for noisy sparse phase retrieval via early-stopped mirror descent |
| title | Nearly minimax-optimal rates for noisy sparse phase retrieval via early-stopped mirror descent |
| title_full | Nearly minimax-optimal rates for noisy sparse phase retrieval via early-stopped mirror descent |
| title_fullStr | Nearly minimax-optimal rates for noisy sparse phase retrieval via early-stopped mirror descent |
| title_full_unstemmed | Nearly minimax-optimal rates for noisy sparse phase retrieval via early-stopped mirror descent |
| title_short | Nearly minimax-optimal rates for noisy sparse phase retrieval via early-stopped mirror descent |
| title_sort | nearly minimax optimal rates for noisy sparse phase retrieval via early stopped mirror descent |
| work_keys_str_mv | AT wuf nearlyminimaxoptimalratesfornoisysparsephaseretrievalviaearlystoppedmirrordescent AT rebeschinip nearlyminimaxoptimalratesfornoisysparsephaseretrievalviaearlystoppedmirrordescent |