Agnostic Estimation for Misspecified Phase Retrieval Models
The goal of noisy high-dimensional phase retrieval is to estimate an s-sparse parameter β * ∈ R d from n realizations of the model Y = (X β * ) 2 + ε. Based on this model, we propose a significant semi-parametric generalization called misspecified phase retrieval (MPR), in which Y = f (X β * , ε) with unknown f and Cov(Y, (X β * ) 2 ) > 0. For example, MPR encompasses Y = h(|X β * |) + ε with increasing h as a special case. Despite the generality of the MPR model, it eludes the reach of most existing semi-parametric estimators. In this paper, we propose an estimation procedure, which consists of solving a cascade of two convex programs and provably recovers the direction of β * . Our theory is backed up by thorough numerical results.
The paper presents a generalization of ‘phase retrieval’ models that encompasses a wider range of data generated from sparse parameter vectors by using a single index model (SIM) with an unknown link function. These models encompass the traditional phase retrieval as well as the Wirtinger Flow models of data acquisition, with a covariance condition on the observations and the square of the inner product instead of just on the covariance of the observations and the inner product of the predictor vector X and the parameter B. The authors show that several different conditions will lead to the model they describe so that the class of MPR (misspecified phase retrieval) models is ‘sufficiently broad’. They then provide a two-step algorithm to solve these misspecified models – the first step involves solving a regularized semidefinite program that was relaxed from a nonconvex problem which tries to find an estimate for the direction of B (the desired parameter vector) using an empirical surrogate for the mean. They later prove that this step has a supremum which is bounded by the inverse of the size of the problem. The second step is an l1 – regularized refinement step which they show does not increase the computational complexity of the overall problem given few enough repetitions. The authors also have minimax bounds on the class of link functions that they define for additive SIMs. They back this up with a few numerical experiments.
The acronym AGENT seems like a bit of a stretch to me. I would like to see more numerical experiments as well as comparing to more than just Wirtinger Flow. I know that there are more classical methods for solving problems in classes like these (though perhaps without the same guarantees!), and would maybe like to see it commented on a little more or compared to in your numerical results. The numerical results section feels somewhat threadbare – we do see how the reinforcement strategy is effective, but the lack of comparisons in computational complexity/effort with other established methods makes it hard to see the benefits in computation; the agnosticism to the model is cool but I think it would also be cool to see exactly how AGENT works on the different models in the same plot for comparison. I think the idea is fairly unique – having a general algorithm that provably works with high probability for different models given enough samples is meritorious.  If the authors never deal with the complex domain, then classifying the paper as relevant for misspecified phase retrieval seems somewhat like a misnomer to me.  Another thing that might be helpful is defining the domain the Y and X reside in, since you have phase retrieval applications, specifying that in certain cases Y is in the real domain vs the complex domain while X has to be in the complex domain (since in the abstract you define B to be wholly real) is fairly important, especially for making comparisons to Wirtinger Flow.   I think one thing that would be helpful for the clarity of the reader is to insert reminders for different definitions to avoid frequent backtracking, for example line 167 instead of “satisfy (2.1)”, maybe “satisfy the covariance condition (2.1)”.  I don’t quite understand why in line 190 that by making this different observation we just can apply l1 regularized least squares (without an empirical estimate for the mean).  Another question I have is regarding equation (3.2), you say that Y~ depends on two directions, but B^ perp is a hyperplane – I think I understand what you mean but this could be slightly confusing?  The authors mix notation for the outer product, in line 211 and equation 3.4, the authors use one notation, but in line 221 the authors simply spell it out. I’m not sure how helpful this is for clarity.  Notationally sometimes Y bar is used and sometimes mu is used to denote the average. Is one for the empirical average and one for the ‘true’ expectation?