Regularization and the small-ball method I: sparse recovery
Guillaume Lecué1,3

Shahar Mendelson2,4,5

arXiv:1601.05584v2 [math.ST] 3 Jan 2017

January 4, 2017
Abstract
We obtain bounds on estimation error rates for regularization procedures of the form
!
N
X
1
2
(Yi − f (Xi )) + λΨ(f )
fˆ ∈ argmin
N i=1
f ∈F
when Ψ is a norm and F is convex.
Our approach gives a common framework that may be used in the analysis of learning
problems and regularization problems alike. In particular, it sheds some light on the
role various notions of sparsity have in regularization and on their connection with the
size of subdifferentials of Ψ in a neighbourhood of the true minimizer.
As ‘proof of concept’ we extend the known estimates for the LASSO, SLOPE and
trace norm regularization.

1

Introduction

The focus of this article is on regularization, which is one of the most significant methods
in modern statistics. To give some intuition on the method and on the reasons behind its
introduction, consider the following standard problem.
Let (Ω, µ) be a probability space and set X to be distributed according to µ. F is a
class of real-valued functions defined on Ω and Y is the unknown random variable that one
would like to approximate using functions in F . Specifically, one would like to identify the
best approximation to Y in F , say in the L2 sense, and find the function f ∗ that minimizes
in F the squared loss functional f → E(f (X) − Y )2 ; that is,
f ∗ = argminf ∈F E(f (X) − Y )2 ,
with the underlying assumption that f ∗ exists and is unique.
Unlike problems in approximation theory, neither the target Y nor the underlying measure µ are known. Therefore, computing the L2 distance between functions in F and Y is
1

CNRS, CREST, ENSAE, 3, avenue Pierre Larousse, 92245 MALAKOFF. France.
Department of Mathematics, Technion, I.I.T., Haifa, Israel and Mathematical Sciences Institute, The
Australian National University, Canberra, Australia
3
Email: guillaume.lecue@ensae.fr
4
Email: shahar@tx.technion.ac.il
5
Supported by the Israel Science Foundation.
2

1

impossible. Instead, one is given partial information: a random sample (Xi , Yi )N
i=1 , selected
independently according to the joint distribution of X and Y .
Because of the random nature of the sample and the limited information it provides,
there is no real hope of identifying f ∗ , but rather, only of approximating it. In an estimation
problem one uses the sample to produce a random function fˆ ∈ F , and the success of the
choice is measured by the distance between fˆ and f ∗ in the L2 (µ) sense. Thus, one would
like to ensure that with high probability with respect to the samples (Xi , Yi )N
i=1 , the error
rate


2
2
= E fˆ(X) − f ∗ (X) |(Xi , Yi )N
fˆ − f ∗
i=1
L2 (µ)

is small. More accurately, the question is to identify the way in which the error rate depends
on the structure of the class F and scales with the sample size N and the required degree
of confidence (probability estimate).
It is not surprising (and rather straightforward to verify) that the problem becomes
harder the larger F is. In contrast, if F is small, chances are that f ∗ (X) is very far from
Y , and identifying it, let alone approximating it, is pointless.
In situations we shall refer to as learning problems, the underlying assumption is that
F is indeed small, and the issue of the approximation error – the distance between Y and
f ∗ is ignored.
While the analysis of learning problems is an important and well-studied topic, the
assumption that F is reasonably small seems somewhat restrictive; it certainly does not
eliminate the need for methods that allow one to deal with very large classes.
Regularization was introduced as an alternative to the assumption on the ‘size’ of F .
One may consider large classes, but combine it with the belief that f ∗ belongs to a relatively
small substructure in F . The idea is to penalize a choice of a function that is far from that
substructure, which forces the learner to choose a function in the ‘right part’ of F .
Formally, let E be a vector space, assume that F ⊂ E is a closed and convex set and
let Ψ : E → R+ be the penalty. Here, we will only consider the case in which Ψ is a norm
on E.
Let λ > 0 and for a sample (Xi , Yi )N
i=1 , set
fˆ ∈ argmin
f ∈F

!
N
1 X
(Yi − f (Xi ))2 + λΨ(f ) ;
N
i=1

fˆ is called a regularization procedure, Ψ is the regularization function and λ is the regularization parameter.
In the classical approach to regularization, the substructure of f ∗ is quantified directly
by Ψ. The underlying belief is that Ψ(f ∗ ) is not ‘too big’ and one expects the procedure
to produce fˆ for which Ψ(fˆ) is of the order of Ψ(f ∗ ). Moreover, the anticipated error rate
kfˆ − f ∗ kL2 (µ) depends on Ψ(f ∗ ). In fact, an optimistic viewpoint is that regularization
could perform as well as the best learning procedure in the class {f : Ψ(f ) ≤ Ψ(f ∗ )}, but
without knowing Ψ(f ∗ ) beforehand.
2

Among the regularization schemes that are based on the classical approach are reproducing kernel Hilbert spaces (RKHS), in which the RKHS norm serves as the penalty. Since
RKHS norms capture various notions of smoothness, in RKHS regularization one is driven
towards a choice of a smooth fˆ – as smooth as f ∗ is.
In more modern regularization problems the situation is very different. Even when
penalizing with a norm Ψ, one no longer cares whether or not Ψ(f ∗ ) is small; rather, one
knows (or at least believes) that f ∗ is sparse in some sense, and the hope is that this sparsity
will be reflected in the error rate.
In other words, although one uses certain norms as regularization functions – norms
that seemingly have nothing to do with ‘sparsity’ – the hope is that the sparse nature of f ∗
will be exposed by the regularization procedure, while Ψ(f ∗ ) will be of little importance.
The most significant example in the context of sparsity-driven regularization is the
celebrated LASSO estimator [33]. Let F = { t, · : t ∈ Rd } and set t∗ to be a minimizer in
Rd of the functional t → E( t, X − Y )2 . The LASSO is defined by
t̂ ∈ argmin
t∈Rd

N
1 X
N
i=1

t, Xi − Yi

2


+ λΨ(t)

Pd

for the choice Ψ(t) = ktk1 = i=1 |ti |.
The remarkable property of the LASSO (see [8] and [3]) is that for a well-chosen regularization parameter λ, if t∗ is supported on at most s coordinates (and under various
assumptions on X and Y to which we will return later), then with high probability,
kt̂ − t∗ k22 .

s log(ed)
.
N

Thus, the error rate of the LASSO does not depend on Ψ(t∗ ) = kt∗ k1 , but rather on the
degree of sparsity of t∗ , measured here by the cardinality of its support kt∗ k0 = |{i : t∗i 6= 0}|.
This fact seems almost magical, because to the naked eye, the regularization function
ktk1 has nothing to do with sparsity; yet ℓ1 regularization leads to a sparsity-driven error
rate.
A standard (yet somewhat unconvincing) explanation of this phenomenon is that the
penalty ktk1 is a convexified version of ktk0 = |{i : ti 6= 0}|, though this loose connection
hardly explains why kt∗ k0 has any effect on the error rate of the LASSO.
A similar phenomenon occurs for other choices of Ψ, such as the SLOPE and tracenorm regularization, which will be explored in detail in what follows. In all these cases
and others like them, the regularization function is a norm that does not appear to be
connected to sparsity, nor to other natural notions of low-dimensional structures for that
matter. Yet, and quite mysteriously, the respective regularization procedure emphasizes
those very properties of t∗ .
The aim of this note is to offer a framework that can be used to tackle standard learning
problems (small F ) and regularized problems alike. Moreover, using the framework, one
may explain how certain norms lead to the emergence of sparsity-based bounds.

3

In what follows we will show that two parameters determine the error rate of regularization problems. The first one captures the ‘complexity’ of each set in the natural hierarchy
in F
Fρ = {f ∈ F : Ψ(f − f ∗ ) ≤ ρ}.
Applying results from [20, 22, 19], the ‘complexity’ of each Fρ turns out to be the optimal
(in the minimax sense) error rate of the learning problem in that set. To be more precise,
the main ingredient in obtaining a sharp error rate of a learning problem in a class H is an
accurate analysis of the empirical excess squared loss functional
f → PN Lf =

N
N
1 X
1 X ∗
(f (Xi ) − Yi )2 −
(f (Xi ) − Yi )2 .
N
N
i=1

(1.1)

i=1

Since the minimizer fˆ of the functional (1.1) satisfies PN Lfˆ ≤ 0, one may obtain an estimate
on the error rate by showing that with high probability, if kf −f ∗ kL2 (µ) ≥ r then PN Lf > 0.
This excludes functions in the set {f ∈ H : kf − f ∗ kL2 (µ) ≥ r} as potential empirical
minimizers. That ‘critical level’ turns out to be the correct (minimax) error rate of a learning
problem in H. That very same parameter is of central importance in regularization problems
— specifically, the ‘critical level’ r(ρ) for each one of the sets {f ∈ F : Ψ(f − f ∗ ) ≤ ρ} (see
Section 2.1 for an accurate definition of r(ρ) and its role in the analysis of learning problems
and regularization problems).
The second parameter, which is the main ingredient in our analysis of regularization
problems, measures the ‘size’ of the subdifferential of Ψ in points that are close to f ∗ : recall
that the subdifferential of Ψ in f is
(∂Ψ)f = {z ∗ ∈ E ∗ : Ψ(f + h) ≥ Ψ(f ) + z ∗ (h) for every h ∈ E}
where E ∗ is the dual space of the normed space (E, Ψ), and that if f 6= 0, the subdifferential
consists of all the norm one linear functionals z ∗ for which z ∗ (f ) = Ψ(f ).
Fix ρ > 0 and let Γf ∗ (ρ) be the collection of functionals that belong to the subdifferential
(∂Ψ)f for some f ∈ F that satisfies Ψ(f − f ∗ ) ≤ ρ/20. Set
Hρ = {f ∈ F : Ψ(f − f ∗ ) = ρ and kf − f ∗ kL2 (µ) ≤ r(ρ)}
and let
∆(ρ) = inf

sup

h∈Hρ z ∗ ∈Γ

f ∗ (ρ)

z ∗ (h − f ∗ ).

/ {f ∈ F : Ψ(f − f ∗ ) ≤ ρ/20}
Hence, Γf ∗ (ρ) is a subset of the unit sphere of E ∗ when 0 ∈
∗
and it is the entire unit ball of E otherwise. And, since Hρ consists of functions whose Ψ
norm is ρ, it is evident that ∆(ρ) ≤ ρ. Therefore, if ∆(ρ) ≥ αρ for a fixed 0 < α ≤ 1 then
Γf ∗ (ρ) is rather large: for every h ∈ Hρ there is some z ∗ ∈ Γf ∗ (ρ) for which z ∗ (h) is ‘almost
extremal’—that is, at least αρ.
Our main result (Theorem 3.2 below) is that if Γf ∗ (ρ) is large enough to
ensure that ∆(ρ) ≥ 4ρ/5, and the regularization parameter λ is set to be of the
4

r 2 (ρ)
ρ ,

then with high probability, the regularized minimizer in F , fˆ,
satisfies that kfˆ − f ∗ kL2 (µ) ≤ r(ρ) and Ψ(fˆ − f ∗ ) ≤ ρ.
order of

Theorem 3.2 implies that one may analyze regularization problems by selecting ρ wisely,
keeping in mind that points in a Ψ-ball of radius ∼ ρ around f ∗ must generate a sufficiently
large subdifferential. And the fact that functionals in Γf ∗ (ρ) need to be ‘almost extremal’
only for points in Hρ rather than for the entire sphere is crucial; otherwise, it would have
forced Γf ∗ (ρ) to be unreasonably large – close to the entire dual sphere.
As will be clarified in what follow, sparsity, combined with the right choice of Ψ, contributes in two places: firstly, if f ∗ is sparse in some sense and Ψ is not smooth on sparse
elements, then Γf ∗ (ρ), which contains the subdifferential (∂Ψ)f ∗ , is large; secondly, for
the right choice of ρ the ‘localization’ Hρ consists of elements that are well placed: if
Ψ(f − f ∗ ) = ρ and kf − f ∗ kL2 (µ) ≤ r(ρ), there is some z ∗ ∈ Γf ∗ (ρ) for which z ∗ (f − f ∗ ) is
large enough. The fact that Hρ is well placed is an outcome of some compatibility between
Ψ and the L2 (µ) norm.
Of course, to find the right choice of ρ one must first identify r(ρ), which is, in itself, a
well-studied yet nontrivial problem.
Before we dive into technical details, let us formulate some outcomes of our main result.
We will show how it can be used to obtain sparsity-driven error rates in three regularization
procedures: the LASSO, SLOPE and trace norm regularization. In all three cases our
results actually extend the known estimates in various directions.
The LASSO.
The LASSO is defined for the class of linear functional F = { t, · : t ∈ Rd }. For a fixed
t0 ∈ Rd , the goal
P is to identify t0 using linear measurements, the regularization function is
Ψ(t) = ktk1 = di=1 |ti |, and the resulting regularization procedure produces
N
1 X
t̂ ∈ argmin
N
t∈Rd
i=1

t, Xi − Yi

2


+ λktk1 .

The LASSO has been studied extensively in the last two decades. Even though some
recent advances [39, 35, 27] have shown the LASSO to have its limitation, historically, it
has been the benchmark estimator of high-dimensional statistics — mainly because a high
dimensional parameter space does not significantly affect its performance as long as t0 is
sparse. This was shown for example, in [3, 15, 36, 37, 17, 26, 34] in the context of estimation
and sparse oracle inequalities, in [16, 40, 2] for support recovery results; and in various other
instances as well; we refer the reader to the books [5, 8] for more results and references on
the LASSO.
SLOPE.
In some sense, SLOPE, introduced in [4, 31], is actually an extension of the LASSO,
even though it has been introduced as an extension of multiple-test procedures. Again,
the underlying class is F = { t, · : t ∈ Rd }, and to define the regularization function let
5

β1 ≥ β2 ≥ ... ≥ βd > 0 and set
Ψ(t) =

d
X

βi t♯i ,

i=1

(t♯i )di=1

where
denotes the non-increasing re-arrangement of (|ti |)di=1 . Thus, the SLOPE
norm is a sorted, weighted ℓ1 -norm, and for (β1 , ..., βd ) = (1, ..., 1), SLOPE regularization
coincides with the LASSO.
Trace-norm regularization.
Consider the trace inner-product on Rm×T . Let F = { A, · : A ∈ Rm×T } and given a
target Y put A∗ to be the matrix that minimizes A → E( A, X − Y )2 . The regularization
function is the trace norm.
Definition 1.1 Let A be a matrix and setP(σi (A)) to be its singular values, arranged in a
non-increasing order. For p ≥ 1, kAkp = ( σip (A))1/p is the p-Schatten norm.

Note that the trace-norm is simply the 1-Schatten norm, the Hilbert-Schmidt norm is the
2-Schatten norm and the operator norm is the ∞-Schatten norm.
The trace norm regularization procedure is
N
1 X

Â ∈ argmin
(Yi − Xi , A )2 + λkAk1
A∈Rm×T N
i=1

and it was introduced for the reconstruction of low-rank, high-dimensional matrices [28, 9,
29, 6, 7, 25].
As will be explained in what follows, our main result holds in rather general situations
and may be implemented in examples once the ‘critical levels’ r(ρ) are identified. Since the
examples we present serve mainly as “proof of concept”, we will focus only on one scenario
in which r(ρ) may be completely characterized for an arbitrary class of functions.
Definition 1.2 Let ℓM
2 be an M -dimensional inner product space and let µ be a measure
on ℓM
.
The
measure
µ
is isotropic if for every x ∈ ℓM
2
2 ,
Z
2
x, t dµ(t) = kxk2ℓM ;
2

it is L-subgaussian if for every p ≥ 2 and every x ∈ ℓM
2 ,

√
k x, · kLp (µ) ≤ L pk x, · kL2 (µ) .

Hence, the covariance structure of an isotropic measure coincides with the inner product in
ℓM
2 , and if µ is an L-subgaussian measure then the Lp (µ) norm of a linear form does not
grow faster than the Lp norm of the corresponding Gaussian variable.

6

Assumption 1.1 Assume that the underlying measure µ is isotropic and L-subgaussian,
and that for f ∗ = t∗ , · (or f ∗ = A∗ , · in the matrix case), the noise1 ξ = f ∗ (X) − Y
belongs to Lq for some q > 2.
When dealing with the LASSO and SLOPE, the natural Euclidean structure is the
standard one in Rd , and for trace norm regularization, the natural Euclidean structure is
endowed by the trace inner product in Rm×T .
Remark 1.3 In the supplementary material we study a general X without assuming it is
isotropic, which means dealing with less natural Euclidean structures in the examples we
present. It is also possible to go beyond the subgaussian case, we refer the reader to [13]
where other moment assumptions on X are considered.
The second part of Assumption 1.1, that ξ ∈ Lq for some q > 2, is rather minimal.
Indeed, for the functional f → E(f (X) − Y )2 to be well defined, one must assume that
f (X) − Y ∈ L2 ; the assumption here is only slightly stronger.
Applying our main result we will show the following:
Theorem 1.4 Consider the LASSO under Assumption 1.1. Let 0 < δ < 1. Assume that
there is some v ∈ Rd supported on at most s coordinates for which
r
log(ed)
∗
.
kt − vk1 ≤ c1 (δ)kξkLq s
N
p
If λ = c2 (L, δ)kξkLq log(ed)/N and N ≥ s log(ed/s), then with probability at least 1 − δ
the LASSO estimator with regularization parameter λ satisfies that for every 1 ≤ p ≤ 2
r
log(ed)
∗
1/p
t̂ − t p ≤ c3 (L, δ)kξkLq s
.
N
The error rate in Theorem 1.4 coincides with the standard estimate on the LASSO (cf. [3]),
but in a broader context: t∗ need not be sparse but only approximated by a sparse vector;
the target Y is arbitrary and the noise ξ may be heavy tailed and need not be independent
of X.
Turning to SLOPE, let us recall the estimates from [31], where the setup is somewhat
restricted: Let X be a Gaussian vector on Rd , set W to be a Gaussian random variable
with variance σ 2 that is independent of X and put Y = t∗ , X + W . Consider some
q ∈ (0, 1), let Φ−1 (α) be the α-th quantile of the standard normal distribution and put
βi = Φ−1 (1 − iq/(2d)).
1
In what follows we will refer to ξ as ‘the noise’ even though it depends in general on Y and X. The
reason for using that term comes from the situation in which Y = f ∗ (X) − W for a symmetric random
variable W that is independent of X (independent additive noise); thus ξ = W . We have opted to call ξ ‘the
noise’ because its role in the general case and its impact on the error rate is rather similar to what happens
for independent noise.

7

Theorem 1.5 [31] Let 1 ≤ s ≤ d satisfy that s/d
√ = o(1) and (s log d)/N = o(1) when
N → ∞. If 0 < ε < 1, N → ∞ and λ = 2σ/ N , the SLOPE estimator with weights
(βi )di=1 and regularization parameter λ satisfies

 N t̂ − t∗ 2
2
>
1
+
3ε
→ 0.
sup P r
2σ 2 s log(d/s)
kt∗ k0 ≤s
Note that Theorem 1.5 is asymptotic in nature and not ‘high-dimensional’. Moreover,
it only holds for a Gaussian X, independent Gaussian noise W , a specific choice of weights
(βi )di=1 and t∗ that is s-sparse.
We consider a more general situation. Let βi ≤ C

p

log(ed/i) and set Ψ(t) =

♯
i=1 βi ti .

Pd

Theorem 1.6 There exists constants c1 , c2 and c3 that depend only on L, δ and C for which
the following holds. Under Assumption 1.1, if there is v ∈ Rd that satisfies |supp(v)| ≤ s
and
 ed 
s
∗
√
,
Ψ(t − v) ≤ c1 kξkLq
log
s
N
√
then for N ≥ c2 s log(ed/s) and with the choice of λ = c2 kξkLq / N , one has
 ed 
 ed 
s
s
2
and
t̂ − t∗ 2 ≤ c3 kξk2Lq log
Ψ(t̂ − t∗ ) ≤ c3 kξkLq √ log
s
N
s
N
with probability at least 1 − δ.
Finally, let us consider trace norm regularization.
Theorem 1.7 Under Assumption 1.1 and if there is V ∈ Rm×T that satisfies that rank(V ) ≤
s and
r
max{m, T }
kA∗ − V k1 ≤ c1 kξkLq s
,
N
q
}
. Then with
one has the following. Let N ≥ c2 s max{m, T } and λ = c3 kξkLq max{m,T
N
probability at least 1 − δ, for any 1 ≤ p ≤ 2
r
max{m, T }
.
Â − A∗ ≤ c4 kξkLq s1/p
N
p
The constants c1 , c2 , c3 and c4 depends only on L and δ.
A result of a similar flavour to Theorem 1.7 is Theorem 9.2 from [8].
Theorem 1.8 Let X be an isotropic and L-subgaussian vector, and W that is mean-zero,
independent of X and belongs to the Orlicz space Lψα for some α ≥ 1. If Y = A∗ , X + W
and
)
(
r
 kξk  √m(t + log N )(t + log m)
m(t + log m)
ψα
1/α
,
, kξkψα log
λ ≥ c1 (L) max kξk2
N
kξkL2
N
then with probability at least 1 − 3 exp(−t) − exp(−c2 (L)N )
2

Â − A∗ ≤ c3 min λ kA∗ k1 , λ2 rank(A∗ ) .
2

8

(1.2)

Clearly, the assumptions of Theorem 1.8 are more restrictive than those of Theorem
1.7, as the latter holds for a heavy tailed ξ that need not be independent of X, and for A∗
that can be approximated by a low-rank matrix. Moreover, if kA∗ k1 is relatively large and
the error rate in Theorem 1.8 is the sparsity-dominated λ2 rank(A∗ ), then the error rate in
Theorem 1.7 is better by a logarithmic factor.
The proofs of the error rates in all the three examples will be presented in Section 5.

1.1

Notation

We end the introduction with some standard notation.
Throughout, absolute constants are denoted by c, c1 ..., etc. Their value may change from
line to line. When a constant depends on a parameter α it will be denoted by c(α). A . B
means that A ≤ cB for an absolute constant c, and the analogous two-sided inequality is
denoted by A ∼ B. In a similar fashion, A .α B implies that A ≤ c(α)B, etc.
Let E ⊂ L2 (µ) be a vector space and set Ψ to be a norm on E. For a set A ⊂ E, t ∈ E
and r > 0, let rA + t = {ra + t : a ∈ A}.
Denote by BΨ = {w ∈ E : Ψ(w) ≤ 1} the unit ball of (E, Ψ) and set SΨ = {f ∈ E :
Ψ(f ) = 1} to be the corresponding unit sphere. BΨ (ρ, f ) is the ball of radius ρ centred in
f and SΨ (ρ, f ) is the corresponding sphere. Also, set D to be the unit ball in L2 (µ), S is
the unit sphere there, and D(ρ, f ) and S(ρ, f ) are the ball and sphere centred in f and of
radius ρ, respectively.
A class of spaces we will be interested in consists of ℓdp , that is, Rd endowed with the ℓp
norm; Bpd denotes the unit ball in ℓdp and S(ℓdp ) is the unit sphere.
For every x = (xi )di=1 , (x♯i )di=1 denotes the non-increasing rearrangement of (|xi |)di=1 .
1 PN
Finally, if (Xi , Yi )N
i=1 is a sample, PN h = N
i=1 h(Xi , Yi ) is the empirical mean of h.

2

Preliminaries: The regularized functional

Let F ⊂ E be a closed and convex class of functions. Recall that for target Y , f ∗ is the
minimizer in F of the functional f → E(f (X) − Y )2 . Since F is closed and convex, the
minimum exists and is unique.
Let Lf (X, Y ) = (f (X) − Y )2 − (f ∗ (X) − Y )2 be the excess squared loss functional and
for λ > 0 let
Lλf (X, Y ) = Lf + λ(Ψ(f ) − Ψ(f ∗ ))
be its regularized counterpart. Thus, for a random sample (Xi , Yi )N
i=1 , the empirical (regularized) excess loss functional is
PN Lλf

N
1 X
=
Lf (Xi , Yi ) + λ(Ψ(f ) − Ψ(f ∗ )),
N
i=1

Note that if ℓf (x, y) = (y − f (x))2 and fˆ minimizes PN ℓf + λΨ(f ) then fˆ also minimizes
PN Lλf . Moreover, since Lλf∗ = 0, it is evident that PN Lλˆ ≤ 0.
f

9

This simple observation shows that the random set {f ∈ F : PN Lλf > 0} may be
excluded from our considerations, as it does not contain potential minimizers. Therefore, if
one can show that with high probability,
{f ∈ F : PN Lλf ≤ 0} ⊂ {f ∈ F : kf − f ∗ kL2 (µ) ≤ r},
then on that event, kfˆ − f ∗ kL2 (µ) ≤ r.
We will identify when PN Lλf > 0 by considering the two parts of the empirical functional:
the empirical excess loss PN Lf and the regularized part λ(Ψ(f ) − Ψ(f ∗ )).
Because of its crucial role in obtaining error estimates in learning problems, the functional f → PN Lf has been studied extensively using the small-ball method, (see, e.g.,
[20, 22, 19]). Thus, the first component in the machinery we require for explaining both
learning problems and regularization problems is well understood and ready-to-use; its details are outlined below.

2.1

The natural decomposition of PN Lf

Set ξ = ξ(X, Y ) = f ∗ (X) − Y and observe that

Lf (X, Y ) =(f − f ∗ )2 (X) + 2(f − f ∗ )(X) · (f ∗ (X) − Y )
=(f − f ∗ )2 (X) + 2ξ(f − f ∗ )(X).

Since F is convex, the characterization of the nearest point map in a Hilbert space shows
that
E(f − f ∗ )(X) · (f ∗ (X) − Y ) ≥ 0

for every f ∈ F . Hence, setting ξi = f ∗ (Xi ) − Yi , one has
PN Lλf

N
N
1 X

1 X
∗ 2
≥
(f − f ) (Xi ) + 2
ξi (f − f ∗ )(Xi ) − Eξ(f − f ∗ )(X)
N
N
i=1

i=1

∗

+λ(Ψ(f ) − Ψ(f )).

To simplify notation, for w ∈ L2 (µ) set Qw = w2 and Mw = ξw − Eξw. Thus, for every
f ∈ F,
(2.1)
PN Lλf ≥ PN Qf −f ∗ + 2PN Mf −f ∗ + λ(Ψ(f ) − Ψ(f ∗ )).
The decomposition of the empirical excess loss to the quadratic component (Qf −f ∗ ) and
the multiplier one (Mf −f ∗ ) is the first step in applying the small-ball method to learning
problems. One may show that on a large event, if kf − f ∗ kL2 (µ) is larger than some critical
level then PN Qf −f ∗ ≥ θkf − f ∗ k2L2 and dominates PN Mf −f ∗ ; hence PN Lf > 0.
To identify this critical level, let us define the following parameters:
Definition 2.1 Let H ⊂ F be a convex class that contains f ∗ . Let (εi )N
i=1 be independent,
symmetric, {−1, 1}-valued random variables that are independent of (Xi , Yi )N
i=1 .
10

For γQ , γM > 0 set
rQ (H, γQ ) = inf

(

r>0:E

sup
h∈H∩D(r,f ∗ )

let
φN (H, s) =
and put

sup
h∈H∩D(s,f ∗ )

N
1 X
εi (h − f ∗ )(Xi ) ≤ γQ r
N
i=1

)

,

N
1 X
√
εi ξi (h − f ∗ )(Xi ) ,
N i=1

o
n

√ 
rM (H, γM , δ) = inf s > 0 : P r φN (H, s) ≤ γM s2 N ≥ 1 − δ .

The main outcome of the small-ball method is that for the right choices of γM and γQ ,
r = max{rM , rQ } is the above-mentioned ‘critical level’ in H, once H satisfies a weak
small-ball condition.
Assumption 2.1 (The small ball condition) Assume that there are constants κ > 0
and 0 < ε ≤ 1, for which, for every f, h ∈ F ∪ {0},

P r |f − h| ≥ κkf − hkL2 (µ) ≥ ε.

There are numerous examples in which the small-ball condition may be verified for κ and ε
that are absolute constants. We refer the reader to [12, 19, 10, 21, 22, 30] for some of them.
Theorem 2.2 ([22]) Let H be a closed, convex class of functions that contains f ∗ and
satisfies Assumption 2.1 with constants κ and ε. If θ = κ2 ε/16 then for every 0 < δ < 1,
with probability at least 1 − δ − 2 exp(−N ε2 /2) one has:
• for every f ∈ H,
|PN Mf −f ∗ | ≤

n
o
θ
2
max kf − f ∗ k2L2 (µ) , rM
(H, θ/10, δ/4) ,
8

• If f ∈ H and kf − f ∗ kL2 (µ) ≥ rQ (H, κε/32) then
PN Qf −f ∗ ≥ θkf − f ∗ k2L2 (µ) .
In particular, with probability at least 1 − δ − 2 exp(−N ε2 /2),
θ
PN Lf ≥ kf − f ∗ k2L2 (µ)
2
for every f ∈ H that satisfies
kf − f ∗ kL2 (µ) ≥ max {rM (H, θ/10, δ/4) , rQ (H, κε/32)} .
From now on, we will assume that F satisfies the small-ball condition with constants κ
and ε, and that θ = κ2 ε/16.
11

Definition 2.3 Let ρ > 0 and set
rM (ρ) = rM F ∩ BΨ (ρ, f ∗ ),

θ δ
,
10 4

and

rQ (ρ) = rQ F ∩ BΨ (ρ, f ∗ ),

κε 
.
32

In what follows we will abuse notation and omit the dependence of rM and rQ on f ∗ , κ, ε
and δ.
Let r(·) be a function that satisfies r(ρ) ≥ supf ∗ ∈F max{rQ (ρ), rM (ρ)}. Finally, put
O(ρ) =

sup
f ∈F ∩BΨ (ρ,f ∗ )∩D(r(ρ),f ∗ )

PN Mf −f ∗ .

Theorem 2.2 implies the following:
Corollary 2.4 ([22]) Using the notation introduced above, on an event of probability at
least 1 − δ − 2 exp(−N ε2 /2), if f ∈ F ∩ BΨ (ρ, f ∗ ) and kf − f ∗ kL2 (µ) ≥ r(ρ) then
θ
PN Lf ≥ kf − f ∗ k2L2 (µ) .
2
Moreover, on the same event,
O(ρ) ≤

θ 2
r (ρ).
8

Remark 2.5 Let us stress once again that r(ρ) plays a central role in the analysis of empirical risk minimization in the set F ∩ BΨ (ρ, f ∗ ). Theorem 2.2 implies that with high
probability, the empirical risk minimizer h̃ in F ∩ BΨ (ρ, f ∗ ) satisfies
kh̃ − h∗ kL2 (µ) ≤ r(ρ).
Moreover, it follows from [11] and [23] that under mild structural assumptions on F , r(ρ)
is the best possible error rate of any learning procedure in F ∩ BΨ (ρ, f ∗ ) – i.e., the minimax
rate in that class.
Let A be the event from Corollary 2.4 and set
γO (ρ) = sup O(ρ).
w∈A

γO will be of little importance in what follows, because it may be upper bounded by
(θ/8)r 2 (ρ). However, it will be of the utmost importance in [13], where complexity-based
regularization is studied (see Section 6 for more details).

3

The main result

Let us turn to the second part of the regularized functional – namely, λ(Ψ(f ) − Ψ(f ∗)). Let
E ∗ be the dual space to (E, Ψ) and set Ψ∗ to be the dual norm. BΨ∗ and SΨ∗ denote the
dual unit ball and unit sphere, respectively; i.e., BΨ∗ consists of all the linear functionals
z ∗ on E for which supΨ(x)=1 |z ∗ (x)| ≤ 1.
12

Definition 3.1 The functional z ∗ ∈ SΨ∗ is a norming functional for z ∈ E if z ∗ (z) = Ψ(z).
In the language of Convex Analysis, a functional is norming for x if and only if it belongs
to (∂Ψ)x , the subdifferential of Ψ in x.
Let Γf ∗ (ρ) be the collection of functionals that are norming for some f ∈ BΨ (ρ/20, f ∗ ).
In particular, Γf ∗ (ρ) contains all the norming functionals of f ∗ .
Set
∆(ρ) = inf
sup z ∗ (h − f ∗ ),
h∈H z ∗ ∈Γ ∗ (ρ)
f

where the infimum is taken in the set
H = F ∩ SΨ (ρ, f ∗ ) ∩ D(r(ρ), f ∗ ) = {h ∈ F : Ψ(h − f ∗ ) = ρ and kh − f ∗ kL2 (µ) ≤ r(ρ)}.
Note that if z ∗ ∈ Γf ∗ (ρ) and h ∈ SΨ (ρ, f ∗ ) then |z ∗ (h − f ∗ )| ≤ Ψ(h − f ∗ ) = ρ. Thus,
a lower bound of the form ∆(ρ) ≥ (1 − δ)ρ implies that Γf ∗ (ρ) is a relatively large subset
of the dual unit sphere: each point in F ∩ SΨ (ρ, f ∗ ) ∩ D(r(ρ), f ∗ ) has an ‘almost norming’
functional in Γf ∗ (ρ).
Our main result is that if Γf ∗ (ρ) is indeed large enough to ensure that ∆(ρ) ≥ 4/5ρ
then with high probability kfˆ − f ∗ kL2 (µ) ≤ r(ρ) and Ψ(fˆ − f ∗ ) ≤ ρ.
Theorem 3.2 Assume that F is closed and convex. Let ρ > 0 and set A to be an event on
which Corollary 2.4 holds. If ∆(ρ) ≥ 4ρ/5 and
3

γO (ρ)
θ r 2 (ρ)
≤λ< ·
,
ρ
2
ρ

then on the event A, a regularized empirical minimizer fˆ ∈ argminf ∈F PN Lλf satisfies
Ψ(fˆ − f ∗ ) ≤ ρ and kfˆ − f ∗ kL2 (µ) ≤ r(ρ).
Moreover, since rO (ρ) ≤ (θ/8)r 2 (ρ), the same assertion holds if
θ r 2 (ρ)
3θ r 2 (ρ)
·
≤λ< ·
.
8
ρ
2
ρ
The proof of the theorem follows in three steps: first, one has to show that PN Lλf is
positive on the set F ∩ SΨ (ρ, f ∗ ). Second, thanks to certain homogeneity properties of the
functional, it is positive in F \BΨ (ρ, f ∗ ), because it is positive on the ‘sphere’ F ∩ SΨ (ρ, f ∗ ).
Finally, one has to study the functional in F ∩ BΨ (ρ, f ∗ ) and verify that it is positive in
that set, provided that kf − f ∗ kL2 (µ) ≥ r(ρ).
Proof. Fix h ∈ F ∩ SΨ (ρ, f ∗ ) and we shall treat two different cases: when kh − f ∗ kL2 (µ) ≥
r(ρ) and when kh − f ∗ kL2 (µ) ≤ r(ρ).
If kh − f ∗ kL2 ≥ r(ρ), then by the triangle inequality for Ψ,
Ψ(h) − Ψ(f ∗ ) = Ψ(h − f ∗ + f ∗ ) − Ψ(f ∗ ) ≥ −Ψ(h − f ∗ ).
13

D(r(ρ), f ∗ )
f∗

SΨ (ρ, f ∗ )
h
f

Hence, for (Xi , Yi )N
i=1 ∈ A and by the upper estimate in the choice of λ,
θ
θ
PN Lλh ≥ kh − f ∗ k2L2 (µ) − λΨ(h − f ∗ ) ≥ r 2 (ρ) − λρ > 0.
2
2

(3.1)

Next, if kh − f ∗ kL2 (µ) ≤ r(ρ) then
PN Lλh ≥ −2O(ρ) + λ(Ψ(h) − Ψ(f ∗ )).
Consider u, v ∈ E that satisfy f ∗ = u + v and Ψ(u) ≤ ρ/20. Let z ∗ be any norming
functional of v; thus, z ∗ ∈ SΨ∗ and z ∗ (v) = Ψ(v). Since Ψ(h) = supx∗ ∈BΨ∗ x∗ (h) it follows
that
Ψ(h) − Ψ(f ∗ ) ≥Ψ(h) − Ψ(v) − Ψ(u) ≥ z ∗ (h − v) − Ψ(u) ≥ z ∗ (h − f ∗ ) − 2Ψ(u).
This holds for any v ∈ BΨ (ρ/20, f ∗ ), and by the definition of ∆(ρ) and for an optimal choice
of z ∗ ,
PN Lλh ≥ −2O(ρ) + λ(z ∗ (h − f ∗ ) − 2Ψ(u)) ≥ −2O(ρ) + λ(∆(ρ) − ρ/10) > 0,

(3.2)

where the last inequality holds because ∆(ρ) ≥ 4ρ/5 and λ ≥ 3γO (ρ)/ρ. Also, since
γO (ρ) ≤ (θ/8)r 2 (ρ), it suffices that λ ≥ (3θ/8)r 2 (ρ)/ρ to ensure that PN Lλh > 0 in (3.2).
This completes the proof of the first step – that PN Lλh > 0 on F ∩ SΨ (ρ, f ∗ ).
Turning to the second step, one has to establish a similar inequality for functions outside
BΨ (ρ, f ∗ ). To that end, let f ∈ F \BΨ (ρ, f ∗ ). Since F is convex and Ψ is homogeneous,
f = f ∗ + α(h − f ∗ ) for some h ∈ F ∩ SΨ (ρ, f ∗ ) and α > 1. Therefore,
PN Qf −f ∗ = α2 PN Qh−f ∗ and PN Mf −f ∗ = αPN Mh−f ∗ ;
moreover, Ψ(f − f ∗ ) = αΨ(h − f ∗ ) and for every functional z ∗ , z ∗ (f − f ∗ ) = αz ∗ (h − f ∗ ).
Thus, by (3.1), when kh − f ∗ kL2 (µ) ≥ r(ρ), PN Lλf > 0, and when kh − f ∗ kL2 (µ) ≤ r(ρ),
PN Lλf ≥ α2 PN Qh−f ∗ + 2αPN Mh−f ∗ + λ(αz ∗ (h − f ∗ ) − 2Ψ(u))

≥ α PN Qh−f ∗ + 2PN Mh−f ∗ + λ(z ∗ (h − f ∗ ) − 2Ψ(u)) > 0.

Finally, when h ∈ F ∩ BΨ (ρ, f ∗ ) and kh − f ∗ kL2 (µ) ≥ r(ρ), (3.1) shows that PN Lλf > 0.
14

Remark 3.3 Note that if ρ ≥ Ψ(f ∗ ) there is no upper limitation on the choice of λ. Indeed,
if kh − f ∗ kL2 (µ) ≥ r(ρ) and Ψ(h) = ρ ≥ Ψ(f ∗ ) then λ(Ψ(h) − Ψ(f ∗ )) ≥ 0, and PN Lλh > 0
just as in (3.1). The rest of the proof remains unchanged.
It follows from the proof that the quadratic component PN Qf −f ∗ and the regularization
one λ(Ψ(f ) − Ψ(f ∗ )) dominate the multiplier component 2PN Mf −f ∗ in different parts of
F . The behaviour of PN Qf −f ∗ allows one to exclude the set (F ∩ Bψ (ρ, f ∗ ))\D(r(ρ), f ∗ ), as
well as any point in F for which the interval [f, f ∗ ] intersects (F ∩ Sψ (ρ, f ∗ ))\D(r(ρ), f ∗ ).
This exclusion is rather free-of-charge, as it holds with no assumptions on the norm Ψ.
The situation is more subtle when trying to exclude points for which the interval [f, f ∗ ]
intersects F ∩ Sψ (ρ, f ∗ ) ∩ D(r(ρ), f ∗ ). That is precisely the region in which the specific
choice of Ψ is important and the regularization component is the reason why PN Lλf > 0.
Figure 1 shows this idea: PN Lλf > 0 for two different reasons: either Q > M – the
quadratic component dominates the multiplier component, or R > M – the regularization
component dominates the multiplier component.
Note that an output of the sparsity equation is that the descent cone TΨ (f ∗ ) = ∪τ >0 {h :
Ψ(f ∗ +τ h) ≤ Ψ(f ∗ )} does not intersect SΨ (ρ, f ∗ )∩D(r(ρ), f ∗ ) when the “sparsity condition”
∆(ρ) ≥ 4ρ/5 is satisfied (cf. Figure 2).
Q>M
R>M

TΨ (f ∗ )

SΨ (ρ, f ∗ )

R>M
D(r(ρ), f ∗ )

Q>M

Q>M
f∗

R>M

f∗

R>M
Q>M

Figure 1: The “Q > M and R > M ” decomposition.

4

Figure 2: TΨ (f ∗ ) ∩ SΨ (ρ, f ∗ ) ∩ D(r(ρ), f ∗ ) = ∅.

The role of ∆(ρ)

It is clear that ∆(ρ) plays a crucial role in the proof of Theorem 3.2, and that the larger
Γf ∗ (ρ) is, the better the lower bound on ∆(ρ).
Having many norming functionals of points in BΨ (ρ/20, f ∗ ) can be achieved somewhat
artificially, by taking ρ ∼ Ψ(f ∗ ). If ρ is large enough, BΨ (ρ/20, f ∗ ) contains a Ψ-ball centred
15

in 0. Therefore, Γf ∗ (ρ) is the entire dual sphere and ∆(ρ) = ρ. This is the situation when
one attempts to derive complexity-based bounds (see Section 6 and [13]), i.e., when one
wishes to find fˆ that inherits some of f ∗ ’s ‘good qualities’ that are captured by Ψ(f ∗ ).
Here, we are interested in cases in which ρ may be significantly smaller than Ψ(f ∗ ) and
enough norming functionals have to be generated by other means.
If Ψ is smooth, each f 6= 0 has a unique norming functional, and for a small ρ, the
norming functionals of points in BΨ (ρ/20, f ∗ ) are close to the (unique) norming functional
of f ∗ ; hence there is little hope that Γf ∗ (ρ) will be large enough to ensure that ∆(ρ) ∼ ρ.
It is therefore reasonable to choose Ψ that is not smooth in f ∗ or in a neighbourhood of f ∗ .
Another important fact is that Γf ∗ (ρ) need not be as large as the entire dual sphere to
ensure that ∆(ρ) ∼ ρ. Indeed, it suffices if Γf ∗ (ρ) contains ‘almost norming’ functionals
only to points that satisfy kwkL2 (µ) ≤ r(ρ)/ρ and Ψ(w) = 1, rather than to every point in
the sphere SΨ .

4.1

∆(ρ) and sparsity

It turns out that the combination of the right notion of sparsity with a wise choice of a
norm Ψ ensures that Γf ∗ (ρ) contains enough ‘almost norming’ functionals precisely for the
subset of the sphere one is interested in.
To give an indication of how this happens, let us show the following:
Lemma 4.1 Let Z ⊂ SΨ∗ , W ⊂ SΨ and 0 < η1 , η2 < 1. If every w ∈ W can be written as
w = w1 + w2 , where Ψ(w1 ) ≤ η1 Ψ(w) and supz ∗ ∈Z z ∗ (w2 ) ≥ (1 − η2 )Ψ(w2 ), then
inf sup z ∗ (w) ≥ (1 − η1 )(1 − η2 ) − η1

w∈W z ∗ ∈Z

In particular, if η1 , η2 ≤ 1/20 then inf w∈W supz ∗ ∈Z z ∗ (w) ≥ 4/5.
Proof. Let w = w1 + w2 and observe that Ψ(w2 ) ≥ Ψ(w) − Ψ(w1 ) ≥ (1 − η1 )Ψ(w). Thus,
for the optimal choice of z ∗ ∈ Z,
z ∗ (w1 + w2 ) ≥(1 − η2 )Ψ(w2 ) + z ∗ (w1 ) ≥ (1 − η2 )Ψ(w2 ) − η1 Ψ(w).

≥ (1 − η1 )(1 − η2 ) − η1 Ψ(w),

and the claim follows because w ∈ SΨ .

Let E = Rd viewed as a class of linear functionals on Rd . Set µ to be an isotropic
2
measure on Rd ; thus {t ∈ Rd : E t, X ≤ 1} = B2d .
Assume that for t ∈ Rd that is supported on I ⊂ {1, ..., d}, the set of its norming
functionals consists of functionals of the form z0∗ + (1 − η2 )u∗ for some fixed z0∗ that is
supported on I and any u ∈ BΨ∗ that is supported on I c (such is the case, for example,
when E = ℓd1 ).
For every such t, consider w ∈ ρSΨ and set w1 = PI w and w2 = PI c w, the coordinate
projections of w onto span(ei )i∈I and span(ei )i∈I c , respectively. Hence, there is a functional
z ∗ = z0∗ + (1 − η2 )u∗ that is norming for t and also satisfies
z ∗ (w2 ) = (1 − η2 )u∗ (w2 ) = (1 − η2 )Ψ(w2 ).
16

Therefore, Lemma 4.1 may be applied once Ψ(PI w) ≤ η1 Ψ(w).
Naturally, such a shrinking phenomenon need not be true for every w ∈ SΨ ; fortunately,
it is only required for w ∈ SΨ ∩ (r(ρ)/ρ)D – and we will show that it is indeed the case
in the three examples we present. In all three, the combination of sparsity and the right
choice of the norm helps in establishing a lower bound on ∆(ρ) in two ways: firstly, the set
Γt∗ (ρ) consists of functionals that are ‘almost norming’ for any x whose support is disjoint
from the support of t∗ ; and secondly, a coordinate projection ‘shrinks’ the Ψ norm of points
in ρSΨ ∩ r(ρ)D.

4.2

∆(ρ) in the three examples

Let us show that in the three examples, the LASSO, SLOPE and trace norm regularization,
∆(ρ) ≥ (4/5)ρ for the right choice of ρ, and that choice depends on the degree of sparsity
in each case.
In all three examples, we will assume that the underlying measure is isotropic; thus the
L2 (µ) norm coincides with the natural Euclidean structure: the ℓd2 norm for the LASSO
and SLOPE, and the Hilbert-Schmidt norm for trace-norm regularization.
The LASSO.
Observe that if f ∗ = t∗ , · is the true minimizer of the functional t, · → E( t, X −Y )2
in F = { t, · : t ∈ Rd }, then any function ht = t, · for which kht − f ∗ kL2 ≤ r(ρ) and
Ψ(ht − f ∗ ) = ρ is of the form ht = t, · = w + t∗ , · , where w ∈ ρS(ℓd1 ) ∩ r(ρ)B2d . Recall
that the dual norm to k · k1 is k · k∞ , and thus
∆(ρ) =

sup

inf

w∈ρS(ℓd1 )∩r(ρ)B2d z∈Γt∗ (ρ)

z, w ,

where Γt∗ (ρ) is the set of all vectors z ∗ ∈ Rd that satisfy
kz ∗ k∞ = 1 and z ∗ (v) = kvk1 for some v for which kv − t∗ k1 ≤ ρ/20.
Lemma 4.2 If t∗ = v+u for u ∈ (ρ/20)B1d and 100|supp(v)| ≤ (ρ/r(ρ))2 then ∆(ρ) ≥ 4ρ/5.
In other words, if t∗ is well approximated with respect to the ℓd1 norm by some v ∈ Rd that
is s-sparse, and s is small enough relative to the ratio (ρ/r(ρ))2 , then ∆(ρ) ≥ (4/5)ρ.
Just as noted earlier, we shall use two key properties of the ℓ1 norm and sparse vectors:
firstly, that if x and y have disjoint supports, there is a functional that is simultaneously
d for which
norming for x and y, i.e., z ∗ ∈ B∞
z ∗ (x) = kxk1 and z ∗ (y) = kyk1 ;

(4.1)

secondly, that if kxk1 = ρ and kxk2 is significantly smaller than ρ, a coordinate projection
‘shrinks’ the ℓd1 norm: kPI xk1 is much smaller than kxk1 .
Proof. Let w ∈ ρS(ℓd1 ) ∩ r(ρ)B2d . Since kt∗ − vk1 ≤ ρ/20 there exists z ∗ ∈ Γt∗ (ρ) that is
norming for v. Moreover, if I = supp(v), then according to (4.1) one can choose z ∗ that is
also norming for PI c w. Thus, kPI c wk1 = z ∗ (PI c w) and
z ∗ (w) = z ∗ (PI w) + z ∗ (PI c w) ≥ kPI c wk1 − kPI wk1 ≥ kwk1 − 2 kPI wk1 .
17

√

√
s kPI wk2 ≤ sr(ρ). Therefore,
√
z, w ≥ ρ − 2 sr(ρ) ≥ 4ρ/5

Since kwk2 ≤ r(ρ), one has kPI wk1 ≤

when 100s ≤ (ρ/r(ρ))2 .
SLOPE.
P
Let β1 ≥ β2 ≥ ... ≥ βd > 0 and recall that Ψ(t) = di=1 βi t∗i .
Note that Ψ(t) = supz∈Z z, t , for
Z=

( d
X

εi βπi ei :

(εi )di=1

i=1

)

d

∈ {−1, 1} , π is a permulation of {1, ..., d} .

P
Therefore, the extreme points of the dual unit ball are of the form di=1 εi βπi ei .
Following the argument outlined above, let us show that if x is supported on a reasonably small I ⊂ {1, ..., d}, the set of norming functionals of x consists of ‘almost norming’
functionals for any y that is supported on I c . Moreover, and just like the ℓd1 norm, if
Ψ(x) = ρ and kxk2 is significantly smaller than ρ, a coordinate projection of x ‘shrinks’ its
Ψ norm.
√
P
Lemma 4.3 Let 1 ≤ s ≤ d and set Bs = i≤s βi / i. If t∗ is ρ/20 approximated (relative
to Ψ) by an s-sparse vector and if 40Bs ≤ ρ/r(ρ) then ∆(ρ) ≥ 4ρ/5.
Proof. Let t∗ = u + v, for v that is supported on at most s coordinates and u ∈ (ρ/20)BΨ .
Set I ⊂ {1, ..., d} to be the support of v and let z = (zi )di=1 be a norming functional for v
to be specified later; thus, z ∈ Γt∗ (ρ).
Given t for which Ψ(t − t∗ ) = ρ and kt − t∗ k2 ≤ r(ρ), one has
z(t − t∗ ) = z(t − v) − z(u) = z(PI c (t − v)) + z(PI (t − v)) − z(u)
X
X
≥
zi (t − v)i +
zi (t − v)i − Ψ(u)
≥

=

i∈I c

i∈I

X

X

i∈I c

X

i∈I c

zi (t − v)i −

zi (t − v)i −

i≤s

X
i≤s

βi (t − v − u)♯i − 2Ψ(u)

βi (t − t∗ )♯i − 2Ψ(u) = (∗).

Since v is supported in I, one may optimize the choice of z by selecting the right permutation
of the coordinates in I c , and
X
X
X
zi (t − v)i ≥
βi (t − v)♯i ≥
βi (t − v − u)♯i − Ψ(u)
i∈I c

=

d
X
i=1

i>s

βi (t − t∗ )♯i −

X
i≤s

i>s

βi (t − t∗ )♯i − Ψ(u).

18

Therefore,
(∗) ≥

d
X
i=1

βi (t − t∗ )♯i − 2

X
i≤s

βi (t − t∗ )♯i − 3Ψ(u) ≥

X
17
ρ−2
βi (t − t∗ )♯i .
20
i≤s

√
Since kt − t∗ k2 ≤ r(ρ), it is evident that (t − t∗ )♯i ≤ r(ρ)/ i, and
s
X
i=1

βi (t

− t∗ )♯i

s
X
β
√i = r(ρ)Bs .
≤ r(ρ)
i
i=1

Hence, if ρ ≥ 40r(ρ)Bs then ∆(ρ) ≥ 4ρ/5.
Trace-norm regularization.
The trace norm has similar properties to the ℓ1 norm. Firstly, one may show that the
dual norm to k · k1 is k · k∞ , which is simply the standard operator norm. Moreover, one
may find a functional that is simultaneously norming for any two elements with ‘disjoint
support’ (and of course, the meaning of ‘disjoint support’ has to be interpreted correctly
here). Finally, it satisfies a ‘shrinking’ phenomenon for matrices whose Hilbert-Schmidt
norm is significantly smaller than their trace norm.
Lemma 4.4 If A∗ = V + U , where kU k1 ≤ ρ/20 and 400rank(V ) ≤ (ρ/r(ρ))2 , then
∆(ρ) ≥ 4ρ/5.
The fact that a low-rank matrix has many norming functionals is well known and follows,
for example, from [38].
Lemma 4.5 Let V ∈ Rm×T and assume that V = PI V PJ for appropriate orthogonal
projections onto subspaces I ⊂ Rm and J ⊂ RT . Then, for every W ∈ Rm×T there is a
matrix Z that satisfies kZk∞ = 1, and
Z, V = kV k1 ,

Z, PI ⊥ W PJ ⊥ = kPI ⊥ W PJ ⊥ k1 ,

Z, PI W PJ ⊥ = 0 and

Z, PI ⊥ W PJ = 0.

Lemma 4.5 describes a similar phenomenon to the situation in ℓd1 , but with a different notion
of ‘disjoint support’: if V is low-rank and the projections PI and PJ are non-trivial, one
may find a functional that is norming both for V and for the part of W that is ‘disjoint’ of
V . Moreover, the functional vanishes on the ‘mixed’ parts PI W PJ ⊥ and PI ⊥ W PJ .
Proof of Lemma 4.4. Recall that S1 is the unit sphere of the trace norm and that B2 is
the unit ball of the Hilbert-Schmidt norm. Hence,
∆(ρ) =

inf

sup

W ∈ρS1 ∩r(ρ)B2 Z∈ΓA∗ (ρ)

Z, W

where ΓA∗ (ρ) is the set of all matrices Z ∈ Rm×T that satisfy kZk∞ = 1 and Z, V
for some V for which kA∗ − V k1 ≤ ρ/20.
19

=1

Fix a rank-s matrix V = PI V PJ , for orthogonal projections PI and PJ that are onto
subspaces of dimension s. Consider W ∈ Rm×T for which kW k1 = ρ and kW k2 ≤ r(ρ) and
put Z to be a norming functional of V as in Lemma 4.5. Thus, Z ∈ ΓA∗ (ρ) and
Z, W = Z, PI ⊥ W PJ ⊥ + Z, PI W PJ = kPI ⊥ W PJ ⊥ k1 − kPI W PJ k1
≥kW k1 − kPI W PJ ⊥ k1 − kPI ⊥ W PJ k1 − 2kPI W PJ k1 .

All that remains is to estimate the trace norms of the three components that are believed
to be ‘low-dimension’ - in the sense that their rank is at most s.
Recall that (σi (A)) are the singular values of A arranged in a non-increasing order.
It is straightforward to verify (e.g., using the characterization of the singular values via
low-dimensional approximation), that
σi (PI W PJ ⊥ ), σi (PI ⊥ W PJ ), σi (PI W PJ ) ≤ σi (W ).
Moreover, kW k2 ≤ r(ρ), therefore, being rank-s operators, one has
kPI W PJ ⊥ k1 , kPI ⊥ W PJ k1 , kPI W PJ k1 ≤
implying that

s
X
i=1

s
1/2 √
√ X
σi (W ) ≤ s
σi2 (W )
≤ sr(ρ),
i=1

√
Z, W ≥ ρ − 4r(ρ) s.

Therefore, if 400s ≤ (ρ/r(ρ))2 , then ∆(ρ) ≥ 4ρ/5.

5

The three examples revisited

The estimates on ∆(ρ) presented above show that in all three examples, when f ∗ is well
approximated by a function whose ‘degree of sparsity’ is . (ρ/r(ρ))2 , then ∆(ρ) ≥ 4ρ/5
and Theorem 3.2 may be used. Clearly, the resulting error rates depend on the right choice
of ρ, and thus on r(ρ).
Because r(ρ) happens to be the minimax rate of the learning problem in the class
F ∩ BΨ (ρ, f ∗ ), its properties have been studied extensively. Obtaining an estimate on r(ρ)
involves some assumptions on X and ξ, and the one setup in which it can be characterized
for an arbitrary class F is when the class is L-subgaussian and ξ ∈ Lq for some q > 2 (though
ξ need not be independent of X). It is straightforward to verify that an L-subgaussian class
satisfies the small-ball condition of Assumption 2.1 for κ = 1/2 and ε = c/L4 where c
is an absolute constant. Moreover, if the class is L-subgaussian, the natural complexity
parameter associated with it is the expectation of the supremum of the canonical Gaussian
process indexed by the class.
Definition 5.1 Let F ⊂ L2 (µ) and set {Gf : f ∈ F } to be the canonical Gaussian process
indexed by F ; that is, each Gf is a centred Gaussian variable and the covariance structure
of the process is endowed by the inner product in L2 (µ). The expectation of the supremum
of the process is defined by
ℓ∗ (F ) = sup{E sup Gf : F ′ ⊂ F is finite}.
f ∈F ′

20

It follows from a standard chaining argument that if F is L-subgaussian then
N
1 X
ℓ∗ (F )
E sup
εi (h − f ∗ )(Xi ) . L √ .
N
f ∈F N
i=1

Therefore, if
Fρ,r = F ∩ BΨ (ρ, f ∗ ) ∩ D(r, f ∗ )

then for every ρ > 0 and f ∗ ∈ F

n
√ o
rQ (ρ) ≤ inf r > 0 : ℓ∗ (Fρ,r ) ≤ C(L)r N .

Turning to rM , we shall require the following fact from [18].

Theorem 5.2 (Corollary 1.10 in [18]) Let q > 2 and L ≥ 1. For every 0 < δ < 1 there
is a constant c = c(δ, L, q) for which the following holds. If H is an L-subgaussian class
and ξ ∈ Lq , then with probability at least 1 − δ,
N
1 X
sup √
εi ξi h(Xi ) ≤ ckξkLq ℓ∗ (H).
N i=1
h∈H

The complete version of Theorem 5.2 includes a sharp estimate on the constant c. However,
obtaining accurate probability estimates is not the main feature of this note and deriving
such estimates leads to a cumbersome presentation. To keep our message to the point, we
have chosen not to present the best possible probability estimates in what follows.
A straightforward application of Theorem 5.2 shows that
n
√ o
rM (ρ) ≤ inf r > 0 : kξkLq ℓ∗ (Fρ,r ) ≤ cr 2 N

for a constant c that depends on L, q and δ.

Recall that we have assumed that X is isotropic, which means that the L2 (µ) norm
coincides with the natural Euclidean structure on the space: the standard ℓd2 norm for the
LASSO and SLOPE and the Hilbert-Schmidt norm for trace norm regularization. Since the
covariance structure of the indexing Gaussian process is endowed by the inner product, it
follows that
ℓ∗ (ρBΨ ∩ rD) = E
sup
G, w
w∈ρBΨ ∩rB2

for the standard Gaussian vector G = (g1 , ..., gd ) in the case of the LASSO and SLOPE and
the Gaussian matrix G = (gij ) in the case of trace norm minimization. Hence, one may
obtain a bound on r(ρ) by estimating this expectation in each case.
The LASSO and SLOPE. Let (βi )di=1 be a non-increasing positive sequence and set
P
Ψ(t) = di=1 t♯i βi .
Since the LASSO corresponds to the choice of (βi )di=1 = (1, ..., 1), it suffices to identify
ℓ∗ (ρBΨ ∩ rB2d ) for the SLOPE norm and a general choice of weights.
21

Lemma 5.3 There exists an absolute constant C for which the following holds. If β and
Ψ are as above, then
)
( r
p
 ed 
log(ed/i)
+ ρ max
E
sup
G, w ≤ C min r (k − 1) log
i≥k
k
k−1
βi
w∈ρBΨ ∩rB d
2

(and if k = 1, the first term is set to be 0).
Proof. Fix 1 ≤ k ≤ d. Let J be the set of indices of the k largest coordinates of (|gi |)di=1 ,
and for every w let Iw be the sets of indices of the k largest coordinates of (|wi |)di=1 . Put
Jw = J ∪ Iw and note that |Jw | ≤ 2k. Hence,
sup

d
X

w∈ρBΨ ∩rB2d i=1

wi gi ≤ sup

.r

X

wi gi + sup

w∈ρBΨ i∈J c

w∈rB2d i∈Jw

X
i<k

(gi♯ )2

!1/2

X

wi gi

w

+ sup

X

w∈ρBΨ i≥k

g♯
wi♯ βi i
βi

.r

X

(gi♯ )2

i<k

!1/2

+ ρ max
i≥k

gi♯
.
βi

As a starting point, note that a standard binomial estimate shows that
 d



p
p
♯
P r i |g| ≥ t log(ed/i)
P r gi ≥ t log(ed/i) ≤
i

≤2 exp(i log(ed/i) − i log(ed/i) · t2 /2).

Applying the union bound one has that for t ≥ 4, with probability at least 1−2 exp(−(t2 /2)k log(ed/k)),
p
(5.1)
gi♯ ≤ c3 t log(ed/i) for every i ≥ k.

The same argument shows that E(gi♯ )2 . log(ed/i).
Let Uk be the set of vectors on the Euclidean sphere that are supported on at most k
coordinates. Set
X
1/2
kxk[k] =
(x♯i )2
= sup x, u
u∈Uk

i≤k

and recall that by the Gaussian concentration of measure theorem (see, e.g., Theorem 7.1
in [14]),
1/q

√
√
≤ EkGk[k] + c q sup k G, u kL2 ≤ EkGk[k] + c1 q.
EkGkq[k]
u∈Uk

Moreover, since

E(gi♯ )2

. log(ed/i), one has
1/2 p
 X
EkGk[k] ≤ E
(gi♯ )2
. k log(ed/k).
i≤k

Therefore, by Chebyshev’s inequality for q ∼ k log(ed/k), for t ≥ 1, with probability at
least 1 − 2t−c1 k log(ed/k) ,
1/2
X
p
(gi♯ )2
≤ c2 t k log(ed/k).
i≤k

22

Turning to the ‘small coordinates’, by (5.1),
gi♯
max
. t max
i≥k βi
i≥k

p

log(ed/i)
.
βi

It follows that for every choice of 1 ≤ k ≤ d,
gi♯
E
sup
G, w . rE
+ ρE max
i≥k βi
w∈ρBΨ ∩rB2d
i<k
p
p
log(ed/i)
,
.r (k − 1) log(ed/(k − 1)) + ρ max
i≥k
βi
X

(gi♯ )2

1/2

and, if k = 1, the first term is set to be 0.

d
√ If β = (1, ..., 1) (which corresponds
√ to the LASSO), then BΨ = B1 , and one may select
k ∼ ρ/r, provided that r ≤ ρ ≤ r d. In that case,
p
E
sup
G, w . ρ log(edr 2 /ρ2 ).
w∈ρB1d ∩rB2d

√
The estimates when r ≥ ρ or r d ≤ ρ are straightforward. Indeed, if r ≥ ρ then ρB1d ⊂ rB2d
and
p
ℓ∗ (ρB1d ∩ rB2d ) = ℓ∗ (ρB1d ) ∼ ρ log(ed),
√
while if r d ≤ ρ then rB2d ⊂ ρB1d , and
√
ℓ∗ (ρB1d ∩ rB2d ) = ℓ∗ (rB2d ) ∼ r d.
The LASSO.
A straightforward computation shows that

kξk2Lq d



N

2
rM (ρ) .L,q,δ
r
 ekξk d 


L

1
 ρ kξkL
√ q
log
N
q
ρ N
and

2
rQ
(ρ)

.L

(

ρ2
N

log

0


c(L)d
N



if ρ2 N &L,q,δ kξk2Lq d2
otherwise,

if N &L d
otherwise.

Proof of Theorem 1.4. We will actually prove a slightly stronger result, which gives an
improved estimation error if one has prior information on the degree of sparsity.
Using the estimates on rM and rQ , it is straightforward to verify that the sparsity
condition of Lemma 4.2 holds when N &L,q,δ s log(ed/s) and for any
r
 ed 
1
ρ &L,q,δ kξkLq s
.
log
N
s
23

It follows from Lemma 4.2 that if there is an s-sparse vector that belongs to t∗ + (ρ/20)B1d ,
then ∆(ρ) ≥ 4ρ/5. Finally, Theorem 3.2 yields the stated bounds on kt̂ − t∗ k1 and kt̂ − t∗ k2
once we set
r
 ed 
1
r 2 (ρ)
λ∼
.
∼L,q,δ kξkLq
log
ρ
N
s
The estimates on kt̂ − t∗ kp for 1 ≤ p ≤ 2 can be easily verified because
−1+2/p

kxkp ≤ kxk1

2−2/p

kxk2

.

In case one has no prior information on s, one may take
r
1
log(ed)
ρ ∼L,q,δ kξkLq s
N
and
λ ∼L,q,δ kξkLq

r

log(ed)
.
N

The rest of the argument remains unchanged.
SLOPE
p
Assume that βi ≤ C log(ed/i), which is the standard assumption for SLOPE [4, 31].
By considering the cases k = 1 and k = d,
√
(5.2)
G, w . min{Cρ, dr}.
E
sup
w∈ρBΨ ∩rB2d

Thus, one may show that
2
rQ
(ρ) .L


 0


ρ2
N

if N &L d
2
and rM
(ρ) .L,q,δ

otherwise,


2 d

 kξkLq N

if ρ2 N &L,q,δ kξk2Lq d2


 kξkL √ρ
q
N

otherwise.

p
√
P
Proof of Theorem 1.6. Recall that Bs = i≤s βi / i, and when βi ≤ C log(ed/i), one
may verify that
p
Bs . C s log(ed/s).

Hence, the condition Bs . ρ/r(ρ) holds when N &L,q,δ s log(ed/s) and
 ed 
s
.
ρ &L,q,δ kξkLq √ log
s
N

It follows from Lemma 4.3 that ∆(ρ) ≥ 4ρ/5 when there is an s-sparse vector in t∗ +
(ρ/20)BΨ ; therefore, one may apply Theorem 3.2 for the choice of
λ∼

kξkL
r 2 (ρ)
∼L,q,δ √ q .
ρ
N

24

The trace-norm.
Recall that B1 is the unit ball of the trace norm, that B2 is the unit ball of the HilbertSchmidt norm, and that the canonical Gaussian vector here is the Gaussian matrix G =
(gij ). Since the operator norm is the dual to the trace norm,
p
ℓ∗ (B1 ) = Eσ1 (G) . max{m, T },
and clearly,

ℓ∗ (B2 ) = E kGk2 .

√

mT .

Thus,
p
√

ℓ∗ (ρBΨ ∩ rB2 ) = ℓ∗ (ρB1 ∩ rB2 ) ≤ min ρℓ∗ (B1 ), rℓ∗ (B2 ) . min{ρ max{m, T }, r mT }.

Therefore,

2
rQ
(ρ) .L



0
}
ρ2 max{m,T
N

if N &L mT
otherwise,

and
2
rM
(ρ) .L,q,δ







kξk2Lq
ρkξkLq

q

mT
N

if ρ2 N &L,q,δ kξk2Lq mT (min {m, T })2

max{m,T }
N

otherwise.

Proof of Theorem 1.7. It is straightforward to verify that if N &L,q,δ s max{m, T } then
s . (ρ/r(ρ))2 when
r
max{m, T }
ρ &L,q,δ kξkLq s
N
as required in Lemma 4.4. Moreover, if there is some V ∈ Rm×T for which kV − A∗ k1 . ρ
and rank(V ) ≤ s, it follows that ∆(ρ) ≥ 4ρ/5. Setting
r
max{m, T }
r 2 (ρ∗ )
,
∼L,q,δ kξkLq
λ∼
∗
ρ
N
Theorem 3.2 yields the bounds on kÂ − A∗ k1 and kÂ − A∗ k2 . The bounds on the Schatten
−1+2/p
2−2/p
norms kÂ − A∗ kp for 1 ≤ p ≤ 2 hold because kAkp ≤ kAk1
kAk2
.

6

Concluding Remarks

As noted earlier, the method we present may be implemented in classical regularization
problems as well, leading to an error rate that depends on Ψ(f ∗ ) – by applying the trivial
bound on ∆(ρ) when ρ ∼ Ψ(f ∗ ).
The key issue in classical regularization schemes is the price that one has to pay for not
knowing Ψ(f ∗ ) in advance. Indeed, given information on Ψ(f ∗ ), one may use a learning
procedure taking values in {f ∈ F : Ψ(f ) ≤ Ψ(f ∗ )} such as Empirical Risk Minimization.
This approach would result in an error rate of r(cΨ(f ∗ )), and the hope is that the error rate
25

of the regularized procedure is close to that – without having prior knowledge on Ψ(f ∗ ).
Surprisingly, as we show in [13], that is indeed the case.
The problem with applying Theorem 3.2 to the classical setup is the choice of λ. One has
no information on Ψ(f ∗ ), and thus setting λ ∼ r 2 (ρ)/ρ for ρ ∼ Ψ(f ∗ ) is clearly impossible.
A first attempt of bypassing this obstacle is Remark 3.3: if ρ & Ψ(f ∗ ), there is no upper
2
constraint on the choice of λ. Thus, one may consider λ ∼ supρ>0 r ρ(ρ) , which suits any
ρ > 0. Unfortunately, that choice will not do, because in many important examples the
supremum happens to be infinite. Instead, one may opt for the lower constraint on λ and
select
γO (ρ)
,
(6.1)
λ ∼ sup
ρ
ρ>0
which is also a legitimate choice for any ρ, and is always finite.
We will show in [13] that the choice in (6.1) leads to optimal bounds in many interesting
examples – thanks to the first part of Theorem 3.2.
An essential component in the analysis of regularization problems is bounding r(ρ),
and we only considered the subgaussian case and completely ignored the question of the
probability estimate. In that sense, the method we presented falls short of being completely
satisfactory.
Addressing both these issues requires sharp upper estimates on empirical and multiplier
processes, preferably in terms of some natural geometric feature of the underlying class.
Unfortunately, this is a notoriously difficult problem. Indeed, the final component in the
chaining-based analysis used to study empirical and multiplier processes is to translate
a metric complexity parameter (e.g., Talagrand’s γ-functionals) to a geometric one (for
example, the mean-width of the set). Such estimates are known almost exclusively in the
Gaussian case – which is, in a nutshell, Talagrand’s Majorizing Measures theory [32].
The chaining process in [18] is based on a more sensitive metric parameter than the
standard Gaussian one. This leads to satisfactory results for other choices of random vectors that are not necessarily subgaussian, for example, unconditional log-concave random
vectors. Still, it is far from a complete theory – as a general version of the Majorizing
Measures Theorem is not known.
Another relevant fact is from [24]. It turns out that if V is a class of linear functionals
on Rd that satisfies a relatively minor symmetry property, and X is an isotropic random
vector for which
√
(6.2)
sup k X, t kLp ≤ L p for 2 ≤ p . log d,
t∈S d−1

then the empirical and multiplier processes indexed by V behave as if X were a subgaussian
vector. In other words, for such “symmetric” problems it suffices to have a subgaussian
moment growth up to p ∼ log d to ensure a subgaussian behaviour.
This fact is useful because all the indexing sets considered here (and in many other
sparsity-based regularization procedures as well) satisfy the required symmetry property.
Finally, a word about the probability estimate in Theorem 5.2. The actual result from
[18] leads to a probability estimate governed by two factors: the Lq space to which ξ belongs

26

and the ‘effective dimension’ of the class. For a class of linear functionals on Rd and an
isotropic vector X, this effective dimension is
 ∗

ℓ (V ) 2
D(V ) =
,
d2 (V )
where ℓ∗ (V ) = E supv∈V | G, v | and d2 (V ) = supv∈V kvkℓd .
2
One may show that with probability at least
1 − c1 w−q N −((q/2)−1) logq N − 2 exp(−c2 u2 D(V )),
N

1 X
sup √
ξi V, Xi − Eξ X, v
. LwukξkLq ℓ∗ (V ).
N i=1
v∈V

(6.3)

If ξ has better tail behaviour, the probability estimate improves; for example, if ξ is subgaussian then (6.3) holds with probability at least 1 − 2 exp(−cw2 N ) − 2 exp(−cu2 D(V )).
The obvious complication is that one has to obtain a lower bound on the effective dimension D(V ). And while it is clear that D(v) & 1, in many cases (including our three
examples) a much better bound is true.
Let us mention that the effective dimension is perhaps the most important parameter in
Asymptotic Geometric Analysis. Milman’s version of Dvoretzky’s Theorem (see, e.g., [1])
shows that D(V ) captures the largest dimension of a Euclidean structure hiding in V . In
fact, this geometric observation exhibits why that part of the probability estimate in (6.3)
cannot be improved.

References
[1] Shiri Artstein-Avidan, Apostolos Giannopoulos, and Vitali D. Milman. Asymptotic geometric analysis. Part I, volume 202 of Mathematical Surveys and Monographs. American Mathematical Society,
Providence, RI, 2015.
[2] Francis R. Bach. Structured sparsity-inducing norms through submodular functions. In Advances in
Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing
Systems 2010. Proceedings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada.,
pages 118–126, 2010.
[3] Peter J. Bickel, Ya’acov Ritov, and Alexandre B. Tsybakov. Simultaneous analysis of lasso and Dantzig
selector. Ann. Statist., 37(4):1705–1732, 2009.
[4] Malgorzata Bogdan, Ewout van den Berg, Chiara Sabatti, Weijie Su, and Emmanuel J. Candès.
SLOPE—Adaptive variable selection via convex optimization. Ann. Appl. Stat., 9(3):1103–1140, 2015.
[5] Peter Bühlmann and Sara van de Geer. Statistics for high-dimensional data. Springer Series in Statistics.
Springer, Heidelberg, 2011. Methods, theory and applications.
[6] Emmanuel J. Candès and Yaniv Plan. Tight oracle inequalities for low-rank matrix recovery from a
minimal number of noisy random measurements. IEEE Trans. Inform. Theory, 57(4):2342–2359, 2011.
[7] David Gross. Recovering low-rank matrices from few coeﬃcients in any basis. IEEE Trans. Inform.
Theory, 57(3):1548–1566, 2011.
[8] 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, École d’Été de Probabilités de Saint-Flour.
[Saint-Flour Probability Summer School].

27

[9] Vladimir Koltchinskii, Karim Lounici, and Alexandre B. Tsybakov. Nuclear-norm penalization and
optimal rates for noisy low-rank matrix completion. Ann. Statist., 39(5):2302–2329, 2011.
[10] Vladimir Koltchinskii and Shahar Mendelson. Bounding the Smallest Singular Value of a Random
Matrix Without Concentration. Int. Math. Res. Not. IMRN, (23):12991–13008, 2015.
[11] Guillaume Lecué and Shahar Mendelson. Learning subgaussian classes: Upper and minimax bounds.
Technical report, CNRS, Ecole polytechnique and Technion, 2013.
[12] Guillaume Lecué and Shahar Mendelson. Sparse recovery under weak moment assumptions. Technical report, CNRS, Ecole Polytechnique and Technion, 2014. To appear in Journal of the European
Mathematical Society.
[13] Guillaume Lecué and Shahar Mendelson. Regularization and the small-ball method ii: complexity-based
bounds. Technical report, CNRS, ENSAE and Technion, I.I.T., 2015.
[14] Michel Ledoux. The concentration of measure phenomenon, volume 89 of Mathematical Surveys and
Monographs. American Mathematical Society, Providence, RI, 2001.
[15] Karim Lounici. Sup-norm convergence rate and sign concentration property of Lasso and Dantzig
estimators. Electron. J. Stat., 2:90–102, 2008.
[16] Nicolai Meinshausen and Peter Bühlmann. High-dimensional graphs and variable selection with the
lasso. Ann. Statist., 34(3):1436–1462, 2006.
[17] Nicolai Meinshausen and Bin Yu. Lasso-type recovery of sparse representations for high-dimensional
data. Ann. Statist., 37(1):246–270, 2009.
[18] Shahar Mendelson. Upper bounds on product and multiplier empirical processes. Technical report. To
appear in Stochastic Processes and their Applications.
[19] Shahar Mendelson. Learning without concentration for general loss function. Technical report, Technion, I.I.T., 2013. arXiv:1410.3192.
[20] Shahar Mendelson. Learning without concentration. In Proceedings of the 27th annual conference on
Learning Theory COLT14, pages pp 25–39. 2014.
[21] Shahar Mendelson. A remark on the diameter of random sections of convex bodies. In Geometric
aspects of functional analysis, volume 2116 of Lecture Notes in Math., pages 395–404. Springer, Cham,
2014.
[22] Shahar Mendelson. Learning without concentration. J. ACM, 62(3):Art. 21, 25, 2015.
[23] Shahar Mendelson. ’local vs. global parameters’, breaking the gaussian compexity barrier. Technical
report, Technion, I.I.T., 2015.
[24] Shahar Mendelson. On multiplier processes under weak moment assumptions. Technical report, Technion, I.I.T., 2015.
[25] Sahand Negahban and Martin J. Wainwright. Restricted strong convexity and weighted matrix completion: optimal bounds with noise. J. Mach. Learn. Res., 13:1665–1697, 2012.
[26] Sahand N. Negahban, Pradeep Ravikumar, Martin J. Wainwright, and Bin Yu. A uniﬁed framework for
high-dimensional analysis of M -estimators with decomposable regularizers. Statist. Sci., 27(4):538–557,
2012.
[27] Richard Nickl and Sara van de Geer. Conﬁdence sets in sparse regression. Ann. Statist., 41(6):2852–
2876, 2013.
[28] Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. Guaranteed minimum-rank solutions of linear
matrix equations via nuclear norm minimization. SIAM Rev., 52(3):471–501, 2010.
[29] Angelika Rohde and Alexandre B. Tsybakov. Estimation of high-dimensional low-rank matrices. Ann.
Statist., 39(2):887–930, 2011.
[30] Mark Rudelson and Roman Vershynin. Small ball probabilities for linear images of high dimensional
distributions. Technical report, University of Michigan, 2014. International Mathematics Research
Notices, to appear. [arXiv:1402.4492].

28

[31] Weijie Su and Emmanuel Candès. SLOPE is adaptive to unknown sparsity and asymptotically minimax.
Ann. Statist., 44(3):1038–1068, 2016.
[32] Michel Talagrand. Upper and lower bounds for stochastic processes, volume 60 of Ergebnisse der
Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results
in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics]. Springer,
Heidelberg, 2014. Modern methods and classical problems.
[33] Robert Tibshirani. Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser. B,
58(1):267–288, 1996.
[34] Sara van de Geer. Weakly decomposable regularization penalties and structured sparsity. Scand. J.
Stat., 41(1):72–86, 2014.
[35] Sara van de Geer, Peter Bühlmann, Ya’acov Ritov, and Ruben Dezeure. On asymptotically optimal
conﬁdence regions and tests for high-dimensional models. Ann. Statist., 42(3):1166–1202, 2014.
[36] Sara A. van de Geer.
The deterministic lasso.
http://www.stat.math.ethz.ch/ geer/lasso.pdf.

Technical report, ETH Zürich, 2007.

[37] Sara A. van de Geer. High-dimensional generalized linear models and the lasso. Ann. Statist., 36(2):614–
645, 2008.
[38] G. Alistair Watson. Characterization of the subdiﬀerential of some matrix norms. Linear Algebra Appl.,
170:33–45, 1992.
[39] Cun-Hui Zhang and Stephanie S. Zhang. Conﬁdence intervals for low dimensional parameters in high
dimensional linear models. J. R. Stat. Soc. Ser. B. Stat. Methodol., 76(1):217–242, 2014.
[40] Peng Zhao and Bin Yu. On model selection consistency of Lasso. J. Mach. Learn. Res., 7:2541–2563,
2006.

7

Supplementary material: non-isotropic design

An inspection of Theorem 3.2 reveals no mention of an isotropicity assumption. There is
no choice of a Euclidean structure, and in fact, the statement itself is not even finite dimensional. All that isotropicity has been used for was to bound the “complexity function” r(·)
and the “sparsity function” ∆(·) in the three applications — the LASSO (in Theorem 1.4),
SLOPE (in Theorem 1.6) and the trace norm regularization (in Theorem 1.7). We may
apply Theorem 3.2 to situations that do not involve an isotropic vector and here we give
an example of how this may be done.
To simplify our presentation we will only consider ℓ1 and SLOPE regularization, which
may both be written as
d
X
βj t♯j ,
Ψ(t) =
j=1

where β1 ≥ · · · ≥ βd > 0 and t♯1 ≥ · · · ≥ t♯d ≥ 0 is the nondecreasing rearrangement of
(|tj |). As mentioned previously, the LASSO
case is recovered for β1 = · · · = βd = 1 and the
p
SLOPE norm is obtained for βj = C log(ed/j) for some constant C. We also denote by
BΨ (resp. SΨ ) the unit ball (resp. sphere) associated with the Ψ-norm.
Let Σ ∈ Rd×d be the covariance matrix of X and set D = {x ∈ Rd : Σ1/2 x 2 ≤ 1} to
be the corresponding ellipsoid. Naturally, if X is not isotropic than Σ is not the identity
matrix.

29

In order to apply Theorem 3.2, we need to bound from above the expectation of the
supremum of the Gaussian process indexed by ρBΨ ∩ rD:
ℓ∗ (ρBΨ ∩ rD) = E

Σ1/2 G, w

sup

(7.1)

w∈ρBΨ ∩rD

where G is a standard Gaussian vector in Rd .
We also need to solve the “sparsity equation”—that is, find ρ∗ > 0 for which ∆(ρ∗ ) ≥
∗
4ρ /5 where, for every ρ > 0,
∆(ρ) =

inf

sup

h∈ρSΨ ∩rD g∈Γ ∗ (ρ)
t

h, g

and Γt∗ (ρ) is the collection of all subgradients of Ψ of vectors in t∗ + (ρ/20)BΨ .
We will show that the same results that have been obtained for the LASSO and SLOPE
in Theorem 1.4 and Theorem 1.6 actually hold under the following assumption.
1/2

Assumption 7.1 Let j ∈ {1, ..., d} and denote by Σj• the j-th row of Σ1/2 . Let s ∈
P
√
{1, . . . , d} and set Bs = sj=1 βj / j.
1/2

1. There exists σ > 0 such that for all j ∈ {1, . . . , d}, Σj•

2. For all x ∈ (20Bs SΨ ) ∩ D, 2 Σ1/2 x

2

2

≤ σ.

≥ sup|J|≤s kxJ k2 .

SLOPE.
We first control the Gaussian mean width in (7.1) when Ψ(·) is the SLOPE norm.
p
Lemma 7.1 Set βj = C log(ed/j) and let Σ be a d × d symmetric nonnegative matrix for
1/2

which maxj Σj•

E

2

≤ σ. If D = {x ∈ Rd : Σ1/2 x

sup
w∈ρBΨ ∩rD

Σ

1/2

G, w ≤ min

(

ρ
C

2

≤ 1} then

)
√
r !
√
3 6σ
π
+r
,r d
8
2

Proof. Note that
E

sup
w∈ρBΨ ∩rD

Σ

1/2

G, w ≤ rE sup G, Σ
w∈D

1/2

w = rE kGk2 ≤ r



E kGk22

1/2

√
≤ r d.


Next, let H : Rd → R be defined by H(u) = sup Σ1/2 u, w : w ∈ ρBΨ ∩ rD and recall
that G is the standard Gaussian vector in Rd . It is straightforward to verify that
H(G) ≤ sup

w∈ρBΨ

Σ

1/2

ξj♯
ρ
max p
G, w ≤
C 1≤j≤d log(ed/j)
30

where we set (ξj )dj=1 = Σ1/2 G and (ξj♯ )dj=1 is the non-increasing rearrangement of (|ξj |)dj=1 .
Observe that for u, v ∈ Rd ,
|H(u) − H(v)| ≤

sup
w∈ρBΨ ∩rD

| Σ1/2 (u − v), w | ≤ r sup | u − v, w | = r ku − vk2 ,
w∈B2d

implying that H is a Lipschitz function with constant r; thus, it follows from p. 21 in
Chapter 1 of [14] that
r
π
EH(G) ≤ Med(H(G)) + r
,
(7.2)
2
where Med(H(G)) is the median of H(G).
Hence, to obtain the claimed bound on E supw∈ρBΨ Σ1/2 G, w it suffices to establish
a suitable upper estimate on the median of max1≤j≤d √

ξj♯
log(ed/j)

. With that in mind, let

ξ1 , . . . , ξN be mean-zero Gaussian variables and assume that for every j = 1, . . . , d,
E exp(ξj2 /L2 ) ≤ e

(7.3)

for some L > 0. Note that in our case, ξ1 , . . . , ξN satisfying (7.3) for L = 3σ/8.
By Jensen’s inequality,
!
!
 2
j
j
d
♯
(ξk♯ )2
ξk
1X
1X
ed
1 X (ξk )2
E exp
E exp
≤
≤
≤ ;
E exp
2
2
2
j
L
j
L
j
L
j
k=1

k=1

k=1

hence,
j

Pr

♯
1 X (ξk )2
≥ 2 log (ed/j)
j
L2
k=1

!

≤ exp (− log (ed/j)) =

j
.
ed

(7.4)

Let q ≥ 0 be the integer that satisfies 2q ≤ d < 2q+1 . It follows from (7.4) that with
probability at least
q−1 ℓ
X
2
2q − 1
1
1−
=1−
> ,
ed
ed
2
ℓ=0

for every ℓ = 0, · · · , q − 1,

ℓ

(ξ2♯ ℓ )2

2
1 X ♯ 2
≤ ℓ
(ξj ) ≤ 2L2 log(ed/2ℓ ).
2
j=1

Moreover, for 2ℓ ≤ j < 2ℓ+1 , we have ξj♯ ≤ ξ2♯ ℓ and log(ed/2ℓ ) ≤ 2 log(ed/j); also for

2q ≤ j ≤ d, we have ξj♯ ≤ ξ2♯ q−1 and log(ed/2ℓ ) ≤ 3 log(ed/j). Therefore,
Pr

max p

1≤j≤d

ξj♯
log(ed/j)

proving the requested bound on Med(H(G)).
31

≤

√

6L

!

1
> ,
2

(7.5)

Observe that up to constant σ, we actually recover the same result as in (5.2); therefore,
one may choose the same “complexity function” r(·) as in the proof of Theorem 1.6.
Let us turn to a lower bound on the “sparsity function”.
Lemma 7.2 There exists an absolute
constant 0 < c < 80 for which the following holds.
P
√
Let s ∈ {1, . . . , d} and set Bs = j≤s βj / j. Assume that for every x ∈ (80Bs Sψ ) ∩ D one
has Σ1/2 x 2 ≥ (1/2) sup|J|≤s kxJ k2 . Let ρ > 0 and assume further that there is a s-sparse
vector in t∗ + (ρ/20)BΨ . If 80Bs ≤ ρ/r(ρ) then
∆(ρ) =

inf

sup

h∈ρSΨ ∩r(ρ)D g∈Γt∗ (ρ)

h, g ≥

4ρ
.
5

Proof. Let h ∈ ρSΨ ∩ r(ρ)D and denote by (h♯j ) the non-increasing rearrangement of (|hj |).
It follows from the proof of Lemma 4.3 that
X
17ρ
sup h, g ≥
−2
βj h♯j .
20
g∈Γt∗ (ρ)
j≤s

Let h♯,s be the s-sparse vector with coordinates given by h♯j for 1 ≤ j ≤ s and 0 otherwise.
We have




r(ρ)
1
h
∈ SΨ ∩
D
D ⊂ SΨ ∩
ρ
ρ
80Bs
√
implying that 2 Σ1/2 h 2 ≥ h♯,s 2 . Furthermore, since h♯j ≤ h♯ 2 / j for every 1 ≤ j ≤ s,
we have
X
βj h♯j ≤ h♯,s Bs ≤ 2Bs Σ1/2 h ≤ 2Bs r(ρ).
2

2

j≤s

Hence, if ρ ≥ 80r(ρ)Bs then ∆(ρ) ≥ 4ρ/5.

We thus recover the same condition as in Lemma 4.3, implying that Theorem 1.6 actually holds under the weaker Assumption 7.1: let X be an L-subgaussian random vector
whose covariance matrix satisfies
Assumption 7.1. The SLOPE estimator with regulariza√
tion parameter λ ∼ kξkLq / N satisfies, with probability at least 1 − δ − exp(−c0 N L8 ),
 ed 
s
and
Ψ(t̂ − t∗ ) ≤ c3 kξkLq √ log
s
N

Σ1/2 (t̂ − t∗ )

2
2

≤ c3 kξk2Lq

 ed 
s
log
N
s

when N ≥ c4 s log(ed/s) and when there is a s-sparse vector close enough to t∗ .
The LASSO.
P
√
√
Here, for every 1 ≤ j ≤ d, βj = 1; BΨ = B1d ; and Bs = sj=1 1/ j ≤ 2 s.

1/2

Lemma 7.3 Let Σ be a d × d symmetric nonnegative matrix for which maxj Σj•

If D = {x ∈ Rd : Σ1/2 x
E

≤ 1} then every ρ > 0 and r > 0,
o
n √
p
Σ1/2 G, w ≤ min r d, ρσ log(ed) .
sup
2

w∈ρB1d ∩rD

32

2

≤ σ.

Proof. Note that
E

sup
w∈ρB1d ∩rD

1/2

√
Σ1/2 G, w ≤ rE sup G, Σ1/2 w = rE kGk2 ≤ r E kGk22
≤ r d.
w∈D

Next, set (ξj )dj=1 = Σ1/2 G and let (ξj♯ )dj=1 be the non-increasing rearrangement of (|ξj |).
Therefore, ξ1 , . . . , ξd are mean-zero Gaussian variables and satisfy E exp(ξj2 /L2 ) ≤ e for
L = 3σ/8. It is evident that

!
!!
!
d
X
ξj2
(ξ1♯ )2
(ξ1♯ )2
 ≤ log (ed) ,
E exp
≤ log E exp
≤ log 
E
L2
L2
L2
j=1

and therefore,
E

sup
w∈ρB1d ∩rD

1/2 3ρσL p

Σ1/2 G, w ≤ E sup Σ1/2 G, w ≤ ρE (ξ1♯ )2
≤
log (ed).
8
w∈ρB d
1

Lemma 7.3 leads to a slightly different result than in the isotropic case (Lemma 5.3), and
as a consequence, r(·) has to be slightly modified. A straightforward computation shows
that
!
r
kξkLq d
log(ed)
2
rM (ρ) .L,q,δ min
, ρσ kξkLq
N
N
and
2
rQ
(ρ)

.L

(

ρ2 σ2
N

0

log c(L)d
N

if N &L d
otherwise.

and still r(ρ) = max{rM (ρ), rQ (ρ)}.
Finally, let us prove the sparsity condition.

Lemma 7.4 There exists an absolute
constant 0 < c < 80 for which the following holds.

P
√
Let s ∈ {1, . . . , d} and set Bs = j≤s 1/ j. Assume that for every x ∈ 20Bs S(ℓd1 ) ∩ D
one has Σ1/2 x 2 ≥ (1/2) sup|J|≤s kxJ k2 . Let ρ > 0 and assume further that there is a
s-sparse vector in t∗ + (ρ/20)B1d . If 20Bs ≤ ρ/r(ρ) then
∆(ρ) =

inf

sup

h∈ρS(ℓd1 )∩r(ρ)D g∈Γt∗ (ρ)

h, g ≥

4ρ
.
5

Proof. Let h ∈ ρS(ℓd1 ) ∩ r(ρ)D and denote by (h♯j ) the non-increasing rearrangement of
(|hj |). It follows from the proof of Lemma 4.2 that
X ♯
sup h, g ≥ ρ − 2
hj .
g∈Γt∗ (ρ)

j≤s

33

Let h♯,s be the s-sparse vector with coordinates given by h♯j for 1 ≤ j ≤ s and 0 otherwise.
Observe that




r(ρ)
1
h
d
d
∈ S(ℓ1 ) ∩
D,
D ⊂ S(ℓ1 ) ∩
ρ
ρ
40Bs
and therefore 2 Σ1/2 h 2 ≥ h♯,s
It follows that
X ♯ √
hj ≤ s h♯
j≤s

2

2

.
≤ Bs h♯

2

≤ 2Bs Σ1/2 h

2

≤ 2Bs r(ρ),

and in particular, if ρ ≥ 20r(ρ)Bs then ∆(ρ) ≥ 4ρ/5.

Using the estimate on r(·) and Lemma 7.4, it is evident that when N &L,q,δ sσ 2 log(ed),
one has ∆(ρ∗ ) ≥ 4ρ∗ /5 for
r
log(ed)
∗
ρ ∼L,q,δ kξkLq s
N
and if there is a s-sparse vector in t∗ + (ρ∗ /20)B1d .
Finally, one may choose the regularization parameter by setting
r
log(ed)
r 2 (ρ∗ )
∼L,q,δ kξkLq s
.
λ∼
∗
ρ
N
It follows that if X is an L-subgaussian random vector that satisfies Assumption 7.1 then
with probability larger than 1 − δ − 2 exp(−c0 N L8 ),
r
r
log(ed)
s log(ed)
1/2
∗
∗
∗
∗
and Σ (t̂ − t ) ≤ r(ρ ) = c2 (L, δ) kξkLq
.
t̂ − t 1 ≤ ρ = c1 (δ) kξkLq s
N
N
2

34

