Regularization and the small-ball method II: complexity dependent error
rates
Guillaume Lecué1,3,5

Shahar Mendelson2,4,6

arXiv:1608.07681v1 [math.ST] 27 Aug 2016

August 30, 2016
Abstract
For a convex class of functions F , a regularization functions Ψ(·) and given the random data
(Xi , Yi )N
i=1 , we study estimation properties of regularization procedures of the form
fˆ ∈ argmin
f ∈F

N

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

for some well chosen regularization parameter λ.
We obtain bounds on the L2 estimation error rate that depend on the complexity of the “true model”
F ∗ := {f ∈ F : Ψ(f ) ≤ Ψ(f ∗ )}, where f ∗ ∈ argminf ∈F E(Y − f (X))2 and the (Xi , Yi )’s are independent
and distributed as (X, Y ). Our estimate holds under weak stochastic assumptions – one of which being
a small-ball condition satisfied by F – and for rather flexible choices of regularization functions Ψ(·).
Moreover, the result holds in the learning theory framework: we do not assume any a-priori connection
between the output Y and the input X).
As a proof of concept, we apply our general estimation bound to various choices of Ψ, for example,
the ℓp and Sp -norms (for p ≥ 1), weak-ℓp, atomic norms, max-norm and SLOPE. In many cases, the
estimation rate almost coincides with the minimax rate in the class F ∗ .

1

Introduction

In the standard learning framework, one would like to approximate / predict an unknown random variable
Y using functions from a given class F , and to do so using only random data. To be more accurate, let
(X , µ) be a probability space and consider a class of functions F on (X , µ). Let X be distributed according
to µ and set X1 , . . . , XN ∈ X to be N independent copies of X.
Given an unknown random variable Y , let D = (Xi , Yi )N
i=1 be a sample selected according to the joint
distribution of (X, Y ). One would like to use the data D and construct a (random) function fˆ(·) = fˆ(D, ·) ∈
F , with fˆ(X) serving as a good guess of Y .
While there are various interpretations of the meaning of ‘a good guess’, the notion we will focus on
here is as follows.
1

CNRS, CREST, ENSAE, Bureau E31, 3 avenue Pierre Larousse, 92245 Malakoﬀ.
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 Chaire Havas-Dauphine ”Economie des nouvelles données” and by Investissements d’Avenir (ANR-11-IDEX0003/Labex Ecodec/ANR-11-LABX-0047)
6
Supported by the Israel Science Foundation, grant 707/14.
2

1

In a typical problem, very little is assumed on the target Y or on the measure µ; on the other hand,
the class F is known and a typical assumption is that F is convex and closed in L2 (µ). Therefore, the
functional f → E(f (X) − Y )2 has a unique minimizer in F ,
f ∗ = argmin E(Y − f (X))2 .

(1.1)

f ∈F

The notion of ‘a good guess’ is that fˆ is close to f ∗ in L2 (µ), and one would like to obtain a high
probability bound on the L2 (µ) distance of the form
h
2
2 i
= E f ∗ (X) − fˆ(X) |D ≤ α2N .
fˆ − f ∗
(1.2)
L2

In this case, α2N is called a rate of convergence, the error rate or the L2 (µ)-estimation rate of the problem.

Clearly, one has to pay a price for allowing a rather general target Y . Also, to have any hope that f ∗
is reasonably close to Y , one has to consider large classes, leading to an error α2N that is often too large to
be of any use.
A possible way of bypassing the fact that F may be very large, is the classical approach to regularization,
where a certain property one believes f ∗ to possess is emphasized by penalizing functions that do not have
that property. The penalty is endowed via a regularization function Ψ(·), defined on an appropriate
subspace E ⊂ L2 (µ) that contains F , and for which Ψ(f ∗ ) is believed to be small (though one does not
know that for certain). As a consequence, regularization procedures are designed to fit the data and to
have a small Ψ value at the same time. One way of achieving that is to search for functions in F that
realize a good trade-off between fitting that data, which is measured via an empirical loss function PN ℓf ,
and the size of the regularization term λΨ(f ).
Definition 1.1 The Regularized Empirical Risk Minimization procedure (RERM) is defined by

fˆ ∈ argmin PN ℓf + λΨ(f ) ,

(1.3)

f ∈F

where here and throughout the article, PN h denotes the empirical mean of h, ℓf is the loss function
associated with f and λ is the so-called regularization parameter.
We only consider the square loss ℓf (x, y) = (y − f (x))2 , and thus,
PN ℓf =

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

A well known example to this, the “classical approach” to regularization, is the cubic smoothing spline
that can be obtained with the choice
Z
Ψ(f ) = f ′′ (t)dt.
Another well-studied example is of the form

Ψ(f ) =

Z

Rd

f¯(t)
dt
Ḡ(t)

where the integration is with respect to the Lebesgue measure, f¯ is the Fourier transform of f and Ḡ is
some positive function tending to zero when |t| goes to infinity (cf. [20]). In fact, this type of regularization
2

methods dates back to Tikhonov ([52]) and is sometimes called Tikhonov regularization; it is also known
as L2 -regularization or Ridge regularization ([21]).
These methods and others like them have been used to “smooth” estimators that have poor generalization capability because of their tendency to over-fit the data, and for the corresponding regularization
functions, having a small Ψ value is a guarantee of smoothness. We refer to [24] for other examples of
regularization functions that have been used to “smooth” estimators.
We said “classical approach to regularization” because in the more modern approach the aim is somewhat different. One uses a penalty that seemingly has little to do with the property one wishes to emphasize
(usually, some notion of sparsity). Yet somehow, almost “magically”, the penalty enhances a hidden property and the resulting error rate does not depend on Ψ(f ∗ ) but on that hidden property of f ∗ . We call
such error rates sparsity-dependent error rates.
The first part of this article ([31]) has dealt with the modern approach to regularization. Here we
would like to complete the picture by exploring bounds that depend on Ψ(f ∗ ) rather than on some hidden
sparsity structure of f ∗ . Such error rates will be called complexity-dependent error rates, since
the aim is to obtain rates of convergence that depend on the complexity of the unknown “true model”
{f ∈ F : Ψ(f ) ≤ Ψ(f ∗ )}. Of course, the two approaches may sometimes be combined advantageously (see
some examples below).
In this context, we will consider regularization functions that satisfy the following properties, which
are more general than the ones considered in [31].
Assumption 1.1 A function Ψ : E → R+ is a regularization function if
• It is nonnegative, even, convex and Ψ(0) = 0.
• There is a constant η ≥ 1, for which, for every f, h ∈ E,
Ψ(f + h) ≤ η(Ψ(f ) + Ψ(h)).
• For every 0 ≤ α ≤ 1 and h ∈ E, Ψ(αh) ≤ αΨ(h).
Remark 1.2 Classical Model Selection regularization functions, such as the cardinality of the support of
a vector or the rank of a matrix, are usually not convex and do not satisfy Assumption 1.1. Such examples
are therefore not considered in what follows.

1.1

Classical vs. modern

As mentioned above, the direction we take here is closely related to the classical approach to regularization
and is rather different from the modern approach. To explain the differences we shall use the celebrated
LASSO estimator (cf. [51, 15]) as an example.
Let F be a class of linear functionals on Rd of the form t, · . Set t∗ ∈ argmint∈Rd E(Y − X, t )2 , and
P
consider the RERM (1.3) with the ℓd1 -norm, ktk1 = di=1 |ti |, serving as a regularization function. Let
N
1 X

2
t̂ ∈ argmin
+ λ ktk1 ,
Yi − Xi , t
N
t∈Rd
i=1

and the resulting minimizer is the LASSO estimator.

3

Estimation, de-noising, prediction and support recovery results have been obtained for the LASSO in
the last decades (see, for example, [51], [3], and the books [19, 5] and [26] for additional references).
The LASSO has been used in ‘high-dimensional’ problems, in which the aim was to enhance a lowdimensional structure. The hope was that if the signal t∗ were sparse (that is, supported on relatively
few coordinates), the regularization procedure t̂ would estimate t∗ with an error rate depending on the
cardinality of the support of t∗ , denoted by kt∗ k0 = |{j ∈ {1, . . . , d} : t∗j 6= 0}|.
However, if t∗ happens to be ‘well-spread’ rather than sparse, though with a reasonable ℓd1 norm, the
sparsity-dependent error rate is useless, while a complexity-dependent error rate, which yields bounds in
terms of kt∗ k1 , is sharper. The obvious example is t∗1 = (1/d, ..., 1/d) and t∗2 = (1, 0, ..., 0): although
kt∗1 k1 = kt∗2 k1 = 1, the cardinalities of their supports are very different, and sparsity-dependent error rates
when t∗ = t∗1 are likely to be bad.
Examples of that nature are the reason why error rates combining both sparsity and complexity have
been obtained for the LASSO. A typical example is Corollary 9.1 in [26]. To formulate it, Let W1 , · · · , WN
be N independent, centered subgaussian variables with variance
deterministic
P σ and set x1 , . . . , xN to be N √
vectors in Rd . Assume that “design matrix”, Γ = N −1/2 N
N , satisfies
x
,
·
e
,
whose
rows
are
x
/
i
i
i
i=1
∗
some Restricted Isometry Property (cf. [9]). If Yi = xi , t + Wi , i = 1, . . . , N , then for a well chosen
regularization parameter λ, one has, with high probability,
(
)
r
2 kt∗ k log d
σ
log
d
2
0
E X, t̂ − t∗ ≤ C min
, σ kt∗ k1
(1.4)
n
n
for a suitable absolute constant C.
the sparsity-dependent error term σ 2 (kt∗ k0 log d)/n,
The error rate from (1.4) consists of two components:
p
and the complexity-dependent error term σ kt∗ k1 (log d)/n, and in what follows we will present a few
other examples that combine the two rates – because the procedure one uses to obtain both types of rate
is the same.
The aim of this article is to address the “complexity-based” aspect of the problem: to study regularization problems in which one believes that the Ψ(f ∗ ) is relatively small, and obtain an error rate that
depends on Ψ(f ∗ ) rather than on some sparsity property of f ∗ .

1.2

Attaining Minimax rates

A natural benchmark for measuring the success of a regularization method is the minimax error rate,
assuming that Ψ(f ∗ ) is known: if one is given additional information on Ψ(f ∗ ), e.g., that f ∗ ∈ {f : Ψ(f ) ≤
R}, one may consider the estimation problem in {f : Ψ(f ) ≤ R} using the given random data. Such a
problem has an optimal error rate (called the minimax rate): it is the best rate any learning procedure
may achieve in the class {f : Ψ(f ) ≤ R} given the random data (Xi , Yi )N
i=1 . This minimax rate will serve
as our benchmark, and will be compared with the error rates that we obtain.
Of course, one is not given additional information on Ψ(f ∗ ) and it is reasonable to expect that the
error rate of the regularization procedure will be significantly slower than this benchmark. The question
we shall study here focuses on that gap. In fact, we will show that the price one has to pay for not knowing
Ψ(f ∗ ) is surprisingly small, under rather weak assumptions.
From a technical perspective, all regularization-based procedures share one crucial aspect: the calibration of the regularization parameter λ. That choice is very important as λ is an essential component
in ensuring that the error rate of the estimator fˆ is well-behaved. Thus, to study the gap between the
regularization error rate and the minimax rate, one has to identify the right choice of λ.
4

Question 1.3 What is the ‘correct choice’ of the regularization parameter λ, and given that choice, what
is the rate of convergence of RERM? Specifically, how far is the resulting rate from the one that could have
been achieved had Ψ(f ∗ ) been given in advance?
An answer to Question 1.3 requires one to identify λ; to find a high probability upper bound on kfˆ−f ∗ k2L2 (µ)
for that choice of λ; and then to compare the error rate to the minimax rate of the estimation problem in
the “true model” {f : Ψ(f ) ≤ Ψ(f ∗ )}.
The strategy we use below follows a similar path to [31] and is based on the small ball method,
introduced in [40, 39, 28, 37].

1.3

The small-ball method

Given a closed and convex class F and an unknown target Y , recall that f ∗ ∈ F is a minimizer in F of the
functional f → E(f (X) − Y )2 .
The excess loss functional associated with f ∈ L2 (µ) is
f → Lf (X, Y ) =ℓf (X, Y ) − ℓf ∗ (X, Y ) = (f (X) − Y )2 − (f ∗ (X) − Y )2
=(f − f ∗ )2 (X) + 2(f ∗ (X) − Y )(f − f ∗ )(X).

(1.5)

Moreover, since F is closed and convex, then by the characterization of the nearest point map in a Hilbert
space,
E(f ∗ (X) − Y )(f − f ∗ )(X) ≥ 0 for every f ∈ F ;
thus
N
N
1 X ∗
1 X ∗
(f (Xi ) − Yi )(f − f ∗ )(Xi ) ≥
(f (Xi ) − Yi )(f − f ∗ )(Xi ) − E(f ∗ (X) − Y )(f − f ∗ )(X). (1.6)
N
N
i=1

i=1

Let E be a subspace that contains F and set Ψ(·) to be a regularization function on E (i.e., a functional
that satisfies Assumption 1.1). Set ρ ≥ 0 and put
Kρ (f ∗ ) = {h ∈ E : Ψ(h − f ∗ ) ≤ ρ},
which, by the convexity of Ψ, is a convex set.
Definition 1.4 For every λ > 0 and any f ∈ L2 (µ), define the regularized excess loss by
Lλf = (ℓf + λΨ(f )) − (ℓf ∗ + λΨ(f ∗ )) = Lf + λ (Ψ(f ) − Ψ(f ∗ )) .
ˆ
Note that for every sample (Xi , Yi )N
i=1 , a minimizer f of the empirical regularized loss functional (1.3)
also minimizes in F the empirical regularized excess loss f → PN Lλf . Hence, since Lλf∗ = 0, it follows that
ˆ
for every (Xi , Yi )N
i=1 , the empirical regularized excess loss in f is non-positive:
PN Lλfˆ ≤ 0.

(1.7)

This observation is at the heart of our analysis, as it allows one to exclude functions f in F that satisfy
PN Lλf > 0 as potential minimizers of the empirical regularized loss function. Our strategy is therefore to
show that if f ∈ F and kf − f ∗ kL2 (µ) is not ‘too small’, then necessarily PN Lλf > 0 (for the right choice of
λ); hence, functions cannot be minimizers of the empirical regularized (excess) loss function.
5

To simplify notation, set ξ = Y − f ∗ (X),
Mf −f ∗ (X, Y ) = ξ(f − f ∗ )(X) − Eξ(f − f ∗ )(X) and Qf −f ∗ (X) = (f − f ∗ )2 (X);
therefore, combining (1.5) and (1.6),
PN Lf ≥ PN Qf −f ∗ − 2 |PN Mf −f ∗ | .

(1.8)

The main step in the small-ball method is to find a lower bound on the quadratic process f → PN Qf −f ∗
and an upper bound on f → |PN Mf −f ∗ |. The two estimates should hold with high probability on certain
subsets of F . Then, they have to be compared with the behaviour of the regularization term λ(Ψ(f )−Ψ(f ∗ ))
on those sets to ensure that PN Lλf > 0.
A uniform lower bound on the quadratic component PN Qf −f ∗ can be obtained under a weak assumption
called the small-ball condition:
Assumption 1.2 Assume that there are constants κ > 0 and 0 < ε ≤ 1, for which, for every f, h ∈ F ,

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

There are numerous examples in which Assumption 1.2 may be verified for κ and ε that are absolute
constants and we refer the reader to [39, 40, 30, 37, 28, 47] for some of them.
To put assumption 1.2 on X in some perspective, recall that the class F = {ft = ·, t : t ∈ Rd } is
identifiable if for every t1 , t2 ∈ Rd , P r(ft1 6= ft2 ) > 0, (where the probability is taken with respect to
the underlying measure µ). By linearity, this condition is equivalent to assuming that for every t ∈ Rd ,
P r(| X, t | > 0) > 0. Thus, the small-ball condition is simply a uniform estimate on the degree of
identifiability of class F and is therefore a rather weak assumption.
Now, let us introduce two complexity parameters that play a central role in our analysis. Let D be the
unit ball in L2 (µ) and for r > 0 set
rDf ∗ = {f ∈ L2 (µ) : kf − f ∗ kL2 (µ) ≤ r} = f ∗ + rD.
Definition 1.5 Given a class F of functions and τ > 0, let
(
∗

rQ (F, τ ) = rQ (F, f , τ ) = inf

r>0:E

sup

f ∈F ∩rDf ∗

N
1 X
εi (f − f ∗ )(Xi ) ≤ τ r
N
i=1

)

,

where (εi )N
i=1 are independent, symmetric, {−1, 1}-valued random variables that are also independent of
(Xi , Yi )N
i=1 .
Set
N
1 X
√
(1.9)
εi ξi (f − f ∗ )(Xi )
φN (F, f ∗ , s) = sup
N i=1
f ∈F ∩sDf ∗
and put

n

o
√ 
rM (F, τ, δ) = rM (F, f ∗ , τ, δ) = inf s > 0 : P r φN (F, f ∗ , s) ≤ τ s2 N ≥ 1 − δ .

One may show the following (see Theorem 3.1 in [40]):
6

Theorem 1.6 Let F be a closed, convex class of functions that satisfies Assumption 1.2 with constants κ
and ε, and set θ = κ2 ε/16. For every δ ∈ (0, 1), with probability at least 1 − δ − 2 exp(−N ε2 /2) one has
both:
• for every f ∈ F ,

|PN Mf −f ∗ | ≤

n
o
θ
2
max kf − f ∗ k2L2 (µ) , rM
(F, θ/5, δ/4) ,
4

• for every f ∈ F with kf − f ∗ kL2 (µ) ≥ rQ (F, κε/32),

PN Qf −f ∗ ≥ θkf − f ∗ k2L2 (µ) .
In particular, with probability at least 1 − δ − 2 exp(−N ε2 /2), PN Lf ≥ 2θ kf − f ∗ k2L2 (µ) for every f ∈ F that
satisfies
kf − f ∗ kL2 (µ) ≥ max {rM (F, θ/5, δ/4) , rQ (F, κε/32)} .
Remark 1.7 An immediate outcome of Theorem 1.6 is that with high probability, a minimizer in F of the
empirical excess-loss functional PN Lf must satisfy
kf˜ − f ∗ kL2 (µ) ≤ max {rM (F, θ/5, δ/4) , rQ (F, κε/32)} .

(1.10)

In fact, results from [29] show that (1.10) is optimal in the minimax sense under additional mild
technical assumptions on F when the data are assumed to satisfied the Gaussian regression model, that is,
when the targets are of the form Y = f0 (X) + W for f0 ∈ F and W that is a centered Gaussian random
variable, independent of X. Empirical risk minimization performed in the set
F ∗ = {f ∈ F : Ψ(f ) ≤ Ψ(f ∗ )}
yields

kf˜ − f ∗ kL2 ≤ max {rM (F ∗ , θ/5, δ/4) , rQ (F ∗ , κε/32)} ,

(1.11)

and the r.h.s. of (1.11) is the minimax rate of the estimation problem in F ∗ (up to the technical assumptions
mentioned earlier); it will serve as a benchmark for the performance of the regularization procedure (1.3).

1.4

The Main result

Let F ∩ Kρ (f ∗ ) = {f ∈ F : Ψ(f − f ∗ ) ≤ ρ} and observe that these are convex subsets of F . To simplify
notation, set




2
∗ κ ε δ
∗ κε
rM (ρ) = rM F ∩ Kρ (f ),
and rQ (ρ) = rQ F ∩ Kρ (f ),
,
(1.12)
,
80 4
32
and let r(·) be a function that satisfies for every ρ ≥ 0
r(ρ) ≥ max{rM (ρ), rQ (ρ)}.

(1.13)

It should be noted that r(ρ) may depend on f ∗ , and that it does depend on other parameters – like δ, κ
and ε. We will not specify the dependence on those parameters, but rather, only on the radius ρ.
The geometry of the sets F ∩ Kρ (f ∗ ) (see Figure 1) determine both the error rate and the regularization
parameter λ, and r(ρ) measures the sets’ ‘sizes’.
The choice of λ is made as follows:
7

rDf ∗
f∗

Kρ (f ∗ ) ∩ F

Figure 1: Localization of the set F ∩ Kρ (f ∗ ), i.e. its intersection with L2 (µ)-balls of various radii r for the
right choice of radius ρ, plays a central role in the analysis of the quadratic and multiplier processes.
Let



O(ρ) = sup |PN Mf −f ∗ | : f ∈ F ∩ Kρ (f ∗ ) ∩ r(ρ)Df ∗

and for τ > 0 and 0 < δ < 1, set

γO (ρ, τ, δ) = inf {x > 0 : P r (O(ρ) ≤ τ x) ≥ 1 − δ}
and
γO (ρ) = γO (ρ, 3/(80η 3 ), δ).
In other words, γO (ρ) is proportional to the smallest possible upper estimate on O(ρ) that still holds with
probability at least 1 − δ.
Definition 1.8 For any τ > 0 and 0 < δ < 1, set
λ0 (δ, τ ) =

sup
ρ>0,f ∗ ∈F

γO (ρ, τ, δ)
.
ρ

To compare λ0 (δ, τ ) with rQ and rM , first note that rM (ρ) and O(ρ) both depend on properties of
the multiplier processes indexed by localizations of F ∩ Kρ (f ∗ ), and recall that symmetrized and centered
2 (ρ); moreover, γ (ρ) is
processes are essentially equivalent. Second, if r(ρ) = rM (ρ) then γO (ρ) ∼ rM
O
2
trivially bounded by ∼ r (ρ) for the right choice of τ and δ. However, if rM (ρ) ≤ rQ (ρ), that is, when
r(ρ) = rQ (ρ) – which is the case when ρ is very large – one may find that γO (ρ) is actually significantly
smaller than ∼ r 2 (ρ). This observation is of crucial importance because of the choice of the regularization
parameter: for the right choice of τ , γO (ρ) ≤ r 2 (ρ) and
λ0 (δ, τ ) ≤

sup

r 2 (ρ)/ρ;

ρ>0,f ∗ ∈F

thus, one may be tempted to select the latter as a regularization term. However, there are natural examples
in which supρ>0 r 2 (ρ)/ρ = ∞, rendering that choice impossible, whereas supρ>0,f ∗ ∈F γO (ρ)/ρ turns out to
be finite. Of course, there are still cases in which supρ>0,f ∗ ∈F r 2 (ρ)/ρ is finite, and λ0 (δ, τ ) is of the same
2 (ρ)/ρ, though that is not the generic situation.
order as supρ>0,f ∗ ∈F rM
We now come to the main result of the article.

8

Theorem 1.9 Let F be a closed, convex class of functions that satisfies Assumption 1.2 with constants κ
and ε. Set Ψ(·) to be a regularization function that satisfies Assumption 1.1 with constant η. Furthermore,
assume that limρ→0 r(ρ) = 0 and put λ > λ0 (δ, 3/(80η 3 )).
If fˆ is the RERM with a regularization parameter λ as in (1.3), then with probability at least 1 − 2δ −
2 exp(−N ε2 /2),
n
o
  32 
kfˆ − f ∗ k2L2 (µ) ≤ max r 2 10ηΨ(f ∗ ) , 2 λΨ(f ∗ ) .
(1.14)
κ ε
Observe that λ0 depends only on the oscillations of the multiplier process. Hence, if the problem is
noise-free then λ0 = 0, showing that any regularization parameter λ > 0 would do. Moreover, in that case
2 (10ηΨ(f ∗ )).
rM (ρ) = 0 and so one can choose r(ρ) ≥ rQ (ρ) obtaining an error rate that depends only on rQ

As noted previously, if one considers empirical risk minimization performed in F ∗ = {f ∈ F : Ψ(f ) ≤
Ψ(f ∗ )}, the resulting error rate is kf˜ − f ∗ k2L2 (µ) ≤ c0 r 2 (cΨ(f ∗ )) for a suitable absolute constant c0 and a
constant c that depends on κ, ε and δ; moreover, under some minor
 additional assumptions, that rate is
optimal in the minimax sense (cf. [29]) when one takes r(ρ) ∼ max rM (ρ), rQ (ρ) . Hence, up to constants
involved, the first term in Theorem 1.9 is essentially the minimax rate that one can obtain if Ψ(f ∗ ) were
known.
If one chooses λ ∼ λ0 (δ, τ ) for τ = 3/(80η 3 ) then the second term in (1.14) is of the order of
λΨ(f ∗ ) =



sup
ρ,f ∗

γO (ρ, τ, δ) 
· Ψ(f ∗ ).
ρ

Note that for ρ that is of the order of Ψ(f ∗ ), one has
γO (ρ, τ, δ)
· Ψ(f ∗ ) ≤ c1 γO (ρ, τ, δ) ≤ c2 r 2 (c3 Ψ(f ∗ )),
ρ
which coincides with the first term, up to the constants involved. Thus, the price that one has to pay for
not knowing Ψ(f ∗ ) is manifested in the need to take the supremum over all possible choices of ρ in the
second term, rather than considering only the level ρ ∼ Ψ(f ∗ ) of the “true model”.
Thankfully, there are many natural cases in which that price is rather small, allowing for satisfactory
outcomes of Theorem 1.9 closed to the minimax rate.
We end this introduction with a word about notation. Throughout, absolute constants or constants
that depend on other parameters are denoted by c, C, c1 , c2 , etc., (and, of course, we will specify when a
constant is absolute and when it depends on other parameters). The values of these constants may change
from line to line. The notation x ∼ y (resp. x . y) means that there exist absolute constants 0 < c < C
for which cy ≤ x ≤ Cy (resp. x ≤ Cy). If b > 0 is a parameter, then x .b y means that x ≤ C(b)y for
some constant C(b) that depends only on b.

P
p 1/p ; the corresponding unit ball
The normed space ℓdp is Rd endowed with the norm kxkp =
j |xj |
is denoted by Bpd and the unit Euclidean sphere in Rd is S d−1 .
Finally, from here on we will write P r and k kL2 without specifying the underlying measure.

2

Proof of Theorem 1.9

The proof of Theorem 1.9 follows an almost identical path as the proof of Theorem 3.2 from [31]. The
differences in the two arguments are minor and their source is the fact that unlike [31], here we do not
9

assume that Ψ is a norm. We will outline in Remark 2.2 how a version of Theorem 1.9 may be derived
directly from Theorem 3.2 in [31] when Ψ is a norm.
Theorem 1.9 is an immediate outcome of the following lemma:
Lemma 2.1 Let λ0 = λ0 (δ, 3/(80η 3 )) and set λ > λ0 . If limρ→0 r(ρ) = 0, ρ ≥ 5ηΨ(f ∗ ) and ρ > 0, then
with probability at least 1 − 2δ − 2 exp(−N ε2 /2),

kfˆ − f ∗ k2L2 ≤ max r 2 (ρ), (32/(κ2 ε))λΨ(f ∗ ) .

To see how Lemma 2.1 can be used to conclude the proof of Theorem 1.9, observe that if Ψ(f ∗ ) > 0, one
may simply select ρ = 5ηΨ(f ∗ ) in the lemma. If, on the other hand, Ψ(f ∗ ) = 0, let (γn )∞
n=1 be a positive
sequence decreasing to 0 and set An = {kfˆ − f ∗ kL2 ≤ γn }, which is a decreasing sequence of events. If
P r(An ) ≥ 1 − ν for some 0 ≤ ν ≤ 1 and every n then P r({fˆ = f ∗ }) ≥ 1 − ν. Since limρ→0 r(ρ) = 0, one
may apply Lemma 2.1 to each member of a nonnegative sequence ρn that decreases to zero and for which
γn = r(ρn ) decreases to zero. By Lemma 2.1, P r(An ) ≥ 1 − 2δ − 2 exp(−N ε2 /2) for every n and the proof
of Theorem 1.9 follows.
Proof of Lemma 2.1. Fix f ∗ and set ρ > 0 that satisfies ρ ≥ 5ηΨ(f ∗ ). Let
F1 = {f ∈ F : Ψ(f − f ∗ ) ≤ ρ} = F ∩ Kρ (f ∗ ),
and
F2 = {f ∈ F : Ψ(f − f ∗ ) = ρ}.

Clearly, F1 is a convex set that contains f ∗ , and by the continuity of the real-valued function t → Ψ(f ∗ +
t(f − f ∗ )), every ray [f ∗ , f ) that originates in f ∗ and passes through some f ∈ F \F1 intersects F2 .
Let θ = κ2 ε/16 and set
rQ (ρ) = rQ (F1 , κε/32) and rM (ρ) = rM (F1 , θ/5, δ/4).
There is an event A0 of probability at least 1 − δ − 2 exp(−N ε2 /2), and for every (Xi , Yi )N
i=1 ∈ A0 the
following holds:
• If f ∈ F1 and kf − f ∗ kL2 ≥ rQ (ρ) then
N
1 X
(f − f ∗ )2 (Xi ) ≥ θkf − f ∗ k2L2 .
N
i=1

• If f ∈ F1 then
N
θ
1 X
2
ξi (f − f ∗ )(Xi ) − Eξ(f − f ∗ )(X) ≤ max{kf − f ∗ k2L2 , rM
(ρ)}.
N
4
i=1

In particular, if f ∈ F1 and kf − f ∗ kL2 ≥ r(ρ) ≥ max{rM (ρ), rQ (ρ)} then
θ
PN Lf ≥ kf − f ∗ k2L2 .
2
10

By the choice of λ, there is an event A1 of probability at least 1−δ on which if f ∈ F1 and kf − f ∗ kL2 ≤ r(ρ),
then
N
2 X
3
3
ξi (f − f ∗ )(Xi ) − Eξ(f − f ∗ )(X) <
λρ.
(2.1)
λρ <
3
N
80η
5η
i=1

Set A = A0 ∩ A1 and let (Xi , Yi )N
i=1 ∈ A. The proof now follows in three steps:

(1) Show that the functional f → PN Lλf is bounded from below – away from zero – in F2 .
6 F \F1 .
(2) An outcome of (1) is that if f ∈ F \F1 , PN Lλf > 0; hence, fˆ ∈
(3) Finally, pin-point fˆ within F1 = {f ∈ F : Ψ(f − f ∗ ) ≤ ρ}.
Q>M
R>M

R>M

Q>M

Q>M
f∗

0

h
f
R>M

R>M
Q>M

Figure 2: 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.
Unlike Theorem 3.2 in [31], here we choose ρ ∼ Ψ(f ∗ ) to ensure that 0 ∈ F ∩ Kρ (f ∗ ).
Step 1. Fix f ∈ F2 and note that by the ‘triangle inequality’ satisfied by Ψ,
Ψ(f ) ≥ η −1 Ψ(f − f ∗ ) − Ψ(f ∗ ).

Recall that η −1 Ψ(f −f ∗ ) ≥ η −1 ρ ≥ 5Ψ(f ∗ ) and thus, Ψ(f )−Ψ(f ∗ ) ≥ (3/5)η −1 ρ. Hence, if kf −f ∗ kL2 ≥ r(ρ)
then
3
> 0.
PN Lλf ≥ (θ/2)kf − f ∗ k2L2 + λρ ·
5η
On the other hand, by the choice of λ, if kf − f ∗ kL2 ≤ r(ρ) then
PN Lλf

N
1 X
ξi (f − f ∗ )(Xi ) − Eξ(f − f ∗ )(X) + λ (Ψ(f ) − Ψ(f ∗ ))
≥−
N

≥−

1
N

i=1
N
X
i=1

ξi (f − f ∗ )(Xi ) − Eξ(f − f ∗ )(X) + λρ ·
11

3
> 0.
5η

It should be noted that the same proof shows that on the event A, for every f ∈ F2 ,
PN Lf +

λ
(Ψ(f ) − Ψ(f ∗ )) > 0,
2η 2

(2.2)

a fact that will be used below. Indeed, (λ/2η 2 ) · (Ψ(f ) − Ψ(f ∗ )) ≥ (λ/2η 2 ) · (3ρ/5η) and by (2.1), if
kf − f ∗ kL2 ≤ r(ρ) then PN Lf ≥ −(3/80) · (λρ/η 3 ).
Step 2. Let f ∈ F \F1 and note that by the convexity of F and the continuity of Ψ on rays, there is some
h ∈ F2 and R > 1 for which f = f ∗ + R(h − f ∗ ). Thus,
PN Lλf =

N
N
2R X
R2 X
(h − f ∗ )2 (Xi ) +
ξi (h − f ∗ )(Xi ) + λ (Ψ(f ) − Ψ(f ∗ )) .
N
N
i=1

i=1

Observe that
Ψ(f ) − Ψ(f ∗ ) ≥

R
(Ψ(h) − Ψ(f ∗ )) ;
2η 2

(2.3)

indeed,
Ψ(f ∗ + R(h − f ∗ )) ≥ η −1 Ψ(R(h − f ∗ )) − Ψ(f ∗ ) ≥ Rη −1 Ψ(h − f ∗ ) − Ψ(f ∗ ),
and thus it suffices to show that
R
R
Ψ(h − f ∗ ) ≥ 2 Ψ(h) + 2Ψ(f ∗ ).
η
2η
But since Ψ(h − f ∗ ) ≥ 5ηΨ(f ∗ ), η ≥ 1 and R ≥ 1, one has
R
R
R
Ψ(h − f ∗ ) ≥
Ψ(h − f ∗ ) + Ψ(f ∗ ) + 2RΨ(f ∗ )
η
2η
2
R
R
≥ (Ψ(h − f ∗ ) + Ψ(f ∗ )) + 2Ψ(f ∗ ) ≥ 2 Ψ(h) + 2Ψ(f ∗ ),
2η
2η
and (2.3) follows.
Finally, applying (2.2) to h ∈ F2 ,
PN Lλf

N
N
R2 X
2R X
R
∗ 2
≥
(h − f ) (Xi ) +
ξi (h − f ∗ )(Xi ) + λ 2 (Ψ(h) − Ψ(f ∗ ))
N
N
2η
i=1
i=1


λ
∗
≥R PN Lh + 2 (Ψ(h) − Ψ(f )) > 0,
2η

and fˆ ∈
6 F \F1 .
Step 3. Turning to F1 = {f ∈ F : Ψ(f −f ∗ ) ≤ ρ} = F ∩Kρ (f ∗ ), recall that if f ∈ F1 and kf −f ∗ kL2 ≥ r(ρ),
then PN Lf ≥ (θ/2)kf − f ∗ k2L2 ; hence, if f is a potential minimizer and kf − f ∗ kL2 ≥ r(ρ) then
0 ≥ PN Lλf ≥(θ/2)kf − f ∗ k2L2 + λ (Ψ(f ) − Ψ(f ∗ )) ≥ (θ/2)kf − f ∗ k2L2 − λΨ(f ∗ ),
and
kfˆ − f ∗ k2L2 ≤
as claimed.
12

2λ
Ψ(f ∗ ),
θ

Remark 2.2 If Ψ happens to be a norm (which is an assumption slightly stronger than Assumption 1.1),
one may apply Theorem 3.2 from [31] directly. Indeed, and using the notation from [31] if ρ & Ψ(f ∗ ) then
the set K = {f : Ψ(f − f ∗ ) ≤ ρ/20} contains a Ψ-ball around 0, and Γf ∗ (ρ) – the collection of norming
functionals (i.e. the sub-gradient of Ψ) of any h ∈ K – is the entire unit ball in the dual space to (E, Ψ).
Recall that
∆(ρ) = inf sup z ∗ (h − f ∗ ),
h z ∗ ∈Γ ∗ (ρ)
f

where the infimum is taken in the set
{h ∈ F : Ψ(h − f ∗ ) = ρ and kh − f ∗ kL2 ≤ r(ρ)}.
Since Γf ∗ (ρ) is the entire dual unit ball, it follows that ∆(ρ) = ρ, and Theorem 3.2 in [31] may be applied.
The desired version of Theorem 1.9 now follows from Remark 3.3 in [31].

3

Towards the examples - preliminary estimates

It is rather obvious that any implementation of Theorem 1.9 requires specific estimates on rM , rQ and λ0 .
This section is devoted to some preliminary facts that will play an instrumental part in establishing such
estimates.
Our main interest is the study of upper bounds on the three processes used to define the parameter
rM , rQ and γO , and which have the following forms:
(∗) = sup

N
X

f ∈F i=1

εi ξi f (Xi ) , (∗∗) = sup

N
X

f ∈F i=1

(ξi f (Xi ) − Eξf (X)) and E sup
f ∈F

N
X

εi f (Xi ) ,

i=1

where X1 , ..., XN are independent and distributed according to the underlying measure µ, ξ1 , ..., ξN are
N
independent copies of ξ ∈ Lq for some q > 2 (though (ξi )N
i=1 need not be independent of (Xi )i=1 ), and
N
(εi )N
i=1 are independent, symmetric {−1, 1}-valued random variables that are independent of (Xi )i=1 and
N
(ξi )i=1 .
Standard symmetrization methods (see, e.g., [18, 33, 54]) show that (∗) and (∗∗) are equivalent in
expectation and in deviation (up to a slight restriction on the deviation parameter). We will present one
example in which this symmetrization argument is carried out in full (Theorem 4.2), but in the other
examples we will only consider the symmetrized case.

3.1

Estimates for subgaussian classes

The first result is from [38], under the assumption that F is an L-subgaussian class of functions.
Definition 3.1 A class of functions F ⊂ L2 (µ) is L-subgaussian if for every f, h ∈ F ∪ {0} and every
u ≥ 1,
P r(|f (X) − h(X)| ≥ Lukf − hkL2 (µ) ) ≤ 2 exp(−u2 /2)

where X is distributed according to µ.

Let F ⊂ L2 (µ) and set {Gf : f ∈ F } to be the centered, canonical Gaussian process indexed by F (i.e.,
the covariance operator of the process is EGf Gg = Ef (X)g(X) for every f, g ∈ F ). Put
ℓ∗ (F ) = E sup Gf , and d2 (F ) = sup kf kL2 (µ) .
f ∈F

f ∈F

13

(3.1)

Theorem 3.2 (Corollary 1.10 in [38]) Let X be distributed according to µ, set ξ ∈ Lq for some q > 2
and assume that F ⊂ L2 (µ) is an L-subgaussian class. There are constants c, c0 , c1 , c2 and c3 that depend
only on q, for which, for any w, u > c, with probability at least
1−


c0 logq N
2 ∗
2
−
2
exp
−c
u
(ℓ
(F
)/d
(F
))
,
1
2
wq N q/2−1

sup
f ∈F

and

N
ℓ∗ (F )
1 X
εi ξi f (Xi ) ≤ c2 Lwu kξkLq √
N
N
i=1

N
1 X
ℓ∗ (F )
sup
ξi f (Xi ) − Eξf (X) ≤ c2 Lwu kξkLq √ .
N
f ∈F N i=1

Corollary 3.3 Using the notation and assumptions of Theorem 3.2, let ξ = Y − f ∗ (X) and assume that
ξ ∈ Lq for some q > 2. Fix τ > 0 and 0 < δ < 1, and set A > 0 for which
√
(3.2)
c2 Lwu kξkLq ℓ∗ (F ∩ ADf ∗ ) ≤ τ A2 N .
If
δ≥
then rM (F, τ, δ) ≤ A.


c0 logq N
+ 2 exp −c1 a0 u2
q
q/2−1
w N

(3.3)

Proof. Clearly, it follows from Theorem 3.2 that if
c0 logq N
δ ≥ q q/2−1 + 2 exp −c1 u2
w N



ℓ∗ (F ∩ ADf ∗ )
d2 (F ∩ ADf ∗ )

2 !

then rM (F, τ, δ) ≤ A. The claim follows because if F ∩ ADf ∗ is nonempty,
ℓ∗ (F ∩ ADf ∗ )
≥ a0
d2 (F ∩ ADf ∗ )
for a suitable absolute constant a0 .
Remark 3.4 The estimate in Corollary 3.3 can be rather loose. The reason for the suboptimal estimate is
that usually, the Gaussian mean-width ℓ∗ (F ∩ ADf ∗ ) is much larger than d2 (F ∩ ADf ∗ ). For example, let
F = { t, · : t ∈ S d−1 } be the class of linear functionals on Rd indexed by the Euclidean unit ball. Assume
that X is an isotropic vector – that is, its covariance structure coincides with the standard Euclidean
structure on Rd ; that f ∗ = 0; and that A ≤ 1. Then F ∩ ADf ∗ = { t, · : ktk2 ≤ A}, d2 (F ∩ ADf ∗ ) = A
√
and ℓ∗ (F ∩ ADf ∗ ) = A d, implying that
ℓ∗ (F ∩ ADf ∗ ) √
≥ d
d2 (F ∩ ADf ∗ )

(3.4)

which is significantly larger than an absolute constant.
Having said that, the question of an accurate probability estimate is not the main issue of this article
and we will not explore that point further.
14

Next, we provide an estimate on γO (ρ, τ, δ) that follows from Theorem 3.2 when F is L-subgaussian
and ξ ∈ Lq for some q > 2. The proof is identical to the one of Corollary 3.3 and is omitted.
Corollary 3.5 Let F be a closed, convex L-subgaussian class of functions and let ξ = Y − f ∗ (X) ∈ Lq for
some q > 2. Set w, u > c, τ > 0, 0 < δ < 1 and ρ > 0. If A > 0 satisfies
√
c2 Lwu kξkLq ℓ∗ (F ∩ Kρ (f ∗ ) ∩ r(ρ)Df ∗ ) ≤ τ A N .
and
δ≥
then γO (ρ, τ, δ) ≤ A.


c0 logq N
+ 2 exp −c1 a0 u2
q
q/2−1
w N

Finally, when F is a L-subgaussian class it follows from a standard chaining argument (cf. [50] or [38])
that
N
1 X
c0 Lℓ∗ (F )
E sup
εi f (Xi ) ≤ √
.
(3.5)
N
f ∈F N
i=1

This observation will be used in what follows to upper bound rQ .

3.2

Estimates under a limited moment condition

In this section we shall consider the case of a class that need not be subgaussian, but rather, the growth of
moments of class members is well-behaved up to some point. More accurately, we will assume that there
is some p0 for which, for every f, h ∈ F ∪ {0} and 2 ≤ p ≤ p0 ,
√
kf − hkLp ≤ L pkf − hkL2 .

(3.6)

√
In contrast, a subgaussian condition is equivalent to having kf − hkLp ≤ L pkf − hkL2 for every p ≥ 2.
The motivation for this type of limited moment assumption is the LASSO estimator. Recent results
on properties of the basis pursuit algorithm in Rd [30, 14] indicate that (3.6) for p0 ∼ log d should suffice
for an optimal estimate on the performance of the LASSO – as if the class were subgaussian.
When analyzing the LASSO via the computation of the fixed points rM and rQ , one encounters the
following scenario. Let X = (xj )dj=1 be a random vector in Rd and set X1 , . . . , XN to be independent copies
of X. Let Xi (j) be the j-th coordinate of Xi and thus (Xi (j))N
i=1 is a random vector with independent
coordinates, distributed as xj .
Consider the random variables appearing in the definition of rM and rQ in the LASSO case:
max

1≤i≤d

and
max

1≤i≤d

N
X

εi Xi (j) ,

(3.7)

N
X

εi ξi Xi (j)

(3.8)

i=1

i=1

The aim of this section is to derive upper bounds on (3.7) in expectation and (3.8) in deviation when
each xj satisfies that
√
kxj kLp ≤ L pkxj kL2
15

for p . log d. Note that an upper bound on the centered empirical process involved in the definition of
γO (ρ) will follow from a symmetrization argument and a bound on (3.8).
The obvious difference between (3.7) and (3.8) are the multipliers (ξi )N
i=1 : although the xj ’s have ∼ log d
moments, ξ may be heavy-tailed, in the sense that it only belongs to Lq for some fixed q > 2; this difference
makes the analysis of (3.8) more difficult.
Upper bounds on (3.7) and (3.8) are obtained under the following assumption.
Assumption 3.1 Let N ≤ d, t ≥ 4 and set p0 = t log d. Assume that p0 . N (and note that p0 ≥ log N )
√
and that for every 1 ≤ j ≤ d and p ≤ p0 , kxj kLp ≤ L pkxj kL2 . Consider ξ ∈ Lq for some q > 2; let
r = min{1/2+q/4, 2}; set r ′ to be the conjugate index of r; and assume that 4r ′ max{2, 1+a0 /a1 } ≤ t log N
(where a0 and a1 are two absolute constants to be specified later – in Lemma 7.3 and Lemma 7.4).
Under this assumption we will prove the following:
Theorem 3.6 Let the random vector X and ξ = Y − f ∗ (X) satisfy Assumption 3.1. Then,
N
p
1 X
√
E max
εi Xi (j) ≤ c0 log d · L max kxj kL2 .
1≤i≤d
1≤j≤d
N i=1

(3.9)

Also, for every u > 2, v > 0, w ≥ 2 and for p = p0 /2 and m = p/ log(eN/p), one has that with probability
at least
exp(−p/2) 4 exp(−p/2)
c2 logq N
− 2 exp(−v 2 t log d),
(3.10)
1−
−
−
q
q/2−1
u2p
uc1 m
w N
N
X
√ p
εi ξi Xi (j) ≤ c3 (q)(uw + u2 v)LkξkLq N t log d max kxj kL2 .
max
(3.11)
1≤j≤d

1≤j≤d

i=1

The proofs of both estimates in Theorem 3.6 follow from a more general result, established in [38], on
the supremum of a centered multiplier process under a limited moment assumption like (3.6). Although
the estimate in [38] is stated for the centered empirical process (cf. Section 4 there) its proof is actually
based on an estimate on the symmetrized process. The proof of Theorem 3.6 will be presented in final
section of this article.

4

The LASSO under a limited moment assumption

In this section, we obtain complexity-dependent error rates for the LASSO. Our aim is to show that the
LASSO (almost) achieves the minimax rates of convergence in the “true model”, and the meaning of the
“true model” is, in this case, the smallest ℓd1 -ball centered in 0 that contains t∗ . Thus, the price one has to
pay for not knowing kt∗ k1 is rather minimal.
The rate we shall be comparing the LASSO’s performance to is the minimax rate of the following
problem. Let X ∼ N (0, Id×d ) and set ξ ∼ N (0, σ 2 ) to be independent of X. Let ρ > 0, consider an
unknown t0 ∈ ρB1d and put Y = X, t0 + ξ.
Let c0 , c1 and c2 be well-chosen absolute constants and consider the cases log d ≤ N ≤ c0 d or c1 d ≤ N .
Following [29], if

σ2 d

if ρ2 N ≥ σ 2 d2


N
r
=0
if N ≥ c0 d






2 /d
eσd
1
2
2
2
2
2
2
√
.
ρ
if
c
ρσ N log ρ N
if σ log d ≤ ρ N ≤ σ d
0 d ≤ N ≤ c1 d
and sQ (ρ)
sM (ρ) = c2
 
2


ρ
q
d
 ∼ log

if N ≤ c1 d,


d
N
N
2 N ≤ σ 2 log d
if
ρ
ρσ log
N
16

then the minimax rate of convergence in the class ρB1d is
n
o
max s2M (ρ), s2Q (ρ)

(4.1)

p
p
when ρ ≥ σ (log d)/N and ρ2 when ρ ≤ σ (log d)/N . Note that when c0 d ≤ N ≤ c1 d (i.e. N ∼ d),
2
s2Q (ρ) decays rapidly from ρN log(d/N ) to 0 and there are no precise estimates on the minimax rate in that
range.
It turns out that for this problem – the so-called Gaussian linear model – the minimax rate in ρB1d is
achieved by the Empirical Risk Minimization procedure (see, e.g., [29]); however, an underlying assumption
is that ρ part of the information one is given. Thanks to regularization, and specifically, thanks to the
LASSO, one does not need to know the value of kt0 k1 in advance to achieve the minimax rate, at least
up to a logarithmic term. In fact, the optimal rate can be achieved using regularization in a much more
general framework than just the Gaussian linear model – as will be explained below.
In what follows we will compare the rates obtained for the LASSO in Theorem 1.9 in the highdimensional case, that is, when N ≤ c1 d. One may do the same when N ≥ c0 d and we leave that to
the reader.
Let X be a random vector in Rd and consider the class of linear functionals F = {ft = ·, t : t ∈ Rd }.
In particular, if Y ∈ L2 is an arbitrary target random variable then f ∗ = ft∗ = ·, t∗ satisfies
t∗ ∈ argmin E Y − X, t
t∈Rd

2

.

(4.2)

As noted in the Introduction, the regularization function associated with the LASSO is the ℓd1 -norm: for
every t = (tj )dj=1 ∈ Rd ,
d
X
|tj |.
Ψ(ft ) = ktk1 =
j=1

Clearly, as a norm, the

ℓd1 -regularization

function satisfies Assumption 1.1 for η = 1.

The LASSO with regularization parameter λ produces
t̂ ∈ argmin
t∈Rd

N

1 X
2
Yi − Xi , t
+ λ ktk1 ,
N

(4.3)

i=1

2

and one would like to control kft̂ − ft∗ k2L2 = E X, t̂ − t∗ , where the expectation is taken with respect to
X conditionally to the data.
It should be noted that despite the LASSO’s popularity, there are relatively few results in the random
design scenario we are interested in (see, e.g., [2], [34] and chapter 8.2 in [26]). The overwhelming majority
of existing results have been obtained for the linear model with subgaussian noise and a fixed design (i.e.,
each data point is of the form Yi = t∗ , zi + ξi ) – and the deterministic design matrix, whose rows are the
vectors zi , satisfies some form of the Restricted Isometry Property – for example, the Restricted Eigenvalue
Condition (REC) from [3] or the Compatibility Condition (CC) from [53]).
To define the restricted eigenvalue condition, let us introduce the following notation: for x ∈ Rd and
a set S0 ⊂ {1, . . . , d} of cardinality |S0 | ≤ s, let S1 be the set of indices of the m largest coordinates of
(|xi |)di=1 that are outside S0 . Let xS01 be the restriction of x to the set S01 = S0 ∪ S1 .

17

Definition 4.1 ([3]) Let Γ be an N × d matrix. For c0 ≥ 1 and an integer 1 ≤ s ≤ m ≤ d for which
m + s ≤ d, the restricted eigenvalue constant is


kΓxk2
κ(s, m, c0 ) = min
: S0 ⊂ {1, . . . , d}, |S0 | ≤ s, xS0c 1 ≤ c0 kxS0 k1 .
kxS01 k2
The matrix Γ satisfies the Restricted Eigenvalue Condition (REC) of order s with a constant c
if κ(s, s, 3) ≥ c.
p
One can show (see, [3], [5]) that if Γ satisfies REC and λ & σ (log d)/N , then with high probability
(with respect to the noise), simultaneously for every 1 ≤ p ≤ 2,
!p
r
σ
log d
∗ p
∗
t̂ − t p .p kt k0
(4.4)
κ(s, s, 3)
N
where kt∗ k0 is the cardinality of the support of t∗ .
The main result in this section is an estimate on kfˆ − f ∗ k2L2 that depends on kt∗ k1 rather than on
the cardinality of the support of t∗ (we refer to [31] for “sparsity-dependent” rates of convergence for the
LASSO in the same framework as we consider here). Such result follow from Theorem 1.9, and to that
end, one has to construct a function r(·) as in (1.13) and to compute λ0 (δ, γ) as in Definition 1.8. We will
do so under the following situation: Set a2 ≥ 4, 2 ≤ p0 = a2 log d . N , q > 2, r = min{1/2 + q/4, 2}
and r ′ that is the conjugate index of r. Assume that 4r ′ max{2, 1 + a0 /a1 } ≤ a2 log N (which is equivalent
to assuming that q > 2 + c1 / log N for some constant c1 = c1 (a0 , a1 , a2 )). Let X = (xj )dj=1 be a random
vector and note that the coordinates x1 , ..., xd need not be independent.
Assumption 4.1 Using the above notation, assume that there are constants κ0 , κ and ε for which the
following holds:
√
• For every 1 ≤ j ≤ d and every 2 ≤ p ≤ p0 , kxj kLp ≤ κ0 p kxj kL2 .
• X satisfies a small-ball condition with constants κ and ε; that is, for every t ∈ Rd ,


P r | X, t | ≥ κ X, t L2 ≥ ε.

(4.5)

• ξ = Y − f ∗ (X) ∈ Lq .

To put this assumption in some perspective, note that an obvious underlying condition in any estimation
problem with respect to the squared loss is that E(f (X) − Y )2 is defined for any f ∈ F , and in particular,
that ξ = Y − f ∗ (X) ∈ L2 . Thus, assuming that ξ ∈ Lq for some q > 2 + c1 / log N is not very restrictive.
Also, as noted previously, the small-ball assumption is rather minimal.
The most restrictive component of Assumption 4.1 is the moment assumption on the coordinates of X
– that their moments exhibit a subgaussian behavior, up to, roughly, p ∼ log d.
While this assumption can be weakened to other types of moment growth condition (e.g., kxj kLp ≤
α
κ0 p kxj kL2 for some α ≥ 1/2 and up to p ∼ log d), the resulting analysis is more involved (see [30]), and
will not be explored here.
Finally, [30] shows that even if one assumes a subgaussian behavior of the coordinates xi , but only up
to p ∼ (log d)/(log log d), Basis Pursuit may fail to recover even a 1-sparse vector, implying that the choice
of p0 in Assumption 4.1 can not be relaxed significantly.
18

Given any ρ ≥ 0, set M = max1≤j≤d kxj kL2 , let σq = kξkq and put
κ0 ρM
Λ(ρ) =
κ2 ε

r

log d
.
N

Moreover, for R(t) = E(Y − X, t )2 , one has
2

R(t) − R(t∗ ) = E X, t − t∗ ,
because X, t∗ is the best approximation of Y in a closed subspace of L2 . Thus, the estimation bounds
also lead to excess risk bounds.
Theorem 4.2 There are absolute constants c0 , ..., c6 for which the following holds. Assume that X and
ξ = Y −f ∗ (X) satisfy Assumption 4.1 and that N ≤ d. Let u > 2, v > 0 and w ≥ 2, and set p = (a2 /2) log d
and m = p/ log(eN/p). Put
δ=

c1 logq N
exp(−p/2) 4 exp(−p/2)
− 2 exp(−v 2 t log d)
−
−
u2p
uc 0 m
wq N q/2−1

and set
2

r (ρ) = c2

(

2
n (uw + u w)σq Λ(ρ)
o
max (uw + u2 v)σq Λ(ρ), κ2 Λ2 (ρ)

(4.6)

if N ≥ (κε/32)2 d
otherwise.

If t̂ is produced by the LASSO for a regularization parameter

λ > c4 (uw + u2 v)κ0 kξkLq η 3 M

r

log d
,
N

then with probability at least 1 − 5δ − 2 exp(−ε2 N/2),
R(t̂) − R(t∗ ) =

X, t̂ − t∗

2
L2

n
o
λ
≤ c5 max r 2 (c6 kt∗ k1 ), 2 kt∗ k1 .
κ ε

Observe that like known estimates on the LASSO, and despite imposing considerably
p weaker assumptions on X and Y , the regularization parameter in Theorem 4.2 is of the order of kξkLq (log d)/N . And,
when kξkLq is equivalent to σ – the variance of ξ – then for N . d, the rate of convergence is
)
(
r
log d ∗ 2 log d
∗
, kt k1
c(M ) max σ kt k1
N
N
for a constant that depend only on M .
Hence, up to a logarithmic
factor, the LASSO attains the minimax rate in kt∗ k1 B1d when log d ≤ N . d
p
∗
and when kt k1 ≥ σ log d/N ; moreover, it does so without knowing in advance the identity of the “true
model” kt∗ k1 B1d .
Note that one may want to combine the sparsity-dependent error rate from Theorem 1.3 in [31] and
the complexity-dependent error rate from Theorem 4.2. To simplify the exposition, results from [31] have
been stated under a subgaussian assumption on the design. Therefore, we will also make this assumption
below. Note also that the probability estimate from Theorem 4.2 can be improved under the subgaussian
assumption on the design and that the third condition from Assumption 4.1 (i.e. q > 2 + c1 / log N ) can be
relaxed to only q > 2 (see more details in the next section, and, in particular, Theorem 5.4). Combining
19

the two approaches, one has that when X is isotropic and L-subgaussian, and when ξ ∈ Lq for some q > 2
then for any u, w > c with probability larger than 1 − δ for
c0 logq N
− c0 exp(−c1 u2 /L2 ),
q
q/2−1
w N
p
the LASSO estimator t̂ with the universal regularization parameter kξkLq (log d)/N satisfies that
(
))
(
r
kt∗ k0 σ 2 log d
log d ∗ 2 log d
∗ 2
∗
t̂ − t 2 .L,q min
(4.7)
, max σ kt k1
, kt k1
N
N
N
δ = 2 exp(−c2 N/L8 ) −

when N & kt∗ k0 log(d/ kt∗ k0 ).
Note that seemingly, (4.7) exhibits a different rate than Corollary 9.1 in [26] (see also (1.4) above): the
d
extra (and necessary) kt∗ k21 log
N term in (4.7), which appears only in the random design scenario. As a
result, the rates of convergence of the LASSO appears to deteriorate when
s
q
N
σ
(4.8)
≤ kt∗ k1 ≤ σ kt∗ k0 .
log d
However, the sparsity-dependent error rate, and therefore Equation (4.7), holds only when N & kt∗ k0 log(d/ kt∗ k0 ).
And, when N & kt∗ k0 log d (which is only slightly larger than kt∗ k0 log(d/ kt∗ k0 )), the error rates in the
two scenarii (random and deterministic design) are the same and are given by
(
)
r
σ 2 kt∗ k0 log d
log
d
min
.
, σ kt∗ k1
N
N

Proof of Theorem 4.2. As noted previously, since k·k1 is a norm, Ψ(t) = ktk1 satisfies Assumption 1.1
for η = 1; therefore, Theorem 1.9 may be applied here, and one has to control r(ρ) ≡ max{rM (ρ), rQ (ρ)}
and λ0 (δ, τ ). In what follows we will invoke the results of Section 3 and estimate these parameters.
Set F (f ∗ , ρ) = F ∩ Kρ (f ∗ ) − f ∗ and recall that rQ (ρ) = rQ (F ∩ Kρ (f ∗ ), κε/32) is determined by the
behavior of
N
1 X
√
(⋆) = E
sup
(4.9)
εi f (Xi ) ;
N i=1
f ∈F (f ∗ ,ρ)∩rD
2

as a consequence, it suffices to upper bound (⋆). Let E = {t ∈ Rd : E X, t ≤ 1}, put E ◦ to be the polar
of E (that is, E ◦ = {u : supt∈E | u, t | ≤ 1}), and set ktkE = supx∈E x, t . Thus,
)
(
N
N
N
1 X
1 X
1 X
√
εi Xi , t ≤ min E sup √
εi Xi , t , E sup √
εi Xi , t
(⋆) = E sup
N i=1
N i=1
N i=1
t∈rE
t∈ρB1d
t∈ρB1d ∩rE


N
N


X
X
1
1
= min ρE √
, rE √
.
εi Xi
εi Xi


N i=1
N i=1
d
◦
ℓ∞

E

It is standard to verify (see, for instance, the proof of Lemma 2.2 in [32]) that
N
1 X
E √
εi Xi
N i=1

20

E◦

≤

√
d.

Moreover, by (3.9),
N
1 X
√
E
εi Xi
N i=1

Therefore,

ℓd∞

N
p
1 X
√
=E max
εi Xi (j) ≤ c0 κ0 log d max kxj kL2 .
1≤j≤d
1≤j≤d
N i=1



√
p
(⋆) ≤ min c0 ρκ0 log d max kxj kL2 , r d ,

(4.10)

1≤j≤d

and setting γ = κε/32, one has

(

rQ (ρ) ≤

c0 ρκ0
γ

q0

log d
N M

if N ≥ γ 2 d
otherwise.

Next, let us establish a high probability upper bound on rM (ρ) = rM (F ∩ Kρ (f ∗ ), κ2 ε/80, δ/4). Note
that
φN (F ∩ Kρ (f ∗ ), f ∗ , s) =

sup
t∈ρB1d ∩sE

N
1 X
√
εi ξi Xi , t
N i=1

N
1 X
εi ξi Xi (j) .
≤ ρ max √
1≤j≤d
N i=1

Applying the second result of Theorem 3.6 for u > 2, v > 0, w ≥ 2, p = (a2 /2) log d, m = p/ log(eN/p) and
δ=

c1 logq N
exp(−p/2) 4 exp(−p/2)
− 2 exp(−v 2 t log d),
−
−
u2p
uc0 m
wq N q/2−1

(4.11)

it follows that with probability at least 1 − δ,
φN (F ∩ Kρ (f ∗ ), f ∗ , s) ≤ c2 κ0 (uw + u2 v) kξkLq ρM
thus,
2
rM
(ρ)

c3 κ0 (uw + u2 v)
kξkLq ρM
≤
κ2 ε

r

p

log d;

log d
.
N

Finally, let us identify an upper bound on λ0 (δ, τ ) for τ = 3/(80η 3 ). Let {e1 , . . . , ed } be the canonical
basis of Rd . Since Kρ (f ∗ ) = {t : kt − t∗ k1 ≤ ρ}, we have
!
N
1 X
ξi (f − f ∗ )(Xi ) − Eξ(f − f ∗ )(X)
(⋆1 ) =
sup
N
f ∈F ∩Kρ (f ∗ )∩r(ρ)Df ∗
i=1
!
N
1 X
∗
∗
ξi Xi , t − t − Eξ X, t − t
≤ρ
max
t−t∗ ∈{±e1 ,...,±ed } N
i=1
!
N
X
1
=ρ
max
ξi Xi , t − Eξ X, t .
t∈{±e1 ,...,±ed } N
i=1

Recall that X = (xj )dj=1 . By a standard symmetrization argument (see, for example, Lemma 2.3.7 in [54]),
p
if z ≥ 4 max1≤j≤d Var(ξxj )/N then
Pr



N
N


z
1 X
1 X
.
max
ξi Xi , t − Eξ X, t ≥ z ≤ 4P r
εi ξi Xi , t ≥
4
t∈{±e1 ,...,±ed } N
t∈{±e1 ,...,±ed } N

max

i=1

i=1

21

q
p
Note that Var(ξxj ) ≤ Eξ 2 x2j ≤ kξkLq kxj kL ′ where q ′ is the conjugate index of q/2. Therefore,
2q
p
√
Var(ξxj ) ≤ κ0 2q ′ kξkLq M as long as 2q ′ ≤ a2 log d, i.e., when q ≥ 2 + 2/(a2 log d − 1) – which is the
case under Assumption 4.1. Therefore, applying the second result of Theorem 3.6 for δ as in (4.11), it
follows that with probability at least 1 − δ,
r
log d
2
,
(⋆1 ) ≤ ρc0 κ0 (uw + u v) kξkLq M
N
and, for τ = 3/(80η 3 ) one may select
λ0 (δ, τ ) = c4 κ0 (uw + u2 v) kξkLq η 3 wM

5

r

log d
.
N

Regularization methods for subgaussian classes

In this section we assume that X is a random vector that takes its values in a Hilbert space H. The main
examples we shall consider are when H is the d-dimensional Euclidean space and when it is the space of
m × T matrices endowed with the Frobenius norm.
The inner product in H is denoted by ·, · , and the norm and unit ball endowed by the inner product
are denoted by k·kH and BH = {t ∈ H : ktkH ≤ 1} respectively.
There is another natural Hilbertian structure on H, endowed by Σ = EXX ⊤ , the covariance operator
2
associated with the random vector X. The corresponding unit ball is E = {t ∈ H : E X, t ≤ 1}, is an
ellipsoid in H.
Let T ⊂ H be a closed and convex set and put
t∗ ∈ argmin E(Y − X, t )2 ;
t∈T

thus, X, t∗ is the best L2 (µ)-approximation of Y by a linear functional t, · for t ∈ T .
Let Ψ(·) be a regularization function on H that satisfies Assumption 1.1. The goal is to estimate t∗ in
L2 (µ) with a rate depending on Ψ(f ∗ ). To that end, set
t̂ ∈ argmin
t∈T

N

1 X
2
Yi − Xi , t
+ λΨ(t)
N

(5.1)

i=1

for a well-chosen regularization parameter λ.
Unlike the results of the previous section, in what follows we will assume that F = { t, · : t ∈ T } is an
L-subgaussian class (see Definition 3.1). Moreover, F satisfies a small-ball property with constants that
depend only on L. Indeed, observe that for every t ∈ T
X, t

L4

.L

X, t

L2

,

and applying the Paley-Zygmund inequality (see, e.g., Corollary 3.3.2 in [13]),


P r | X, t | ≥ κ X, t L2 ≥ ε for κ = 1/2 and ε = c/L4 .
22

(5.2)

From here on we will say that the random vector X taking its values in H is L-subgaussian if the class
consisting of all the linear functionals on H, i.e., { t, · : t ∈ H}, is L-subgaussian. Also, throughout this
section, we will assume that ξ = Y − f ∗ (X) ∈ Lq for some q > 2, σq = kξkLq , and
T ∩ Kρ (t∗ ) = {t ∈ T : Ψ(t − t∗ ) ≤ ρ}.

5.1

‘Heavy tailed’ noise

Thanks to the subgaussian assumption, both r(ρ) and λ0 = λ0 (δ, 3/(80η 3 )) may be determined using the
Gaussian mean-widths of the sets T ∩Kρ (t∗ ) for all ρ > 0. Recall that for T0 ⊂ H the Gaussian mean-width
of T0 is ℓ∗ (T0 ) = E supt∈T0 Gt , where (Gt )t∈T0 is the centered canonical Gaussian process indexed by T0
with covariance structure given by EGt1 Gt2 = E X, t1 X, t2 for every t1 , t2 ∈ T .

Definition 5.1 Let rEt∗ = t ∈ H : k t − t∗ , · kL2 (µ) ≤ r = t∗ + rE, and for α, β > 0 set
and

n
√ o
r̃Q (ρ, α) = inf r > 0 : ℓ∗ (T ∩ Kρ (t∗ ) ∩ rEt∗ ) ≤ αr N

n
√ o
r̃M (ρ, β) = inf r > 0 : ℓ∗ (T ∩ Kρ (t∗ ) ∩ rEt∗ ) ≤ βr 2 N .

Let c0 be an absolute constant to be specified later. Fix u, w > c, and ε and κ as in (5.2). Consider
α=

κε
κ2 c1 ε
, β=
, and γ = c0 η 3 Lwu kξkLq ,
c0 L
Lwu kξkLq

(5.3)

put
r(ρ) ≥ max {r̃Q (ρ, α), r̃M (ρ, β)}
and set
λ0 (γ) = γ

sup
ρ>0,t∗ ∈T

ℓ∗ (T ∩ Kρ (t∗ ) ∩ r(ρ)Et∗ )
√
.
ρ N

(5.4)
(5.5)

The first result we present is rather general and holds for any closed and convex subset T ⊂ H and any
regularization function satisfying Assumption 1.1. It allows to take into account an additional constraint
on the “signal” t∗ ∈ T .
Theorem 5.2 There are absolute constants c, c1 and c2 for which the following holds. Let Ψ be a regularization function satisfying Assumption 1.1. Assume that X is L-subgaussian for some L > 0 and that
ξ = Y − X, t∗ is in Lq for some q > 2.
If t̂ is given by (5.1) for a regularization parameter λ > λ0 (γ) as in (5.5), then with probability larger
than
c0 logq N
(5.6)
1 − 2 exp(−N ε2 /8) − q q/2−1 − c0 exp(−c1 u2 /L2 ),
w N

2
X, t̂ − t∗ L2 ≤ max r(10ηΨ(t∗ ))2 , (32/κ2 ε)λΨ(t∗ )
for r(·) given by (5.4).

23

Proof. The proof follows from Theorem 1.9 by estimating r(ρ) and λ0 using the ‘local’ Gaussian meanwidths of the sets T ∩ Kρ (t∗ ).

Since X is L-subgaussian, the process X, t : t ∈ H is L-subgaussian. Setting F = { t, · : t ∈ H}
and f ∗ = t∗ , · , a standard chaining argument shows that
E

sup
f ∈F ∩Kρ (f ∗ )∩rDf ∗

N
1 X
ℓ∗ (T ∩ Kρ (t∗ ) ∩ rEt∗ )
√
εi (f − f ∗ )(Xi ) ≤ c0 L
.
N
N
i=1

Thus,


κε 
≤ r̃Q (ρ, α).
rQ F ∩ Kρ (f ∗ ),
32
As for the fixed point associated with the multiplier process, it follows from Corollary 3.3 that

κ2 ε δ 
≤ r̃M (ρ, β)
,
rM F ∩ Kρ (f ∗ ),
160 4

(5.7)

(5.8)

for β as defined in (5.3), and as long as

δ
c0 logq N
≥ q q/2−1 + 2 exp(−c1 u2 /L2 ).
4
w N
Finally by Corollary 3.5, λ0 (δ, γ) ≤ λ0 (γ). The claim now follows from Theorem 1.9.

If one is to apply Theorem 5.2, an essential component is an upper bound on ℓ∗ (T ∩ Kρ (t∗ ) ∩ rEt∗ ) –
which in turn determines r and λ. To simplify the analysis we shall use an additional assumption on Ψ:
Assumption 5.1 Assume that for every x, y ∈ H and λ ≥ 0,
Ψ(x) = Ψ(−x),
Also, recall that E = {t ∈ H : E X, t


Ψ(x + y) ≤ η Ψ(x) + Ψ(y) and Ψ(λx) ≤ λΨ(x).

2

(5.9)

≤ 1}, σq = kξkq and set K = {t ∈ H : Ψ(t) ≤ 1}.

Theorem 5.3 Assume
√ that Ψ satisfies Assumption 5.1 and that the assumptions of Theorem 5.2 hold.
∗
Let Λ(ρ) ≥ ρℓ (K)/ N for every ρ > 0, w, u > c and consider the RERM
N
1 X

t̂ ∈ argmin
(Yi − Xi , t )2 + c0 η 3 Lwuσq Λ(Ψ(t)) .
N
t∈H
i=1

Then, with probability larger than the one in (5.6),
R(t̂) − R(t∗ ) =

X, t̂ − t∗

where, for α and β defined in (5.3) and, for any ρ ≥ 0,
(
Λ(ρ)
β
2
o
n
r (ρ) =
Λ2 (ρ)
,
max Λ(ρ)
β
α2

2
L2

≤ c0 r 2 (10ηΨ(t∗ ))

2
if N ≥ ℓ∗ (E)/α
otherwise.

(5.10)

Proof. The result follows immediately from Theorem 5.2. Indeed, for every ρ > 0, r > 0 and t∗ ∈ T = H,
ℓ∗ (T ∩ Kρ (t∗ ) ∩ rEt∗ ) = ℓ∗ (Kρ (0) ∩ rE) ≤ ℓ∗ (ρK ∩ rE) ≤ min {ρℓ∗ (K), rℓ∗ (E)} ,

because Kρ (0) ⊂ ρK = {ρt : t ∈ K}.
24

√
Note that in a d-dimensional space, the trivial bound ℓ∗ (E) ≤ d holds (see, e.g., Lemma 2.2 in [32]).
Therefore, one only needs to control ℓ∗ (K). In the next section, we provide several examples of applications
of Theorem 5.3 that follow from estimates on ℓ∗ (K). We will simplify the analysis by assuming that there
is some compatibility between the norm k·kH and the one endowed by the covariance structure of X:
2 1/2
Assumption 5.2 Assume that X is isotropic; that is, for every t ∈ H, E X, t
= ktkH .
Observe that under Assumption 5.2, ℓ∗ (K) = E supt∈K Gt , where (Gt )t∈K is the canonical Gaussian process
indexed by K with the covariance EGt1 Gt2 = t1 , t2 for every t1 , t2 ∈ K, because the inner-product in H
coincides with the one endowed by L2 (µ).

5.2

Regularization methods in Rd

Consider a regularization function Ψ(·) satisfying Assumption 5.1. Assume that X is L-subgaussian and
isotropic in Rd with respect to the standard√
Euclidean inner-product, and that ξ ∈ Lq for some q > 2. Let
∗
u, w > c. For any ρ ≥ 0 set Λ(ρ) ≥ ρℓ (K)/ N and put

wuσq Λ(ρ)
when N &L d

r 2 (ρ) ∼L,q


max wuσq Λ(ρ), Λ2 (ρ)
otherwise.
It follows from Theorem 5.3 that if

N
1 X

(Yi − Xi , t )2 + c0 η 3 Lwuσq Λ(Ψ(t))
t̂ ∈ argmin
N
t∈Rd

(5.11)

i=1

then with probability larger than the one in (5.6)
t̂ − t∗ , ·

2
L2 (µ)

. r 2 (10ηΨ(t∗ )).

As a consequence, one can derive an estimation result for (5.11) whenever ℓ∗ (K) may be controlled from
above. In the following section, we shall apply this observation to some classical problems and compare the
error rates obtained by the RERM (5.11) to the minimax rate in the “true model” {t ∈ T : Ψ(t) ≤ Ψ(t∗ )}.
Example: ℓp -regularization for 1 ≤ p ≤ ∞. In this section, we consider a regularization function
Ψ(t) = ktkp for some p ≥ 1. Assumption 5.1 holds with η = 1 because k·kp is a norm. In order to apply
the general result for the RERM in (5.11), one has to compute the Gaussian mean-width of the unit ball
associated with the regularization function Ψ(·) = k·kp .
In the range 1 ≤ p ≤ 1+(log d)−1 , we recover the same result as for the LASSO, because B1d ⊂ Bpd ⊂ cB1d
p
for a suitable absolute constant c; hence, ℓ∗ (Bpd ) ∼ ℓ∗ (B1d ) ∼ log(ed).
When 1 + (log(ed))−1 ≤ p, set r to be the conjugate index for p and one may easily verify that
√
∗
ℓ (Bpd ) ∼ rd1/r .
Applying Theorem 5.3, one has the following:
Theorem 5.4 Under the assumptions of Theorem 5.3 and using its notation,
• If 1 ≤ p ≤ 1 + 1/(log d) and
r
N
1 X
log d 
2
3
(Yi − Xi , t ) + c2 ηp Lwuσq ktkp
t̂ ∈ argmin
N
N
t∈Rd
i=1

25

then with probability larger than the one in (5.6),

q
d
∗


wuσq kt kp log

N

2
t̂ − t∗ 2 .p,L,q

q


log d
∗k

, kt∗ k2
max
wuσ
kt

q
p

N

log d
p N

if N &L d,


otherwise.

• If p ≥ 1 + 1/(log d) and

p
N
1 X
p/(p − 1)d(p−1)/p 
2
√
,
t̂ ∈ argmin
(Yi − Xi , t ) + c2 σq Lwu ktkp
N
N
t∈Rd
i=1
then with probability larger than the one in (5.6)

(p−1)/p

wuσq kt∗ kp d p√N


2
t̂ − t∗ 2 .L,q
n


 max wuσq kt∗ k d(p−1)/p
√
, kt∗ k2p
p
N

if N &L d,
d2(p−1)/p
N

o

otherwise.

Remark. [the case 0 < p < 1] Despite being a non-convex function, ℓp -regularization for 0 < p < 1 has
attracted much attention in the context of Signal Processing and High-Dimensional Statistics. Among the
problems studied using ℓp regularization were the linear regression model with a deterministic design (cf.
[44, 45, 55]); the sequence space model [15, 1]; and the random design linear regression model [56].
From our point of view, there is no particular restriction on p as long as the regularization function
satisfies Assumption 5.1. We can therefore consider a regularization function Ψ(t) = ktkp for any 0 < p < 1.
In that range of p, Assumption 5.1 holds for η = ηp = 21/p (see, for example, page 2 in [16]) and the Gaussian
mean width of the “unit ball” associated with Ψ(·) = k·kp for 0 < p < 1 can also be computed.
To that end, let {e1 , . . . , ed } be the canonical basis of Rd . Since {±e1 , . . . , ±ed } ⊂ Bpd ⊂ B1d for p < 1, it
√
is evident that ℓ∗ (Bpd ) ∼ log d. Thus, the error rates of the LASSO, obtained in Theorem 4.2, dominate
all the ℓp -regularization rates when 0 < p ≤ 1. We therefore obtain the same result for ℓp -regularization
with 0 < p < 1 as the one in the first case of Theorem 5.4 for ℓp -regularization with 1 ≤ p ≤ 1 + 1/ log p.
However, the resulting rate is not the minimax rate in the true model, as can be seen from [44].
Indeed, fix 0 < p ≤ 1. Consider an unknown t∗ ∈ ρBpd and the corresponding Gaussian linear model
Yi = xi , t∗ + Wi , i = 1, . . . , N , where the matrix whose rows are (xi )N
i=1 satisfies some RIP property and
W1 , · · · , WN are independent, centered Gaussian variables with variance σ 2 . For specific asymptotics of N
and d (see [44] for a precise formulation), the authors show that minimax rate of the problem is given by
 log d 1− p
2
,
σ2 ρ
N

and similar results have been obtained in [56]. Thus, our estimate recovers the minimax rate in the true
model only when p = 1. When 0 < p < 1, it is possible that the choice of the Ψ(t) = ktkp is suboptimal,
and instead one should use Ψ(t) = ktkpp as was suggested in [46] for the problem of Sp -regularization for
0 < p ≤ 1.
Example: weak-ℓp -regularization for 0 < p ≤ 1. Weak-ℓp norms have been used to model sparsity in
High-Dimensional Statistics (see, for instance, [1, 56]). To define those norms, let t∗1 ≥ t∗2 ≥ . . . ≥ t∗d be
26

d = {t ∈ Rd : t∗ ≤
the non-increasing rearrangement of (|ti |)di=1 . Set ktkp∞ = max1≤j≤d j 1/p t∗j and put Bp∞
j
j −1/p for every 1 ≤ j ≤ d}.
One can use the following well-known fact (see, e.g., Theorem B in [22]) to control the Gaussian
mean-width of the unit ball associated with k·kp∞ .

Proposition 5.5 For 0 < p ≤ 1,
∗

ℓ (Bp∞ ) .







√

log d
p−1

if 0 < p < 1

3/2
log d

if p = 1.

Now, one may apply Theorem 5.3 and obtain the following result.
Theorem 5.6 Under the assumptions of Theorem 5.3 and using its notation,
• If p < 1 and

r
N
1 X
log d 
t̂ ∈ argmin
,
(Yi − Xi , t )2 + c2 ηp3 σq Lwu ktkp∞
N
N
t∈Rd
i=1

then with probability larger than the one in (5.6)

q
log d
∗k


σ
wu
kt
q

p∞
N

∗ 2
t̂ − t 2 .p,L,q

q


log d

, kt∗ k2
 max σq wu kt∗ k
p

• If p = 1 and

N

if N &L d,

log d
p∞ N

N
1 X
t̂ ∈ argmin
(Yi − Xi , t )2 + c2 η13 σq ktk1∞
N
d
t∈R
i=1

then with probability larger than the one in (5.6)

q
log3 d

∗k

σ
wu
kt
q

1∞
N

∗ 2
t̂ − t 2 .L,δ,q

q


(log d)3
∗

, kt∗ k2
 max σq wu kt k
1∞

N


s

log3 d
1∞ N

otherwise.

log3 d 
,
N

if N &L d,


otherwise.

Example: the Micchelli, Morales and Pontil’s regularization functions.
Let Θ be a nonempty convex cone in [0, ∞)d , and for every t ∈ Rd set
d


1 X  t2j
+ θj .
θ∈Θ 2
θj

Ω(t|Θ) = inf

j=1

It was shown in [35] that Ω(t|Θ) is a norm on Rd .

27

(5.12)

This family of norms captures several classical regularization functions, by an appropriate choice of the
cone Θ. For instance, the ℓd1 -norm is obtained by selecting Θ = [0, ∞)d . Also, the group LASSO introduced
in [57] is generated by a cone: indeed, if (G1 , · · · , GT ) is a partition of {1, . . . , d} and
Θ = {θ ∈ [0, ∞)d that is constant within each group Gℓ },
then
Ω(t|Θ) =

T p
X
ℓ=1

|Gℓ | t|Gℓ

2

(5.13)

,

where |Gℓ | is the cardinality of the set of coordinates Gℓ and t|Gℓ is the restriction of t to Gℓ .
Error bounds for procedures that use Ψ(t) = Ω(t|Θ) as regularization functions have been established
in [36], under the assumption that the loss functions is bounded and Lipschitz (see Theorem 1 there).
Naturally, the squared loss is not covered by such a result because it is not bounded in Rd , nor is it
Lipschitz. Our aim is to provide similar results as the one in [36] for a quadratic loss for a subgaussian
random vector X and a noise in Lq for some q > 2. To that end, we first compute the Gaussian mean
width of the unit ball of such a norm.
Proposition 5.7 Let Θ be a nonempty convex cone in [0, ∞)d and set B = {t : Ω(t|Θ) ≤ 1}. Let S1d−1 be
the unit sphere of ℓd1 and put Ex to be the set of extreme points of Θ ∩ S1d−1 . If M = maxa∈Ex kak1/2
∞ , then,
for an absolute constant c,
q

∗
ℓ (B) ≤ 1 + cM 2 log |Ex| .
(5.14)

The proof of Proposition 5.7 may be derived in various ways (see a similar result in [36]), though we
will use a chaining argument which actually leads to a stronger estimate than (5.14).
Definition 5.8 Let T ⊂ Rd and k·k be a norm on Rd . For every α > 1 set
γα (T, k·k) = inf sup

∞
X

(Ts ) t∈T
s=0

2s/α kπs+1 t − πs tk

where the infimum is taken with respect to all sequences (Ts ) of subsets of T for which |T0 | = 1 and for
s
s ≥ 1, |Ts | ≤ 22 , and πs t is the nearest point to t in Ts with respect to k·k.
Clearly, if T is finite then γα (T, k k) . supt∈T ktk · log1/α |T |.
Proof of Proposition 5.7. It is straightforward to verify (see, e.g., [35]) that the dual norm to Ω(·|Θ) is
∗

Ω (t|Θ) = max
a∈Ex

d
X
j=1

aj t2j

1/2

.

(5.15)

Let g1 , ..., gd be independent, standard Gaussian random variables, Applying a Bernstein type inequality
for a sum of independent ψ1 random variables (see Corollary 2.10 in [49]), it follows that for every a1 , ..., aN ,
every u > 0 and any s ∈ N,


d
X
aj (gj2 − 1) ≥ u2s/2 kak2 + u2 2s kak∞  ≤ 2 exp(c1 2s u2 ).
Pr 
j=1

28

Hence, using a standard chaining argument,
E sup

d
X

a∈Ex j=1

aj gj2 ≤ 1 + c2 (γ2 (Ex, k k2 ) + γ1 (Ex, k k∞ )) .

Now one may apply the trivial estimates on γ1 and γ2 . Firstly, γ1 (Ex, k·k∞ ) . M 2 log(|Ex|), and secondly,
p
P
noting that | dj=1 aj | ≤ kak1 = 1 and thus kak2 ≤ kak1/2
log(|Ex|). Therefore,
∞ , one has γ2 (Ex, k·k2 ) . M
by Jensen’s inequality,
d
X
p
1/2
E sup
aj gj2
≤ 1 + cM log(|Ex|).
a∈Ex j=1

Theorem 5.9 Using the notation above and of Theorem 5.3, let
r
log(|Ex|)
Λ(t) = Ω(t|Θ)M
.
N
If
t̂ ∈ argmin
t∈Rd

N
1 X

(Yi − Xi , t )2 + c2 σq LwuΛ(t)
N
i=1

then with probability larger than the one in (5.6)

σq wuΛ(t∗ )
if N &L d,

∗
2
k t̂ − t , · kL2 (µ) .L,q


max σq LwuΛ(t∗ ), Λ2 (t∗ )
otherwise.
p
√
When Θ = [0, ∞)d then M log(Ex) . log d. Hence, Theorem 5.9 yields the same error rate as
the one obtained for the LASSO in Theorem 4.2 and Theorem 5.4, though under a stronger subgaussian
assumption on X. This is not surprising because when Θ = [0, ∞)d , Ω(t|Θ) = ktk1 and the resulting
RERM is just the LASSO.
p
p
In the p
case of the group LASSO, for Θ as in (5.13), one has M log(Ex) . log |T |, and Λ(t∗ ) ∼
Ω(t∗ |Θ)M (log |T |)/N .
Example: The SLOPE regularization
In [48, 4], the authors introduced the regularization function:
Ψ(t) = ktkSLOP E =

d
X

λj t∗j

j=1

where λ1 ≥ · · · ≥ λd ≥ 0 and t∗1 ≥ · · · ≥ t∗d ≥ 0 is the non-increasing rearrangement of (|ti |)di=1 .
In [48] the given data is generated by the Gaussian linear model Yi = Xi , t∗ + Wi , i = 1, . . . , N for
a Gaussian design Xi ∼ N (0, N −1 Id×d ) (note that the covariance matrix is normalized by 1/N ) and a
centered Gaussian noise Wi with variance σ 2 that is independent of the design Xi . Setting Φ−1 (α) to be
the α-th quantile of a standard normal distribution and q ∈ (0, 1), the weights were chosen to be
λi = Φ−1 (1 − iq/(2d)),
29

(5.16)

and, for this choice of weights, SLOPE was defined by
N
 1 X
ktkSLOP E 
(Yi − Xi , t )2 + σ √
t̂ ∈ argmin
.
2N
N
t∈Rd
i=1

The result in [48] is asymptotic in the sample size N and in the dimension d in the following sense:
Theorem 5.10 (Theorem 1.2 [48]) Let 0 < ε < 1 and set 1 ≤ k ≤ d that satisfy k/d = o(1) and
(k log d)/N = o(1) when N → ∞. Then,
lim

sup P r

N →∞ kt∗ k ≤k
0

 N t̂ − t∗ 2

2
>
1
+
3ε
= 0,
2σ 2 k log(d/k)

where the supremum is taken with respect to all vectors that are supported on at most k coordinates.
It was shown in [48] that 2σ 2 k log(d/k)/N is the (asymptotic) minimax rate for t∗ that is k-sparse.
The article [48] (see Section 6 there) raises the question of extending Theorem 5.10 beyond the Gaussian
case, especially when the coordinates of X may be correlated. We study this question in the context of
sparse recovery and for an arbitrary choice of weights in [31], leading to error bounds that depend on kt∗ k0 .
Here, we obtain a complexity-dependent error rate that depends on kt∗ kSLOP E .
Proposition 5.11 p
Set B = {t ∈ Rd : ktkSLOP E ≤ 1}. There exists an absolute constant C, for which, if
−1
M = max1≤j≤d λj
log(ed/j), then ℓ∗ (B) ≤ CM .

Proof. The proof is outcome of a standard binomial estimate. Let G = (gi )di=1 be a standard Gaussian
vector and observe that
ℓ∗ (B) = E sup G, t ≤ E sup
t∈B

d
X

t∈B j=1

gj∗ t∗j ≤ E sup

d
X
gj∗

t∈B j=1

λj

gj∗
.
1≤j≤d λj

λj t∗j ≤ E max

For u ≥ 1,
d  
d
 X
 X
gj∗
d
∗
P r gj ≥ uλj ≤
P r j (|g| ≥ uλj )
≥u ≤
P r max
1≤j≤d λj
j
j=1

j=1

≤2

d
X
j=1



 ed 
− c1 ju2 λ2j ≤ 2 exp(c2 u2 ),
exp j log
j

where the last inequality follows if one sets u2 ≥ maxj λ−2
j log(ed/j). The proof is concluded by integrating
the tails.
Theorem 5.3 leads to estimation properties of SLOPE.
Theorem 5.12 Using the notation of Theorem 5.3, if Ψ(t) = ktkSLOP E , maxj λ−1
j
N
1 X
ktkSLOP E 
,
(Yi − Xi , t )2 + c2 σq Lwu √
t̂ ∈ argmin
N
N
t∈Rd
i=1

30

p

log(ed/j) ≤ C and

then with probability larger than the one in (5.6),

σq wukt∗ kSLOP E

√


N
∗ 2
t̂ − t 2 .L,q,C
n
o

∗k
kt∗ k2SLOP E

 max σq Lwukt
√ SLOP E ,
N
N

if N &L d,
otherwise.

As was done for the LASSO, one may combine the sparsity-dependent error rate for SLOPE from [31]
and the complexity-dependent error rate from Theorem 5.12. To that end, assume that X is isotropic,
L-subgaussian and that the noise ξ is in Lq for some q > 2. Then, with probability larger than the one in
(5.6)
))
(
(
 ed 
σq wu kt∗ kSLOP E kt∗ k2SLOP E
σq kt∗ k0
∗ 2
√
,
, max
log
,
t̂ − t 2 .L,q,C min
N
kt∗ k0
N
N

for N & kt∗ k0 log(ed/ kt∗ k0 ).

5.3

Regularization methods in Rm×T

In this section,
in the set of m×T matrices,endowed with the inner product
P we assume that X takes values
2
∗
and thus X, A∗ is the best
A, B = u,v Auv Buv . We consider A ∈ argminA∈Rm×T E Y − X, A
(linear) approximation √
of Y in the L2 sense.
Let Λ(ρ) ≥ ρℓ∗ (K)/ N for all ρ > 0, u, w > C and set
Â ∈ argmin
A∈Rm×T

N
1 X

(Yi − Xi , A )2 + c2 η 3 σq LwuΛ(Ψ(A)) .
N

(5.17)

i=1

By Theorem 5.3, with probability larger than the one in (5.6)
Â − A
where for ρ ≥ 0,
2

r(ρ) ∼L,q





2
2

=

X, Â − A∗

2
L2

. r(10ηΨ(A∗ ))2

σq wuΛ(ρ)

when N &L mT

n
o

 max σq wuΛ(ρ), Λ2 (ρ)

otherwise.

Let us turn to estimates on ℓ∗ (K) for the unit balls of the regularization functions used in the matrix
completion and collaborative filtering problems.
Example: Sp -regularization for p ≥ 1.
For any A ∈ Rm×T , let σ1 (A) ≥ σ2 (A) ≥ · · · ≥ σm∧T (A) be the ordered singular values of A and set
m ∧ T = min{m, T }. Recall that the p-Schatten norm k·kSp of A is defined by
kAkSp =

 m∧T
X
j=1

σj (A)p

1/p

.

Schatten norms have been used extensively in matrix completion and in collaborative filtering. Exact
reconstruction properties of various procedures have been established via the minimization of the S1 -norm,
31

constrained to matching the data (see, e.g., [7, 10, 8, 23, 12]). S1 regularization has also been used in the
noisy setup for independent subgaussian noise and, in most case, for subgaussian or deterministic designs,
in [27, 46, 26, 42, 17, 25].
A result that is closely related to ours is Theorem 9.2 from [26], in which X is isotropic and Lsubgaussian; ξ is a symmetric random variable that is independent of X and for which kξkψα < ∞ for
some α ≥ 1 (cf. [43] for more details on the ψα -norms); and the target is Y = X, A∗ + ξ.
Let N & m · rank(A∗ ) and set
)
(
r
 kξk  √m(t + log N )(t + log m)
m(t + log m)
ψα
.
, kξkψα log1/α
λ & max kξk2
N
kξkL2
N
The S1 -regularization procedure with regularization parameter λ satisfies that for every t > 0, with probability larger than 1 − 3 exp(−t) − exp(−c0 N ),
Â − A∗

2
S2


. min λ kA∗ kS1 , λ2 rank(A∗ ) .

(5.18)

In comparison, an estimation result for Sp -norm regularization (for any p ≥ 1) follows from Theorem 5.3,
and does not require any assumptions on the “noise” ξ = Y − A∗ , X , other than ξ ∈ Lq for some q > 2. in
particular, ξ need not belong to ψα , nor does it have to be independent of X. The result uses the following
estimate on the Gaussian mean-width of the unit ball of Sp -norms (see, for instance, Proposition 1.4.4 in
[11]):
Proposition 5.13 Let p ≥ 1 and set BpmT to be the unit ball of k·kSp . Then
√
ℓ∗ (BpmT ) ∼ min{m, T }1−1/p m + T .

Combining the previous result with Theorem 5.3, one obtains the following:
ρ min{m, T }1−1/p

Theorem 5.14 Assume that the assumptions of Theorem 5.3 hold. Let Λp (ρ) =
for all ρ > 0 and
N

1 X
(Yi − Xi , A )2 + c2 σq LwuΛp (kAkSp ) .
Â ∈ argmin
A∈Rm×T N

q

m+T
N

i=1

Then with probability at least 1 − δ,

σq wuΛp (kA∗ kSp )


2
.p,L,q
Â − A∗
o
n

S2
 max σ wuΛ (kA∗ k ), Λ2 (kA∗ k )
q
p
p
Sp
Sp

if N &L mT,
otherwise.

Remark.
As in the vector case mentioned earlier, Theorem 5.3 also applies for Sp -regularization for
1.1 is satisfied for η = 21/p and the Gaussian mean width of the
0 < p < 1. In that case, Assumption
√
∗
mT
Sp -unit ball satisfies ℓ (Bp ) . m + T . It therefore follows from Theorem 5.3 that under the same
p
assumptions as in Theorem 5.3 and for Λ(ρ) = ρ (m + T )/N for all ρ > 0, the RERM
N
1 X

Â ∈ argmin
(Yi − Xi , A )2 + c2 σq LwuΛ(kAkSp ) ,
A∈Rm×T N
i=1

32

satisfies, with probability larger than the one in (5.6),

σq wuΛ(kA∗ kSp )


2
.p,L,q
Â − A∗
o
n

S2
 max σ wuΛ(kA∗ k ), Λ2 (kA∗ k )
q
Sp
Sp

if N &L mT,
otherwise.

Observe that just as in the vector case, when 0 < p < 1 this rate is not the minimax rate in the true
model kA∗ kSp BpmT . Indeed, [46] provides the minimax rate, and, in fact, also shows that the minimax rate
may be attained using Ψ(A) = kAkpSp as a regularization function. To be more accurate, [46] considers the
following problem: let x1 , . . . , xN be N deterministic matrices in Rm×T satisfying some RIP property and
set Wi to be N independent, standard Gaussian variables with variance σ 2 . Set Yi = xi , A∗ + Wi , i =
1, . . . , N , leading to the so-called matrix regression model with Gaussian noise and a deterministic design.
It is shown in [46] that when ρBpmT for some 0 < p ≤ 1, the minimax rate of the problem in ρBpmT is
σ 2 ρp

 m + T 1− p
2

N

in some specific range of N, σ and ρ. Our result recovers this rate only for p = 1.
Example: Max-norm regularization. The max-norm of a matrix is defined by
kAkmax =

inf

A=U V ⊤

kU k2→∞ kV k2→∞ ,

with the infimum is taken with respect to all pairs of matrices U, V for which A = U V ⊤ .
Constrained empirical risk minimization procedures that are based on the max-norm have been used in
[6, 41] for bounded and Lipschitz loss functions and in [29] for the squared loss and for a subgaussian and
isotropic design vector X and a subgaussian noise ξ independent of X. One may show that the minimax
rate in the matrix regression model Yi = Xi , A∗ + Wi , i = 1, . . . , N where X1 , . . . , XN are independent
isotropic and subgaussian matrices, W1 , . . . , WN are independent centered gaussian variables with variance
σ 2 that are independent of the Xi ’s and A∗ belongs to the max-norm ball of radius ρ, is
)
( r
(mT )(m + T ) ρ2 (mt)(m + T )
,
(5.19)
max σρ
N
N
for some specific regime of ρ, σ and N (cf. [29]).
To apply Theorem 5.3, let us estimate the Gaussian mean-width of the unit ball of the max-norm ball,
that is, of B = {A ∈ Rm×T : kAkmax ≤ 1}.
Lemma 5.15 There exists an absolute constant c for which, for every m and T ,
p
ℓ∗ (B) . (mT )(m + T ).

Proof. An application of Grothendieck’s inequality (see, e.g., [41]) shows that


conv X± ⊂ B ⊂ KG conv X±

where KG is the Grothendieck constant and X± = {uv ⊤ : u ∈ {±1}m , v ∈ {±1}T }. If G = (gij )1≤u≤m:1≤v≤T
is a standard m × T Gaussian matrix, it follows from the Gaussian maximal inequality (see, e.g., Chapter 3
33

in [33]) that
ℓ∗ (B) = E sup | G, A | ≤ KG E
A∈B

sup
A∈conv(X± )

= KG E sup | G, A | . max kAkHS
A∈X±

A∈X±

p

| G, A |

log |X± | .

p
(mT )(m + T ).

p
Theorem 5.16 Using the assumptions and notation of Theorem 5.3, and setting Λ(ρ) = ρ (mT )(m + T )/N ,
if
N

1 X
(Yi − Xi , A )2 + c2 σq LwuΛ(kAkmax ) ,
Â ∈ argmin
A∈Rm×T N
i=1

then with probability larger than the one in (5.6)

σq wuΛ(kA∗ kmax )


kÂ − A∗ k2S2 .L,q
n
o

2 (kA∗ k
 max σq wuΛ(kA∗ k
),
Λ
)
max
max

if N &L mT,
otherwise.

As a consequence, we recover the minimax rate of convergence in the matrix regression model with
subgaussian design and gaussian noise in the class kA∗ kmax B thanks to max-norm regularization and
without knowing kA∗ kmax in advance.

Example: Atomic-norm regularization.
The atomic-norm has been used in [12] in the context of exact and robust recovery using few Gaussian
linear measurements of a signal or of a matrix.
Given A ⊂ Rm×T , the elements in A are called atoms. Set conv(A) to be the convex hull of A and put
kAkA = inf {t > 0 : A ∈ tconv(A)} .

(5.20)

Even though k·kA need not be a norm (because conv(A) need not be centrally-symmetric), it is positive
homogeneous and satisfies a triangle inequality: for every A, B ∈ Rm×T and λ ≥ 0:
kA + BkA ≤ kAkA + kBkA and kλAkA = λ kAkA .
And, if we assume that A is centrally-symmetric, then k kA is a norm, (5.9) is satisfied and Theorem 5.3
applies.
Set B to be the unit ball with respect to k kA and note that ℓ∗ (B) = ℓ∗ (A). For example, assume that
m = T and put A to be the set of all orthogonal matrices. Since the unit ball of the spectral norm is the
convex hull of the set of orthogonal matrices, one has k·kA = k·kS2 and
√
ℓ∗ (B) = E kGkS2 ≤ mE kGkS∞ . m.
Theorem 5.17 Using the assumptions
and notation of Theorem 5.3, let A ⊂ Rm×T be a symmetric set
√
∗
of atoms and set Λ(ρ) ≥ ρℓ (A)/ N for any ρ > 0. If
N

1 X
(Yi − Xi , A )2 + c2 σq LwuΛ(kAkA )
Â ∈ argmin
A∈Rm×T N
i=1

34

then with probability larger than the one in (5.6)

σq wuΛ(kA∗ kA )


2
.L,q
Â − A∗
n
o

S2
 max σq wuΛ(kA∗ k ), Λ2 (kA∗ k )
A
A

6

if N &L mT,
otherwise.

Conclusions

We have presented a general result (Theorem 1.9) describing statistical properties of a constrained regularized procedure in the learning theoretical framework. This result highlights the role played by the
quadratic and multiplier processes in calibrating the regularization parameter λ as well as their effect on
the estimation error rate. It appears that:
1. the rates of convergence depend on Ψ(f ∗ ) and we recover the minimax rate in the “true model”
{f ∈ F : Ψ(f ) ≤ Ψ(f ∗ )} – up to a logarithmic factor – in many well-studied examples .
2. no statistical model is needed to study RERM; all the analysis has been carried out here in the
general learning theory setup, and thus without assuming any statistical model. Theorem 1.9 and
all its corollaries and applications are true regardless of any relation between the target Y and the
input X. For instance, when predicting Y using linear functionals of X there is no need to assume
that Y equals a linear functional of X plus an independent noise; our results hold even if Y were, for
instance, a noisy version of a quadratic function of a linear functional of X (e.g. phase retrieval) or
even when Y is independent of X.
Our analysis shows that despite considering the more general learning theory framework, the error
rate and the regularization parameter used to construct RERM almost match the ones that would
have been obtained with more information – namely, a given statistical model. In the examples
we considered, Statistical models are superfluous for the analysis of RERM and as a consequence,
they may actually hide what really determines the error rate and the right choice of a regularization
parameter:
• calibration of the regularization parameter depends only on the multiplier process – which
measures the empirical correlation between the noise Y − f ∗ (X) and the class F . When this
correlation is small or even null (in the free-noise case) the regularization parameter will also be
small.
• the key parameters are the “structure” of the “unit ball” of the regularization function (measured
here using the Gaussian mean width) and the “noise level”, which we measure through the Lq
norm of Y − f ∗ (X).

7

Proof of Theorem 3.6

Following [38], the proof of Theorem 3.6 is based on properties of the following norm:
Definition 7.1 For a random variable Z and p ≥ 1, set
kZkLq
√ .
q
1≤q≤p

kZk(p) = sup

35

The k·k(p) norm is a ‘local’ version of the ψ2 norm. While
kZkLq
kZkψ2 ∼ sup √ ,
q
q≥1
kZk(p) captures the subgaussian behavior of Z up to the p-th moment.
Under Assumption 3.1, a high probability bound on (3.7) can be derived from the next result.
Proposition 7.2 (Lemma 2.8 in [30]) There exists an absolute constant c0 for which the following
holds. Let Z be a mean-zero real-valued random variable and let Z1 , ..., ZN be independent copies of Z. Let
p1 ≥ 1 and assume that kZk(p1 ) ≤ L, then
N
1 X
√
Zi
N i=1

(p1 )

≤ c0 L.

P
Setting Uj = N −1/2 N
i=1 εi Xi (j) and p1 = log d (recalling that t ≥ 1 and d ≥ N in Assumption 3.1),
it follows from Proposition 7.2 that
√
kUj kLp1 ≤ c0 L p1 kxj kL2 .

Therefore,
Pr



≤d

max |Uj | ≥ u

1≤j≤d





√

≤

d
X
j=1

P r (|Uj | ≥ u) ≤

c0 L p1 max1≤j≤d kxj kL2
u

p 1

=d

d
X

kUj kLp

1

u

j=1

!p 1

!log d
√
c0 L log d max1≤j≤d kxj kL2
u

.

√
Let w ≥ e and set u = c0 Lw log d max1≤j≤d kxj kL2 ; therefore,
Pr



max |Uj | ≥ c1 Lw

1≤j≤d

p

log d max kxj kL2
1≤j≤d



≤

 e log d
w

,

(7.1)

which is a high probability estimate on (3.7) under a limited moment assumption. Integrating the tail,
N
p
1 X
εi Xi (j) . L log d max kxj kL2
E max √
1≤j≤d
1≤j≤d
N i=1

proving (3.9).
Next, we obtain high probability bounds on (3.8) – which requires some preparation.
Let j ∈ {1, . . . , d} and set Zi = Xi (j). Consider the Bernoulli sums
Qj =

N
X

εi ξi Xi (j) =

N
X
i=1

i=1

36

εi ξi Zi .

N
Denote by (a∗i )N
i=1 the non-increasing rearrangement of (|ai |)i=1 . A straightforward application of Höffding’s
N
N
inequality shows that conditioned on (ξi )i=1 and (Zi )i=1 , for any v > 0, with probability at least 1 −
2 exp(−v 2 /2) relative to (εi )N
i=1 ,

1/2
X
X
(ξi∗ Zi∗ )2 
ξi∗ Zi∗ + v 
|Qj | ≤
(7.2)
i≥m

i≤m



≤

X

1/2 

(ξi∗ )2 

i≤m



X

1/2

(Zi∗ )2 

i≤m



+v

X

1/2r 

(ξi∗ )2r 

i≥m



X

2r ′

(Zi∗ )

i≥m

1/2r′


,

where r and r ′ are conjugate indices.
As a consequence, high probability bounds on the rearrangements (ξi∗ ) and (Zi∗ ) can be used to obtain
high probability bounds on |Qj | (and therefore, on max1≤j≤d |Qj | as well, using the union bound).
The next two observations, whose proofs may be found in [38] give information on the structure of a
typical (Zi )N
i=1 when Z has at least t log d subgaussian moments. It turns out that one may decompose
N
(Zi )i=1 to a sum of two vectors, supported on disjoint sets: one consists of the largest m coordinates of
N
(|Zi |)N
i=1 , and its ℓ2 norm is determined by relatively high moments of Z; the other one consists of the
N
N − m smaller coordinates of (|Zi |)N
i=1 , and if Z ∈ Lq1 , its ℓr norm is well-behaved for r < q1 .
The ‘level’ m depends on the desired probability estimate and on the moments of Z: if one wishes to
obtain a probability estimate of 1 − 2 exp(−p) for p ≥ log N (as we will), then Z should have roughly p
moments and one should select m ∼ p/ log(eN/p).
First, let us consider the smaller coordinates:
Lemma 7.3 (Lemma 3.2 in [38]) There exist absolute constants a0 and c1 for which the following holds.
Let 1 ≤ r1 < q1 , set Z ∈ Lq1 and put Z1 , ..., ZN to be independent copies of Z. Fix 1 ≤ p ≤ N , let u > 2
and set


a0 p
.
m=
((q1 /r1 ) − 1) log(4 + eN/p)

If m > 1, then, with probability at least 1 − 2u−mq1 exp(−p),
!1/r1
1/r1

N
X
q1
∗ r1
uN 1/r1 kZkLq1
(Zi )
≤ c1
q1 − r1
i=m

and, if m = 1 and 0 < β < q1 /r1 − 1 then with probability at least 1 − c2 u−q1 N −β ,
!1/r1
N


X
q1
|Zi |r1
≤ c1
u kZkLq N 1/r1 .
1
q1 − (β + 1)r1
i=1

Next, we consider the larger coordinates:
Lemma 7.4 (Lemma 3.4 in [38]) There exists absolute constants a1 and c0 for which the following
holds. Let Z1 , ..., ZN be independent
copies of a random variable Z, set p ≥ log N and put 1 ≤ m ≤ N/2e

that satisfy m ≤ a1 p/ log eN/p . Then, for every u > 1, with probability at least 1 − u−2p exp(−p), one
has
!1/2
m
X
√
∗ 2
(Zi )
≤ c0 u pkZk(2p) .
i=1

37

In particular, under Assumption 3.1, we apply Lemma 7.3 and Lemma 7.4 to p, q1 and r1 defined by
n
a0 o
2p = t log d, r1 = 2r ′ and q1 = r1 max 2, 1 +
,
a1
where a0 and a1 are the absolute constants from Lemma 7.3 and 7.4. We also set


a0 p
m=
log(4 + eN/p)

(7.3)

and observe that if


a0 p
m0 =
((q1 /r1 ) − 1) log(4 + eN/p)



then m0 ≤ m ≤

a1 p
log(eN/p)

and m0 q1 ∼ m. Moreover, if κ0 is a large enough absolute constant and t ≥ κ0 , then m0 > 1. Recalling
that p ≥ 2 log d and setting Zi = Xi (j) for i = 1, . . . , N , it follows that for any u > 2, with probability at
least 1 − u−2p exp(−p/2) − 2u−c0 m exp(−p/2), for every 1 ≤ j ≤ d
m
X
(Zi∗ )2
i=1

and
N
X

2r ′

(Zi∗ )

i=m

!1/2

!1/2r′

p
√
. u p kZk(2p) . uL t log d kxj kL2

√
′
′
. u kZkLq N 1/2r . uL r ′ kxj kL2 N 1/2r .
1

(7.4)

(7.5)

Let ξ1 , ..., ξN be independent copies of ξ and recall that (ξi∗ )N
i=1 is the monotone non-increasing rearrangement of (|ξi |)N
.
We
apply
Lemma
7.3
for
q
=
q,
r
=
2r
and
set
1
1
i=1


a0 p
m1 =
.
((q1 /r1 ) − 1) log(4 + eN/p)
Thus, m1 > 1 when t ≥ κ0 for a large enough constant κ0 , and if m is as in (7.3) one has m ≥ m1 and
m1 q1 ∼ m. Hence, for p = (t/2) log d, with probability larger than 1 − 2u−c0 m exp(−p),
N
X

(ξi∗ )2r
i=m

!1/2r

≤ c(q)u kξkLq N 1/2r .

(7.6)

This provides a high probability bound on the smaller coefficients of (|ξi |)N
i=1 , and now we shall turn to a
result on the larger ones.
Lemma 7.5 (Lemma 4.3 in [38]) Let q > 2 and assume that ξ ∈ Lq . If ξ1 , . . . , ξN are independent
copies of ξ then for every w > 1 with probability larger than 1 − c0 w−q N −((q/2)−1) logq N ,
m
X
i=1

ξi2

!1/2

≤

N
X
i=1

ξi2

!1/2

38

≤ c1 w kξkLq

√

N.

Setting Zi = Xi (j) for i = 1, . . . , N and applying (7.4), (7.5), (7.6) and Lemma 7.5, we obtain, with
probability larger than
exp(−p/2) 4 exp(−p/2)
c0 logq N
1−
−
−
u2p
uc 0 m
wq N q/2−1
that for every j = 1, . . . , d



X

(ξi∗ )2 

i≤m

and




X

i≥m

1/2 


X

i≤m

1/2r 

(ξi∗ )2r 



1/2

(Zi∗ )2 

X

i≥m

. uwL

1/2r′

′
(Zi∗ )2r 

p

t log d kxj kL2 kξkLq

≤ c(q)u2 L kξkLq

√
N

√
N kxj kL2 .

Then, by plugging those inequalities in (7.2), it is evident that under Assumption 3.1, for u > 2, v > 0,
w ≥ 2, 2p = t log d and m ∼ p/ log(eN/p), with probability at least
1−
max

1≤j≤d

N
X
i=1

exp(−p/2) 4 exp(−p/2)
c1 logq N
− 2 exp(−v 2 t log d),
−
−
u2p
uc0 m
wq N q/2−1

√ p
εi ξi Xi (j) = max |Qj | .q (uw + u2 v)LkξkLq N t log d max kxj kL2 .
1≤j≤d

1≤j≤d

References
[1] Felix Abramovich, Yoav Benjamini, David L. Donoho, and Iain M. Johnstone. Adapting to unknown sparsity by controlling the false discovery rate. Ann. Statist., 34(2):584–653, 2006.
[2] Peter L. Bartlett, Shahar Mendelson, and Joseph Neeman. ℓ1 -regularized linear regression: persistence and oracle
inequalities. Probab. Theory Related Fields, 154(1-2):193–224, 2012.
[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] T. Tony Cai and Wen-Xin Zhou.
10(1):1493–1525, 2016.

Matrix completion via max-norm constrained optimization.

Electron. J. Stat.,

[7] 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.
[8] Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Found. Comput. Math.,
9(6):717–772, 2009.
[9] Emmanuel J. Candès, Justin Romberg, and Terence Tao. Robust uncertainty principles: exact signal reconstruction from
highly incomplete frequency information. IEEE Trans. Inform. Theory, 52(2):489–509, 2006.
[10] Emmanuel J. Candès and Terence Tao. The power of convex relaxation: near-optimal matrix completion. IEEE Trans.
Inform. Theory, 56(5):2053–2080, 2010.
[11] Djalil Chafaı̈, Olivier Guédon, Guillaume Lecué, and Alain Pajor. Interactions between compressed sensing random
matrices and high dimensional geometry, volume 37 of Panoramas et Synthèses [Panoramas and Syntheses]. Société
Mathématique de France, Paris, 2012.

39

[12] Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, and Alan S. Willsky. The convex geometry of linear inverse
problems. Found. Comput. Math., 12(6):805–849, 2012.
[13] Vı́ctor H. de la Peña and Evarist Giné. Decoupling. Probability and its Applications (New York). Springer-Verlag, New
York, 1999. From dependence to independence, Randomly stopped processes. U -statistics and processes. Martingales and
beyond.
[14] Sjoerd Dirksen, Guillaume Lecué, and Holger Rauhut. On the gap between rip-properties and sparse recovery conditions.
Technical report, 2014. To appear in IEEE Transactions on Information Theory.
[15] David L. Donoho and Iain M. Johnstone. Minimax risk over lp -balls for lq -error. Probab. Theory Related Fields, 99(2):277–
303, 1994.
[16] D. E. Edmunds and H. Triebel. Function spaces, entropy numbers, differential operators, volume 120 of Cambridge Tracts
in Mathematics. Cambridge University Press, Cambridge, 1996.
[17] Stéphane Gaı̈ﬀas and Guillaume Lecué. Sharp oracle inequalities for high-dimensional matrix prediction. IEEE Trans.
Inform. Theory, 57(10):6942–6957, 2011.
[18] Evarist Giné and Joel Zinn. Some limit theorems for empirical processes. Ann. Probab., 12(4):929–998, 1984. With
discussion.
[19] Christophe Giraud. Introduction to high-dimensional statistics, volume 139 of Monographs on Statistics and Applied
Probability. CRC Press, Boca Raton, FL, 2015.
[20] F. Girosi, M. Jones, and T. Poggio. Regularization theory and neural network architectures. Neural Computation,
7:219–269, 1995.
[21] Gene H. Golub, Michael Heath, and Grace Wahba. Generalized cross-validation as a method for choosing a good ridge
parameter. Technometrics, 21(2):215–223, 1979.
[22] Yehoram Gordon, Alexandre E. Litvak, Shahar Mendelson, and Alain Pajor. Gaussian averages of interpolated bodies
and applications to approximate reconstruction. J. Approx. Theory, 149(1):59–73, 2007.
[23] David Gross. Recovering low-rank matrices from few coeﬃcients in any basis. IEEE Trans. Inform. Theory, 57(3):1548–
1566, 2011.
[24] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The elements of statistical learning. Springer Series in Statistics.
Springer, New York, second edition, 2009. Data mining, inference, and prediction.
[25] Olga Klopp. Noisy low-rank matrix completion with general sampling distribution. Bernoulli, 20(1):282–303, 2014.
[26] 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] 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.
[28] 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.
[29] Guillaume Lecué and Shahar Mendelson. Learning subgaussian classes: Upper and minimax bounds. In Topics in
Learning Theory. Société Mathématique de France, (S. Boucheron and N. Vayatis Eds.). To appear.
[30] 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.
[31] Guillaume Lecué and Shahar Mendelson. Regularization and the small-ball method I: sparse recovery. Technical report,
CNRS, Ecole Polytechnique and Technion, 2015. submitted.
[32] Guillaume Lecué and Shahar Mendelson. Performance of empirical risk minimization in linear aggregation. Bernoulli,
22(3):1520–1534, 2016.
[33] Michel Ledoux and Michel Talagrand. Probability in Banach spaces, volume 23 of Ergebnisse der Mathematik und ihrer
Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1991. Isoperimetry and
processes.
[34] Pascal Massart and Caroline Meynet. The Lasso as an ℓ1 -ball model selection procedure. Electron. J. Stat., 5:669–687,
2011.
[35] Andreas Maurer, Charles Micchelli, and Massimiliano Pontil. A family of penalty functions for structured sparsity. NIPS,
2010.

40

[36] Andreas Maurer and Massimiliano Pontil. Structured sparsity and generalization. J. Mach. Learn. Res., 13:671–690,
2012.
[37] Shahar Mendelson. Learning without concentration for a general loss function. In Topics in Learning Theory. Société
Mathématique de France, (S. Boucheron and N. Vayatis Eds.). To appear.
[38] Shahar Mendelson. Upper bounds on product and multiplier empirical processes. Technical report, Technion, I.I.T.,
2013. To appear in Stochastic Processes and their Applications.
[39] 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.
[40] Shahar Mendelson. Learning without concentration. J. ACM, 62(3):Art. 21, 25, 2015.
[41] Srebro Nathan and Shraibman Adi. Rank, trace-norm and max-norm. 18th Annual Conference on Learning Theory
(COLT), 2005.
[42] 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.
[43] M. M. Rao and Z. D. Ren. Theory of Orlicz spaces, volume 146 of Monographs and Textbooks in Pure and Applied
Mathematics. Marcel Dekker, Inc., New York, 1991.
[44] Garvesh Raskutti, Martin J. Wainwright, and Bin Yu. Minimax rates of estimation for high-dimensional linear regression
over ℓq -balls. IEEE Trans. Inform. Theory, 57(10):6976–6994, 2011.
[45] Philippe Rigollet and Alexandre Tsybakov. Exponential screening and optimal rates of sparse estimation. Ann. Statist.,
39(2):731–771, 2011.
[46] Angelika Rohde and Alexandre B. Tsybakov. Estimation of high-dimensional low-rank matrices. Ann. Statist., 39(2):887–
930, 2011.
[47] Mark Rudelson and Roman Vershynin. Small ball probabilities for linear images of high-dimensional distributions. Int.
Math. Res. Not. IMRN, (19):9594–9617, 2015.
[48] Weijie Su and Emmanuel J. Candès. SLOPE is adaptive to unknown sparsity and asymptotically minimax. Ann. Statist.,
44(3):1038–1068, 2016.
[49] Michel Talagrand. The supremum of some canonical processes. Amer. J. Math., 116(2):283–325, 1994.
[50] Michel Talagrand. The generic chaining. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2005. Upper
and lower bounds of stochastic processes.
[51] Robert Tibshirani. Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser. B, 58(1):267–288, 1996.
[52] A. N. Tikhonov. On the stability of inverse problems. C. R. (Doklady) Acad. Sci. URSS (N.S.), 39:176–179, 1943.
[53] Sara A. van de Geer. The deterministic lasso. 2007. In JSM proceedings. American Statistical Association.
[54] Aad W. van der Vaart and Jon A. Wellner. Weak convergence and empirical processes. Springer Series in Statistics.
Springer-Verlag, New York, 1996. With applications to statistics.
[55] Nicolas Verzelen. Minimax risks for sparse regressions: ultra-high dimensional phenomenons. Electron. J. Stat., 6:38–90,
2012.
[56] Zhan Wang, Sandra Paterlini, Fuchang Gao, and Yuhong Yang. Adaptive minimax regression estimation over sparse
ℓq -hulls. J. Mach. Learn. Res., 15:1675–1711, 2014.
[57] Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. J. R. Stat. Soc. Ser. B Stat.
Methodol., 68(1):49–67, 2006.

41

