Minimax rate of convergence and the performance of empirical risk minimization in phase retrieval

We study the performance of Empirical Risk Minimization in both noisy and noiseless phase retrieval problems, indexed by subsets of ℝⁿ and relative to subgaussian sampling; that is, when the given data is y_i = 〈a_i; x₀ 〉² + w_i for a subgaussian random vector a, independent subgaussian noise w and a fixed but unknown x₀ that belongs to a given T ⊂ ℝⁿ. We show that ERM performed in T produces ẍ whose Euclidean distance to either x₀ or x₀ depends on the gaussian mean-width of T and on the signal-to-noise atio of the problem. The bound coincides with the one for linear regression when ǁx₀ǁ₂ is of the order of a constant. In addition, we obtain a sharp lower bound for the phase retrieval problem. As examples, we study the class of d-sparse vectors in ℝn and the unit ball in ∫ⁿ₁.