11footnotetext: CNRS, CMAP, Ecole Polytechnique, 91120 Palaiseau,
France.22footnotetext: Department of Mathematics, Technion, I.I.T, Haifa
32000, Israel.33footnotetext: Email<EMAIL_ADDRESS>44footnotetext: Email<EMAIL_ADDRESS>Supported by
the Mathematical Sciences Institute – The Australian National University.

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

Guillaume Lecué1,3 Shahar Mendelson2,4,5

###### 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}=\bigl{<}a_{i},x_{0}\bigr{>}^{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 $\|x_{0}\|_{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}$.

##  1 Introduction

Phase retrieval has attracted much attention recently, as it has natural
applications in areas that include X-ray crystallography, transmission
electron microscopy and coherent diffractive imaging (see, for example, the
discussion in [2] and references therein).

In phase retrieval, one attempts to identify a vector $x_{0}$ that belongs to
an arbitrary set $T\subset\mathbb{R}^{n}$ using noisy, quadratic measurements
of $x_{0}$. The given data is a sample of cardinality $N$,
$(a_{i},y_{i})_{i=1}^{N}$, for vectors $a_{i}\in\mathbb{R}^{n}$ and

$y_{i}=|\bigl{<}a_{i},x_{0}\bigr{>}|^{2}+w_{i},$ (1.1)

for a noise vector $(w_{i})_{i=1}^{N}$.

Our aim is to investigate phase retrieval from a theoretical point of view,
relative to a well behaved, random sampling method. To formulate the problem
explicitly, let $\mu$ be an isotropic, $L$-subgaussian measure on
$\mathbb{R}^{n}$ and set $a$ to be a random vector distributed according to
$\mu$. Thus, for every $x\in\mathbb{R}^{n}$,
$\mathbb{E}\bigl{<}x,a\bigr{>}^{2}=\|x\|_{2}^{2}$ (isotropicity) and for every
$u\geq 1$, $Pr(|\bigl{<}x,a\bigr{>}|\geq
Lu\|\bigl{<}x,a\bigr{>}\|_{L_{2}})\leq 2\exp(-u^{2}/2)$ ($L$-subgaussian).

Given a set $T\subset\mathbb{R}^{n}$ and a fixed, but unknown $x_{0}\in T$,
$y_{i}$ are the random noisy measurements of $x_{0}$: for a sample size $N$,
$(a_{i})_{i=1}^{N}$ are independent copies of $a$ and $(w_{i})_{i=1}^{N}$ are
independent copies of a mean-zero variable $w$ that are also independent of
$(a_{i})_{i=1}^{N}$.

Clearly, due to the nature of the given measurements, $x_{0}$ and $-x_{0}$ are
indistinguishable, and the best that one can hope for is a procedure that
produces $\hat{x}\in T$ that is close to one of the two points.

The goal here is to find such a procedure and identify the way in which the
distance between $\hat{x}$ and either $x_{0}$ or $-x_{0}$ depends on the
structure of $T$, the measure $\mu$ and the noise.

The procedure studied here is empirical risk minimization (ERM), which
produces $\hat{x}$ that minimizes the empirical risk in $T$:

$P_{N}\ell_{x}=\frac{1}{N}\sum_{i=1}^{N}\big{(}\bigl{<}a_{i},x\bigr{>}^{2}-y_{i}\big{)}^{2}.$

The loss is the standard squared loss functional, which, in this
case,satisfies

$\ell_{x}(a,y)=(f_{x}(a)-y)^{2}=(\bigl{<}x,a\bigr{>}^{2}-\bigl{<}x_{0},a\bigr{>}^{2}-w)^{2}=(\bigl{<}x-x_{0},a\bigr{>}\bigl{<}x+x_{0},a\bigr{>}-w)^{2}.$

Comparing the empirical and actual structures on $T$ is a vital component in
the analysis of ERM. In phase recovery, the centered empirical process that is
at the heart of this approach is defined for any $x\in T$ by,

$P_{N}(\ell_{x}-\ell_{x_{0}})=\frac{1}{N}\sum_{i=1}^{N}\bigl{<}x-x_{0},a_{i}\bigr{>}^{2}\bigl{<}x+x_{0},a_{i}\bigr{>}^{2}-\frac{2}{N}\sum_{i=1}^{N}w_{i}\bigl{<}x-x_{0},a_{i}\bigr{>}\bigl{<}x+x_{0},a_{i}\bigr{>}.$

Both the first and second components are difficult to handle directly, even
when the underlying measure is subgaussian, because of the powers involved (an
effective power of $4$ in the first component and of $3$ in the second one).

Therefore, rather than trying to employ the concentration of empirical means
around the actual ones, which might not be sufficiently strong in this case,
one uses a combination of a small-ball estimate for the ‘high order’ part of
the process, and a more standard deviation argument for the low-order
component (see Section 3 and the formulation of Theorem A and Theorem B).

We assume that linear forms satisfy a certain small-ball estimate, and in
particular, do not assign too much weight to small neighbourhoods of $0$.

###### Assumption 1.1

There is a constant $\kappa_{0}>0$ satisfying that for every
$s,t\in\mathbb{R}^{n}$,

$\mathbb{E}|\bigl{<}a,s\bigr{>}\bigl{<}a,t\bigr{>}|\geq\kappa_{0}\|s\|_{2}\|t\|_{2}.$

Assumption 1.1 is not very restrictive and holds for many natural choices of
random vectors in $\mathbb{R}^{n}$, like the gaussian measure or any isotropic
log-concave measure on $\mathbb{R}^{n}$ (see, for example, the discussion in
[2]).

It is not surprising that the error rate of ERM depends on the structure of
$T$, and because of the subgaussian nature of the random measurement vector
$a$, the natural parameter that captures the complexity of $T$ is the gaussian
mean-width associated with normalizations of $T$.

###### Definition 1.1

Let $G=(g_{1},...,g_{n})$ be the standard gaussian vector in $\mathbb{R}^{n}$.
For $T\subset\mathbb{R}^{n}$, set

$\ell(T)=\mathbb{E}\sup_{t\in T}\Big{|}\sum_{i=1}^{n}g_{i}t_{i}\Big{|}.$

The normalized sets in question are

$\displaystyle T_{-,R}$ $\displaystyle=\left\\{\frac{t-s}{\|t-s\|_{2}}\ :\
t,s\in T,\ \ R<\|t-s\|_{2}\|t+s\|_{2}\right\\},$ $\displaystyle T_{+,R}$
$\displaystyle=\left\\{\frac{t+s}{\|t+s\|_{2}}\ :\ t,s\in T,\ \
R<\|t-s\|_{2}\|t+s\|_{2}\right\\},$

which have been used in [2], or their ‘local’ versions,

$\displaystyle T_{-,R}(x_{0})$
$\displaystyle=\left\\{\frac{t-x_{0}}{\|t-x_{0}\|_{2}}\ :\ t\in T,\ \
R<\|t-x_{0}\|_{2}\|t+x_{0}\|_{2}\right\\},$ $\displaystyle T_{+,R}(x_{0})$
$\displaystyle=\left\\{\frac{t+x_{0}}{\|t+x_{0}\|_{2}}\ :\ t\in T,\ \
R<\|t-x_{0}\|_{2}\|t+x_{0}\|_{2}\right\\}.$

The sets in question play a central role in the exclusion argument that is
used in the analysis of ERM. Setting ${\cal L}_{x}=\ell_{x}-\ell_{x_{0}}$, the
excess loss function associated with $\ell$ and $x\in T$, it is evident that
$P_{N}{\cal L}_{\hat{x}}\leq 0$ (because ${\cal L}_{x_{0}}=0$ is a possible
competitor). If one can find an event of large probability and $R>0$ for which
$P_{N}{\cal L}_{x}>0$ if $\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}\geq R$, then on that
event, $\|\hat{x}-x_{0}\|_{2}\|\hat{x}+x_{0}\|_{2}\leq R$, which is the
estimate one is looking for.

The normalization allows one to study ‘relative fluctuations’ of $P_{N}{\cal
L}_{x}$ – in particular, the way these fluctuations scale with
$\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}$. This is achieved by considering empirical
means of products of functions
$\bigl{<}u,\cdot\bigr{>}\bigl{<}v,\cdot\bigr{>}$, for $u\in T_{+,R}(x_{0})$
and $v\in T_{-,R}(x_{0})$.

The obvious problem with the ‘local’ sets $T_{+,R}(x_{0})$ and
$T_{-,R}(x_{0})$ is that $x_{0}$ is not known. As a first attempt of bypassing
this problem, one may use the ‘global’ sets $T_{+,R}$ and $T_{-,R}$ instead,
as had been done in [2].

Unfortunately, this global approach is not completely satisfactory. Roughly
put, there are two types of subsets of $\mathbb{R}^{n}$ one is interested in,
and that appear in applications. The first type consists of sets for which the
‘local complexity’ is essentially the same everywhere, and the sets
$T_{+,R},T_{-,R}$ are not very different from the seemingly smaller
$T_{+,R}(x_{0})$, $T_{-,R}(x_{0})$, regardless of $x_{0}$.

A typical example of such a set is $d$-sparse vectors – a set consisting of
all the vectors in $\mathbb{R}^{n}$ that are supported on at most
$d$-coordinates. For every $x_{0}\in T$ and $R>0$, the sets
$T_{+,R}(x_{0}),T_{-,R}(x_{0})$, and $T_{+,R},T_{-,R}$ are contained in the
subset of the sphere consisting of $2d$-sparse vectors, which is a relatively
small set.

For this kind of set, the ‘global’ approach, using $T_{+,R}$ and $T_{-,R}$,
suffices, and the choice of the target $x_{0}$ does not really influence the
rate in which
$\left\|\hat{x}-x_{0}\right\|_{2}\left\|\hat{x}+x_{0}\right\|_{2}$ decays to
$0$ with $N$.

In contrast, sets of the second type one would like to study, have vastly
changing local complexity, with the typical example being a convex, centrally
symmetric set (i.e. if $x\in T$ then $-x\in T$).

Consider, for example, the case $T=B_{1}^{n}$, the unit ball in
$\ell_{1}^{n}$. It is not surprising that for small $R$, the sets $T_{+,R}(0)$
and $T_{-,R}(0)$ are very different from $T_{-,R}(e_{1})$ and
$T_{+,R}(e_{1})$: the ones associated with the centre $0$ are the entire
sphere, while for $e_{1}=(1,0,....,0)$, $T_{+,R}(e_{1})$ and $T_{-,R}(e_{1})$
consist of vectors that are well approximated by sparse vectors (whose support
depend on $R$), and thus are rather small subsets of the sphere .

The situation that one encounters in $B_{1}^{n}$ is generic for convex
centrally-symmetric sets. The sets become locally ‘richer’ the closer the
centre is to $0$, and at $0$, for small enough $R$, $T_{+,R}(0)$ and
$T_{-,R}(0)$ are the entire sphere. Since the sets $T_{+,R}$ and $T_{-,R}$ are
blind to the location of the centre, and are, in fact, the union over all
possible centres of the local sets, they are simply too big to be used in the
analysis of ERM in convex sets. A correct estimate on the performance of ERM
for such sets requires a more delicate local analysis and additional
information on $\|x_{0}\|_{2}$. Moreover, the rate of convergence of ERM truly
depends on $\|x_{0}\|_{2}$ in the phase recovery problem via the signal-to-
noise ratio $\left\|x_{0}\right\|_{2}/\sigma$.

We begin by formulating our results using the ‘global’ sets $T_{+,R}$ and
$T_{-,R}$. Let $T_{+}=T_{+,0}$ and $T_{-}=T_{-,0}$, set

$E_{R}=\max\\{\ell(T_{+,R}),\ell(T_{-,R})\\},\ \ \
E=\max\\{\ell(T_{+}),\ell(T_{-})\\}$

and observe that as nonempty subsets of the sphere
$\ell(T_{-,r}),\ell(T_{+,r})\geq\mathbb{E}|g|=\sqrt{2/\pi}$.

The first result presented here is that the error rate of ERM for the phase
retrieval problem in $T$ depends on the fixed points

$r_{2}(\gamma)=\inf\left\\{r>0:E_{r}\leq\gamma\sqrt{N}r\right\\}$

and

$r_{0}(Q)=\inf\left\\{r>0:E_{r}\leq Q\sqrt{N}\right\\},$

for constants $\gamma$ and $Q$ that will be specified later.

Recall that the $\psi_{2}$-norm of a random variable $w$ is defined by
$\|w\|_{\psi_{2}}=\inf\\{c>0:\mathbb{E}\exp(w^{2}/c^{2})\leq 2\\}$ and set
$\sigma=\|w\|_{\psi_{2}}$.

Theorem A. For every $L>1$, $\kappa_{0}>0$ and $\beta>1$, there exist
constants $c_{0},c_{1}$ and $c_{2}$ that depend only on $L$, $\kappa_{0}$ and
$\beta$ for which the following holds. Let $a$ and $w$ be as above and assume
that $w$ has a finite $\psi_{2}$-norm. If $\ell$ is the squared loss and
$\hat{x}$ is produced by ERM, then with probability at least

$1-2\exp(-c_{0}\min\\{\ell^{2}(T_{+,r_{2}^{*}}),\ell^{2}(T_{-,r_{2}^{*}})\\})-2N^{-\beta+1},$
$\|\hat{x}-x_{0}\|_{2}\|\hat{x}+x_{0}\|_{2}\leq
r_{2}^{*}:=\max\\{r_{0}(c_{1}),r_{2}(c_{2}/\sigma\sqrt{\log N})\\}.$

When $\left\|w\right\|_{\infty}<\infty$ the term $\sigma\sqrt{\log N}$ may be
replaced by $\left\|w\right\|_{\infty}$.

The upper estimate of $\max\\{r_{0},r_{2}\\}$ in Theorem A represents two
ranges of noise. It follows from the definition of the fixed points that
$r_{0}$ is dominant if $\sigma\leq r_{0}/\sqrt{\log N}$. As explained in [7]
for linear regression, $r_{0}$ captures the difficulty of recovery in the
noise free case, when the only reason for errors is that there are several
far-away functions in the class that coincide with the target on the noiseless
data. When the noise level $\sigma$ surpasses that threshold, errors occur
because of the interaction class members have with the noise, and the
dominating term becomes $r_{2}$.

Of course, there are cases in which $r_{0}=0$ for $N$ sufficiently large. This
is precisely when exact recovery is possible in the noise-free environment.
And, in such cases, the error of ERM tends to zero with $\sigma$.

The behavior of ERM in the noise-free case is one of the distinguishing
features of sets with well behaved ‘global complexity’ – because $E$ is not
too large. Since $E_{R}\leq E$ for every $R>0$, it follows that when $N\gtrsim
E^{2}$, $r_{0}=0$ and that $r_{2}(\gamma)\leq E/(\gamma\sqrt{N})$. Therefore,
on the event from Theorem A,

$\|\hat{x}-x_{0}\|_{2}\|\hat{x}+x_{0}\|_{2}\lesssim\sigma\frac{E}{\sqrt{N}}\sqrt{\log
N}.$

This estimate suffices for many applications. For example, when $T$ is the set
of $d$-sparse vectors, one may show (see, e.g. [2]) that

$E\lesssim\sqrt{d\log(en/d)}.$

Hence, by Theorem A, when $N\gtrsim d\log\big{(}en/d\big{)}$, with high
probability,

$\|\hat{x}-x_{0}\|_{2}\|\hat{x}+x_{0}\|_{2}\lesssim\sigma\sqrt{\frac{d\log(en/d)}{N}}\sqrt{\log
N}.$

The proof of this observation regarding $d$-sparse vectors, and that this
estimate is sharp in the minimax sense (up to the logarithmic term) may be
found in Section 6.

One should note that Theorem A improves the main result from [2] in three
ways. First of all, the error rate (the estimate on
$\|\hat{x}-x_{0}\|_{2}\|\hat{x}+x_{0}\|_{2}$) established in Theorem A is
$\sim E/\sqrt{N}$ (up to logarithmic factors), whereas in [2], it scaled like
$c/N^{1/4}$ for very large values of $N$. Second, the error rate scales
linearly in the noise level $\sigma$ in Theorem A. On the other hand, the rate
obtained in [2] does not decay with $\sigma$ for $\sigma\leq 1$. Finally, the
probability estimate has been improved, though it is still likely to be
suboptimal.

Although the main motivation for [2] was dealing with phase retrieval for
sparse classes, and for which Theorem A is well suited, we next turn to the
question of more general classes, the most important example of which is a
convex, centrally-symmetric class. For such a class, the global localization
is simply too big to yield a good bound.

###### Definition 1.2

Let

$r_{N}^{*}(Q)=\inf\left\\{r>0:\ell(T\cap rB_{2}^{n})\leq Qr\sqrt{N}\right\\},$
$s_{N}^{*}(\eta)=\inf\left\\{s>0:\ell(T\cap sB_{2}^{n})\leq\eta
s^{2}\sqrt{N}\right\\},$

and

$v_{N}^{*}(\zeta)=\inf\left\\{v>0:\ell(T\cap vB_{2}^{n})\leq\zeta
v^{3}\sqrt{N}\right\\},$

The parameters $r_{N}^{*}$ and $s_{N}^{*}$ have been used in [7] to obtain a
sharp estimate on the performance of ERM for linear regression in an arbitrary
convex set, and relative to $L$-subgaussian measurements. This result is
formulated below in a restricted context, analogous to the phase retrieval
setup: a linear model $z=\bigl{<}a,x_{0}\bigr{>}+w$, for an isotropic,
$L$-subgaussian vector $a$, independent noise $w$ and $x_{0}\in T$.

Let $\hat{x}$ be the output of ERM using the data $(a_{i},z_{i})_{i=1}^{N}$
and set $\|w\|_{\psi_{2}}=\sigma$.

###### Theorem 1.3

For every $L\geq 1$ there exist constants $c_{1},c_{2},c_{3}$ and $c_{4}$ that
depend only on $L$ for which the following holds. Let $T\subset\mathbb{R}^{d}$
be a convex set, put $\eta=c_{1}/\sigma$ and set $Q=c_{2}$.

1\. If $\sigma\geq c_{3}r_{N}^{*}(Q)$ then with probability at least
$1-4\exp(-c_{4}N\eta^{2}(s_{N}^{*}(\eta))^{2})$,

$\|x-x_{0}\|_{2}\leq s_{N}^{*}(\eta).$

2\. If $\sigma\leq c_{3}r_{N}^{*}(Q)$ then with probability at least
$1-4\exp(-c_{4}NQ^{2})$,

$\|x-x_{0}\|_{2}\leq r_{N}^{*}(Q).$

Our main result is a phase retrieval version of Theorem 1.3. Theorem B. For
every $L\geq 1$, $\kappa_{0}>0$ and $\beta$ there exist constants
$c_{1},c_{2},c_{3}$, $c_{4},c_{5}$ and $Q$ that depend only on $L$ and
$\kappa_{0}$ and $\beta$ for which the following holds. Let
$T\subset\mathbb{R}^{d}$ be a convex, centrally-symmetric set, and let $a$ and
$w$ be as in Theorem A. Assume that $(\sigma/\|x_{0}\|_{2})\geq
c_{0}r_{N}^{*}(Q)/\sqrt{\log N}$, set
$\eta=c_{1}\|x_{0}\|_{2}/(\sigma\sqrt{\log N})$ and let
$\zeta=c_{1}/(\sigma\sqrt{\log N})$.

1\. If $\|x_{0}\|_{2}\geq v_{N}^{*}(c_{2})$, then with probability at least
$1-2\exp(-c_{3}N\eta^{2}(s_{N}^{*}(\eta))^{2})-2N^{-\beta+1}$,

$\min\\{\|x-x_{0}\|_{2},\|x+x_{0}\|_{2}\\}\leq c_{4}s_{N}^{*}(\eta).$

2\. If $\|x_{0}\|_{2}\leq v_{N}^{*}(c_{2})$ then with probability at least
$1-2\exp(-c_{3}N\zeta^{2}(v_{N}^{*}(\zeta))^{2})-2N^{-\beta+1}$,

$\max\\{\|x-x_{0}\|_{2},\|x+x_{0}\|_{2}\\}\leq c_{4}v_{N}^{*}(\zeta).$

If $(\sigma/\|x_{0}\|_{2})\geq c_{0}r_{N}^{*}(Q)/\sqrt{\log N}$ the same
assertion as in 1. and 2. holds, with an upper bound of $r_{N}^{*}(Q)$
replacing $s_{N}^{*}(\eta)$ and $v_{N}^{*}(\zeta)$.

Theorem B follows from Theorem A and a more transparent description of the
localized sets $T_{-,R}(x_{0})$ and $T_{+,R}(x_{0})$ (see Lemma 4.1).

To put Theorem B in some perspective, observe that $v_{N}^{*}$ tends to zero.
Indeed, since $\ell(T\cap rB_{2}^{n})\leq\ell(T)$, it follows that
$v_{N}^{*}(\zeta)\leq(\ell(T)/\sqrt{N}\zeta)^{1/3}$. Hence, for the choice of
$\zeta\sim(\sigma\sqrt{\log N})^{-1}$ as in Theorem B,

$v_{N}^{*}\leq\left(\sigma\ell(T)\sqrt{\frac{\log N}{N}}\right)^{1/3},$

which tends to zero when $\sigma\to 0$ and when $N\to\infty$. Therefore, if
$x_{0}\not=0$, the first part of Theorem B describes the ‘long term’ behaviour
of ERM.

Also, and using the same argument,

$r_{N}^{*}(Q)\leq\frac{\ell(T)}{Q\sqrt{N}}.$

Thus, for every $\sigma>0$ the problem becomes ‘high noise’ in the sense that
the condition $(\sigma/\|x_{0}\|_{2})\geq c_{0}r_{N}(Q)/\sqrt{\log N}$ is
satisfied when $N$ is large enough.

In the typical situation, which is both ‘high noise’ and ‘large
$\|x_{0}\|_{2}$’, the error rate depends on
$\eta=c_{1}\|x_{0}\|_{2}/\sigma\sqrt{\log N}$. We believe that the
$1/\sqrt{\log N}$ factor is an artifact of the proof, but the other term,
$\|x_{0}\|_{2}/\sigma$ is the signal-to-noise ratio, and is rather natural.

Although Theorem A and Theorem B clearly improve the results from [2], it is
natural to ask whether these are optimal in a more general sense. The final
result presented here is that Theorem B is close to being optimal in the
minimax sense. The formulation and proof of the minimax lower bound is
presented in Section 5.

Finally, we end the article with two examples of classes that are of interest
in phase retrieval: $d$-sparse vectors and the unit ball in $\ell_{1}^{n}$.
The first is a class with a fixed ‘local complexity’, and the second has a
growing ‘local complexity’.

##  2 Preliminaries

Throughout this article, absolute constants are denoted by $C,c,c_{1},...$
etc. Their value may change from line to line. The fact that there are
absolute constants $c,C$ for which $ca\leq b\leq Ca$ is denoted by $a\sim b$;
$a\lesssim b$ means that $a\leq cb$, while $a\sim_{L}b$ means that the
constants depend only on the parameter $L$.

For $1\leq p\leq\infty$, let $\|\cdot\|_{p}$ be the $\ell_{p}^{n}$ norm
endowed on $\mathbb{R}^{n}$, and for a function $f$ (or a random variable $X$)
on a probability space, set $\|f\|_{L_{p}}$ to be its $L_{p}$ norm.

Other norms that play a significant role here are the Orlicz norms. For basic
facts on these norms we refer the reader to [9, 15].

Recall that for $\alpha\geq 1$,

$\|f\|_{\psi_{\alpha}}=\inf\\{c>0:\mathbb{E}\exp(|f|^{\alpha}/c^{\alpha})\leq
2\\},$

and it is straightforward to extend the definition for $0<\alpha<1$.

Orlicz norms measure the rate of decay of a function. One may verify that
$\|f\|_{\psi_{\alpha}}\sim\sup_{p\geq 1}\|f\|_{L_{p}}/p^{1/\alpha}$. Moreover,
for $t\geq 1$, $Pr(|f|\geq t)\leq
2\exp(-ct^{\alpha}/\|f\|_{\psi_{\alpha}}^{\alpha})$, and
$\|f\|_{\psi_{\alpha}}$ is equivalent to the smallest constant $\kappa$ for
which $Pr(|f|\geq t)\leq 2\exp(-t^{\alpha}/\kappa^{\alpha})$ for every $t\geq
1$.

###### Definition 2.1

A random variable is $L$-subgaussian if it has a bounded $\psi_{2}$ norm and
$\|X\|_{\psi_{2}}\leq L\|X\|_{L_{2}}$.

Observe that for $L$-subgaussian random variables, all the $L_{p}$ norms are
equivalent and their tails exhibits a faster decay than the corresponding
gaussian. Indeed, if $X$ is $L$-subgaussian,

$\|X\|_{L_{p}}\lesssim\sqrt{p}\|X\|_{\psi_{2}}\lesssim
L\sqrt{p}\|X\|_{L_{2}},$

and for every $t\geq 1$,

$Pr(|X|>t)\leq 2\exp(-ct^{2}/\|X\|_{\psi_{2}}^{2})\leq
2\exp(-ct^{2}/(L^{2}\|X\|_{L_{2}}^{2}))$

for a suitable absolute constant $c$.

It is standard to verify that for every $f,g$,
$\|fg\|_{\psi_{1}}\lesssim\|f\|_{\psi_{2}}\|g\|_{\psi_{2}}$, and that if
$X_{1},...,X_{N}$ are independent copies of $X$ and $1\leq\alpha\leq 2$, then

$\|\max_{1\leq i\leq
N}X_{i}\|_{\psi_{\alpha}}\lesssim\|X\|_{\psi_{\alpha}}\log^{1/\alpha}N.$ (2.1)

An additional feature of $\psi_{\alpha}$ random variables is concentration,
namely that if $(X_{i})_{i=1}^{N}$ are independent copies of a $\psi_{\alpha}$
random variable $X$, then $N^{-1}\sum_{i=1}^{N}X_{i}$ concentrates around
$\mathbb{E}X$. One example of such a concentration result is the following
Bernstein-type inequality (see, e.g., [15]).

###### Theorem 2.2

There exists an absolute constant $c_{0}$ for which the following holds. If
$X_{1},...,X_{N}$ are independent copies of a $\psi_{1}$ random variable $X$,
then for every $t>0$,

$Pr\left(\left|\frac{1}{N}\sum_{i=1}^{N}X_{i}-\mathbb{E}X\right|>t\|X\|_{\psi_{1}}\right)\leq
2\exp(-c_{0}N\min\\{t^{2},t\\}).$

One important example of a probability space considered here is the discrete
space $\Omega=\\{1,...,N\\}$, endowed with the uniform probability measure.
Functions on $\Omega$ can be viewed as vectors in $\mathbb{R}^{N}$ and the
corresponding $L_{p}$ and $\psi_{\alpha}$ norms are denoted by
$\|\cdot\|_{L_{p}^{N}}$ and $\|\cdot\|_{\psi_{\alpha}^{N}}$.

A significant part of the proofs of Theorem A has to do with the behaviour of
a monotone non-increasing rearrangement of vectors. Given
$v\in\mathbb{R}^{N}$, let $(v_{i}^{*})_{i=1}^{N}$ be a non-increasing
rearrangement of $(|v_{i}|)_{i=1}^{N}$. It turns out that the
$\psi_{\alpha}^{N}$ norm captures information on the coordinates of
$(v_{i}^{*})_{i=1}^{N}$.

###### Lemma 2.3

For every $1\leq\alpha\leq 2$ there exist constants $c_{1}$ and $c_{2}$ that
depend only on $\alpha$ for which the following holds. For every
$v\in\mathbb{R}^{N}$,

$c_{1}\sup_{i\leq
N}\frac{v_{i}^{*}}{\log^{1/\alpha}(eN/i)}\leq\|v\|_{\psi_{\alpha}^{N}}\leq
c_{2}\sup_{i\leq N}\frac{v_{i}^{*}}{\log^{1/\alpha}(eN/i)}.$

Proof. We will prove the claim only for $\alpha=2$ as the other cases follow
an identical path.

Let $v\in\mathbb{R}^{N}$ and denote by $Pr$ the uniform probability measure on
$\Omega=\\{1,\ldots,N\\}$. By the tail characterization of the $\psi_{2}$
norm,

$N^{-1}|\\{j:|v_{j}|>t\\}|=Pr(|v|>t)\leq
2\exp(-ct^{2}/\|v\|_{\psi_{2}^{N}}^{2}).$

Hence, for $t_{i}=c^{-1/2}\|v\|_{\psi_{2}^{N}}\sqrt{\log(eN/i)}$,
$|\\{j:|v_{j}|>t_{i}\\}|\leq 2i/e\leq i$, and for every $1\leq i\leq N$,
$v_{i}^{*}\leq t_{i}$. Therefore,

$\sup_{i\leq N}\frac{v_{i}^{*}}{\sqrt{\log(eN/i)}}\leq
c^{-1/2}\|v\|_{\psi_{2}^{N}},$

as claimed.

In the reverse direction, consider

${\cal B}=\big{\\{}\beta>0:\forall\ 1\leq i\leq N,\
\|v\|_{\psi_{2}^{N}}\geq\beta v_{i}^{*}/\sqrt{\log(eN/i)}\big{\\}}.$

It is enough to show that ${\cal B}$ is bounded by a constant that is
independent of $v$. To that end, fix $\beta\in{\cal B}$ and without loss of
generality, assume that $\beta>2$. Set $B=\sup_{i\leq N}\beta
v_{i}^{*}/\sqrt{\log(eN/i)}$ and since $\beta\in{\cal B}$,
$\|v\|_{\psi_{2}^{N}}\geq B$.

Also, since $1/\beta^{2}<1$,

$\sum_{i=1}^{N}\left(\frac{1}{i}\right)^{1/\beta^{2}}\leq
1+\int_{1}^{N}\left(\frac{1}{x}\right)^{1/\beta^{2}}dx\leq\frac{N^{1-1/\beta^{2}}}{1-1/\beta^{2}}.$

Therefore,

$\displaystyle\sum_{i=1}^{N}\exp(v_{i}^{2}/B^{2})=\sum_{i=1}^{N}\exp((v_{i}^{*})^{2}/B^{2})\leq\sum_{i=1}^{N}\exp(\beta^{-2}\log(eN/i))$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N}\left(\frac{eN}{i}\right)^{1/\beta^{2}}\leq(eN)^{1/\beta^{2}}\cdot\frac{N^{1-1/\beta^{2}}}{1-1/\beta^{2}}\leq\frac{Ne^{1/\beta^{2}}}{1-1/\beta^{2}}<2N,$

provided that $\beta\geq c_{1}$. Thus, if $\beta\geq c_{1}$,
$\|v\|_{\psi_{2}^{N}}<B$ which is a contradiction, showing that ${\cal B}$ is
bounded by $c_{1}$.

###  2.1 Empirical and Subgaussian processes

The sampling method used here is isotropic and $L$-subgaussian, meaning that
the vectors $(a_{i})_{i=1}^{N}$ are independent and distributed according to a
probability measure $\mu$ on $\mathbb{R}^{n}$ that is both isotropic and
$L$-subgaussian [15]:

###### Definition 2.4

Let $\mu$ be a probability measure on $\mathbb{R}^{n}$ and let $a$ be
distributed according to $\mu$. The measure $\mu$ is isotropic if for every
$t\in\mathbb{R}^{n}$, $\mathbb{E}\bigl{<}a,t\bigr{>}^{2}=\|t\|_{2}^{2}$. It is
$L$-subgaussian if for every $t\in\mathbb{R}^{n}$ and every $u\geq 1$,
$Pr(|\bigl{<}a,t\bigr{>}|\geq Lu\|\bigl{<}t,a\bigr{>}\|_{2})\leq
2\exp(-u^{2}/2)$.

Given $T\subset\mathbb{R}^{n}$, let $d_{T}=\sup_{t\in T}\|t\|_{2}$ and put
$k_{*}(T)=(\ell(T)/d_{T})^{2}$. The latter appears naturally in the context of
Dvoretzky type theorems, and in particular, in Milman’s proof of Dvoretzky’s
Theorem (see, e.g., [11]).

###### Theorem 2.5

[10] For every $L\geq 1$ there exist constants $c_{1}$ and $c_{2}$ that depend
only on $L$ and for which the following holds. For every $u\geq c_{1}$, with
probability at least $1-2\exp(-c_{2}u^{2}k_{*}(T))$, for every $t\in T$ and
every $I\subset\\{1,...,N\\}$,

$\left(\sum_{i\in I}\bigl{<}t,a_{i}\bigr{>}^{2}\right)^{1/2}\leq
Lu^{3}\left(\ell(T)+d_{T}\sqrt{|I|\log(eN/|I|)}\right).$

For every integer $N$, let $j_{T}$ be the largest integer $j$ in
$\\{1,...,N\\}$ for which

$\ell(T)\geq d_{T}\sqrt{j\log(eN/j)}.$

It follows from Theorem 2.5 that if $t\in T$ and $|I|\leq j_{T}$,

$(\sum_{i\in I}\bigl{<}t,a_{i}\bigr{>}^{2})^{1/2}\lesssim_{L,u}\ell(T),$

and if $|I|\geq j_{T}$,

$(\sum_{i\in
I}\bigl{<}t,a_{i}\bigr{>}^{2})^{1/2}\lesssim_{L,u}d_{T}\sqrt{|I|\log(eN/|I|)}.$

Therefore, if $v=(\bigl{<}t,a_{i}\bigr{>})_{i=1}^{N}$ and
$(v_{i}^{*})_{i=1}^{N}$ is a monotone non-increasing rearrangement of
$(|v_{i}|)_{i=1}^{N}$, then

$v_{i}^{*}\leq\left(\frac{1}{i}\sum_{j=1}^{i}(v_{j}^{*})^{2}\right)^{1/2}\lesssim_{L,u}\left\\{\begin{array}[]{cc}\frac{\ell(T)}{\sqrt{i}}&\mbox{if}\
\ i\leq j_{T}\\\ &\\\
d_{T}\sqrt{\log(eN/i)}&\mbox{otherwise}.\end{array}\right.$ (2.2)

This observation will be used extensively in what follows.

The next fact deals with product processes.

###### Theorem 2.6

[10] There exist absolute constants $c_{0},c_{1}$ and $c_{2}$ for which the
following holds. If $T_{1},T_{2}\subset\mathbb{R}^{n}$, $1\leq 2^{j}\leq N$
and $u\geq c_{0}$, then with probability at least $1-2\exp(-c_{1}u^{2}2^{j})$,

$\displaystyle\sup_{t\in T_{1},\ s\in
T_{2}}\left|\sum_{i=1}^{N}\bigl{<}a_{i},t\bigr{>}\bigl{<}a_{i},s\bigr{>}-\mathbb{E}\bigl{<}a,t\bigr{>}\bigl{<}a,s\bigr{>}\right|$
$\displaystyle\leq$ $\displaystyle
c_{2}L^{2}u^{2}\left(\ell(T_{1})\ell(T_{2})+u\sqrt{N}\left(\ell(T_{1})d(T_{2})+\ell(T_{2})d(T_{1})+2^{j/2}d(T_{1})d(T_{2})\right)\right)$

and

$\displaystyle\sup_{t\in T_{1},\ s\in
T_{2}}\left|\sum_{i=1}^{N}|\bigl{<}a_{i},t\bigr{>}\bigl{<}a_{i},s\bigr{>}|-\mathbb{E}|\bigl{<}a,t\bigr{>}\bigl{<}a,s\bigr{>}|\right|$
$\displaystyle\leq$ $\displaystyle
c_{2}L^{2}u^{2}\left(\ell(T_{1})\ell(T_{2})+u\sqrt{N}\left(\ell(T_{1})d(T_{2})+\ell(T_{2})d(T_{1})+2^{j/2}d(T_{1})d(T_{2})\right)\right).$

###### Remark 2.7

Let $(\varepsilon_{i})_{i=1}^{N}$ be independent, symmetric,
$\\{-1,1\\}$-valued random variables. It follows from the results in [10] that
with the same probability estimate in Theorem 2.6 and relative to the product
measure $(\varepsilon\otimes X)^{N}$,

$\displaystyle\sup_{t\in T_{1},\ s\in
T_{2}}\left|\sum_{i=1}^{N}\varepsilon_{i}\bigl{<}a_{i},t\bigr{>}\bigl{<}a_{i},s\bigr{>}\right|$
$\displaystyle\lesssim$ $\displaystyle
L^{2}u^{2}\left(\ell(T_{1})\ell(T_{2})+u\sqrt{N}\left(\ell(T_{1})d(T_{2})+\ell(T_{2})d(T_{1})+2^{j/2}d(T_{1})d(T_{2})\right)\right).$

Assume that
$(k^{*}(T_{1}))^{1/2}=\ell(T_{1})/d(T_{1})\geq\ell(T_{2})/d(T_{2})$. Setting
$2^{j/2}=\ell(T_{1})/d(T_{1})$, Theorem 2.6 and Remark 2.7 yield that with
probability at least $1-2\exp(-c_{1}u^{2}k_{*}(T_{1}))$,

$\sup_{t\in T_{1},\ s\in
T_{2}}\left|\sum_{i=1}^{N}\bigl{<}a_{i},t\bigr{>}\bigl{<}a_{i},s\bigr{>}-\mathbb{E}\bigl{<}a,t\bigr{>}\bigl{<}a,s\bigr{>}\right|\lesssim
L^{2}u^{2}\ell(T_{1})\left(\ell(T_{2})+u\sqrt{N}d(T_{2})\right),$ $\sup_{t\in
T_{1},\ s\in
T_{2}}\left|\sum_{i=1}^{N}|\bigl{<}a_{i},t\bigr{>}\bigl{<}a_{i},s\bigr{>}|-\mathbb{E}|\bigl{<}a,t\bigr{>}\bigl{<}a,s\bigr{>}|\right|\lesssim
L^{2}u^{2}\ell(T_{1})\left(\ell(T_{2})+u\sqrt{N}d(T_{2})\right)$

and

$\sup_{t\in T_{1},\ s\in
T_{2}}\left|\sum_{i=1}^{N}\varepsilon_{i}\bigl{<}a_{i},t\bigr{>}\bigl{<}a_{i},s\bigr{>}\right|\lesssim
L^{2}u^{2}\ell(T_{1})\left(\ell(T_{2})+u\sqrt{N}d(T_{2})\right).$ (2.3)

One case which is of particular interest is when $T_{1}=T_{2}=T$, and then,
with probability at least $1-2\exp(-c_{1}u^{2}k_{*}(T))$,

$\sup_{t\in
T}\left|\sum_{i=1}^{N}\bigl{<}a_{i},t\bigr{>}^{2}-\mathbb{E}\bigl{<}a,t\bigr{>}^{2}\right|\lesssim
L^{2}u^{2}\left(\ell^{2}(T)+u\sqrt{N}d(T)\ell(T)\right).$

###  2.2 Monotone rearrangement of coordinates

The first goal of this section is to investigate the coordinate structure of
$v\in\mathbb{R}^{m}$, given information on its norm in various $L_{p}^{m}$ and
$\psi_{\alpha}^{m}$ spaces. The vectors we will be interested in are of the
form $(\bigl{<}a_{i},t\bigr{>})_{i=1}^{N}$ for $t\in T$, and for which, thanks
to the results presented in Section 2.1, one has the necessary information at
hand.

It is standard to verify that if $\|v\|_{\psi_{\alpha}^{m}}\leq A$, then
$\|v\|_{p}\lesssim_{p,\alpha}A\cdot m^{1/p}$. Thus,
$\|v\|_{L_{p}^{m}}\lesssim_{p}\|v\|_{\psi_{\alpha}^{m}}$.

It turns out that if the two norms are equivalent, $v$ is regular in some
sense. The next lemma, which is a version of the Paley-Zygmund Inequality,
(see, e.g. [4]), describes the regularity properties needed here in the case
$p=\alpha=1$.

###### Lemma 2.8

For every $\beta>1$ there exist constants $c_{1}$ and $c_{2}$ that depend only
on $\beta$ and for which the following holds. If
$\|v\|_{\psi_{1}^{m}}\leq\beta\|v\|_{L_{1}^{m}}$, there exists
$I\subset\\{1,...,m\\}$ of cardinality at least $c_{1}m$, and for every $i\in
I$, $|v_{i}|\geq c_{2}\|v\|_{L_{1}^{m}}$.

Proof. Recall that $\|v\|_{\psi_{1}^{m}}\sim\sup_{1\leq i\leq
m}v_{i}^{*}/\log(em/i)$. Hence, for every $1\leq j\leq m$,

$\sum_{\ell=1}^{j}v_{\ell}^{*}\lesssim\|v\|_{\psi_{1}^{m}}\sum_{\ell=1}^{j}\log(em/\ell)\lesssim\beta\|v\|_{L_{1}^{m}}j\log(em/j).$

Therefore,

$m\|v\|_{L_{1}^{m}}=\sum_{\ell=1}^{m}|v_{\ell}|=\sum_{\ell\leq
j}v_{\ell}^{*}+\sum_{\ell=j+1}^{m}v_{\ell}^{*}\leq
c_{0}\beta\|v\|_{L_{1}^{m}}j\log(em/j)+\sum_{\ell=j+1}^{m}v_{\ell}^{*}.$

Setting $c_{1}(\beta)\sim 1/(\beta\log(e\beta))$ and $j=c_{1}(\beta)m$,

$c_{0}\beta\|v\|_{L_{1}^{m}}j\log(em/j)\leq(m/2)\|v\|_{L_{1}^{m}}.$

Thus, $\sum_{\ell=j+1}^{m}v_{\ell}^{*}\geq(m/2)\|v\|_{L_{1}^{m}}$, while

$v_{j+1}^{*}\leq\frac{1}{j+1}\sum_{\ell\leq
j+1}v_{\ell}^{*}\lesssim\beta\log(e\beta)\|v\|_{L_{1}^{m}}.$

Let $I$ be the set of the $m-j$ smallest coordinates of $v$. Fix $\eta>0$ to
be named later, put $I_{\eta}\subset I$ to be the set of coordinates in $I$
for which $|v_{i}|\geq\eta\|v\|_{L_{1}^{m}}$ and denote by $I_{\eta}^{c}$ its
complement in $I$. Therefore,

$\displaystyle(m/2)\|v\|_{L_{1}^{m}}\leq$ $\displaystyle\sum_{\ell\geq
j+1}v_{\ell}^{*}=\sum_{\ell\in I_{\eta}}|v_{\ell}|+\sum_{\ell\in
I_{\eta}^{c}}|v_{\ell}|\leq
v_{j+1}^{*}|I_{\eta}|+\eta\|v\|_{L_{1}^{m}}|I_{\eta}^{c}|$
$\displaystyle\lesssim$
$\displaystyle\|v\|_{L_{1}^{m}}|I|\left(\beta\log(e\beta)\frac{|I_{\eta}|}{|I|}+\eta\frac{|I_{\eta}^{c}|}{|I|}\right).$

Hence,

$\frac{m}{2}\lesssim|I|\left(\beta\log(e\beta)\frac{|I_{\eta}|}{|I|}+\eta\left(1-\frac{|I_{\eta}|}{|I|}\right)\right)\lesssim
m\left(\left(\beta\log(e\beta)-\eta\right)\frac{|I_{\eta}|}{|I|}+\eta\right).$

If $\eta=\min\\{1/4,(\beta/2)\log(e\beta)\\}$, then
$|I_{\eta}|\geq(\eta/2)|I|\geq c_{2}(\beta)m$, as claimed.

Next, let us turn to decomposition results for vectors of the form
$(\bigl{<}a_{i},t\bigr{>})_{i=1}^{N}$. Recall that for a set
$T\subset\mathbb{R}^{N}$, $j_{T}$ is the largest integer for which
$\ell(T)\geq d_{T}\sqrt{j\log(eN/j)}$.

###### Lemma 2.9

For every $L>1$ there exist constants $c_{1}$ and $c_{2}$ that depend only on
$L$ and for which the following holds. Let $T\subset\mathbb{R}^{n}$ and set
$W=\\{t/\|t\|_{2}:t\in T\\}\subset S^{n-1}$. With probability at least
$1-2\exp(-c_{1}\ell^{2}(W))$, for every $t\in T$,
$(\bigl{<}a_{i},t\bigr{>})_{i=1}^{N}=v_{1}+v_{2}$ and $v_{1},v_{2}$ have the
following properties:

1\. The supports of $v_{1}$ and $v_{2}$ are disjoint.

2\. $\|v_{1}\|_{2}\leq c_{2}\ell(W)\|t\|_{2}$ and $|{\rm supp}(v_{1})|\leq
j_{W}$.

3\. $\|v_{2}\|_{\psi_{2}^{N}}\leq c_{2}\|t\|_{2}$.

Proof. Fix $t\in T$ and let $J_{t}\subset\\{1,...,N\\}$ be the set of the
largest $j_{W}$ coordinates of $(|\bigl{<}a_{i},t\bigr{>}|)_{i=1}^{N}$. Set

${\bar{v}}_{1}=(\bigl{<}a_{j},t/\|t\|_{2}\bigr{>})_{j\in J_{t}}\ \ {\rm and}\
\ {\bar{v}}_{2}=(\bigl{<}a_{j},t/\|t\|_{2}\bigr{>})_{j\in J_{t}^{c}}.$

By Theorem 2.5 and the characterization of the $\psi_{2}^{N}$ norm of a vector
using the monotone rearrangement of its coordinates (Lemma 2.3),

$\|\bar{v}_{1}\|_{2}\lesssim L\ell(W),\ \ {\rm and}\ \
\|\bar{v}_{2}\|_{\psi_{2}^{N}}\lesssim L.$

To conclude the proof, set $v_{1}=\|t\|_{2}\bar{v}_{1}$ and
$v_{2}=\|t\|_{2}{\bar{v}}_{2}$.

Recall that for every $R>0$,

$T_{+,R}=\left\\{\frac{t+s}{\|t+s\|_{2}}:\ t,s\in T,\
\|t+s\|_{2}\|t-s\|_{2}\geq R\right\\},$

and a similar definition holds for $T_{-,R}$. Set $j_{+,R}=j_{T_{+,R}}$,
$j_{-,R}=j_{T_{+,R}}$ and $E_{R}=\max\\{\ell(T_{+,R}),\ell(T_{-,R})\\}$.
Combining the above estimates leads to the following corollary.

###### Corollary 2.10

For every $L>1$ there exist constants $c_{1},c_{2},c_{3}$ and $c_{4}$ that
depend only on $L$ for which the following holds. Let $T\subset\mathbb{R}^{n}$
and $R>0$, and consider $T_{+,R}$ and $T_{-,R}$ as above. With probability at
least $1-4\exp(-c_{1}L^{2}\min\\{\ell^{2}(T_{+,R}),\ell^{2}(T_{-,R})\\})$, for
every $s,t\in T$ for which $\|t-s\|_{2}\|t+s\|_{2}\geq R$,

1\. $(\bigl{<}s-t,a_{i}\bigr{>})_{i=1}^{N}=v_{1}+v_{2}$, for vectors $v_{1}$
and $v_{2}$ of disjoint supports satisfying

$|{\rm supp}(v_{1})|\leq j_{-,R},\ \ \|v_{1}\|_{2}\leq
c_{2}\ell(T_{-,R})\|s-t\|_{2}\ \ {\rm and}\ \ \|v_{2}\|_{\psi_{2}^{N}}\leq
c_{2}\|s-t\|_{2}.$

2\. $(\bigl{<}s+t,a_{i}\bigr{>})_{i=1}^{N}=u_{1}+u_{2}$, for vectors $u_{1}$
and $u_{2}$ of disjoint supports satisfying

$|{\rm supp}(u_{1})|\leq j_{+,R},\ \ \|u_{1}\|_{2}\leq
c_{2}\ell(T_{+,R})\|s+t\|_{2}\ \ {\rm and}\ \ \|u_{2}\|_{\psi_{2}^{N}}\leq
c_{2}\|s+t\|_{2}.$

3\. If
$h_{s,t}(a)=\bigl{<}\frac{s+t}{\|s+t\|_{2}},a\bigr{>}\bigl{<}\frac{s-t}{\|s-t\|_{2}},a\bigr{>}$,
then

$\left|\frac{1}{N}\sum_{i=1}^{N}|h_{s,t}(a_{i})|-\mathbb{E}|h_{s,t}|\right|\leq
c_{3}\left(\frac{E_{R}}{\sqrt{N}}+\frac{E_{R}^{2}}{N}\right).$

In particular, recalling that for every $s,t\in T$,

$\mathbb{E}|\bigl{<}s+t,a\bigr{>}\bigl{<}s-t,a\bigr{>}|\geq\kappa_{0}{\|s+t\|_{2}\|s-t\|_{2}},$

it follows that if $\sqrt{N}\geq c_{4}(L)E_{R}/\kappa_{0}$ then

4.

$\frac{\kappa_{0}}{2}\|s+t\|_{2}\|s-t\|_{2}\leq\frac{1}{N}\sum_{i=1}^{N}|\bigl{<}s+t,a_{i}\bigr{>}\bigl{<}s-t,a_{i}\bigr{>}|\lesssim_{L}\|s+t\|_{2}\|s-t\|_{2}.$
(2.4)

From here on, denote by $\Omega_{1,R}$ the event on which Corollary 2.10 holds
for the sets $T_{+,R}$ and $T_{-,R}$ and samples of cardinality
$N\gtrsim_{L}E_{R}^{2}/\kappa_{0}^{2}$.

###### Lemma 2.11

There exist constants $c_{0}$ depending only on $L$ and $c_{1},\kappa_{1}$
that depend only on $\kappa_{0}$ and $L$ for which the following holds. If
$N\geq c_{0}E_{R}^{2}/\kappa_{0}^{2}$, then for
$(a_{i})_{i=1}^{N}\in\Omega_{1,R}$, for every $s,t\in T$ for which
$\|s-t\|_{2}\|s+t\|_{2}\geq R$, there is $I_{s,t}\subset\\{1,...,N\\}$ of
cardinality at least $\kappa_{1}N$, and for every $i\in I_{s,t}$,

$|\bigl{<}s-t,a_{i}\bigr{>}\bigl{<}s+t,a_{i}\bigr{>}|\geq
c_{1}\|s-t\|_{2}\|s+t\|_{2}.$

Lemma 2.11 is an empirical “small-ball” estimate, as it shows that with high
probability, and for every pair $s,t$ as above, many of the coordinates of
$(|\bigl{<}a_{i},s-t\bigr{>}|\cdot|\bigl{<}a_{i},s+t\bigr{>}|)_{i=1}^{N}$ are
large.

Proof. Fix $s,t\in T$ as above and set

$y=(\bigl{<}s-t,a_{i}\bigr{>})_{i=1}^{N},\ \ {\rm and}\ \
x=(\bigl{<}s+t,a_{i}\bigr{>})_{i=1}^{N}.$

Let $y=v_{1}+v_{2}$ and $x=u_{1}+u_{2}$ as in Corollary 2.10. Let
$j_{0}=\max\\{j_{-,R},j_{+,R}\\}$ and put $J={\rm supp}(v_{1})\cup{\rm
supp}(u_{1})$. Observe that $|J|\leq 2j_{0}$ and that

$\displaystyle\sum_{j\in J}|y(j)|\cdot|x(j)|\leq\sum_{j\in{\rm
supp}(v_{1})}|v_{1}(j)x(j)|+\sum_{j\in{\rm supp}(u_{1})}|y(j)u_{1}(j)|$
$\displaystyle\leq$
$\displaystyle\|v_{1}\|_{2}\left(\sum_{i=1}^{2j_{0}}(x^{2}(j))^{*}\right)^{1/2}+\|u_{1}\|_{2}\left(\sum_{i=1}^{2j_{0}}(y^{2}(j))^{*}\right)^{1/2}$
$\displaystyle\lesssim_{L}$
$\displaystyle\ell(T_{-,R})\|s-t\|_{2}\cdot\sqrt{j_{0}\log(eN/j_{0})}\|s+t\|_{2}$
$\displaystyle+$
$\displaystyle\ell(T_{+,R})\|s+t\|_{2}\cdot\sqrt{j_{0}\log(eN/j_{0})}\|s-t\|_{2}$
$\displaystyle\lesssim_{L}$ $\displaystyle
E_{R}^{2}\|s-t\|_{2}\|s+t\|_{2}\leq\frac{\kappa_{0}N}{4}\|s-t\|_{2}\|s+t\|_{2},$

because, by the definition of $j_{0}$,
$\sqrt{j_{0}\log(eN/j_{0})}\lesssim\max\\{\ell(T_{-,R}),\ell(T_{+,R})\\}$ and
since $N\geq c_{0}E_{R}^{2}/\kappa_{0}^{2}$ for $c_{0}=c_{0}(L)$ large enough.

Thus, by (2.4),

$\sum_{j\in J^{c}}|y(j)x(j)|\geq N\kappa_{0}\|s-t\|_{2}\|s+t\|_{2}/4.$

Set $m=|J^{c}|$ and let $z=(y(j)x(j))_{j\in J^{c}}=(v_{2}(j)u_{2}(j))_{j\in
J^{c}}$. Since $N\gtrsim_{L}E_{R}^{2}/\kappa_{0}^{2}$, it is evident that
$j_{0}\leq N/2$; thus $N/2\leq m\leq N$ and

$\|z\|_{L_{1}^{m}}=\frac{1}{m}\sum_{j\in
J^{c}}|y(j)x(j)|\geq\frac{N}{4m}\kappa_{0}\|s-t\|_{2}\|s+t\|_{2}\gtrsim\kappa_{0}\|s-t\|_{2}\|s+t\|_{2}.$

On the other hand,

$\|z\|_{\psi_{1}^{m}}\leq\|(v_{2}u_{2}(j))_{j\in
J_{c}}\|_{\psi_{1}^{m}}\lesssim\|v_{2}\|_{\psi_{2}^{m}}\|u_{2}\|_{\psi_{2}^{m}}\lesssim_{L}\|s-t\|_{2}\|s+t\|_{2},$

and $z$ satisfies the assumption of Lemma 2.8 for $\beta=c_{1}(L,\kappa_{0})$.
The claim follows immediately from that lemma.

##  3 Proof of Theorem A

It is well understood that when analyzing properties of ERM relative to a loss
$\ell$, studying the excess loss functional is rather natural. The excess loss
shares the same empirical minimizer as the loss, but it has additional
qualities: for every $x\in T$, $\mathbb{E}{\cal L}_{x}\geq 0$ and ${\cal
L}_{x_{0}}=0$.

Since $0$ is a potential minimizer of $\\{P_{N}{\cal L}_{x}:x\in T\\}$, the
minimizer $\hat{x}$ satisfies that $P_{N}{\cal L}_{\hat{x}}\leq 0$, giving one
a way of excluding parts of $T$ as potential empirical minimizers. One simply
has to show that with high probability, those parts belong to the set
$\\{x:P_{N}{\cal L}_{x}>0\\}$, for example, by showing that $P_{N}{\cal
L}_{x}$ is equivalent to $\mathbb{E}{\cal L}_{x}$, as the latter is positive
for points that are not true minimizers.

The squared excess loss has a simple decomposition to two processes: a
quadratic process and a multiplier one. Indeed, given a class of functions $F$
and $f\in F$,

$\big{(}f(a)-y\big{)}^{2}-\big{(}f^{*}(a)-y\big{)}^{2}=\big{(}f(a)-f^{*}(a)\big{)}^{2}-2\big{(}f(a)-f^{*}(a)\big{)}\big{(}f^{*}(a)-y\big{)}.$

where, as always, $f^{*}$ is a minimizer of the functional
$\mathbb{E}\big{(}f(a)-y\big{)}^{2}$ in $F$.

In the phase retrieval problem, $y=\bigl{<}x_{0},a\bigr{>}^{2}+w$ for a noise
$w$ that is independent of $a$, and each $f_{x}\in F$ is given by
$f_{x}=\bigl{<}x,\cdot\bigr{>}^{2}$. Thus,

$\displaystyle{\cal L}_{x}(a,y)$
$\displaystyle=\ell_{x}(a,y)-\ell_{x_{0}}(a,y)=\big{(}f_{x}(a)-y\big{)}^{2}-\big{(}f_{x_{0}}(a)-y\big{)}^{2}$
$\displaystyle=\left(\bigl{<}x-x_{0},a\bigr{>}\bigl{<}x+x_{0},a\bigr{>}\right)^{2}-2w\bigl{<}x-x_{0},a\bigr{>}\bigl{<}x+x_{0},a\bigr{>}.$

Since $w$ is a mean-zero random variable that is independent of $a$, and by
Assumption 1.1,

$\mathbb{E}{\cal
L}_{x}(a,y)=\mathbb{E}|\bigl{<}x-x_{0},a\bigr{>}\bigl{<}x+x_{0},a\bigr{>}|\geq\kappa_{0}^{2}\|x-x_{0}\|_{2}^{2}\|x+x_{0}\|_{2}^{2}.$

Therefore, $\mathbb{E}\big{(}f_{x}(a)-y\big{)}^{2}$ has a unique minimizer in
$F$: $f^{*}=f_{x_{0}}=f_{-x_{0}}$.

To show that $P_{N}{\cal L}_{x}>0$ on a large subset $T^{\prime}\subset T$, it
suffices to obtain a high probability lower bound on

$\inf_{x\in
T^{\prime}}\frac{1}{N}\sum_{i=1}^{N}\left(\bigl{<}x-x_{0},a_{i}\bigr{>}\bigl{<}x+x_{0},a_{i}\bigr{>}\right)^{2}$

that dominates a high probability upper bound on

$\sup_{x\in
T^{\prime}}\left|\frac{2}{N}\sum_{i=1}^{N}w_{i}\bigl{<}x-x_{0},a_{i}\bigr{>}\bigl{<}x+x_{0},a_{i}\bigr{>}\right|.$

The set $T^{\prime}$ that will be used is $T_{R}=\\{x\in
T:\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}\geq R\\}$ for a well-chosen $R$.

###### Theorem 3.1

There exist a constant $c_{0}$ depending only on $L$, and constants
$c_{1},\kappa_{1}$ depending only on $\kappa_{0}$ and $L$ for which the
following holds. For every $R>0$ and $N\geq c_{0}E_{R}^{2}/\kappa_{0}^{2}$,
with probability at least

$1-4\exp(-c_{1}L^{2}\min\\{\ell^{2}(T_{+,R}),\ell^{2}(T_{-,R})\\}),$

for every $x\in T_{R}$,

$\frac{1}{N}\sum_{i=1}^{N}\bigl{<}x_{0}-x,a_{i}\bigr{>}^{2}\bigl{<}x_{0}+x,a_{i}\bigr{>}^{2}\geq
c_{1}\|x_{0}-x\|_{2}^{2}\|x_{0}+x\|_{2}^{2}.$

Theorem 3.1 is an immediate outcome of Lemma 2.11

###### Theorem 3.2

There exist absolute constants $c_{1}$ and $c_{2}$ for which the following
holds. For every $\beta>1$, with probability at least

$1-2\exp(-c_{1}L^{2}\min\\{\ell^{2}(T_{+,R}),\ell^{2}(T_{-,R})\\})-2N^{-(\beta-1)},$

for every $x\in T_{R}$,

$\left|\frac{1}{N}\sum_{i=1}^{N}w_{i}\bigl{<}x-x_{0},a_{i}\bigr{>}\bigl{<}x+x_{0},a_{i}\bigr{>}\right|\leq
c_{2}\sqrt{\beta}\|w\|_{\psi_{2}}\sqrt{\log{N}}\cdot\frac{E_{R}}{\sqrt{N}}\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}.$

Proof. By standard properties of empirical process, and since $w$ is mean-zero
and independent of $a$, it suffices to estimate

$\sup_{x\in
T_{R}}\left|\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}|w_{i}|\bigl{<}x-x_{0},a_{i}\bigr{>}\bigl{<}x+x_{0},a_{i}\bigr{>}\right|,$

for independent signs $(\varepsilon_{i})_{i=1}^{N}$. By the contraction
principle for Bernoulli processes (see, e.g., [9]), it follows that for every
fixed $(w_{i})_{i=1}^{N}$ and $(a_{i})_{i=1}^{N}$,

$\displaystyle Pr_{\varepsilon}\left(\sup_{x\in
T_{R}}\left|\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}|w_{i}|\bigl{<}\frac{x-x_{0}}{\|x-x_{0}\|_{2}},a_{i}\bigr{>}\bigl{<}\frac{x+x_{0}}{\|x+x_{0}\|_{2}},a_{i}\bigr{>}\right|>u\right)$
$\displaystyle\leq$ $\displaystyle 2Pr_{\varepsilon}\left(\max_{i\leq
N}|w_{i}|\cdot\sup_{x\in
T_{R}}\left|\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}\bigl{<}\frac{x-x_{0}}{\|x-x_{0}\|_{2}},a_{i}\bigr{>}\bigl{<}\frac{x+x_{0}}{\|x+x_{0}\|_{2}},a_{i}\bigr{>}\right|>\frac{u}{2}\right).$

Applying Remark 2.7, if $N\gtrsim_{L}E_{R}$ then with $(\varepsilon\otimes
a)^{N}$-probability of at least
$1-2\exp(-c_{1}L^{2}\min\\{\ell^{2}(T_{+,R}),\ell^{2}(T_{-,R})\\})$,

$\sup_{x\in
T_{R}}\left|\frac{1}{N}\sum_{i=1}^{N}\varepsilon_{i}\bigl{<}\frac{x-x_{0}}{\|x-x_{0}\|_{2}},a_{i}\bigr{>}\bigl{<}\frac{x+x_{0}}{\|x+x_{0}\|_{2}},a_{i}\bigr{>}\right|\leq
c_{2}L^{2}\frac{E_{R}}{\sqrt{N}}.$

Also, because $w$ is a $\psi_{2}$ random variable,

$Pr(w_{1}^{*}\geq t\|w\|_{\psi_{2}})\leq 2N\exp(-t^{2}/2),$

and thus, $w_{1}^{*}\leq\sqrt{2\beta\log N}\|w\|_{\psi_{2}}$ with probability
at least $1-2N^{-\beta+1}$.

Combining the two estimates and a Fubini argument, it follows that with
probability at least
$1-2\exp(-c_{1}L^{2}\min\\{\ell^{2}(T_{+,R}),\ell^{2}(T_{-,R})\\})-2N^{-\beta+1}$,
for every $x\in T_{R}$,

$\left|\frac{1}{N}\sum_{i=1}^{N}w_{i}\bigl{<}x-x_{0},a_{i}\bigr{>}\bigl{<}x+x_{0},a\bigr{>}\right|\leq
c_{3}L^{2}\sqrt{\beta}\|w\|_{\psi_{2}}\sqrt{\log{N}}\frac{E_{R}}{\sqrt{N}}\cdot\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}.$

On the intersection of the two events appearing in Theorem 3.1 and Theorem
3.2, if $N\gtrsim_{\kappa_{0},L}E_{R}^{2}$ and setting

$\rho=\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}\geq R\geq
r_{2}(c_{1}\kappa_{0}/(c_{2}L^{2}\sqrt{\beta})),$

then for every $x\in T_{R}$,

$\displaystyle P_{N}{\cal L}_{x}\geq$
$\displaystyle\left(c_{1}\kappa_{0}^{2}\rho-
c_{2}L^{2}\sqrt{\beta}\|w\|_{\psi_{2}}\sqrt{\log{N}}\frac{E_{R}}{\sqrt{N}}\right)\rho$
$\displaystyle\geq$
$\displaystyle\left(c_{1}\kappa_{0}^{2}R-c_{2}L^{2}\sqrt{\beta}\|w\|_{\psi_{2}}\sqrt{\log{N}}\frac{E_{R}}{\sqrt{N}}\right)R.$

Therefore, if $N\gtrsim_{L,\kappa_{0}}E_{R}^{2}$ and

$E_{R}\leq
c_{3}(L,\kappa_{0})\frac{R}{\|w\|_{\psi_{2}}}\sqrt{\frac{N}{\beta\log N}},$
(3.1)

then $P_{N}{\cal L}_{x}>0$ and $\hat{x}\not\in T_{R}$. Theorem A follows from
the definition of $r_{2}(\gamma)$ for a well chosen $\gamma$.

##  4 Proof of Theorem B

Most of the work required for the proof of Theorem B has been carried out in
Section 3. A literally identical argument, in which one replaces the sets
$T_{+,R}$ and $T_{-,R}$ with $T_{+,R}(x_{0})$ and $T_{-,R}(x_{0})$ may be
used, leading to an analogous version of Theorem A, with the obvious
modifications: the complexity parameter is
$\max\\{\ell(T_{+,R}(x_{0})),\ell(T_{-,R}(x_{0}))\\}$ for the right choice of
$R$, and the probability estimate is
$1-2\exp(-c_{0}\min\\{\ell^{2}(T_{+,R}(x_{0})),\ell^{2}(T_{-,R}(x_{0}))\\})-N^{-\beta+1}$.

All that remains to complete the proof of Theorem B is to analyze the
structure of the local sets and identify the fixed points $r_{0}$ and $r_{2}$.
A first step in that direction is the following:

###### Lemma 4.1

There exist absolute constants $c_{1}$ and $c_{2}$ for which the following
holds. For every $R>0$ and $\|x_{0}\|_{2}\geq\sqrt{R}/4$,

1\. If $\|x_{0}\|_{2}\min\\{\|x-x_{0}\|_{2},\|x+x_{0}\|_{2}\\}\geq R$ then
$\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}\geq c_{1}R$.

2\. If $\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}\geq R$ then
$\|x_{0}\|_{2}\min\\{\|x-x_{0}\|_{2},\|x+x_{0}\|_{2}\\}\geq c_{2}R$.

Moreover, if $\|x_{0}\|_{2}\leq\sqrt{R}/4$ then
$\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}\geq R$ if and only if
$\|x\|_{2}\gtrsim\sqrt{R}$.

Proof. Assume without loss of generality that
$\|x-x_{0}\|_{2}\leq\|x+x_{0}\|_{2}$.

If $\|x-x_{0}\|_{2}\leq\|x_{0}\|_{2}$ then

$\|x_{0}\|_{2}\leq
2\|x_{0}\|_{2}-\|x-x_{0}\|_{2}\leq\|x+x_{0}\|_{2}\leq\|x-x_{0}\|_{2}+2\|x_{0}\|_{2}\leq
3\|x_{0}\|_{2}.$

Hence, $\|x_{0}\|_{2}\sim\|x+x_{0}\|_{2}$, and

$\|x_{0}\|_{2}\min\\{\|x-x_{0}\|_{2},\|x+x_{0}\|_{2}\\}\sim\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}.$

Otherwise, $\|x-x_{0}\|_{2}>\|x_{0}\|_{2}$.

If, in addition,

$\|x_{0}\|_{2}\geq(\|x-x_{0}\|_{2}\|x+x_{0}\|_{2})^{1/2}/4,$

then

$4\|x_{0}\|_{2}\geq(\|x-x_{0}\|_{2}\|x+x_{0}\|_{2})^{1/2}\geq\|x_{0}\|_{2}^{1/2}\|x+x_{0}\|_{2}^{1/2},$

and thus $\|x+x_{0}\|_{2}\leq 16\|x_{0}\|_{2}$. Since
$\|x_{0}\|_{2}<\|x-x_{0}\|_{2}\leq\|x+x_{0}\|_{2}$, it follows that
$\|x+x_{0}\|_{2}\sim\|x-x_{0}\|_{2}\sim\|x_{0}\|_{2}$, and again,

$\|x_{0}\|_{2}\min\\{\|x-x_{0}\|_{2},\|x+x_{0}\|_{2}\\}\sim\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}.$

Therefore, the final case, and the only one in which there is no point-wise
equivalence between $\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}$ and
$\|x_{0}\|_{2}\min\\{\|x-x_{0}\|_{2},\|x+x_{0}\|_{2}\\}$, is when
$\min\\{\|x-x_{0}\|_{2},\|x+x_{0}\|_{2}\\}\geq\|x_{0}\|_{2}$ and
$\|x_{0}\|_{2}\leq(\|x-x_{0}\|_{2}\|x+x_{0}\|_{2})^{1/2}/4$. In that case, if
$\|x_{0}\|_{2}\geq\sqrt{R}/4$ then

$\|x_{0}\|_{2}\min\\{\|x-x_{0}\|_{2},\|x+x_{0}\|_{2}\\}\geq\|x_{0}\|_{2}^{2}\geq
R/16,$

and

$\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}\geq 4\|x_{0}\|_{2}^{2}\geq R/4,$

from which the first part of the claim follows immediately.

For the second one, observe that

$\|x\|_{2}^{2}-2\|x_{0}\|_{2}\|x\|_{2}\leq\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}\leq\|x\|_{2}^{2}+2\|x\|_{2}\|x_{0}\|_{2}+\|x_{0}\|_{2}^{2},$

and if $\|x_{0}\|_{2}\leq\sqrt{R}/4$, the equivalence is evident.

In view of Lemma 4.1, the way the product $\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}$
relates to $\min\\{\|x-x_{0}\|_{2},\|x+x_{0}\|_{2}\\}$ depends on
$\|x_{0}\|_{2}$. If $\|x_{0}\|_{2}\geq\sqrt{R}/4$, then

$\\{x\in T:\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}\leq R\\}\subset\\{x\in
T:\min\\{\|x-x_{0}\|_{2},\|x+x_{0}\|_{2}\\}\leq c_{1}R/\|x_{0}\|_{2}\\},$

and if $\|x_{0}\|_{2}\leq\sqrt{R}/4$,

$\\{x\in T:\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}\leq R\\}\subset\\{x\in
T:\|x\|_{2}\leq c_{1}\sqrt{R}\\},$

for a suitable absolute constant $c_{1}$.

When $T$ is convex and centrally-symmetric, the corresponding complexity
parameter - the gaussian average of $T_{+,R}(x_{0})=T_{-,R}(x_{0})$ is

$E_{R}(x_{0})\lesssim\begin{cases}\frac{\|x_{0}\|_{2}}{R}\cdot\ell(2T\cap(c_{1}R/\|x_{0}\|_{2})B_{2}^{n})&\mbox{if}\
\ \|x_{0}\|_{2}\geq\sqrt{R},\\\ \\\ \frac{1}{\sqrt{R}}\ell(2T\cap
c_{1}\sqrt{R}B_{2}^{n})&\mbox{if}\ \ \|x_{0}\|<\sqrt{R}.\end{cases}$

The fixed point conditions appearing in Theorem A now become

$r_{0}=\inf\\{R:E_{R}(x_{0})\leq c_{2}\sqrt{N}\\}$ (4.1)

and

$r_{2}(\gamma)=\inf\\{R:E_{R}(x_{0})\leq\gamma\sqrt{N}R\\},$ (4.2)

where one selects the slightly suboptimal $\gamma=c_{2}/\sigma\sqrt{\log N}$.
The assertion of Theorem A is that with high probability, ERM produces
$\hat{x}$ for which

$\|\hat{x}-x_{0}\|_{2}\|\hat{x}+x_{0}\|_{2}\leq\max\\{r_{2}(\gamma),r_{0}\\}.$

If $\|x_{0}\|_{2}\geq\sqrt{R}$, the fixed-point condition (4.1) is

$\ell(2T\cap(c_{1}R/\|x_{0}\|_{2})B_{2}^{n})\leq
c_{3}\left(\frac{R}{\|x_{0}\|_{2}}\right)\sqrt{N}$ (4.3)

while (4.2) is,

$\frac{\|x_{0}\|_{2}}{R}\ell(2T\cap(c_{1}R/\|x_{0}\|_{2})B_{2}^{n})\leq(c_{4}/\sigma\sqrt{\log
N})\cdot\sqrt{N}R.$ (4.4)

Recall that

$r_{N}^{*}(Q)=\inf\\{r>0:\ell(T\cap rB_{2}^{n})\leq Qr\sqrt{N}\\},$

and

$s_{N}^{*}(\eta)=\inf\\{s>0:\ell(T\cap sB_{2}^{n})\leq\eta s^{2}\sqrt{N}\\}.$

Therefore, it is straightforward to verify that

$r_{0}=2\|x_{0}\|_{2}r_{N}^{*}(c_{3})\ \ {\rm and}\ \
r_{2}\big{(}c_{2}/(\sigma\sqrt{\log
N})\big{)}=2\|x_{0}\|_{2}s_{N}^{*}(c_{4}\|x_{0}\|_{2}/\sigma\sqrt{\log{N}}).$

Setting
$R=2\|x_{0}\|_{2}\max\\{r_{N}^{*}(c_{3}),s_{N}^{*}(c_{4}\|x_{0}\|_{2}/\sigma\sqrt{\log{N}})\\}$,
it remains to ensure that $\|x_{0}\|_{2}^{2}\geq R$; that is,

$2\max\\{s_{N}^{*}(c_{4}\|x_{0}\|_{2}/\sigma\sqrt{\log
N}),r_{N}^{*}(c_{3})\\}\leq\|x_{0}\|_{2}.$ (4.5)

Observe that if

$r_{N}^{*}(c_{3})\leq\frac{c_{3}\sigma}{c_{4}\|x_{0}\|_{2}}\sqrt{\log N},$
(4.6)

then $r_{N}^{*}(c_{3})\leq s_{N}^{*}(c_{4}\|x_{0}\|_{2}/\sigma\sqrt{\log N})$.
Indeed, applying the convexity of $T$, it is standard to verify that
$r_{N}^{*}(Q)$ is attained and $r_{N}^{*}(Q)\leq\rho$ if and only if
$\ell(T\cap\rho B_{2}^{n})\leq Q\rho\sqrt{N}$ – with a similar statement for
$s_{N}^{*}$ (see, e.g., the discussion in [7]). Therefore,
$s_{N}^{*}(\eta)\geq r_{N}^{*}(Q)$ if and only if $\ell(T\cap
r_{N}^{*}(Q))\geq\eta(r_{N}^{*}(Q))^{2}\sqrt{N}$. The latter is evident
because $\ell(T\cap r_{N}^{*}(Q))=Qr_{N}^{*}(Q)\sqrt{N}$ and recalling that
$Q=c_{3}$ and $\eta=c_{4}\|x_{0}\|_{2}/\sigma\sqrt{\log N}$.

Under (4.6), an assumption which has been made in the formulation of Theorem
B, (4.5) becomes $2s_{N}^{*}(c_{4}\|x_{0}\|_{2}/\sigma\sqrt{\log
N})\leq\|x_{0}\|_{2}$ and, by the definition of $s_{N}^{*}$, this is the case
if and only if

$\ell(T\cap\|x_{0}\|_{2}B_{2}^{n})\leq\frac{c_{4}\|x_{0}\|_{2}}{\sigma\sqrt{\log
N}}\cdot\|x_{0}\|_{2}^{2}\sqrt{N};$

that is simply when $\|x_{0}\|_{2}\geq v_{N}^{*}(\zeta)$ for
$\zeta=c_{4}/\sigma\sqrt{\log N}$.

Hence, by Theorem A, combined with Lemma 4.1, it follows that with high
probability,

$\min\\{\|\hat{x}-x_{0}\|_{2},\|\hat{x}+x_{0}\|_{2}\\}\leq
2s_{N}^{*}(c_{4}\|x_{0}\|_{2}/\sigma\sqrt{\log N}).$

The other cases, when either $\|x_{0}\|_{2}$ is ‘small’, or when $r_{0}$
dominates $r_{2}$ are treated is a similar fashion, and are omitted.

##  5 Minimax lower bounds

In this section we study the optimality of ERM as a phase retrieval procedure,
in the minimax sense. The estimate obtained here is based on the maximal
cardinality of separated subsets of the class with respect to the $L_{2}(\mu)$
norm.

###### Definition 5.1

Let $B$ be the unit ball in a normed space. For any subset $A$ of the space,
let $M(A,rB)$ be the maximal cardinality of a subset of $A$ that is
$r$-separated with respect to the norm associated with $B$.

Observe that if $M(A,rB)\geq L$ there are $x_{1},...,x_{L}\in A$ for which the
sets $x_{i}+(r/3)B$ are disjoint. A similar statement is true in the reverse
direction. Let $F$ be a class of functions on $(\Omega,\mu)$ and let $a$ be
distributed according to $\mu$. For $f_{0}\in F$ and a centred gaussian
variable $w$, which has variance $\sigma$ and is independent of $a$, consider
the gaussian regression model

$y=f_{0}(a)+w.$ (5.1)

Any procedure that performs well in the minimax sense, must do so for any
choice of $f_{0}\in F$ in (5.1).

Following [7], there are two possible sources of ‘statistical complexity’ that
influence the error rate of gaussian regression in $F$.

1\. Firstly, that there are functions in $F$ that, despite being far away from
$f_{0}$, still satisfy $f_{0}(a_{i})=f(a_{i})$ for every $1\leq i\leq N$, and
thus are indistinguishable from $f_{0}$ on the data.

This statistical complexity is independent of the noise, and for every
$f_{0}\in F$ and ${\mathbb{A}}=(a_{i})_{i=1}^{N}$, it is captured by the
$L_{2}(\mu)$ diameter of the set

$K(f_{0},{\mathbb{A}})=\\{f\in
F:(f(a_{i}))_{i=1}^{N}=(f_{0}(a_{i}))_{i=1}^{N}\\},$

which is denoted by $d_{N}^{*}({\mathbb{A}})$.

2\. Secondly, that the set $(F-f_{0})\cap rD=\\{f-f_{0}:f\in
F,\|f-f_{0}\|_{L_{2}}\leq r\\}$ is ‘rich enough’ at a scale that is
proportional to its $L_{2}(\mu)$ diameter $r$.

The richness of the set is measured using the cardinality of a maximal
$L_{2}(\mu)$-separated set. To that end, let $D$ be the unit ball in
$L_{2}(\mu)$, set

$C(r,\theta_{0})=\sup_{f_{0}\in F}r\log^{1/2}M(F\cap(f_{0}+\theta_{0}rD),rD)$

and put

$q^{*}_{N}(\eta)=\inf\big{\\{}r>0:C(r,\theta_{0})\leq\eta
r^{2}\sqrt{N}\big{\\}}.$ (5.2)

###### Theorem 5.2

[7] For every $f_{0}\in F$ let $\mathbb{P}_{f_{0}}^{\otimes N}$ be the
probability measure that generates samples $(a_{i},y_{i})_{i=1}^{N}$ according
to (5.1). For every $\theta_{0}\geq 2$ there exists a constant $\theta_{1}>0$
for which

$\inf_{\hat{f}}\sup_{f_{0}\in F}\mathbb{P}_{f_{0}}^{\otimes
N}\Big{(}\left\|f_{0}-\hat{f}\right\|_{2}\geq\max\\{q_{N}^{*}(\theta_{1}/\sigma),(d_{N}^{*}({\mathbb{A}})/4)\\}\Big{)}\geq
1/5$ (5.3)

where $\inf_{\hat{f}}$ is the infimum over all possible estimators constructed
using the given data.

Earlier versions of this minimax bound may be found in [14], [16] and [1].

To apply this general principle to the phase recovery problem, note that the
regression function is $f_{0}(x)=\bigl{<}x_{0},x\bigr{>}^{2}:=f_{x_{0}}(x)$
for some unknown vector $x_{0}\in T\subset\mathbb{R}^{n}$, while the
estimators are $\hat{f}=\bigl{<}\hat{x},\cdot\bigr{>}^{2}$. Also, observe that
for every $x_{1},x_{2}\in T$,

$\left\|f_{x_{0}}-f_{x_{1}}\right\|_{L^{2}(\mu)}^{2}=\mathbb{E}\big{(}\bigl{<}x_{0},a\bigr{>}^{2}-\bigl{<}x_{1},a\bigr{>}^{2}\big{)}^{2}=\mathbb{E}\bigl{<}x_{0}-x_{1},a\bigr{>}^{2}\bigl{<}x_{0}+x_{1},a\bigr{>}^{2}$

and therefore, one has to identify the $L_{2}$ structure of the set

$F-f_{x_{0}}=\\{\bigl{<}x,\cdot\bigr{>}^{2}-\bigl{<}x_{0},\cdot\bigr{>}^{2}:x\in
T\\}.$

To obtain the desired bound, it suffices to assume the following:

###### Assumption 5.1

There exist constants $C_{1}$ and $C_{2}$ for which, for every
$s,t\in\mathbb{R}^{n}$,

$C_{1}^{2}\|s-t\|_{2}^{2}\|s+t\|_{2}^{2}\leq\mathbb{E}\bigl{<}s-t,a\bigr{>}^{2}\bigl{<}s+t,a\bigr{>}^{2}\leq
C_{2}^{2}\|s-t\|_{2}^{2}\|s+t\|_{2}^{2}.$

It is straightforward to verify that if $a$ is an $L$-subgaussian vector on
$\mathbb{R}^{n}$ that satisfies Assumption 1.1, then it automatically
satisfies Assumption 5.1.

The norm $\left\|x_{0}\right\|_{2}$ plays a central role in the analysis of
the rates of convergence of the ERM in phase recovery. Therefore, the minimax
lower bounds presented here are not only for the entire model $T$ but for
every shell $V_{0}=T\cap R_{0}S^{n-1}$. A minimax lower bound over $T$ follows
by taking the supremum over all possible choices of $R_{0}$.

To apply Theorem 5.2, observe that by Assumption 5.1, for every $u,v\in T$,

$C_{1}\|u-v\|_{2}\|u+v\|_{2}\leq\|f_{v}-f_{u}\|_{L_{2}}\leq
C_{2}\|u-v\|_{2}\|u+v\|_{2}.$

Fix $R_{0}>0$ and consider $V_{0}=T\cap R_{0}S^{n-1}$. Clearly, for every
$r>0$ and every $x_{0}\in V_{0}$,

$\Big{\\{}u\in
V_{0}:\|u-x_{0}\|_{2}\|u+x_{0}\|_{2}\leq\frac{\theta_{0}r}{C_{2}}\Big{\\}}\subset\\{u\in
V_{0}:f_{u}\in F^{\prime}\cap(f_{x_{0}}+\theta_{0}rD)\\}$ (5.4)

where $F^{\prime}=\\{f_{u}:u\in V_{0}\\}$.

Fix $\theta_{0}>2$ to be named later, and let $\theta_{1}$ be as in Theorem
5.2. If there are $x_{0}\in V_{0}$ and $\\{x_{1},...,x_{M}\\}\subset V_{0}$
that satisfy

1\. $\|x_{i}-x_{0}\|_{2}\|x_{i}+x_{0}\|_{2}\leq\theta_{0}r/C_{2}$,

2\. for every $1\leq i<j\leq M$, $\|x_{i}-x_{j}\|_{2}\|x_{i}+x_{j}\|_{2}\geq
r/C_{1}$, and

3\. $\log M>N(\theta_{1}r/\sigma)^{2}$,

then $\sup_{f_{0}\in
F^{\prime}}r\log^{1/2}M(F^{\prime}\cap(f_{0}+\theta_{0}rD),rD)>\theta_{1}r\sqrt{N}/\sigma$,
and the best possible rate in phase recovery in $V_{0}$ is larger than $r$.

Fix $x_{0}\in V_{0}$ and $r>0$, and let $R=r/C_{2}$. We will present two
different estimates, based on $R_{0}=\left\|x_{0}\right\|_{2}$, the ‘location’
of $x_{0}$.

Centre of ‘small norm’. Recall that $\theta_{0}>2$ and assume first that
$R_{0}=\|x_{0}\|_{2}\leq\sqrt{\theta_{0}R}/4$. Note that

$V_{0}\cap(\sqrt{R}/8)B_{2}^{n}\subset\Big{\\{}u\in
V_{0}:\|u-x_{0}\|_{2}\|u+x_{0}\|_{2}\leq\frac{\theta_{0}r}{C_{2}}\Big{\\}},$

and thus it suffices to constructed a separated set in
$V_{0}\cap(\sqrt{R}/8)B_{2}^{n}$.

Set $x_{1},...,x_{L}$ to be a maximal $c_{3}\sqrt{R}$-separated subset of
$V_{0}\cap(\sqrt{R}/8)B_{2}^{n}$ for a constant $c_{3}$ that depends only on
$C_{1}$ and $C_{2}$ and which will be specified later; thus,
$L=M(V_{0}\cap(\sqrt{R}/8)B_{2}^{n},c_{3}\sqrt{R}B_{2}^{n})$.

###### Lemma 5.3

There is a subset $I\subset\\{1,...,L\\}$ of cardinality $M\geq L/2-1$ for
which $(x_{i})_{i\in I}$ satisfies 1. and 2..

Proof. Since $x_{i}\in(\sqrt{R}/8)B_{2}^{n}$ and
$\|x_{0}\|_{2}\leq\sqrt{\theta_{0}R}/4$,

$\|x_{i}-x_{0}\|_{2}\|x_{i}+x_{0}\|_{2}\leq((\sqrt{\theta_{0}}+1)\sqrt{R}/4)^{2}\leq\theta_{0}R=\theta_{0}r/C_{2},$

and thus 1. is satisfied for every $1\leq i\leq L$.

To show that 2. holds for a large subset, it suffices to find
$I\subset\\{1,...,L\\}$ of cardinality at least $L/2-1$ such that for every
$i,j\in I$,

$\|x_{i}-x_{j}\|_{2}\geq c_{3}\sqrt{R}/2\ \ {\rm and}\ \
\|x_{i}+x_{j}\|_{2}\geq c_{3}\sqrt{R}/2$

for a well-chosen $c_{3}$.

To construct the subset, observe that if there are distinct integers $1\leq
i,j,k\leq L$ for which $\|x_{i}+x_{j}\|_{2}<c_{3}\sqrt{R}/2$ and
$\|x_{i}+x_{k}\|_{2}<c_{3}\sqrt{R}/2$, then
$\|x_{j}-x_{k}\|_{2}<c_{3}\sqrt{R}$, which is impossible. Therefore, for every
$x_{i}$ there is at most a single index $j\in\\{1,...,L\\}\backslash\\{i\\}$
satisfying that $\|x_{i}+x_{j}\|_{2}<c_{3}\sqrt{R}/2$. With this observation
the set $I$ is constructed inductively.

Without loss of generality, assume that $I=\\{1,...,M\\}$ for $M\geq L/2-1$.
If $i\not=j$ and $1\leq i,j\leq M$,

$\|x_{i}-x_{j}\|_{2}\|x_{i}+x_{j}\|_{2}\geq c_{3}^{2}R/4\geq 2r/C_{1},$

for the right choice of $c_{3}$, and thus $(x_{i})_{i=1}^{M}$ satisfies 2..

Centre of ‘large norm’. Next, assume that
$R_{0}=\|x_{0}\|_{2}\geq\sqrt{\theta_{0}R}/4$. By Lemma 4.1, there is an
absolute constant $c_{4}<1/32$, for which, if $\|x_{0}\|_{2}\geq\sqrt{\rho}/4$
and $\|x_{0}\|_{2}\min\\{\|x-x_{0}\|_{2},\|x+x_{0}\|_{2}\\}\leq c_{4}\rho$,
then $\|x-x_{0}\|_{2}\|x+x_{0}\|_{2}\leq\rho$. Therefore, applied to the
choice $\rho=\theta_{0}R$,

$\displaystyle\left(V_{0}\cap(x_{0}+(c_{4}\theta_{0}R/\|x_{0}\|_{2})B_{2}^{n})\right)\cup\left(V_{0}\cap(-x_{0}+(c_{4}\theta_{0}R/\|x_{0}\|_{2})B_{2}^{n})\right)$
$\displaystyle\subset$ $\displaystyle\left\\{u\in
V_{0}:\|x_{0}-u\|_{2}\|x_{0}+u\|_{2}\leq\theta_{0}R\right\\},$

and it suffices to a find a separated set in the former.

Note that if $x\in V_{0}\cap(x_{0}+(c_{4}\theta_{0}R/\|x_{0}\|_{2})B_{2}^{n})$
then

$\|x\|_{2}\geq\|x_{0}\|_{2}-c_{4}\theta_{0}R/\|x_{0}\|_{2}\geq\|x_{0}\|_{2}/2\geq\sqrt{\theta_{0}R/4}/4$

because one can choose $c_{4}\leq 1/32$, and $\|x\|_{2}\leq 3\|x_{0}\|_{2}/2.$
Moreover, if $x_{1},x_{2}\in
V_{0}\cap(x_{0}+(c_{4}\theta_{0}R/\|x_{0}\|_{2})B_{2}^{n})$, then

$\|x_{1}+x_{2}\|_{2}\geq
2\|x_{0}\|_{2}-2c_{4}\theta_{0}R/\|x_{0}\|_{2}\geq\|x_{0}\|_{2}.$

Applying Lemma 4.1, there is an absolute constant $c_{5}$, for which, if

$\|x_{0}\|_{2}\min\left\\{\|x_{i}-x_{j}\|_{2},\|x_{i}+x_{j}\|_{2}\right\\}\geq\theta_{0}R/4,$
(5.5)

then

$\|x_{i}-x_{j}\|_{2}\|x_{i}+x_{j}\|_{2}\geq c_{5}\theta_{0}R/4.$

Hence, if $x_{1},...,x_{M}\in
V_{0}\cap(x_{0}+(c_{4}\theta_{0}R/\|x_{0}\|_{2})B_{2}^{n})$ is
$\theta_{0}R/4\|x_{0}\|_{2}$-separated, then (5.5) holds, and

$\|x_{i}-x_{j}\|_{2}\|x_{i}+x_{j}\|_{2}\geq c_{5}\theta_{0}R/4\geq r/C_{1},$

provided that $\theta_{0}$ is a sufficiently large constant that depends only
on $C_{1}$ and $C_{2}$.

###### Corollary 5.4

There exist absolute constants $\theta_{1}$, $c_{1},c_{2}$ and $c_{3}$ that
depend only on $C_{1}$ and $C_{2}$ and for which the following holds. Let
$R_{0}>0$ and set $V_{0}=T\cap R_{0}S^{n-1}$. Define

$q^{\prime}(r)=\left\\{\begin{array}[]{cc}\log M(V_{0}\cap
c_{1}\sqrt{r}B_{2}^{n},c_{2}\sqrt{r}B_{2}^{n})&\mbox{if}\ \ R_{0}\leq
c_{3}\sqrt{r},\\\ &\\\ \sup_{x_{0}\in V_{0}}\log
M\left(V_{0}\cap\left(x_{0}+c_{1}\left(\frac{r}{R_{0}}\right)B_{2}^{n}\right),c_{2}\frac{r}{R_{0}}B_{2}^{n}\right)&\mbox{if}\
\ R_{0}>c_{3}\sqrt{r}\end{array}\right.$

If $q^{\prime}(r)\geq\theta_{1}(r/\sigma)^{2}N$, then the minimax rate in
$V_{0}$ is larger than $r$.

Now, a minimax lower bound for the risk
$\min\\{\left\|\tilde{x}-x_{0}\right\|_{2},\left\|\tilde{x}+x_{0}\right\|_{2}\\}$
for all shells $V_{0}$ (and therefore, for $T$) may be derived using Lemma
4.1. To that end, let $c_{0}$ be a large enough absolute constant and

$C(R_{0},r)=\sup_{x_{0}\in
T:\left\|x_{0}\right\|_{2}=R_{0}}r\log^{1/2}M\big{(}(T\cap
R_{0}S^{n-1})\cap(x_{0}+c_{0}rB_{2}^{n}),rB_{2}^{n}).$ (5.6)

###### Definition 5.5

Fix $R_{0}>0$. For every $\alpha,\beta>0$ set

$q_{N}^{*}(\alpha)=\inf\big{\\{}r>0:C(R_{0},r)\leq\alpha
r^{2}\sqrt{N}\big{\\}}$

and put

$t_{N}^{*}(\beta)=\inf\big{\\{}r>0:C(R_{0},r)\leq\beta
r^{3}\sqrt{N}\big{\\}}.$

Note that for any $c>0$, if $t_{N}^{*}(c)\leq 1$ then $t_{N}^{*}(c)\geq
q_{N}^{*}(c)$ and $q_{N}^{*}\big{(}cR_{0}/\sigma\big{)}\geq
t_{N}^{*}(c/\sigma)$ if and only if $q_{N}^{*}\big{(}cR_{0}/\sigma\big{)}\geq
R_{0}$.

Theorem C. There exists an absolute constant $c_{1}$ for which the following
holds. Let $R_{0}>0$.

  1. 1.

If $R_{0}\geq t_{N}^{*}\big{(}c_{1}/\sigma\big{)}$, then for any procedure
$\tilde{x}$, there exists $x_{0}\in T$ with $\left\|x_{0}\right\|_{2}=R_{0}$
and for which, with probability at least $1/5$,

$\left\|\tilde{x}-x_{0}\right\|_{2}\left\|\tilde{x}+x_{0}\right\|_{2}\geq\left\|x_{0}\right\|_{2}q_{N}^{*}\Big{(}\frac{c_{1}\left\|x_{0}\right\|_{2}}{\sigma}\Big{)}$

and

$\min\\{\left\|\tilde{x}-x_{0}\right\|_{2},\left\|\tilde{x}+x_{0}\right\|_{2}\\}\geq
q_{N}^{*}\Big{(}\frac{c_{1}\left\|x_{0}\right\|_{2}}{\sigma}\Big{)}.$

  2. 2.

If $R_{0}\leq t_{N}^{*}\big{(}c_{1}/\sigma\big{)}$ then for any procedure
$\tilde{x}$ there exists $x_{0}\in T$ with $\left\|x_{0}\right\|_{2}=R_{0}$
for which, with probability at least $1/5$,

$\left\|\tilde{x}-x_{0}\right\|_{2}\left\|\tilde{x}+x_{0}\right\|_{2}\geq\Big{(}t_{N}^{*}\Big{(}\frac{c_{1}}{\sigma}\Big{)}\Big{)}^{2}$

and

$\left\|\tilde{x}\right\|_{2},\left\|\tilde{x}-x_{0}\right\|_{2},\left\|\tilde{x}+x_{0}\right\|_{2}\geq
t_{N}^{*}\Big{(}\frac{c_{1}}{\sigma}\Big{)}.$

Theorem C is a general minimax bound, and although it seems strange at first
glance, the parameters appearing in it are very close to those used in Theorem
C. Following the same path as in [7], let us show that Theorem C and Theorem C
are almost sharp, under some mild structural assumptions on $T$.

First, recall Sudakov’s inequality (see, e.g., [9]):

###### Theorem 5.6

If $W\subset\mathbb{R}^{n}$ and $\varepsilon>0$ then

$c\varepsilon\log^{1/2}M(W,\varepsilon B_{2}^{n})\leq\ell(W),$

where $c$ is an absolute constant.

Fix $R_{0}>0$ set $V_{0}=T\cap R_{0}B_{2}^{n}$, and put

$s_{N}^{*}=s_{N}^{*}\big{(}c_{1}R_{0}/(\sigma\sqrt{\log N})\big{)}\ \ {\rm
and}\ \ v_{N}^{*}=v_{N}^{*}\big{(}c_{1}R_{0}/(\sigma\sqrt{\log N})\big{)}.$

Assume that there is some $x_{0}\in T$, with the following properties:

1\. $\left\|x_{0}\right\|_{2}=R$.

2\. The localized sets $V_{0}\cap(x_{0}+s_{N}^{*}B_{2}^{n})$ and
$V_{0}\cap(x_{0}+v_{N}^{*}B_{2}^{n})$ satisfy that

$\ell(V_{0}\cap(x_{0}+s_{N}^{*}S^{n-1}))\sim\ell(T\cap s_{N}^{*}B_{2}^{n})$

and that

$\ell(V_{0}\cap(x_{0}+v_{N}^{*}S^{n-1}))\sim\ell(T\cap v_{N}^{*}B_{2}^{n}),$

which is a mild assumption on the complexity structure of $T$.

3\. Sudakov’s inequality is sharp at the scales $s_{N}^{*}$ and $v_{N}^{*}$,
namely,

$s_{N}^{*}\log^{1/2}M(V_{0}\cap(x_{0}+c_{0}s_{N}^{*}B_{2}^{n}),s_{N}^{*}B_{2}^{n})\sim\ell(V_{0}\cap(x_{0}+s_{N}^{*}B_{2}^{n}))$
(5.7)

and a similar assertion holds for $v_{N}^{*}$.

In such a case, the rates of convergence obtained in Theorem B are minimax (up
to the an extra $\sqrt{\log N}$ factor) thanks to Theorem C.

When Sudakov’s inequality is sharp as in (5.7), we believe that ERM should be
a minimax procedure in phase recovery, despite the logarithmic gap between
Theorem B an Theorem C. A similar conclusion for linear regression was
obtained in [7].

Sudakov’s inequality is sharp in many cases - most notably, when
$T=B_{1}^{n}$, but not always. It is not sharp even for standard sets like the
unit ball in $\ell_{p}^{n}$ for $1+(\log n)^{-1}<p<2$.

##  6 Examples

Here, we will present two simple applications of the upper and lower bounds on
the performance of ERM in phase recovery. Naturally, there are many other
examples that follow in a similar way and that can be derived using very
similar arguments. The choice of the examples has been made to illustrate the
question of the optimality of Theorem A, B and C, as well as an indication of
the similarities and differences between phase recovery and linear regression.
Since the estimate used in these examples are rather well known, some of the
details will not be presented in full.

###  6.1 Sparse vectors

The first example we consider represents classes with a local complexity that
remains unchanged, regardless of the choice of $x_{0}$.

Let $T=W_{d}$ be the set of $d$-sparse vectors in $\mathbb{R}^{n}$ (for some
$d\leq N/4$) – that is, vectors with at most $d$ non-zero coordinates.
Clearly, for every $R>0$ $T_{+,R},T_{-,R}\subset W_{2d}\cap S^{n-1}$. Also,
for any $x_{0}\in T$ and any $I\subset\\{1,...,n\\}$ of cardinality $d$ that
is disjoint of ${\rm supp}(x_{0})$,

$(1/\sqrt{2})S^{I}\subset\left\\{\frac{(x-x_{0})_{i\in
I}}{\|x-x_{0}\|_{2}}:x\in W_{d}\right\\},\left\\{\frac{(x+x_{0})_{i\in
I}}{\|x+x_{0}\|_{2}}:x\in W_{d}\right\\},$

where $S^{I}$ is the unit sphere supported on the coordinates $I$.

With this observation, a straightforward argument shows that,

$\ell(T_{+,R}),\ell(T_{-,R})\sim\sqrt{d\log(en/d)}.$

Applying Theorem A, if follows that for $N\gtrsim d\log\big{(}en/d\big{)}$,
with probability at least $1-2\exp(-c(d\log(en/d)))-N^{-\beta+1}$, ERM
produces $\hat{x}$ that satisfies

$\|\hat{x}-x_{0}\|_{2}\|\hat{x}+x_{0}\|_{2}\lesssim_{\kappa_{0},L,\beta}\sigma\sqrt{\frac{d\log(en/d)}{N}}\sqrt{\log
N}=(*).$ (6.1)

Moreover, with the same probability estimate, if
$\left\|x_{0}\right\|_{2}^{2}\gtrsim(*)$ then by Lemma 4.1,

$\min\\{\|\hat{x}-x_{0}\|_{2},\|\hat{x}+x_{0}\|_{2}\\}\lesssim_{\kappa_{0},L,\beta}\frac{\sigma}{\left\|x_{0}\right\|_{2}}\sqrt{\frac{d\log(en/d)}{N}}\sqrt{\log
N}$ (6.2)

and if $\left\|x_{0}\right\|_{2}^{2}\lesssim(*)$ then

$\left\|\hat{x}\right\|_{2}^{2},\|\hat{x}-x_{0}\|_{2}^{2},\|\hat{x}+x_{0}\|_{2}^{2}\lesssim_{\kappa_{0},L}\sigma\sqrt{\frac{d\log(en/d)}{N}}\sqrt{\log
N}.$ (6.3)

In particular, when $\left\|x_{0}\right\|_{2}$ is of the order of a constant,
the rate of convergence in (6.1) and (6.2) is identical to the one obtained in
[7] in the linear regression (up to a $\sqrt{\log N}$ term). In the latter,
ERM achieves the minimax rate (with the same probability estimate) of

$\|\hat{x}-x_{0}\|_{2}\lesssim_{L}\sigma\sqrt{\frac{d\log(en/d)}{N}}.$

Otherwise, when $\left\|x_{0}\right\|_{2}$ is large, the rate of convergence
of the ERM in (6.2) is actually better than in linear regression, but, when
$\left\|x_{0}\right\|_{2}$ is small, it is worse - deteriorating to the square
root of the rate in linear regression (up to logarithmic terms).

When the noise level $\sigma$ tends to zero, the rates of convergence in
linear regression and phase recovery tend to zero as well. In particular,
exact reconstruction happens – that is $\hat{x}=x_{0}$ in linear regression
and $\hat{x}=x_{0}$ or $\hat{x}=-x_{0}$ in phase recovery – when $N\gtrsim
d\log\big{(}en/d\big{)}$.

For the lower bound, it is well known that $\log^{1/2}M(W_{d}\cap
c_{0}rB_{2}^{n},rB_{2}^{n})\sim\sqrt{d\log(en/d)}$ for every $r>0$ (and
$c_{0}\geq 2$). Combined with the results of the previous section, this
suffices to show that the rate obtained in Theorem A is the minimax one (up to
a $\sqrt{\log N}$ term in the “large noise” regime) and that the ERM is a
minimax procedure for the phase retrieval problem when the signal $x_{0}$ is
known to be $d$-sparse and $N\gtrsim d\log\big{(}en/d\big{)}$.

###  6.2 The unit ball of $\ell_{1}^{n}$

Consider the set $T=B_{1}^{n}$, the unit ball of $\ell_{1}^{n}$. Being convex
and centrally symmetric, it is a natural example of a set with changing ‘local
complexity’ – which becomes very large when $x_{0}$ is close to $0$. Moreover,
it is an example in which one may obtain sharp estimates on
$\ell(B_{1}^{n}\cap rB_{2}^{n})$ at every scale. Indeed, one may show (see,
for example, [5]) that

$\ell\big{(}B_{1}^{n}\cap
rB_{2}^{n}\big{)}\sim\left\\{\begin{array}[]{cc}\sqrt{\log(enr^{2})}&\mbox{ if
}r^{2}n\geq 1\\\ &\\\ r\sqrt{n}&\mbox{ otherwise.}\end{array}\right.$

It follows that for $B_{1}^{n}$, one has

$r_{N}^{*}(Q)\ \
\left\\{\begin{array}[]{cc}\sim\Big{(}\frac{1}{Q^{2}N}\log\Big{(}\frac{n}{Q^{2}N}\Big{)}\Big{)}^{1/2}&\mbox{
if }n\geq C_{0}Q^{2}N\\\ &\\\ \lesssim\frac{1}{N}&\mbox{ if }C_{1}Q^{2}N\leq
n\leq C_{0}Q^{2}N\\\ &\\\ =0&\mbox{ if }n\leq C_{1}Q^{2}N.\end{array}\right.$

where $C_{0}$ and $C_{1}$ are absolute constants. The only range in which this
estimate is not sharp is when $n\sim Q^{2}N$, because in that range,
$r_{N}^{*}(Q)$ decays to zero very quickly. A more accurate estimate on
$\ell(B_{1}^{n}\cap rB_{2}^{n})$ can be performed when $n\sim Q^{2}N$ (see
[8]), but since it is not our main interest, we will not pursue it further,
and only consider the cases $n\leq C_{1}Q^{2}N$ and $n\geq C_{0}Q^{2}N$.

A straightforward computation shows that the two other fixed points satisfy:

$s_{N}^{*}(\eta)\sim\left\\{\begin{array}[]{cc}\Big{(}\frac{1}{\eta^{2}N}\log\Big{(}\frac{n^{2}}{\eta^{2}N}\Big{)}\Big{)}^{1/4}&\mbox{
if }n\geq\eta\sqrt{N}\\\ \\\ \sqrt{\frac{n}{\eta^{2}N}}&\mbox{ if
}n\leq\eta\sqrt{N}\end{array}\right.$

and

$v_{N}^{*}(\zeta)\sim\left\\{\begin{array}[]{cc}\Big{(}\frac{1}{\zeta^{2}N}\log\Big{(}\frac{n^{3}}{\zeta^{2}N}\Big{)}\Big{)}^{1/6}&\mbox{
if }n\geq\zeta^{2/3}N^{1/3}\\\ \\\
\Big{(}\frac{n}{\zeta^{2}N}\Big{)}^{1/4}&\mbox{ if
}n\leq\zeta^{2/3}N^{1/3}.\end{array}\right.$

The estimates above will be used to derive rates of convergence for the ERM
$\hat{x}$ (for the squared loss) of the form

$\min\\{\left\|\hat{x}-x_{0}\right\|_{2},\left\|\hat{x}+x_{0}\right\|_{2}\\}\leq
rate.$

Upper bounds on the rate of convergence ${\it rate}$ follow from Theorem B,
and hold with high probability as stated in there. For the sake of brevity, we
will not present the probability estimates, but those can be easily derived
from Theorem B.

Thanks to Theorem B, obtaining upper bounds on ${\it rate}$ involves the study
of several different regimes, depending on $\left\|x_{0}\right\|_{2}$, the
noise level $\sigma$ and the way the number of observations $N$ compares with
the dimension $n$. The noise-free case: $\sigma=0$. In this case, rate is
upper bounded by $r_{N}^{*}(Q)$, for $Q$ that is an absolute constant. In
particular, when $n\geq C_{0}Q^{2}N$, the rate is less than

$\big{(}N^{-1}\log\big{(}n/N\big{)}\big{)}^{1/2}.$

At this point, it is natural to wonder whether there is a procedure that
outperforms ERM in the noise-free case. The minimax lower bound
$d_{N}^{*}({\mathbb{A}})$ in Theorem 5.2 may be used to address this question,
as no algorithm can do better than $d_{N}^{*}({\mathbb{A}})/4$, with
probability greater than $1/5$.

In the phase recovery problem and using the notation of section 5, one has

$\displaystyle d_{N}^{*}({\mathbb{A}})$
$\displaystyle=\sup\left\\{\left\|f_{x}-f_{x_{0}}\right\|_{2}:x\in B_{1}^{n},\
f_{x}(a_{i})=f_{x_{0}}(a_{i})\ ,i=1,\ldots,N\right\\}$
$\displaystyle\sim\sup\left\\{\left\|x-x_{0}\right\|_{2}\left\|x+x_{0}\right\|_{2}:\
x\in B_{1}^{n},\ |\bigl{<}a_{i},x\bigr{>}|=|\bigl{<}a_{i},x_{0}\bigr{>}|,\
i=1,\ldots,N\right\\}$
$\displaystyle\gtrsim\inf_{L:\mathbb{R}^{n}\rightarrow\mathbb{R}^{N}}\sup\left\\{\left\|x-x_{0}\right\|_{2}\left\|x+x_{0}\right\|_{2}:\
x\in B_{1}^{n},\ L(x)=L(x_{0})\right\\}$

with an infimum taken over all linear operators
$L:\mathbb{R}^{n}\to\mathbb{R}^{N}$.

By Lemma 4.1, for $x_{0}=(1/2,0,\ldots,0)\in B_{1}^{n}$ (in fact, any vector
$x_{0}$ in $B_{1}^{n}$ for which $\left\|x_{0}\right\|_{2}$ is a positive
constant smaller than $1/2$ would do)

$\displaystyle d_{N}^{*}({\mathbb{A}})$
$\displaystyle\gtrsim\inf_{L:\mathbb{R}^{n}\rightarrow\mathbb{R}^{N}}\sup_{x\in
B_{1}^{n}\cap({\rm
ker}L-x_{0})}\min\\{\left\|x-x_{0}\right\|_{2},\left\|x+x_{0}\right\|_{2}\\}$
$\displaystyle\gtrsim\inf_{L:\mathbb{R}^{n}\rightarrow\mathbb{R}^{N}}\sup_{x,y\in
B_{1}^{n}\cap{\rm ker}L}\left\|x-y\right\|_{2}=c_{N}(B_{1}^{n})$

which is the Gelfand $N$-width of $B_{1}^{n}$. By a result due to Garnaev and
Gluskin (see [3]),

$c_{N}(B_{1}^{n})\sim\left\\{\begin{array}[]{cc}\min\Big{\\{}1,\sqrt{\frac{1}{N}\log\Big{(}\frac{en}{N}\Big{)}}\Big{\\}}&\mbox{
if }N\leq n\\\ \\\ 0&\mbox{ otherwise}.\end{array}\right.$

which is of the same order as $r_{N}^{*}$ (except when $n\sim N$, which is not
treated here). Therefore, no algorithm can outperform ERM and ERM is a minimax
procedure in this case.

Note that when $n\leq c_{1}Q^{2}N$, exact reconstruction of $x_{0}$ or
$-x_{0}$ is possible and it can happens only in that case (i.e. $\sigma=0$ and
$n\leq c_{1}Q^{2}N$) because of the minimax lower bound provided by
$d_{N}^{*}({\mathbb{A}})$. The noisy case: $\sigma>0$. According to Theorem B,
the rate of convergence rate depends on $r_{N}^{*}=r_{N}^{*}(Q)$ for some
absolute constant $Q$, $s_{N}^{*}=s_{N}^{*}(\eta)$ for
$\eta=c_{1}\left\|x_{0}\right\|_{2}/(\sigma\sqrt{\log N})$ and on
$v_{N}^{*}=v_{N}^{*}(\zeta)$ for $\zeta=c_{1}/(\sigma\sqrt{\log N})$. The
outcome of Theorem B is presented in Figure 1.

rate $\lesssim$ | $\sigma/\left\|x_{0}\right\|_{2}\leq c_{0}r_{N}^{*}/\sqrt{\log N}$ | $\sigma/\left\|x_{0}\right\|_{2}\geq c_{0}r_{N}^{*}/\sqrt{\log N}$
---|---|---
$\left\|x_{0}\right\|_{2}\leq v_{N}^{*}$ | $r_{N}^{*}$ | $s_{N}^{*}$
$\left\|x_{0}\right\|_{2}\geq v_{N}^{*}$ | $r_{N}^{*}$ | $v_{N}^{*}$
Figure 1: High probability bounds on the rate of convergence of the ERM
$\hat{x}$ for the square loss in phase recovery:
$\min\\{\left\|\hat{x}-x_{0}\right\|_{2},\left\|\hat{x}+x_{0}\right\|_{2}\\}\leq
rate$.

As the proof of all the estimates is similar, a detailed analysis is only
presented when $\zeta^{2/3}N^{1/3}\leq\eta\sqrt{N}\leq C_{1}Q^{2}N$, which is
equivalent to

$\Big{(}\frac{\sigma^{2}\log
N}{c_{1}N}\Big{)}^{1/6}\leq\left\|x_{0}\right\|_{2}\leq\frac{c_{1}Q^{2}\sigma\sqrt{N\log
N}}{c_{1}}.$

The upper bounds on  rate  change according to the way the number of
observations $N$ scales relative to $n$:

  1. 1.

$n\geq C_{0}Q^{2}N$. In this situation,
$r_{N}^{*}\sim\big{(}\log(n/N)/N\big{)}^{1/2}$. Therefore, if
$\sigma/\left\|x_{0}\right\|_{2}\lesssim\sqrt{\log(n/N)/(N\log N)}$ then
$rate\leq\big{(}\log(n/N)/N\big{)}^{1/2}$, and if
$\sigma/\left\|x_{0}\right\|_{2}\gtrsim\sqrt{\log(n/N)/(N\log N)}$,

$rate\leq\left\\{\begin{array}[]{cc}\Big{(}\frac{\sigma^{2}\log
N}{\left\|x_{0}\right\|_{2}^{2}N}\log\Big{(}\frac{\sigma^{2}n^{2}}{\left\|x_{0}\right\|_{2}^{2}N}\Big{)}\Big{)}^{1/4}&\mbox{
if }\left\|x_{0}\right\|_{2}\geq\Big{(}\frac{\sigma^{2}\log
N}{N}\log\Big{(}\frac{\sigma^{2}n^{3}}{N}\Big{)}\Big{)}^{1/6}\\\ \\\
\Big{(}\frac{\sigma^{2}\log
N}{N}\log\Big{(}\frac{\sigma^{2}n^{3}}{N}\Big{)}\Big{)}^{1/6}&\mbox{
otherwise}.\end{array}\right.$ (6.4)

  2. 2.

$c_{1}\left\|x_{0}\right\|_{2}/(\sigma\sqrt{\log N})\sqrt{N}\leq n\leq
C_{1}Q^{2}N$. In that case $r_{N}^{*}=0$. In particular
$\sigma/\left\|x_{0}\right\|_{2}>c_{0}r_{N}^{*}/\sqrt{\log N}$ and therefore,
the rate is upper bounded as in (6.4).

  3. 3.

$\big{(}c_{1}/(\sigma\sqrt{\log N})\big{)}^{2/3}N^{1/3}\leq n\leq
c_{1}\left\|x_{0}\right\|_{2}/(\sigma\sqrt{\log N})\sqrt{N}$. Again, in this
case, $r_{N}^{*}=0$. Therefore, one is in the situation of the small signal-
to-noise ratio and

$rate\leq\left\\{\begin{array}[]{cc}\frac{\sigma}{\left\|x_{0}\right\|_{2}}\sqrt{\frac{n\log
N}{N}}&\mbox{ if }\left\|x_{0}\right\|_{2}\geq\Big{(}\frac{\sigma^{2}\log
N}{N}\log\Big{(}\frac{\sigma^{2}n^{3}}{N}\Big{)}\Big{)}^{1/6}\\\ \\\
\Big{(}\frac{\sigma^{2}\log
N}{N}\log\Big{(}\frac{\sigma^{2}n^{3}}{N}\Big{)}\Big{)}^{1/6}&\mbox{
otherwise}.\end{array}\right.$

  4. 4.

$n\leq\big{(}c_{1}/(\sigma\sqrt{\log N})\big{)}^{2/3}N^{1/3}$. Once again,
$r_{N}^{*}=0$, and

$rate\leq\left\\{\begin{array}[]{cc}\frac{\sigma}{\left\|x_{0}\right\|_{2}}\sqrt{\frac{n\log
N}{N}}&\mbox{ if }\left\|x_{0}\right\|_{2}\geq\Big{(}\sigma\sqrt{\frac{n\log
N}{N}}\Big{)}^{1/2}\\\ \\\ \Big{(}\sigma\sqrt{\frac{n\log
N}{N}}\Big{)}^{1/2}&\mbox{ otherwise}.\end{array}\right.$

One may ask whether these estimates are optimal in the minimax sense, or
perhaps there is another procedure that can outperform ERM. It appears that
(up to an extra $\sqrt{\log N}$ factor), ERM is indeed optimal.

To see that, it is enough to apply Theorem C and verify that Sudakov’s
inequality is sharp in the following sense: (see the discussion following
Theorem C): that if $\|x_{0}\|_{1}\leq 1/2$, then for every $\varepsilon<1/4$

$\varepsilon\log^{1/2}M(B_{1}^{n}\cap(x_{0}+c_{0}\varepsilon
B_{2}^{n}),\varepsilon B_{2}^{n})\sim\ell\big{(}B_{1}^{n}\cap\varepsilon
B_{2}^{n}\big{)}.$

This fact is relatively straightforward to verify (see, e.g., Example 2 in
[10]).

Therefore, up to the extra $\sqrt{\log N}$ factor, which we believe is
parasitic, ERM is a minimax phase-recovery procedure in $B_{1}^{n}$.

## References

  * [1] L. Birgé, Approximation dans les espaces métriques et théorie de l’estimation, Z. Wahrsch. Verw. Gebiete (2) vol. 65, 1983
  * [2] Y. C. Eldar, S. Mendelson, Phase Retrieval: Stability and Recovery Guarantees, preprint.
  * [3] A. Yu. Garnaev and E. D. Gluskin.  The widths of a Euclidean ball.  Dokl. Akad. Nauk SSSR, 277(5):1048–1052, 1984.
  * [4] E. Giné, V. de la Peña, Decoupling: From Dependence to Independence, Springer-Verlag, 1999.
  * [5] Y.Gordon, A.E. Litvak, S. Mendelson and A. Pajor, Gaussian averages of interpolated bodies and applications to approximate reconstruction, J. Approx. Theory, 149 (1), 2007
  * [6] Vladimir Koltchinskii.  Oracle inequalities in empirical risk minimization and sparse recovery problems, volume 2033 of Lecture Notes in Mathematics.  Springer, Heidelberg, 2011.  Lectures from the 38th Probability Summer School held in Saint-Flour, 2008, École d’Été de Probabilités de Saint-Flour. [Saint-Flour Probability Summer School].
  * [7] G. Lecué, S. Mendelson, Learning subgaussian classes : Upper and minimax bounds, preprint, available at http://arxiv.org/pdf/1305.4825.pdf.
  * [8] G. Lecué, S. Mendelson, On the optimality of the empirical risk minimization procedure for the convex aggregation problem, Annales de l’Institut Henri Poincaré Probabilités et Statistiques, 49 (1), 2013.
  * [9] M. Ledoux, M. Talagrand, Probability in Banach spaces. Isoperimetry and processes, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 23. Springer-Verlag, Berlin, 1991.
  * [10] S. Mendelson, On the geometry of subgaussian coordinate projections, preprint.
  * [11] V.D. Milman, G. Schechtman, Asymptotic theory of finite dimensional normed spaces, Lecture Notes in Mathematics 1200, Springer, 1986.
  * [12] M. Schmuckenschlaeger, Bernstein inequalities for a class of random variables, Proc. Amer. Math. Soc. Proceedings of the American Mathematical Society (4), vol. 117, 1993.
  * [13] Alain Pajor and Nicole Tomczak-Jaegermann.  Subspaces of small codimension of finite-dimensional Banach spaces.  Proc. Amer. Math. Soc., 97(4):637–642, 1986.
  * [14] Alexandre B. Tsybakov.  Introduction to nonparametric estimation.  Springer Series in Statistics. Springer, New York, 2009.  Revised and extended from the 2004 French original, Translated by Vladimir Zaiats.
  * [15] A.W. Van der Vaart, J.A. Wellner, Weak convergence and empirical processes, Springer Verlag, 1996\.
  * [16] Yuhong Yang and Andrew Barron.  Information-theoretic determination of minimax rates of convergence.  Ann. Statist., 27(5):1564–1599, 1999.