Minimax rate of convergence and the performance of ERM in phase recovery

Abstract

We study the performance of Empirical Risk Minimization in noisy phase retrieval problems, indexed by subsets of ${\mathbb{R}}^n$ and relative to subgaussian sampling; that is, when the given data is $y_i=\inr{a_i,x_0}^2+w_i$ for a subgaussian random vector $a$, independent noise $w$ and a fixed but unknown $x_0$ that belongs to a given subset of ${\mathbb{R}}^n$. We show that ERM produces $\hat{x}$ whose Euclidean distance to either $x_0$ or $-x_0$ depends on the gaussian mean-width of the indexing set and on the signal-to-noise ratio of the problem. The bound coincides with the one for linear regression when $\Vert x_0{\Vert }_2$ is of the order of a constant. In addition, we obtain a minimax lower bound for the problem and identify sets for which ERM is a minimax procedure. As examples, we study the class of $d$-sparse vectors in ${\mathbb{R}}^n$ and the unit ball in ${\ell }_1^n$.

References in corpus (1)

• Learning subgaussian classes : Upper and minimax bounds

Cited by in corpus (3)

• Max-Affine Regression: Provable, Tractable, and Near-Optimal Statistical Estimation
• Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization