arXiv:1702.05327v2 [cs.LG] 30 Sep 2017

Solving Equations of Random Convex Functions
via Anchored Regression
Sohail Bahmani
sohail.bahmani@ece.gatech.edu

Justin Romberg
jrom@ece.gatech.edu

October 3, 2017
Abstract
We consider the question of estimating a solution to a system of equations that
involve convex nonlinearities, a problem that is common in machine learning and
signal processing. Because of these nonlinearities, conventional estimators based on
empirical risk minimization generally involve solving a non-convex optimization program.
We propose anchored regression, a new approach based on convex programming that
amounts to maximizing a linear functional (perhaps augmented by a regularizer) over a
convex set. The proposed convex program is formulated in the natural space of the
problem, and avoids the introduction of auxiliary variables, making it computationally
favorable. Working in the native space also provides great flexibility as structural priors
(e.g., sparsity) can be seamlessly incorporated.
For our analysis, we model the equations as being drawn from a fixed set according
to a probability law. Our main results provide guarantees on the accuracy of the
estimator in terms of the number of equations we are solving, the amount of noise
present, a measure of statistical complexity of the random equations, and the geometry
of the regularizer at the true solution. We also provide recipes for constructing the
anchor vector (that determines the linear functional to maximize) directly from the
observed data.

1

Introduction

We consider the problem of (approximately) solving a system of nonlinear equations with
convex nonlinearities. In particular, we observe
y1 = f1 (x? ) + ξ1
y2 = f2 (x? ) + ξ2
..
.
yM = fM (x? ) + ξM ,

(1.1)

where x? ∈ RN contains the ground-truth parameters to be estimated, the functions
f1 , f2 , . . . , fM are convex and known, and the ξ1 , ξ2 , . . . , ξM are additive noise terms. Given
1

the observations (1.1), we propose as an estimator for x? the solution of a convex program
that balances consistency with the observations against structure induced by a (convex)
regularization term. This convex formulation means that if the functions fm and their first few
derivatives can be computed efficiently, the proposed estimator is computationally tractable.
Our main results give error bounds on the quality of the produced estimate, specified by
the Euclidean distance to x? , under a model where the functions fm are drawn at random
from a set F according to some probability law. The estimation error, and the sufficient
number of equations M needed to achieve it, depend on the Rademacher complexity of a
set A with respect to the induced probability law on the gradients ∇fm — A is essentially
the set of all ascent directions of the functional being maximized at x? , and depends on the
geometry of the regularizer.
One of these results, Corollary 2.2, shows that if the fm are “generic” convex functions
(in that their gradients are sufficiently diverse in RN ), then x? can be recovered from M ∼ N
observations ym = fm (x? ).

1.1

Motivating examples

To illustrate the broad applicability of the observation model (1.1), we provide a few motivating
examples.
Example 1.1 (Convex function of linear predictor). Perhaps the simplest example is the
case that
fm (x) = φ(aTm x)

m = 1, 2, . . . , M ,

(1.2)

for a given convex function φ : R → R, and data samples a1 , a2 , . . . , aM ∈ RN . This form
of observation appears in many instances of generalized linear models (GLM) [21] with φ
being the mean function (or the inverse link function) of the GLM. In some cases, the mean
function may not be convex itself, but it has a property (e.g., it is concave, log-convex, or
log-concave) that allows us to easily convert it to a convex function. In such cases, φ would
be the appropriate transformation of the mean function.
Equations of the form (1.2) also appear in the phase retrieval problem from computational
imaging. The goal in phase retrieval is to estimate an signal/image (up to a global phase) from
intensity of some linear observations. More precisely, given (random) measurement vectors
a1 , a2 , . . . , aM ∈ CN the goal is to estimate x? ∈ CN from noisy intensity measurements
ym = |a∗m x? |2 + ξm for m = 1, 2, . . . , M . Aside from minor technicalities for treating complexvalued vectors, clearly the observation model in phase retrieval is a special case of (1.2) with
φ(z) = |z|2 being the nonlinearity.
Example 1.2 (A simple neural net with partially known weights). The second example
is related to learning with a single hidden-layer neural network [12, 30]. Given prescribed
weights w1 , w2 , . . . , wK ≥ 0 for the hidden layer of a single hidden-layer neural network, and
an activation function φ : R → R, the output of the network can be expressed as
fm (x) =

K
X

wk φ (aTm xk ) ,

k=1

2

h

iT

where x = xT1 xT2 · · · xTK
denotes the input layer’s weight parameters and am denotes
the mth data sample. For convex activation functions such as the popular φ(u) = max(u, 0)
and φ(u) = log2 (1 + eu ), the functions fm (x) are also convex and the model assumed in
(1.1) applies.
Example 1.3 (A simple neural net with unknown weights). In the previous example, if the
activation function is also positive homogeneous, then the knowledge of the output weights
can be dropped from the assumptions. In fact, each non-negative weight wk of the output
layer can be absorbed into the corresponding input layer weight xk because they interact only
through wk φ(aTm xk ) = φ (aTm (wk xk )). Therefore, this case reduces to the previous example
with w1 = w2 = · · · = wK = 1. We may need to adapt the regularizer on the wk and xk to
account for this combination of variables.
Example 1.4 (Dimensionality reduction). Another example where our framework can be
used is the problem of learning a dimensionality reduction. The goal of this problem is to
find a linear embedding of data samples a1 , a2 , · · · , aM ∈ RN to RK with K < N that still
allows accurate prediction of the corresponding labels y1 , y2 , . . . , yM . More precisely, given
functions µ1 , µ2 , . . . , µT : RN ×K → R, we want to estimate X such that the functions
fm (X) =

T
X

wt µt (X T am )

t=1

for some weights w1 , w2 , . . . , wT , accurately predict the corresponding labels ym for m =
1, 2, . . . , M . By naturally flattening X into a vector in RN K , and assuming that the functions
µt (·) are convex with known weights wt ≥ 0, our framework applies to this model. Similar
to the previous example, we may also relax
the knowledge iof wt ’s assuming that µt ’s are
h
T
positive homogeneous so that with w = w1 w2 · · · wT
we can write
fm (w, X) =

T
X

µt (wt X T am ) .

t=1

Again we can flatten X to x ∈ RN K and observe that the functions fm (w, X) only depend
on the rank-one matrix Z = xwT . Namely, we can write
fm (w, X) =

T
X

µt ((IK×K ⊗ aTm ) zt ) ,

t=1

where ⊗ denotes the Kronecker product and zt is the tth column of Z. As a function of
Z, the observation functions fm (Z) are convex and compatible with the observation model
(1.1). The only remaining concern is inducing the rank-one structure of Z which can be done
through nuclear norm regularization in the estimator.
The last two examples can be extended further to address composition of non-negative
mixtures of positive homogeneous functions by lifting the unknown parameters to a higher
order low-rank tensor. However, estimating low-rank tensors usually involves computationally
prohibitive operations which renders these mentioned extensions less interesting from practical
point of view.
3

1.2

Anchored regression

In this paper, we propose anchored regression to estimate x? in the parametric model described
by (1.1). An anchor vector a0 ∈ RN is a unit vector (i.e., ka0 k2 = 1) that obeys
ha0 , x? i ≥ δ kx? k2 ,

(1.3)

for an absolute constant δ ∈ (0, 1]. In words, the anchor vector has a non-vanishing correlation
with a ground truth. Given an anchor vector a0 , our proposed estimator for (1.1) is the
convex program
argmax ha0 , xi − Ω (x)
x
(1.4)
+
+
subject to RM
(x) ≤ RM
(x? ) + ε ,
+
where Ω (x) is a convex regularizer, ε > 0 is a small constant, and RM
(·) is the empirical
one-sided error

def

+
RM
(x) =

M
1 X
(fm (x) − ym )+ ,
M m=1

(·)+ = max(·, 0),

which is also convex. Note that when there is no noise in the observations and we take ε = 0,
+
the constraint RM
(x) ≤ 0 is equivalent to fm (x) ≤ ym for all m. Of course, when there is
noise, the value of
M
1 X
+
RM
(x? ) =
(−ξm )+ ,
M m=1
+
is unknown in general, but depending on the noise model we may assume RM
(x? ) can be
estimated and the absolute error of such an estimate is captured by ε in (1.4).
The anchor vector a0 can be interpreted as a “rough guess” for the solution x? . This
guess might come from some kind of a priori information about the solution, or it might
be formed directly from the observations. In Section 3 below, we describe some schemes by
which an a0 obeying (1.3) can be constructed in a data-driven manner.

1.3

Advantages of anchored regression

Solving the system of nonlinear equations (1.1) is in general a hard problem. In the particular
case where the fm are multivariate polynomials, a standard approach is to lift the variables to a
higher-dimensional space that linearizes the equations. The key idea is that any homogeneous
polynomial function of the vector x ∈ RN of degree d can be expressed as a linear function of
the tensor X = x⊗d . In the lifted domain, then, solving (1.1) amounts to finding a rank-one
tensor solution to a system of linear equations. For quadratic polynomials (d = 2), there is a
natural convex relaxation to this problem using semi-definite programming; the effectiveness
of this relaxation for solving generic quadratic equations was studied in [4], and analysis
for several types of structured equations that arise in engineering problems can be found in
[1, 5, 20]. For d ≥ 3, it is not clear how the lifted problem can be relaxed, as the required
tensor computational primitives are computationally hard [13]. Even in the d = 2 case where
4

the relaxation can be cast as an SDP, the computational cost in squaring the number of
variables can be prohibitive for medium- to large-scale problems.
In contrast, our estimator works for observations that are general convex functions of the
unknown variables.1 Our method works in the natural domain of the unknown variables,
which is computationally efficient and provides us with the flexibility to incorporate prior
structural information about the ground truth through regularization.
The anchor a0 also allows us to avoid one of the pitfalls of convexification. It can be that
there are multiple equally valid solutions to (1.1), especially since the fm are convex. For
instance, in the phase retrieval problem where fm (x) = |a∗m x|2 for a set of complex-valued
vectors am , a global change of phase to x? will not affect the measurements at all. Minimizing
a convex loss function that assigns an equal score to each of these equivalent solutions is
bound to fail, as all of the points in the convex hull of the equivalence set will score equally
well or better. The lifting approach for quadratic equations gets around this by mapping
every equivalent solution to the same point in the lifted space. Our method also handles this
in a straightforward way by introducing a bias towards the solutions best aligned with the
anchor a0 .

1.4

Geometry of convex equations

The analysis of (1.4) for solving (1.1) has a very clean geometric interpretation. Suppose that
the observations are noise-free, ym = fm (x? ), and we solve (1.4) without the regularization
+
term and with ε = 0. Since RM
(x? ) = 0, this is equivalent to solving
maximize
hx, a0 i
N
x∈R

(1.5)

subject to fm (x) ≤ ym , m = 1, . . . , M .
Since all of the constraints in the program above are active at x? , the KKT conditions for
this program tell us that x? is indeed the solution when
−a0 +

M
X

λm ∇fm (x? ) = 0,

m=1

for some λ1 , . . . , λM ≥ 0. More succinctly, (1.5) is successful when




a0 ∈ cone {∇fm (x? )}M
m=1 .
This is illustrated in Figure 1. If we knew the ∇fm (x? ) in addition to the f (x? ), then
generating such a a0 would be straightforward. But in general, we do not have knowledge of
these gradients.
The main results in this paper say that it is enough to find a a0 that is roughly aligned
with x? . That is, if the fm (and hence the ∇fm (x? )) are generated at random, then with
high probability


hx? , a0 i ≥ δ ⇒ a0 ∈ cone {∇fm (x? )}M
m=1 ,
1

Of course, we need to be able to evaluate the fm and some number of its derivatives to actually solve
(1.4).

5

rf1 (x? )

x?

x?
rf2 (x? )

{x : f2 (x)  y2 }

K

K
{x : f1 (x)  y1 }

(a)

(b)

Figure 1: A simple set of two nonlinear equations, y1 = f1 (x? ) and y2 = f2 (x? ), in R2 . (a) The
unknown x? is an extreme point of K = {x : fm (x) ≤ ym , m = 1, . . . , M }. (b) The program (1.5)
will recover x? when a0 is in the cone generated by the two gradients.

provided that the number of equations M is large enough. In fact, we show that every roughly
aligned vector will work. Geometrically, this means that the cone of all valid anchor vectors
Cδ = {z : hz, x? i ≥ δkx? k2 kzk2 } ,
is included in the cone generated by the gradients




Cδ ⊆ cone {∇fm (x? )}M
m=1 ,
again when M is large enough. As δ becomes smaller (meaning that the anchor is more
aligned with the true solution) the cone Cδ shrinks, and the inclusion above may be satisfied
with smaller M .
Adding a convex regularizer Ω(x) to the program makes the optimality conditions weaker.
If we again observe ym = fm (x? ) and then solve
maximize
ha0 , xi − Ω(x)
N
x∈R

subject to fm (x) ≤ ym ,

m = 1, 2, . . . , M ,

then x? is the solution when




?
a0 ∈ cone {∇fm (x? )}M
m=1 + ∂Ω(x ),

where ∂Ω(x? ) is the subdifferential of Ω at x? ,
n

o

∂Ω(x) = g : Ω(x + z) ≥ Ω(x) + g T z for all z ∈ RN .
Finding such a a0 is now easier than in the unregularized case, as the convex cone that
needs to enfold it is larger. The (subdifferential of the) regularization term is effectively
working as an additional set of observations — if the subgradients in ∂Ω(x? ) are not aligned
with the ∇fm (x? ), we may be able to get away with many fewer equations.
6

1.5

Related work

As mentioned in Section 1.1 our approach can be applied to most GLMs. Another relevant
model is the semiparametric single index model (see [14], for example) where, again, the
model assumes linear predictors, but the nonlinear function µ is not known. Under some
regularity assumption on µ, in [28, 29] simple estimators based on convex programming are
shown to produce accurate estimates (up to some scaling factor). Because µ is unknown,
our framework does not apply to the single index model. However, there are interesting
instances of (1.1) (e.g., phase retrieval) where the results of [28, 29] do not apply as the
assumed regularity conditions lead to trivial bounds.
The most relevant results to our work are the recent methods proposed for phase retrieval
in [2] and independently in [8] that exploit anchor vectors. As mentioned above, the phase
retrieval problem can be described by the model (1.1) with fm (x) = |a∗m x|2 for some random
measurement vector am . It is shown in [2, 8] that, using an anchor, the ground truth x?
can be estimated accurately and with optimal sample complexity through a convex program
analogous to (1.4). The analyses in [8] and [2] differ in that the former assumes the anchor
is independent of the measurements whereas the latter does not make this assumption.
Alternative proofs and variations of this phase retrieval method also appeared later in [9–11].

2

Main result

To show that (1.4) produces an accurate estimate of x? , it suffices to show that the set of
ascent directions,
A = {h : ha0 − g, hi ≥ 0, for all g ∈ ∂Ω (x? )} ,
does not contain any vector with large `2 norm that is consistent with the constraint. Namely,
+
+
if h ∈ A has a large `2 norm, then RM
(x? + h) > RM
(x? ) + ε.
As explained further in Section 3, we will be interested in anchor vectors a0 constructed
from the observations ym (and knowledge of the fm ). However, the dependence of the set A
on the observations would complicate the probabilistic analysis. We avoid this dependence
by an expansion of the set A that allows us to decouple it from a0 .
Let h⊥ and a0⊥ denote the projection of h and a0 onto the hyperplane orthogonal to x? ,
respectively. Using the property of the anchor vector (1.3) we can write
x? xT? a0
, hi
kx? k22
!
xT? a0
x?
x?
≤ ka0⊥ k2 kh⊥ k2 +
−δ h
, hi + δh
, hi
kx? k2
kx? k2
kx? k2

ha0 , hi = ha0⊥ , hi + h

v
u
u
t

!2 s

xT? a0
x?
x?
≤
−δ
kh⊥ k22 + h
, hi2 + δh
, hi
+
kx? k2
kx? k2
kx? k2
√
x?
≤ 1 − δ 2 khk2 + δh
, hi .
kx? k2
ka0⊥ k22

7

This implies the inclusion
(
def

A ⊂ Aδ = h :

√

)

δx?
− g, hi ≥ 0, for all g ∈ ∂Ω (x? )
1 − δ 2 khk2 + h
kx? k2

.

(2.1)

It suffices to show that Aδ does not contain any point with (relatively) large `2 norm consistent
with the constraints as mentioned above.
As it becomes clear in the sequel, it is critical that Aδ excludes a sufficiently large subset of
N
R . Therefore, we may require δ to be bounded away from zero. For example, in unstructured
2
phase retrieval, where fm (x) = (aTm x)
√ and Ω(x) = 0, the set Aδ should
√ not contain −x? .
Therefore, in this case we must have 1 − δ 2 < δ or equivalently δ > 1/ 2. Throughout, we
implicitly assume that such required lower bounds on δ hold. Furthermore, instead of (2.1)
we could have used the tighter approximation
√
x?
δx?
A⊆ h : h
, hi < δ khk2 and 1 − δ 2 kh⊥ k2 + h
− g, hi ≥ 0 for all g ∈ ∂Ω (x? )
kx? k2
kx? k2
)
(
[
x?
, hi ≥ δ khk2 and khk2 − hg, hi ≥ 0 for all g ∈ ∂Ω (x? ) ,
h : h
kx? k2
(

where h⊥ denotes part of h that is orthogonal to x? . While using this approximation improves
the dependence of our result on δ, we prefer (2.1) merely for simpler notation and derivations.
Our main theorem below provides a sample complexity for establishing the desired
sufficient condition and thus accuracy of (1.4) in terms of a Rademacher complexity and a
probability bound for ∇f (x? ) being in certain half-spaces. Let us pause here to describe
these two quantities first.
For a set H ⊂ RN define the Rademacher complexity2 with respect to ∇fm (x? )’s as
M
h
1 X
def
m h∇fm (x? ) ,
i,
CM (H) = E sup √
khk2
M m=1
h∈H

(2.2)

where 1 , 2 , . . . , M are i.i.d. Rademacher random variables independent of everything else.
If H is non-negative homogeneous (e.g., it is a convex cone), then CM (H) is a measure of
“wideness” of H near the origin; the notion of wideness here depends on the law of ∇f (x? ).
For example, in the case that ∇f (x? ) is a standard Gaussian random vector, the vector
P
M −1/2 M
m=1 m ∇fm (x? )i is also distributed like a standard Gaussian vector and CM (H)
reduces to the Gaussian width of H which is defined as
def

γ(H) = E sup hg,
h∈H

h
i,
khk2

g ∼ Normal(0, I) .

The reduction of the Rademacher complexity CM (H) to the Gaussian width γ(H) is also possible for ∇f (x? ) that is not Gaussian but has a sufficiently regular law: for any fixed h, assuming
P
bounded moments of sufficiently high order the random quantity M −1/2 M
m=1 m h∇fm (x? ), hi
can be approximated by a Gaussian using Berry-Esséen theorem; we only need to make
2

Unlike conventional definition of Rademacher complexities, we use a normalization by square root of the
number of samples.

8

)

this approximation uniform over the entire H. While the Gaussian width of H can provide
sharp approximations for CM (H), it is generally a difficult quantity to compute. In Section
2.2 we use different techniques to bound the Rademacher complexity in the special cases of
unstructured and sparse regression problems.
The second quantity that affects the sample complexity of our method is a probability
lower bound defined for H and a positive parameter τ as
def

pτ (H) = inf P (h∇f (x? ) , hi ≥ τ khk2 ) .

(2.3)

h∈H

Intuitively, pτ (H) measures how “well-spread” the random vector ∇f (x? ) is in the space.
A smaller value of pτ (H) indicates that realizations of ∇f (x? ) are often confined to some
half-space whose normal vector belongs to H.
We now state our main theorem in terms of the quantities CM (Aδ ) and pτ (Aδ ). In
Sections 2.1 and 2.2 below, we show how these quantities can be bounded in a way that
shows their dependence on the probability law for ∇f (x? ) more clearly.
Theorem 2.1. Let Aδ be defined as in (2.1) for which CM (Aδ ) and pτ (Aδ ) can be determined
using (2.2) and (2.3), respectively. For any t > 0, if
2CM (Aδ ) + tτ
M ≥4
τ pτ (Aδ )

!2

(2.4)

,

b of (1.4) obeys
then with probability ≥ 1 − exp(−2t2 ) any solution x
M
1 X
|ξm | + ε .
M m=1

!

2
b − x? k2 ≤
kx
τ pτ (Aδ )

The factor 4 in (2.4) can be made arbitrarily close to 1 at the cost of increasing the
constant factor in the error bound. Proof of Theorem 2.1, provided below in Section 4,
is based on the idea of small-ball method introduced in [16, 23] and further developed in
[17, 18, 24].

2.1

Simplifying pτ (Aδ ) and the dependence on τ

The sample complexity in the statement of Theorem 2.1 depends critically depends on the
parameters τ and pτ (Aδ ). Approximating pτ (Aδ ) is challenging in general and may require
detailed calculations even for specific cases (see, for example, [2, Lemmas 3 and 5] where this
is done for the phase retrieval problem fm (x) = |hx, am i|2 with Gaussian vectors am ). In
this section, we show how pτ (Aδ ) and τ can be approximated by expressions that capture
the interplay between the probability distribution on the fm and the geometry of the set Aδ .
These may still be very difficult to calculate, but they will allow us to state more interpretable
corollaries to our main theorem,
We start by observing that




P (h∇f (x? ), hi ≥ τ khk2 ) = P (h∇f (x? ), hi)+ ≥ τ khk2 ,
9

and then define
def

τ (h) =

E (h∇f (x? ), hi)+
,
khk2

def

τ (Aδ ) =

inf

h∈Aδ \{0}

τ (h).

(2.5)

Clearly, both of these quantities are non-negative. However, to ensure that pτ (Aδ ) > 0 for
some τ > 0, it is necessary that τ (Aδ ) is strictly positive. The only way this does not occur
is when there is some h ∈ Aδ \{0} for which h∇f (x? ), hi ≤ 0 almost surely. This means
that with probability 1, ∇f (x? ) lies in a half-space determined whose normal vector is in Aδ .
Qualitatively, if the distribution for ∇f (x? ) is well-spread, then this situation does not occur,
and τ (Aδ ) is positive.
By the Paley-Zygmund inequality [27][6, Corollary 3.3.2],
1
P (h∇f (x? ), hi)+ ≥ τ (h)khk2
2




≥

τ 2 (h)khk22
.
E[(h∇f (x? ), hi)2+ ]

Since (h∇f (x? ), hi)2+ ≤ |∇f (x? )T h|2 = hT ∇f (x? )∇f (x? )T h, we have for τ = τ (Aδ )/2,
τ 2 (Aδ )
,
ς 2 (Aδ )

pτ (Aδ ) ≥

(2.6)

where
def

ς 2 (Aδ ) =

hT Σ? h
,
2
h∈Aδ \{0} khk2

with Σ? = E [∇f (x? )∇f (x? )T ] .

sup

(2.7)

This gives us the following corollary to Theorem 2.1:
Corollary 2.1. Let Aδ be defined as in (2.1), and CM (Aδ ), τ (Aδ ), ς 2 (Aδ ) as in (2.2), (2.5),
and (2.7). For any t > 0, if
16 ς 4 (Aδ )
M ≥
τ 4 (Aδ )

2CM (Aδ ) t
+
τ (Aδ )
2

!2

(2.8)

,

b of (1.4) obeys
then with probability ≥ 1 − 2 exp(−2t2 ), any solution x
b − x ? k2 ≤
kx

4 ς 2 (Aδ )
τ 3 (Aδ )

!

M
1 X
|ξm | + ε .
M m=1

!

(2.9)

A simple dimensional analysis can help us understand how the bound above scale qualitatively. The entries in the gradient vector ∇f (x) represent quantities in “units of f ” divided
by “units of x”. The constants ς(Aδ ), τ (Aδ ), and CM (Aδ ) all have the same units as ∇f (x).
Thus the lower bound on the number of equations M in (2.8) is dimensionless, as we expect.
As the noise variables ξm are also in “units of f ”, both sides of the inequality in (2.9) are in
“units of x”.

2.2

Bounding the Rademacher complexity CM (Aδ )

To make the result of Theorem 2.1 more explicit we consider the special cases of unstructured
regression (i.e., x? is arbitrary and Ω (x) = 0) and sparse regression (i.e., x? is sparse and
Ω (x) = λ kxk1 for some λ > 0). The specific choice of Ω (x) helps to simplify the Rademacher
complexity CM (Aδ ). Of course, CM (Aδ ) would depend on the law of f1 , f2 , . . . , fM as well.
10

2.2.1

Unstructured regression

In the first example, we approximate CM (Aδ ) when no regularization is applied, i.e., Ω (x) = 0.
In this case, (2.1) reduces to
(

Aδ = h :

√

)

δx?
, hi ≥ 0
1 − δ 2 khk2 + h
kx? k2

,

which we approximate by the entire space (i.e., Aδ ⊆ RN ). Because CM (·) is monotonic, we
obtain


CM (Aδ ) ≤ CM RN



M
1 X
h
= E sup √
i
m h∇fm (x? ) ,
khk2
M m=1
h
M
1 X
m ∇fm (x? )
= E √
M m=1

.
2

Applying the Cauchy-Schwarz for the square-root function which is concave, we deduce that
CM (Aδ ) ≤

=
=

v
u
u
u
tE
v
u
u
t
q

M
1 X
√
m ∇fm (x? )
M m=1

2

2

M
1 X
k∇fm (x? )k22
E
M m=1

E k∇f (x? )k22 ,

where the second and third lines respectively hold because m s are independent zero-mean
random variables and fm s are i.i.d. copies of f . The following corollary of Theorem 2.1 is the
immediate result of the bound above.
Corollary 2.2. Let Aδ and pτ (Aδ ) be defined by (2.1) and (2.3), respectively. For any t > 0,
if
2

 q

2 E k∇f (x? )k22 + tτ
 ,

M ≥4
τ pτ (Aδ )

(2.10)

b of (1.4) obeys
then with probability ≥ 1 − exp(−2t2 ) any solution x

2
b − x? k2 ≤
kx
τ pτ (Aδ )

M
1 X
|ξm | + ε .
M m=1

!

Applying the bounds (2.6) and (2.7) from the last section, (2.10) becomes
 q

2

kΣ? k2  4 tr(Σ? )
M ≥ 4 4
+ t ,
τ (Aδ )
τ (Aδ )
11

where again Σ? is the correlation matrix of the gradient of fm , and we have applied the
bound ς 2 (Aδ ) ≤ kΣ? k. Since tr(Σ? ) ≤ N kΣ? k, it suffices to take
2

q



kΣ? k
kΣ? k  √
4 N
M ≥ 4 4
+ t .
τ (Aδ )
τ (Aδ )
2

q

When kΣ? k/τ (Aδ ) is on the order of a constant, this means we can take M & N . Provided
we have an anchor vector that obeys (1.3), we can robustly recover a vector x? of length N
through observations of slightly more than N convex functions of x?
2.2.2

Sparse regression

Next, we approximate CM (Aδ ) for the case of `1 -regularized anchored regression, i.e., Ω (x) =
λ kxk1 for some λ > 0. Let S? denote the support set of x? (i.e., S? = {i ∈ [1, N ] : x?i 6= 0})
and s = |S? |. The subdifferential of the Ω (·) at x? can be expressed as
n



∂Ω (x? ) = g : kgk∞ ≤ λ and g|S? = λ sgn x? |S?

o

.

Therefore, we have
(

Aδ = h :

√

)

1−

δ2

khk2 − λ h|S?c



δx? |S?
− λ sgn x? |S? , h|S? i ≥ 0
+h
1
kx? k2

.

It follows from the Cauchy-Schwarz inequality that
h





δx? |S?
δx? |S?
− λ sgn x? |S? , h|S? i ≤
− λ sgn x? |S?
kx? k2
kx? k2

δx?
− λ sgn (x? )
kx? k2

=

h|S?
2

h|S?

2

2

2

,

thereby
(

Aδ ⊆

A0δ

def

= h :

√

1 − δ 2 khk2 − λ h|S?c

δx?
+
− λ sgn (x? )
1
kx? k2

)

h|S?
2

2

≥0

.

For any non-zero h and any z ∈ RN , it follows from Hölder’s inequality that
hz,

h
i ≤ z|S?
khk2

h|S?
2

khk2

2

+ z|S?c

h|S?c
∞

khk2

1

(2.11)

.

Therefore, recalling the definition (2.2), we can write
CM (Aδ ) ≤ CM (A0δ )
M
1 X
h
√
= E sup
m h∇fm (x? ) ,
i
0
khk2
M m=1
h∈Aδ

≤ E sup
h∈A0δ

+ E sup
h∈A0δ

M
1 X
√
m ∇fm (x? ) |S?
M m=1

h|S?
2

M
1 X
√
m ∇fm (x? ) |S?c
M m=1

12

2

khk2
h|S?c
∞

khk2

1

where the first inequality follows from the fact that Aδ ⊆ A0δ and the second inequality is
P
an application of (2.11) for z = √1M M
m=1 m ∇fm (x? ) followed by a triangle inequality. We
kh|S? k2
always have khk
≤ 1 and the definition of A0δ implies that
2

h|S?c

1

khk2

√
1 − δ 2 1 δx?
≤
+
− λ sgn (x? )
λ
λ kx? k2
√
1 − δ 2 1 δx?
≤
+
− λ sgn (x? )
λ
λ kx? k2

h|S?

2

khk2

2

.
2

Hence, we deduce that
M
1 X
CM (Aδ ) ≤ E √
m ∇fm (x? ) |S?
M m=1
2
√
!
M
2
1−δ
1 δx?
1 X
+
+
m ∇fm (x? ) |S?c
− λ sgn (x? )
E √
λ
λ kx? k2
M m=1
2

.
∞

Next, we bound the terms with the expectation. For the first term, the Cauchy-Schwarz
inequality and the fact that m s are independent and zero-mean guarantees that
1
E √
M

M
X

m ∇fm (x? ) |S?

m=1

≤

v
u
u
u
tE

=

v
u
u
t

2

M
1 X
√
m ∇fm (x? ) |S?
M m=1

M
1 X
E ∇fm (x? ) |S?
M m=1

r

E ∇f (x? ) |S?

=

2
2

2

2

2
2

.

For the second term, a similar application of the Cauchy-Schwarz inequality, followed by
the Nemirovski’s inequality (see [25, Lemma 5.2.2] and [7, Theorem 2.2]) with the minor
assumption that N − s ≥ 3, yield
1
E √
M

M
X
m=1

m ∇fm (x? ) |S?c

≤

v
u
u
u
tE

≤

v
u
u
t2e log (N

∞

M
1 X
√
m ∇fm (x? ) |S?c
M m=1

2e log N E ∇f (x? ) |S?c

Therefore, we obtain the following corollary of Theorem 2.1.

13

∞

M
1 X
− s) ·
E ∇fm (x? ) |S?c
M m=1

r

≤

2

2
∞

.

2
∞

Corollary 2.3.Let Aδ and pτ (Aδ ) be defined by (2.1) and (2.3), respectively. Furthermore,
√
√
2
?
+ λ1 kxδx??k − λ sgn (x? ) . For any t > 0, if
let Cδ,λ
= 2 2e 1−δ
λ
2

2

 r
2

M ≥ 4


E ∇f (x? ) |S?

2
2

+

?
Cδ,λ

r

log (N ) E ∇f (x? ) |S?c

2
∞

2

+ tτ 



τ pτ (Aδ )

,

b of (1.4) obeys
then with probability ≥ 1 − exp(−2t2 ) any solution x
M
1 X
|ξm | + ε .
M m=1

!

2
b − x? k2 ≤
kx
τ pτ (Aδ )

Let us consider the particular case of regression with linear predictors to make the result
of Corollary 2.3 more explicit.
Example 2.1 (Sparse regression with linear predictor). Suppose that f (x) = φ(aT x) for
a ∼ Normal (0, I) and a convex φ(·) that has derivatives of sufficiently high order. Moreover,
in the calculations below we implicitly assume that the expectations that involve φ(·) or its
derivatives exist. Clearly, we can write ∇f (x? ) = φ0 (aT x? )a and obtain
E ∇f (x? ) |S?

2
2



02



02

2

T

= E φ (a x? ) a|S?



2



2

= E φ (kx? k2 g)(g + |S? | − 1) ,


g ∼ Normal(0, 1)



2

= s E φ0 (kx? k2 g)


00 2



000

+ 2E φ (kx? k2 g) + φ (kx? k2 g)φ (kx? k2 g) kx? k22 .
0

where the second equation follows from independence of projections of a|S? onto subspaces
parallel and orthogonal to x? . The third equation follows by applying the Stein’s lemma [31]
twice. Furthermore, we have
E ∇f (x? ) |S?c

2
∞



02

T

02

T

= E φ (a


x? ) maxc a2i
i∈S?


= E φ (a x? ) E





maxc a2i
i∈S?



1
X 2q q
E
a 






2

≤ E φ0 (kx? k2 g)

i

g ∼ Normal(0, 1)

,

i∈S?c





2

≤ E φ0 (kx? k2 g)



(N − s)E g 2q

 1
q

,

where the second line holds by independence of aT x? and ai for i ∈ S?c , the third line holds
for any positive integer q, and the fourth line follows from concavity of t 7→ t1/q and the
Jensen’s inequality. Hence, for q = O(log N ) we obtain
E ∇f (x? ) |S?c

2
∞



2



. E φ0 (kx? k2 g) log N .
14

Treating the terms that only depend on kx? k2 as constants we can summarize the derived
bounds as
E ∇f (x? ) |S?

2

2

. log N .
E ∇f (x? ) |S?c
2
∞
√
If we choose the regularization parameter as λ = O(1/ s) for a suitable constant factor that
depends on δ, then we obtain
√
?
Cδ,λ
≤ cδ s ,
. s,

and

where cδ is a constant decreasing in δ. Therefore, we can conclude that having
!2
√
√
s + cδ s log (N ) + tτ
M&
τ pτ (Aδ )
is sufficient
to meet
the requirements in Corollary 2.3. This result suggests a sample complexity


2
of O s log N which is optimal up to the dependence on log N . A more refined bound
can be obtained using a tighter bound for E
Corollary 2.3.

3

√1
M

PM

m=1 m ∇fm

(x? ) |S?c

∞

in the proof of

Recipes for creating anchors

While it may be assumed that the anchor vector is provided by an oracle, it is more realistic
to have a data-driven method to construct the anchor vector. This requires us to impose
new assumptions, albeit implicitly, on the class of functions F where the random samples
f1 , f2 , . . . , fM are drawn from. A natural assumption is that for a certain sample loss function
def
` : R × R → R the corresponding risk R (x) = E` (f (x) , f (x? )) “encodes” the information
about x? in its derivatives at some reference point x0 , i.e., ∇k R (x0 ) for k = 1, 2, 3, . . . . For
simplicity, henceforth we take the origin as the reference point, i.e., x0 = 0. This assumption
is reasonable, for instance, if R (x) has a Taylor series approximation around the origin. Note
that we are implicitly assuming that the random functions drawn from the class F as well as
the sample loss ` (·, ·) are k-times differentiable. Furthermore, to allow the derivative operator
and expectation to commute, the required regularity conditions for the law of f are assumed.
Definition 3.1 (Spiked Derivatives). We say that the risk R (x) = E` (f (x) , f (x? )) has a
spiked kth-order derivative if x? is a simple principal eigenvector of −∇k R (0) 6= 0. Namely,
x?
∈ argmax h−∇k R (0) , u⊗k i ,
kx? k2
u∈SN −1

(3.1)

and every other maximizer is parallel to x? .
For computational considerations, we focus only on risks with spiked gradient (i.e., 1storder derivative) or spiked Hessian (i.e., 2nd-order derivative). In the case of spiked gradients
the condition (3.1) reduces to −∇R (0) being perfectly aligned with x? , that is,
x?
∇R (0)
=−
.
kx? k2
k∇R (0)k2
15

(3.2)

Similarly, for spiked Hessians, the condition (3.1) reduces to x? being a simple principal
eigenvector of −∇2 R (0). Specifically, we have
x?
∈ argmax −uT ∇2 R (0) u
kx? k2
u∈SN −1
def



2





,

(3.3)



2

γ? = λ1 −∇ R (0) − λ2 −∇ R (0) > 0
where λi (·) denotes the ith largest (multiplicity inclusive) eigenvalue of its argument. For
example, with the squared error ` (s, t) = 12 (s − t)2 as the sample loss function, if the risk
R (x) = E 12 (f (x) − f (x? ))2 has a spiked gradient then
x?
1
=
E ((f (x? ) − f (0)) ∇f (0)) .
kx? k2
kE ((f (x? ) − f (0)) ∇f (0))k2
and if it has spiked Hessian then


x?
∈ argmax uT E f (x? )∇2 f (0) − ∇f (0) ∇T f (0) u ,
kx? k2
u∈SN −1

and the Hessian has a positive spectral gap.
Let us again consider the problem of regression with linear predictors as a concrete
example.
Example 3.1 (Spiked derivatives in regression with linear predictor). Let f (x) = φ(aT x) for
a ∼ Normal(0, I) and a twice-differentiable convex function φ(·). Without loss of generality
we may assume that φ(0) = 0. Suppose that we observe M i.i.d. samples of f (x? ), i.e.,
ym = fm (x? ) = φ(aTm x? ) for m = 1, 2, . . . , M with am s being i.i.d. copies of a. The risk with
respect to the squared loss `(u, v) = 21 (u − v)2 is
2

R(x) = E (φ(aT x) − φ(aT x? )) .
Therefore, we can calculate ∇R(0) as
∇R(0) = E (φ0 (0) (φ(0) − φ(aT x? )) a)
= −φ0 (0)E (φ(aT x? )a)
= −φ0 (0)Eφ0 (kxk2 g)x?

, g ∼ Normal(0, 1) ,

where the third line follows from Stein’s lemma. Similarly, we can write
∇2 R(0) = E





2



2



2

φ0 (0) − φ00 (0)φ(aT x? ) aaT





= φ0 (0) − φ00 (0)Eφ(aT x? ) I − φ00 (0)Eφ00 (aT x? )x? xT?


= φ0 (0) − φ00 (0)Eφ(kx? k2 g) I − φ00 (0)Eφ00 (kx? k2 g)x? xT? .
If φ0 (0) 6= 0 then R(·) clearly has a spiked gradient. If φ0 (0) = 0, however, ∇R(0) = 0 and
we need to inspect the second derivative. In that case, if φ00 (0) 6= 0 then we have
∇2 R(0) = −φ00 (0)Eφ00 (kx? k2 g)x? xT? − φ00 (0)Eφ(kx? k2 g)I .
16

Because φ(·) is convex, φ00 (·) is non-negative and the matrix above is clearly a spiked
Hessian with spectral gap γ? = φ00 (0) kx? k22 Eφ00 (kx? k2 g). By a simple change of variable the
derivations above can be extended to the case where the Gaussian random vector a is still
zero-mean, but has an arbitrary covariance matrix.
Of course, in practice we do not have access to R (x). With finite number of observations,
however, the empirical risk
RM (x) =

M
1 X
` (fm (x) , ym ) ,
M m=1

may provide a sufficiently good approximation for R (x). Therefore, with sufficient number of
observations, ∇RM (0), as an approximation to ∇R (0), or ∇2 RM (0), as an approximation
to ∇2 R (0), can be used to find an anchor vector under the spiked gradient or spiked Hessian
conditions, respectively.
In case of the spiked gradient, it suffices to have sufficiently large number of samples (i.e.,
M ) such that
a0 = −

∇RM (0)
,
k∇RM (0)k 2

obeys anchor vectors’ required property (1.3). Suppose that the law of f is such that ∇RM (0)
concentrates around ∇R(0), namely
k∇RM (0) − ∇R(0)k2 ≤  k∇R(0)k2 ,
with high probability for a small  ∈ (0, 1). If R(·) has a spiked gradient, then obtain
ha0 ,

x?
∇RM (0)
∇R (0)
i=h
,
i
kx? k2
k∇RM (0)k 2 k∇R (0)k 2
(1 − 2 )k∇R (0)k22 + k∇RM (0)k22
2k∇RM (0)k2 k∇R (0)k2
√
≥ 1 − 2 ,
≥

where the√third line follows from the AM-GM inequality. Therefore, a0 would satisfy (1.3)
with δ = 1 − 2 .
In the case that R (·) has a spiked Hessian, using a variant of the Davis–Kahan’s theorem
[34, Corollary 3], we can show that for
a0 ∈ argmax −uT ∇2 RM (0) u ,

(3.4)

u∈SN −1

we have
1
2 k∇2 RM (0) − ∇2 R (0)k
T
a0 a0 −
x? x? ≤
,
γ?
kx? k22
T

where γ? is the spectral gap defined in (3.3). Therefore, if k∇2 RM (0) − ∇2 R (0)k is sufficiently
small relative to the spectral gap γ? , the inequality above implies a0 (or −a0 ) can obey
the required property (1.3) for some δ > 0. Depending on the law of f , we can bound
k∇2 RM (0) − ∇2 R (0)k using matrix concentration inequalities as ∇2 RM (0) can be written
as a sum of independent random matrices.
17

3.1

Anchors for structured regression

How does construction of the anchor change if we need to estimate a structured ground truth
(e.g., a sparse vector)? In this scenario, the situation is more complicated compared to what
described above mainly because computationally efficient methods may not achieve optimal
sample complexity.
Ideally, we would have a method for constructing the anchor vector from a number of
observations that does not dominate the sample complexity of the estimator. This may be
possible if we impose an explicit structural constraint u ∈ S with S denoting a prescribed
set of structured vectors; namely we would have
a0 ∈ argmax h−∇k RM (0) , u⊗k i .

(3.5)

u∈SN −1 ,u∈S

Regardless of whether this construction can achieve (1.3) at an appropriate sample complexity,
there is no guarantee that solving (3.5) is computationally tractable. For some of the problems
discussed above, there are relaxations of (3.5) that produce an anchor, but at the cost of
increasing M well beyond the required sample complexity (2.4) of the main estimation
procedure.
As a concrete example, consider phase retrieval for a (real-valued) sparse target x? using
noiseless measurements obtained through i.i.d. copies of a ∼ Normal (0, I) as the measure
2
ment vectors. As in the ordinary phase retrieval, the risk R (x) = E 21 |aT x|2 − |aT x? |2 has
a spiked Hessian because −∇2 R (0) = E |aT x? |2 aaT = kx? k22 I + 2x? xT? whose spectral gap
is γ? = 2 kx? k22 . Ignoring the computational restrictions, if S is the set of (sufficiently) sparse
vectors, a brute force estimator generally solves (3.5) for k = 2 by searching over all possible
sparse support sets. This estimator can produce the desired a0 with (near) optimal sample
complexity as we only need small submatrices of −∇2 RM (0) to concentrate around their
expected values. In the case of sparse phase retrieval, the desired concentration occurs when
M (i.e., the number of samples) grows (nearly) linearly with the sparsity of x? (i.e., kx? k0 ).
However, computationally tractable relaxations of (3.5), which rely on diagonal thresholding
or mixed nuclear-norm `1 -norm regularization, require M to grow quadratically with kx? k0
to guarantee accuracy. This situation is similar to the case of sparse principal component
analysis (SPCA) [15, 35], where the goal is to estimate the sparse principal component of
a (covariance) matrix from an empirical (covariance) matrix. It is widely believed that
computationally efficient estimators cannot achieve the optimal sample complexity in SPCA
[3]. Suboptimality of mixed nuclear-norm `1 -norm regularization is also shown in estimation
of simultaneously sparse and low-rank matrices [26].

4

Proof of the main result

In this section we provide a proof of Theorem 2.1. The argument is based on the small-ball
method introduced in [16, 23] with minor modifications. Our derivations mostly follow the
exposition of this method in [32].
def

Proof of Theorem 2.1. For t ≥ 0, let ψt (s) = (s)+ − (s − t)+ which is a contraction (i.e.,
18

+
|ψτ (s2 ) − ψτ (s1 )| ≤ |s2 − s1 | for all s1 , s2 ∈ R). We can bound RM
(x? + h) from below as

+
RM

M
1 X
(fm (x? + h) − ym )+
(x? + h) =
M m=1
M
1 X
=
(fm (x? + h) − fm (x? ) − ξm )+
M m=1
M
1 X
(h∇fm (x? ) , hi − ξm )+
≥
M m=1
M
M
1 X
1 X
≥
(h∇fm (x? ) , hi)+ −
(ξm )+
M m=1
M m=1
M
M
1 X
1 X
≥
ψτ khk2 (h∇fm (x? ) , hi) −
(ξm )+ ,
M m=1
M m=1

(4.1)

where the inequalities hold, respectively, because fm (·) is convex, (·)+ is subadditive, and
(s)+ ≥ ψt (s). Furthermore, using the fact that t1 (s ≥ t) ≤ ψt (s), we have
τ khk2 P (h∇f (x? ) , hi ≥ τ khk2 ) = τ khk2 E (1 (h∇f (x? ) , hi ≥ τ khk2 ))


≤ E ψτ khk2 (h∇f (x? ) , hi)



Therefore, by adding and subtracting the sides of the inequality above in the right-hand side
of (4.1) and some rearrangement we obtain
+
RM

M
1 X
(x? + h) ≥ τ khk2 P (h∇f (x? ) , hi ≥ τ khk2 ) −
(ξm )+
M m=1
M


1 X
ψτ khk2 (h∇fm (x? ) , hi) − E ψτ khk2 (h∇f (x? ) , hi) .
+
M m=1

(4.2)

We only need to establish a uniform lower bound over h ∈ Aδ for the expression in the
second line of (4.2).
It is easy to verify that for every α, t ≥ 0 and s ∈ R the identity

s
ψαt (s) = tψα t holds.3 Thus, we write
M


1 X
ψτ khk2 (h∇fm (x? ) , hi) − E ψτ khk2 (h∇f (x? ) , hi)
M m=1
M
X
1
h
= − khk2
E ψτ h∇f (x? ) ,
i
M
khk2
m=1

!!

!

− ψτ

h
h∇fm (x? ) ,
i ,
khk2

and we only need to find an upper bound for
M
1 X
h
i
FAδ (f1 , f2 , . . . , fM ) = sup
E ψτ h∇f (x? ) ,
khk2
h∈Aδ M m=1
def

3

!!

!

− ψτ

h
h∇fm (x? ) ,
i .
khk2

Because ψα (·) is bounded, we can treat t = 0 as t → 0 to avoid the issue of division by zero.

19

Since ψτ (·) is bounded by 0 and τ , a standard application of the bounded difference inequality
[22] to FAδ (·) shows that for any t > 0 we have
tτ
FAδ (f1 , f2 , . . . , fM ) ≤ EFAδ (f1 , f2 , . . . , fM ) + √ ,
M

(4.3)

with probability ≥ 1 − exp(−2t2 ).
It remains only to upper bound EFAδ (f1 , f2 , . . . , fM ). Writing the inner expectation
in EFAδ (f1 , f2 , . . . , fM ) with respect to random functions fem that are i.i.d. copies of f ,
independent of everything else, we obtain
M
1 X
h
EFAδ (f1 , f2 , . . . , fM ) = E sup
E ψτ h∇f (x? ) ,
i
khk2
h∈Aδ M m=1

!!

!

− ψτ

h
h∇fm (x? ) ,
i
khk2

M
1 X
h
h
≤ E sup
ψτ h∇fem (x? ) ,
i − ψτ h∇fm (x? ) ,
i ,
khk2
khk2
h∈Aδ M m=1

!

!

where in the second line the expectation with respect to the fem is pulled outside of the
supremum. The next step is the standard symmetrization argument [see e.g., 33, Lemma
2.3.1]. Since fm and fem are i.i.d., multiplying each summand in the right-hand side of the
inequality above by a corresponding m = ±1 does not change the distribution of the random
process and thereby the desired expected value. Take 1 , 2 , . . . , M to be i.i.d. Rademacher
random variables independent of everything else. Therefore, we obtain
"

EFAδ (f1 , f2 , . . . , fM ) ≤ E sup

h∈Aδ

M
1 X
h
m ψτ h∇fem (x? ) ,
i
M m=1
khk2

!

!#

−m ψτ

h
i
h∇fm (x? ) ,
khk2

M
1 X
h
≤ E sup
m ψτ h∇fem (x? ) ,
i
khk2
h∈Aδ M m=1

!

M
h
1 X
−m ψτ h∇fm (x? ) ,
i
+ E sup
khk2
h∈Aδ M m=1
M
1 X
h
= 2 E sup
m ψτ h∇fm (x? ) ,
i .
khk2
h∈Aδ M m=1

!

!

(4.4)

Because ψτ (0) = 0 and ψτ (·) is a contraction, we can invoke the Rademacher contraction
principle [19, Theorem 4.12] to show that
M
M
1 X
h
1 X
h
E sup
m ψτ h∇fm (x? ) ,
i ≤ E sup
m h∇fm (x? ) ,
i
khk2
khk2
h∈Aδ M m=1
h∈Aδ M m=1
1
= √ CM (Aδ ) ,
M
where CM (Aδ ) is defined in (2.2) and can be interpreted as a measure of complexity of Aδ
with respect to the law of f . It follows from (4.4) that
2
EFAδ (f1 , f2 , . . . , fM ) ≤ √ CM (Aδ ) .
M

!

20

This bound together with (4.3) guarantees that
2
tτ
FAδ (f1 , f2 , . . . , fM ) ≤ √ CM (Aδ ) + √ ,
M
M
with probability ≥ 1 − exp(−2t2 ). Finally, on the same event, it follows from (4.2) that for
all h ∈ Aδ we have
+
RM
(x? + h) ≥ τ khk2 P (h∇f (x? ) , hi ≥ τ khk2 ) −

M
1 X
(ξm )+
M m=1

2 khk
tτ khk
− √ 2 CM (Aδ ) − √ 2
M
M
M
1 X
2 khk
tτ khk
≥ τ khk2 pτ (Aδ ) −
(ξm )+ − √ 2 CM (Aδ ) − √ 2 .
M m=1
M
M
If x? + h is feasible in (1.4), then
+
+
RM
(x? + h) ≤ RM
(x? ) + ε
M
1 X
(−ξm )+ + ε .
=
M m=1

b denotes a solution to (1.4) and h = x
b − x? , then we have
Therefore, if x

τ khk2 pτ (Aδ ) −

M
1 X
(ξm )+
M m=1

M
2 khk
tτ khk
1 X
− √ 2 CM (Aδ ) − √ 2 ≤
(−ξm )+ + ε ,
M m=1
M
M

or equivalently
2CM (Aδ ) + tτ
√
τ pτ (Aδ ) −
M

!

khk2 ≤

M
1 X
|ξm | + ε .
M m=1

Applying the assumption (2.4) on the left-hand side completes the proof as
2
b − x? k2 = khk2 ≤
kx
τ pτ (Aδ )

M
1 X
|ξm | + ε .
M m=1

!

References
[1] A. Ahmed, B. Recht, and J. Romberg. Blind deconvolution using convex programming.
IEEE Trans. Inform. Theory, 60(3):1711–1732, 2014.
21

[2] S. Bahmani and J. Romberg. Phase retrieval meets statistical learning theory: A flexible
convex relaxation. In A. Singh and J. Zhu, editors, Proceedings of the 20th International
Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine
Learning Research, pages 252–260, Fort Lauderdale, FL, USA, 20–22 Apr 2017. PMLR.
[3] Q. Berthet and P. Rigollet. Complexity theoretic lower bounds for sparse principal
component detection. In Journal of Machine Learning Research W&CP, volume 30 of
Proceedings of the 26th Conference on Learning Theory (COLT’13), pages 1046–1066,
2013.
[4] E. Candès and X. Li. Solving quadratic equations via PhaseLift when there are about
as many equations as unknowns. Found. of Comput. Math., 14:1017–1026, 2014.
[5] E. Candès, T. Strohmer, and V. Voroninski. Phaselift: Exact and stable signal recovery
from magnitude measurements via convex programming. Comm. Pure Appl. Math., 66
(8):1241–1274, 2013.
[6] V. H. de la Peña and E. Giné. Decoupling: From dependence to independence. Probability
and its Applications. Springer-Verlag, New York, 1999.
[7] L. Dümbgen, S. A. van de Geer, M. C. Veraar, and J. A. Wellner. Nemirovski’s inequalities
revisited. American mathematical monthly, 117(2):138–160, 2010.
[8] T. Goldstein and C. Studer. PhaseMax: convex phase retrieval via basis pursuit. preprint
arXiv: 1610.07531 [], Oct. 2016.
[9] P. Hand and V. Voroninski. Compressed sensing from phaseless gaussian measurements
via linear programming in the natural parameter space. preprint arXiv:1611.05985,
2016.
[10] P. Hand and V. Voroninski. Corruption robust phase retrieval via linear programming.
preprint arXiv:1612.03547, 2016.
[11] P. Hand and V. Voroninski. An elementary proof of convex phase retrieval in the natural
parameter space via the linear program PhaseMax. preprint arXiv:1611.03935, 2016.
[12] S. Haykin. Neural Networks and Learning Machines. Pearson, Upper Saddle River, NJ,
USA, 3rd edition, 2009.
[13] C. J. Hillar and L. Lim. Most tensor problems are NP-hard. Journal of the ACM, 60(6):
45:1–45:39, Nov. 2013.
[14] H. Ichimura. Semiparametric least squares (SLS) and weighted SLS estimation of
single-index models. Journal of Econometrics, 58(1):71 – 120, 1993.
[15] I. M. Johnstone and A. Y. Lu. On consistency and sparsity for principal components
analysis in high dimensions. Journal of the American Statistical Association, 104(486):
682–693, 2009.
22

[16] V. Koltchinskii and S. Mendelson. Bounding the smallest singular value of a random
matrix without concentration. International Mathematics Research Notices, 2015(23):
12991–13008, 2015.
[17] G. Lecué and S. Mendelson. Regularization and the small-ball method I: Sparse recovery.
preprint arXiv:1601.05584 [], 2016.
[18] G. Lecué and S. Mendelson. Regularization and the small-ball method II: Complexity
dependent error rates. preprint arXiv:1608.07681 [], 2016.
[19] M. Ledoux and M. Talagrand. Probability in Banach Spaces: Isoperimetry and processes.
Springer Science & Business Media, 2013.
[20] S. Ling and T. Strohmer. Self-calibration and biconvex compressive sensing. Inverse
Problems, 31:115002, 2015.
[21] P. Mccullagh and J. A. Nelder. Generalized linear models, volume 37 of Monographs on
statistics and applied probability. Chapman and Hall/CRC, London ; New York, 2nd
edition, 1989.
[22] C. McDiarmid. On the method of bounded differences. Surveys in combinatorics, 141
(1):148–188, 1989.
[23] S. Mendelson. Learning without concentration. In Proceedings of the 27th Conference
on Learning Theory (COLT), volume 35 of JMLR W&CP, pages 25–39, 2014.
[24] S. Mendelson. Learning without concentration for general loss functions. preprint;
arXiv:1410.3192, 2014.
[25] A. Nemirovski. Topics in Non-parametric Statistics, chapter 5, pages 183–206. Springer
Berlin Heidelberg, Berlin, Heidelberg, 2000.
[26] S. Oymak, A. Jalali, M. Fazel, Y. Eldar, and B. Hassibi. Simultaneously structured
models with application to sparse and low-rank matrices. Information Theory, IEEE
Transactions on, 61(5):2886–2908, 2015.
[27] R. E. A. C. Paley and A. Zygmund. A note on analytic functions in the unit circle.
Mathematical Proceedings of the Cambridge Philosophical Society, 28(3):266–272, 1932.
[28] Y. Plan and R. Vershynin. The generalized LASSO with non-linear observations. IEEE
Transactions on Information Theory, 62(3):1528–1537, Mar. 2016.
[29] Y. Plan, R. Vershynin, and E. Yudovina. High-dimensional estimation with geometric
constraints. Information and Inference, 2016.
[30] S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory
to Algorithms. Cambridge University Press, New York, NY, USA, 2014.
23

[31] C. Stein. A bound for the error in the normal approximation to the distribution of a
sum of dependent random variables. In Proceedings of the Sixth Berkeley Symposium on
Mathematical Statistics and Probability, volume 2 of Probability Theory, pages 583–602,
Berkeley, Calif., 1972. University of California Press.
[32] J. A. Tropp. Convex Recovery of a Structured Signal from Independent Random Linear
Measurements, pages 67–101. Springer International Publishing, Cham, 2015.
[33] A. W. van Der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes.
Springer Series in Statistics. Springer, 1996.
[34] Y. Yu, T. Wang, and R. J. Samworth. A useful variant of the Davis–Kahan theorem for
statisticians. Biometrika, 102(2):315–323, 2014.
[35] H. Zou, T. Hastie, and R. Tibshirani. Sparse principal component analysis. Journal of
Computational and Graphical Statistics, 15(2):265–286, 2006.

24

