arXiv:1608.00757v1 [math.ST] 2 Aug 2016

Risk minimization by median-of-means tournaments
Gábor Lugosi†‡

Shahar Mendelson

∗

§

August 3, 2016

Abstract
We consider the classical statistical learning/regression problem, when the value of a
real random variable Y is to be predicted based on the observation of another random
variable X. Given a class of functions F and a sample of independent copies of (X, Y ), one
needs to choose a function fb from F such that fb(X) approximates Y as well as possible,
in the mean-squared sense. We introduce a new procedure, the so-called median-of-means
tournament, that achieves the optimal tradeoff between accuracy and confidence under
minimal assumptions, and in particular outperforms classical methods based on empirical
risk minimization.

1

Introduction

Estimation and prediction problems are of central importance in statistics and learning theory.
In the standard regression setup, (X, Y ) is a pair of random variables: X takes its values in
some (measurable) set X and is distributed according to an unknown probability measure µ,
while Y is real valued that is also unknown. Given a class F of real-valued functions defined
on X , one wishes to find f ∈ F for which f (X) is a good prediction of Y . Although one
may consider various notions of ‘a good prediction’, we restrict our attention to the–perhaps
most commonly used–squared error : the learner is penalized by (f (X) − Y )2 for predicting
f (X) instead of Y . Thus, one would like to find a function f ∈ F for which the expected loss
E(f (X) − Y )2 , known as the risk, is as small as possible. Naturally, the best performance one
may hope for is of the risk minimizer in the class, that is, that of
f ∗ = argmin E(f (X) − Y )2 .
f ∈F

We assume in what follows that the minimum is attained and f ∗ ∈ F exists and is unique,
as is the case when F ⊂ L2 (µ) is a closed, convex set.
One may formulate two natural goals in estimation and prediction problems. One of them
is to find a function f ∈ F whose L2 (µ) distance to f ∗

1/2
E (f (X) − f ∗ (X))2
(1.1)
∗

Gábor Lugosi was supported by the Spanish Ministry of Economy and Competitiveness, Grant MTM201567304-P and FEDER, EU. Shahar Mendelson was supported in part by the Israel Science Foundation.
†
Department of Economics and Business, Pompeu Fabra University, Barcelona, Spain, gabor.lugosi@upf.edu
‡
ICREA, Pg. Llus Companys 23, 08010 Barcelona, Spain
§
Department of Mathematics, Technion, I.I.T, and Mathematical Sciences Institute, The Australian National University, shahar@tx.technion.ac.il

1

is as small as possible. The other is to ensure that the excess risk of the selected function
R(f ) = E(f (X) − Y )2 − E(f ∗ (X) − Y )2 ,

(1.2)

is a small.
The crucial difference between this type of problems and standard questions in approximation theory is that the available information is limited to a random sample. One observes
DN = ((X1 , Y1 ), . . . , (XN , YN )), that is, N independent pairs, where each (Xi , Yi ) has the
same distribution as (X, Y ) and DN is independent of (X, Y ). The fact that the distribution of the pair (X, Y ) is not known makes it impossible to invoke approximation-theoretical
methods and identify directly the true minimizer of the risk.
Given a sample size N , a learning procedure is a map Φ : (X × R)N → F that assigns to
b
each sample DN = (Xi , Yi )N
i=1 a (random) function in F, which we denote by fN . The mean
squared error (also called the estimation error ) of Φ is the squared L2 (µ) distance between the
true minimizer f ∗ and the function selected by Φ given the data DN , that is, the conditional
expectation

kfbN − f ∗ k2L2 = E (fbN (X) − f ∗ (X))2 |DN ≡ Ee2 ,
where throughout the article, for q ≥ 1, we use the notation
kf − gkLq = (E |f (X) − g(X)|q )1/q

and also

kf − Y kLq = (E |f (X) − Y |q )1/q .

The excess risk, also known as the prediction error, compares the ‘predictive capabilities’
of fbN to that of the best in the class, and is defined by the conditional expectation

R(fbN ) = E (fbN (X) − Y )2 |DN − E(f ∗ (X) − Y )2 ≡ Ep2 .

Both the mean squared error and the excess risk are functions of the given data DN , and
as such are random quantities. It is worth noting here that in the special situation when
f ∗ (X) = E(Y |X), we have R(fbN ) = kfbN − f ∗ k2L2 . This is the case, for example, when
Y = f (X) + W for some f ∈ F and a zero-mean random variable W that is independent of
X. However, in general, a small mean squared error does not automatically imply a small
excess risk, or vice-versa.
In what follows we refer to both Ee and Ep as the accuracy1 of learning procedure Φ. The
confidence of Φ for an error rate of E is the probability (with respect to the product measure
on (X × R)N endowed by the pair (X, Y )) with which Φ performs with accuracy smaller than
E.
Note that, up to this point, Y was an arbitrary square-integrable real-valued random
variable, and obviously one would like to be able to treat as wide a variety of targets as
possible. Clearly, the accuracy and confidence one may establish may depend on some features
of the target–for example, some a-priori estimate on its Lq norm–, or on its “distance” to F,
etc. We consider a broad set of admissible targets Y, and the accuracy and confidence of Φ
relates to its performance for any admissible target Y ∈ Y. Thus, a learning problem is the
triplet (F, Y, X), when X and Y are not known, though the learner does know that Y ∈ Y.
It is clear that there is a tradeoff between the accuracy and confidence in a given learning
problem: the smaller the error is, the harder it is to attain it. The question of this accuracy/confidence tradeoff is of utmost importance in statistical learning theory, and has been
1

Sometimes the accuracy is defined by Ee2 and Ep2 .

2

investigated extensively in numerous manuscripts since the early days of the area in the late
1960’s (see, for example, the books [42, 13, 41, 2, 39, 28, 22, 38, 10] for a sample of the work
devoted to this question). To find the right accuracy/confidence tradeoff one must first identify a lower bound on the tradeoff in terms of the sample size, the structure of F and possibly
some additional information on X and Y , and then come up with a learning procedure that
attains the tradeoff.
Roughly put, one should explore the tradeoff for the set of “achievable accuracies” of
each learning problem. An accuracy E is achievable if there is a learning procedure in F
that achieves the accuracy E for the problem (F, Y, X) with constant probability–say at least
3/4–, and because Y is not known, this has to hold for any Y ∈ Y. We define the accuracy
edge as the smallest achievable accuracy of a problem.
The primary question is to find the correct accuracy/confidence tradeoff for any (reasonable) learning problem and identify a learning procedure that attains that tradeoff all the way
down to the accuracy edge. It should be noted that up to this point in time, and other than
in a few isolated examples, no learning procedure even came close to the optimal tradeoff at
any nontrivial accuracy level.
In this article we solve this problem by presenting an optimal learning procedure: it yields
the best possible accuracy/confidence tradeoff (almost) up to the achievable edge, and under
minimal assumptions on the learning problem.
The minor reservation “almost” is due to fact that more often than not, the identity of the
accuracy edge of a learning problem is not known. As it is explained in what follows, while one
may provide lower estimates on the accuracy edge, there is a very real possibility that such
estimates are too optimistic and the real accuracy edge is larger. Regardless, the procedure
we introduce “gets as close” to the accuracy edge as any other known procedure–or better,
and with a dramatically better confidence. It also exhibits the optimal accuracy/confidence
tradeoff for larger errors, something that no other procedure is known to do.
It should be clarified at this point that by “optimal accuracy” we mean an accuracy that is
optimal up to a constant factor and optimality in the confidence means that the probability
with which the claimed accuracy does not hold is optimal up to a constant factor in the
exponent.
Before we present a more accurate formulation of our main results and describe the optimal
procedure, let us explain what our procedure is not: it is not empirical risk minimization
(ERM), nor any of its “family members”.

1.1

ERM–the wrong choice

Perhaps the most natural way of choosing fbN is by empirical risk minimization, that is, by
least squares regression,
N
X
b
(f (Xi ) − Yi )2 .
fN = argmin
f ∈F

i=1

Again, we assume that the minimum is attained, while if there are several minimizers, fbN
may be chosen among them in an arbitrary way.
The performance of least squares regression has been thoroughly studied in many different
scenarios. A sample of the rich literature includes Györfi, Kohler, Krzyzak, Walk [17], van de
Geer [39], Bartlett, Bousquet, and Mendelson [6], Koltchinskii [23], Massart [28].

3

The simple
risk minimization is that, for each f ∈ F, the empirical
PN idea behind empirical
2
risk (1/N ) i=1 (f (Xi ) − Yi ) is a good estimate of the risk E(f (X) − Y )2 and the minimizer
of the empirical risk should nearly match that of the “true” risk.
It turns out that the performance of ERM changes dramatically according to the tail
behaviour of the functions involved in the given learning problem. One may show (see,
e.g., [24]) that if F is convex and the functions in F (more precisely, the random variables
{f (X) : f ∈ F}) and the target Y have well-behaved tails (and by “well-behaved” we mean
sub-Gaussian), ERM preformed in F yields good results: for an accuracy that is not far from
the accuracy edge, it attains the optimal confidence, though it does not maintain the optimal accuracy/confidence tradeoff for larger errors. Unfortunately, the situation deteriorates
considerably when either members of F or one of the admissible targets is heavy-tailed in
some sense. In such cases, the performance of ERM is significantly weaker than the known
theoretical limitations of the accuracy/confidence tradeoff. Moreover, replacing ERM with
a different procedure is of little use: other than in few and rather special learning problems, there have been no known alternatives to ERM whose performance comes close to the
known theoretical limitations of the accuracy/confidence tradeoff, and certainly not when the
problem is heavy-tailed.
The reason for ERM’s diminished capacity is that it is sensitive to even a small number
of atypical points in the sample (Xi , Yi )N
i=1 : since ERM selects a minimizer of the empirical
mean of the squared loss, atypical values may distort the selection and send ERM to the
wrong part of F. This sensitivity is clearly reflected in the confidence with which ERM
operates in heavy-tailed situations: roughly put, one can guarantee that ERM performs with
the right accuracy only on samples that are not contaminated by a significant number of
atypical values. However, in heavy-tailed situations, the latter does not occur frequently, and
having atypical values is simply a fact of life one has to deal with.
In contrast, the procedure we suggest as an alternative to ERM leads to the optimal
accuracy/confidence tradeoff even in heavy-tailed situations. Unlike ERM, it is not sensitive
even to a large number of atypical sample points.
Before we dive into a more technical description of our results, let us present the following
classical example of linear regression in Rn , exhibiting the limitations of empirical risk minimization in heavy-tailed problems, and comparing its performance to that of the procedure
we introduce.
Let F = {ht, ·i : t ∈ Rn } be the class of linear functionals on Rn . Let X be an isotropic
random vector in Rn (i.e., E ht, Xi2 = 1 for every t in the Euclidean unit sphere) and assume
that X exhibits some (very weak) norm equivalence in the following sense: there are q > 2
and L > 1 for which, for every t ∈ Rn , k hX, ti kLq ≤ Lk hX, ti kL2 .
Assume that one is given N noisy measurements of ht0 , ·i for a fixed but unknown t0 ∈ Rn .
Specifically, assume that Y = ht0 , Xi + W for some symmetric random variable W that is
independent of X and has variance σ 2 . One observes the “noisy” data (Xi , Yi )N
i=1 and the
aim is to approximate t0 with a small error (accuracy) and with high probability (confidence)
using this random data only.
One may show that a nontrivial estimate is possible only when N ≥ cn for a suitable
absolute constant c, and we consider only such values of N . Also, there are known estimates
on the theoretical
limitations of this problem: a lower bound on the accuracy edge is of the
p
order
p of σ n/N , and for an accuracy level that is proportional to the accuracy edge, say,
c0 σ n/N for a suitable absolute constant c0 , the conjectured confidence is 1 − 2 exp(−c1 n).
If there is no information on higher than q-th moments for linear functionals, and no
4

information beyond the second moment for W is available, this clearly is a (potentially)
heavy-tailed scenario. It turns out (the claims made here follow from results of [24], see the
next section for the general statements) that the best that one can guarantee using ERM is
t, X − ht0 , Xi kL2 ≤ r with
a choice of b
t ∈ Rn , for which the Euclidean norm kb
t − t0 k2 = k b
probability at least 1− δ − 2 exp(−cN ); the error r is defined as the smallest number for which
N
1 X
(∗) = √
Wi Xi
N i=1

2

√
≤ c Nr

with probability at least 1 − δ .

Since X is isotropic, one has EkXk22 = n. Therefore, the mean of (*) is bounded as
N
1 X
Wi Xi
E √
N i=1

2



N
1 X

≤ E √
Wi Xi
N i=1

2

2

1/2


√
= σ(EkXk22 )1/2 = σ n .

Moreover, because of the minimal assumptions on W and X, the best estimate one can hope
for on (∗) and that holds with probability 1 − δ follows from Chebyshev’s inequality. In
particular, it leads to the following, rather unsatisfactory, estimate on the performance of
ERM:
r
c
(q,
L)
n
0
σ
with probability 1 − δ − 2 exp(−c1 N ) .
kb
t − t0 k2 ≤
δ
N

Also, if one wishes for
p an error that is proportional to the (conjectured) accuracy edge, that
is, of the order of σ n/N , the best that one can hope for is a constant confidence–a very
different estimate from the conjectured confidence of 1 − 2 exp(−c1 n).
Although what we have described is an upper bound, one may show (see [24]) that this
estimate captures the performance of empirical risk minimization, and in particular exhibits
ERM’s inability to deal with atypical
sample points. The reality is that ERM performs with
p
an accuracy of the order of σ n/N only on the relatively few samples that contain almost
no misleading data.
The main result of this article, when applied to this example, shows that under the same
assumptions, the procedure we suggest selects b
t for which
r
n
b
with probability 1 − 2 exp(−cn)
(1.3)
kt − t0 k2 ≤ Cσ
N

for some numerical constants c, C > 0; that is, it performs with optimal confidence at a level
that is proportional to the
paccuracy edge. In fact, our procedure gives the optimal confidence
for any accuracy r ≥ c′ σ n/N .
Note that for the special case of linear regression described above, Hsu and Sabato [19]
achieve slightly (by a factor logarithmic in n) weaker bounds than (1.3) under slightly stronger
((4 + ǫ)-th moment) assumptions. We also refer to Minsker [34] for related bounds for sparse
regression under possibly heavy-tailed variables. Of course, these results hold in a rather
special example, while our main result yields optimal estimates for almost any convex class
F and target Y , and not just for linear regression in Rn .
In the next section we present the required definitions, outline the current state of the
art, and formulate our main results. In Section 3, we describe the new procedure in detail.
In Section 4 we illustrate the power of the main results on some canonical examples, before
turning to the proofs of our results.
5

Let us point out the well-understood fact that the behaviour of the accuracy and confidence
in learning problems in which F is not convex is trivial in some sense, and totally different
from the convex case, which is why focus on the latter. As it happens, the dominating
factor in non-convex problems is the ‘location’ of the targets Y relative to F rather than the
structure of F, and an ‘unfavourable location’ of a target Y completely distorts the accuracy
and confidence of the learning problem. However, even if F is not convex, all the targets of
the form Y = f0 (X) + W for f0 ∈ F and W that is symmetric and independent of X happen
to be in a ‘favourable’ location and thus our results apply to such problems as well.

2

The accuracy edge and the accuracy/confidence tradeoff

We begin by describing the known theoretical limitations on the accuracy edge and on the
accuracy/confidence tradeoff for a given learning problem. To this end, let us introduce some
notation, following the path of [29, 30].
Let D = {f : kf kL2 ≤ 1} be the unit ball in L2 (µ) and set S = {f : kf kL2 = 1} to be the
unit sphere. For h ∈ L2 (µ) and r > 0, put rDh = {f : kf − hkL2 ≤ r}. Let
star(F, h) = {λf + (1 − λ)h : 0 ≤ λ ≤ 1, f ∈ F} .
Thus, star(F, h) is the star-shaped hull of F around h, that is, the union of all segments for
which one end-point is h and the other is in F.
The star-shaped hull star(F, h) adds regularity to the class around the fixed centre h: on
the one hand, it does not increase the size of the class by much, while on the other hand, it
implies that every function of the form f − h has a ‘scaled-down’ version when one moves
towards 0. In particular, the level sets star(F − h, 0) ∩ rS become ‘richer’ as r gets smaller:
each one of them contains scaled-down copies of all ‘higher’ levels.
Consider the localization of F
Fh,r = star(F − h, 0) ∩ rD,
which is given by the shift that maps the designated point h to 0. Then the resulting class
is made ‘more regular’ by taking its star-shaped hull around 0, and finally it is localized, by
considering its intersection with rD, the L2 (µ) ball of radius r, centred in 0.
Observe that if F is convex then for any h ∈ F, star(F, h) = F. Also, in that case,
Fh,r = {f − h : f ∈ F, kf − hkL2 ≤ r} ,
and if, in addition, F is centrally symmetric (that is, if f ∈ F then −f ∈ F), then Fh,r ⊂
2F ∩ rD.
One way of deriving lower estimates on the accuracy edge and on the accuracy/confidence
tradeoff is based on the packing numbers of the localizations Fh,r .
Definition 2.1. Given a set H ⊂ L2 (µ) and ε > 0, denote by M(H, εD) the cardinality of a
maximal ε-separated subset of H. That is, M(H, εD) is the maximal cardinality of a subset
{h1 , ..., hm } ⊂ H, for which khi − hj kL2 ≥ ε for every i 6= j.
Note that if H ′ is a maximal ε-separated subset of H, then it is also an ε-cover of H in
the sense that for every h ∈ H there is some h′ ∈ H ′ that satisfies kh′ − hkL2 ≤ ε.
6

Definition 2.2. For κ, η > 0 and h ∈ F, set
λQ (κ, η, h) = inf{r : log M(Fh,r , ηrD) ≤ κ2 N } ,

(2.1)

and let
λQ (κ, η) = sup λQ (κ, η, h) .
h∈F

For every fixed h ∈ F , the parameter λQ pin-points the level r at which the localization
Fh,r becomes “too rich” in the following sense: given the sample size N , Fh,r contains a subset
of cardinality exp(κ2 N ) that is ηr-separated with respect to the L2 (µ) norm. Note that λQ
is not affected by the fine structure of Fh,r . Indeed, the set Fh,r ∩ (ηr/2)D cannot contain
more than two points that are ηr-separated, and thus it does not contribute to the existence
of a large ηr-separated set in Fh,r .
One may show that λQ serves as a lower bound on the accuracy edge of a learning problem,
when F is convex and centrally symmetric and the admissible targets are noise-free: that is,
Y = {f (X) : f ∈ F}.
Proposition 2.3. [30] There exist absolute constants κ and η for which the following holds.
Let F ⊂ L2 (µ) be convex and centrally symmetric. For any learning procedure Φ there exists
an f0 ∈ F and target Y = f0 (X) for which, with probability at least 1/4,
kΦ(DN ) − f0 k2L2 ≥ λQ (κ, η) .
The following variant of λQ also serves as a lower bound on the accuracy edge, this time,
because of ‘noisy’ targets.
Definition 2.4. For κ > 0, 0 < η < 1 and h ∈ F, set
λM (κ, η, h) = inf{r : log M(Fh,r , ηrD) ≤ κ2 N r 2 }

(2.2)

and let
λM (κ, η) = sup λM (κ, η, h) .
h∈F

Proposition 2.5. (See, e.g., [30].) There exist absolute constants κ and η for which the
following holds. Let F ⊂ L2 (µ) and set W to be a centred Gaussian variable with variance
σ > 0 that is independent of X. Then, for any learning procedure Φ there exists f0 ∈ F and
a target Y = f0 (X) + W for which, with probability at least 1/4,
kΦ(DN ) − f0 k2L2 ≥ λM (κ/σ, η) .
In particular, if Y contains all the targets of the form f0 (X) + W , for f0 ∈ F and W that
is a centred Gaussian variable with variance σ that is independent of X, then the accuracy
edge is at least λM (κ/σ, η).
Combining these two facts, we have a lower bound on the accuracy edge:
λ∗ ≡ max{λQ (κ1 , η1 ), λM (κ2 /σ, η2 )} ,
for some constants κi , ηi , i = 1, 2. However, there is no guarantee that this lower estimate is
sharp. As we explain in what follows, it is very possible that the true accuracy edge is larger.
7

Let us turn to the theoretical limitations of the accuracy/confidence tradeoff, assuming
that the set of admissible targets Y is not too trivial. By that we mean that it at least
contains all the targets of the form Y = f0 (X) (the noise-free problems) and Y = f0 (X) + W ,
for f0 ∈ F and W that is a centred Gaussian variable with variance σ, and is independent of
X. We call this set of targets minimal, and of course, Y could be much larger.
Applying the results in [24] and [30] one has the following:
Proposition 2.6. There exists an absolute constant c for which the following holds. Let
F ⊂ L2 (µ) be a class that is star-shaped around one of its points (i.e., for some f0 ∈ F and
every f ∈ F, [f0 , f ] ⊂ F). Consider Y that contains the minimal set of targets. If Φ is a
learning procedure that performs with accuracy r and confidence 1 − δ for every such target,
then
δ ≥ exp(−cN min{1, r 2 /σ 2 }).
These facts set our first benchmark (which may be too optimistic, of course): the lower
bound on the accuracy edge
λ∗ = max{λQ (κ1 , η1 ), λM (κ2 /σ, η2 )} ,

(2.3)

and the bound on the accuracy/confidence tradeoff for r ≥ c0 λ∗ ,

1 − 2 exp −c1 N min{1, σ −2 r 2 } .

(2.4)

As we noted earlier, λ∗ is an optimistic, and perhaps not very realistic, lower bound on
the accuracy edge. A more reasonable conjecture relies on more “global” parameters that
take into account the fine structure of F at an arbitrarily small level, defined next.
From here on, let (εi )N
i=1 be independent, symmetric {−1, 1}-valued random variables that
are independent of (Xi , Yi )N
i=1 .
Definition 2.7. For κ > 0 and h ∈ F let
(
rE (κ, h) = inf

r : E sup
u∈Fh,r

N
√
1 X
√
εi u(Xi ) ≤ κ N r
N i=1

)

,

(2.5)

and set rE (κ) = suph∈F rE (κ, h).
The parameter rE (κ, h) measures the empirical oscillation around h. It does not depend
on the identity of the target Y and is a purely intrinsic parameter of the class F. However, it
may be highly affected by functions in F that are close to h, and as such it is more “global”
than λQ .
The other “global” parameter we require does depend on Y . It is used to calibrate the
interaction between F and the target.
Definition 2.8. For κ > 0 and h ∈ F set r M (κ, h) to be
)
(
N
√ 2
1 X
εi u(Xi ) · (h(Xi ) − Yi ) ≤ κ N r .
r M (κ, h) = inf r : E sup √
N i=1
u∈Fh,r
(σ)

For σ > 0 put FY

(2.6)

= {f ∈ F : kf (X) − Y kL2 ≤ σ} and let reM (κ, σ) = suph∈F (σ) rM (κ, h).
Y

8

(σ)

Remark. The role of σ and of FY in Definition 2.8 deserves some explanation. The mean
oscillation in Definition 2.8 involves the “multipliers” (h(Xi ) − Yi )N
i=1 , and the right choice for
the centre h is the unknown f ∗ . While one may take into account the “worst” h ∈ F, doing
so makes little sense, as f ∗ is the minimizer of the L2 distance between F and Y , and for the
worst h, kh − Y kL2 could be significantly larger than kf ∗ − Y kL2 . To overcome this obstacle
we assume that an a-priori estimate on the L2 distance between Y and F (i.e., a value σ such
that kf ∗ − Y kL2 ≤ σ) is available. With this information one still needs to consider the worst
centre h, but only among all functions h ∈ F that satisfy kh − Y kL2 ≤ σ. As we explain
in Section 4, thanks to known estimates for the expectation of the supremum of a multiplier
process, one only needs to keep in mind that the multipliers ξi = h(Xi ) − Yi are independent
copies of some random variable ξ that satisfies some moment condition, such as kξkLq ≤ Lσ
for some q > 2 and a suitable constant L.
In light of the results from [29], a realistic alternative to λ∗ is
r ∗ = max{λQ (c1 , c2 ), λM (c1 /σ, c2 ), rE (c1 ), reM (c1 , σ)} ,

(2.7)

for some constants c1 , c2 , and when for the given (and unknown) target Y ∈ Y one has
kY − f ∗ (X)kL2 ≤ σ. Indeed, in [29] it was shown that under some mild conditions on
the learning problem, specified below, ERM performs in F with accuracy cr ∗ and constant
confidence. Thus, r ∗ is a potential (and to-date, the best) candidate for the accuracy edge.
Therefore, up to the issue of the true identity of the accuracy edge, the (somewhat vaguely
formulated) question of the accuracy/confidence tradeoff is as follows:
Question 2.9. Is there a learning procedure which, for any reasonable learning problem
 and
∗
−2
2
any r ≥ c1 r , performs with accuracy r and confidence 1 − 2 exp −c2 N min{1, σ r } , thus
achieving the optimal accuracy/confidence tradeoff ?
Our main result answers Question 2.9 in the affirmative where our notion of a “reasonable
learning problem” is formulated rigorously below.
The first theorem we present requires the following conditions:
Assumption 2.1. Let L be a constant and let X be distributed according to the measure µ
on X . Given a locally compact, convex class of functions F ⊂ L2 (µ) and Y ∈ L2 , assume
that
• for every f, h ∈ F, kf − hkL4 ≤ Lkf − hkL2 ;
• for every f ∈ F, kf − Y kL4 ≤ Lkf − Y kL2 ;
• kf ∗ − Y kL2 ≤ σ for some known constant σ > 0.
Theorem 2.10. Let L ≥ 1, σ > 0, and suppose Assumption 2.1. There exist constants
c, c0 , c1 and c2 that depend only on L for which the following holds. Let
r ∗ (f ∗ ) = max{λQ (c1 , c2 , f ∗ ), λM (c1 /σ, c2 , f ∗ ), rE (c1 , f ∗ ), r M (c1 , f ∗ )} ,
and fix r ≥ 2r ∗ (f ∗ ).
There exists a procedure that, based on the data DN = (Xi , Yi )N
i=1 and the values of L, σ
and r, selects a function fb ∈ F such that, with probability at least

1 − exp −c0 N min{1, σ −2 r 2 } ,

kfb − f ∗ kL2 ≤ cr and E (fb(X) − Y )2 |DN ≤ E(f ∗ (X) − Y )2 + (cr)2 .
9

Of course, the identity of f ∗ is not known, and therefore, it is not reasonable to expect
that r ∗ (f ∗ ) is known beforehand. A “legal” data-independent choice is any r ≥ 2r ∗ that
is larger than 2r ∗ (f ∗ ) regardless of the identity of f ∗ . In particular, Theorem 2.10 gives
the optimal accuracy/confidence tradeoff for any accuracy r ≥ 2r ∗ . Alternatively, one may
consider the “right” choice of the parameter r as a model selection problem that may be
selected using cross validation if independent data are available. We do not discuss the rather
straightforward details further here.
Remark. In our main assumption of Theorem 2.10 we use the equivalence between the L4
and L2 norms for functions of the form Y − f (X). This allows us to derive bounds in terms
of the variance of Y − f ∗ (X). In fact, if instead of norm equivalence we just have a bound
on σ4 = kY − f ∗ (X)kL4 , the arguments work equally well, with σ4 replacing σ. The sets FYσ
need to be adjusted as well: it should be replaced by all functions in F whose L4 distance to
Y is at most σ4 .
It turns out that, when dealing with independent noise, the assumptions required in
Theorem 2.10 may be relaxed even further. In particular, we do not require convexity of the
class F and the assumption of norm equivalence may be relaxed:
Theorem 2.11. Let q > 2, L > 1, and σ > 0. There exist constants c, c0 , c1 and c2 that
depend only on q and L for which the following holds. Let F be a locally compact class of
functions and assume that for every f ∈ span(F), kf kLq ≤ Lkf kL2 . Assume further that
Y = f0 (X) + W for some f0 ∈ F and W that is mean-zero, independent of X, and satisfies
kW kL2 ≤ σ.
Let r ∗ (f ∗ ) be as above and fix r ≥ 2r ∗ (f ∗ ). There exists a procedure that, based on the
b
data DN = (Xi , Yi )N
i=1 and the values of L, q, σ and r, selects a function f ∈ F such that,
with probability at least

1 − exp −c0 N min{1, σ −2 r 2 } ,

kfb − f0 kL2 ≤ cr and E (fb(X) − Y )2 |DN ≤ E(f0 (X) − Y )2 + (cr)2 .

Note that in the case of independent additive noise, the assumptions of Theorem 2.11
are almost the minimal needed for the learning problem to be well defined: norm equivalence for q that may be arbitrarily close to 2 and W ∈ L2 that perhaps does not have
any higher moments. Even under these minimal assumptions, we still obtain the optimal
accuracy/confidence tradeoff.

2.1

State of the art

To put Theorem 2.10 in perspective, we describe the current sharpest estimates on the accuracy and confidence of a learning problem, focusing on possibly heavy-tailed distributions.
Firstly, there were no known results that are based on the “averaged” parameter r M .
Instead, the interaction between class members and the target were measured using the
following “in-probability” version of r M :
Definition 2.12. For every κ > 0, 0 ≤ δ ≤ 1 and h ∈ F, set rM (κ, δ, h) to be the infimum of
the set of all values of r for which
!
N
√ 2
1 X
≥ 1−δ .
εi u(Xi ) · (h(Xi ) − Yi ) ≤ κ N r
P sup √
N i=1
u∈Fh,r
10

The best known estimate on prediction and estimation in a general convex class are based
on a quite weak condition, rather than the norm equivalence we use. Recall that a class F
satisfies a small-ball condition with constants κ0 and ρ0 if for every f, h ∈ F ∪ {0},
P(|f − h| ≥ κ0 kf − hkL2 ) ≥ ρ0 .
Theorem 2.13. (Mendelson [29].) Let F ⊂ L2 (µ) be a convex class that satisfies the smallball condition with constants κ0 and ρ0 , and let Y ∈ L2 . If r = max{rE (c1 ), rM (c2 , δ, f ∗ )}
and fb is selected in F using empirical risk minimization, then, with probability at least
kfb − f ∗ kL2 ≤ r

1 − δ − 2 exp(−c3 N ) ,

and E (fb(X) − Y )2 |DN ≤ E(f ∗ (X) − Y )2 + r 2 ,

(2.8)

(2.9)

for constants c1 , c2 and c3 that depend only on κ0 and ρ0 .

The obvious weakness of Theorem 2.13 is the poor tradeoff between the accuracy term
rM (c2 , δ, f ∗ ) and the confidence δ. There is no hope of obtaining a high confidence result–say
as in (2.4)–, unless both F and Y − f ∗ (X) exhibit a sub-Gaussian tail behaviour. If not, then
for δ as in (2.4), the value rM (c2 , δ, f ∗ ) is very large, and the resulting accuracy estimate is
rather useless–far worse than r ∗ . Moreover, replacing the small-ball assumption with some
norm equivalence as in Theorem 2.10 does not improve the outcome. Thus, Theorem 2.13
is significantly weaker than Theorem 2.10 in every aspect. This phenomenon exhibits the
nature of ERM: it does not perform with both high accuracy and high confidence in heavytailed situations, and falls well short of our benchmarks, but still, it was the best available
alternative prior to this work.

Regression in Rn revisited
We now show how our general results imply the optimal accuracy/confidence tradeoff for
linear regression in Rn all the way to a number proportional to the conjectured accuracy
edge.
Recall that the class of functions in question is F = {ht, ·i : t ∈ Rn }, X is an isotropic
random vector on Rn (i.e., E ht, Xi2 = 1 for every t in the Euclidean unit sphere), and
Y = ht0 , ·i + W , for t0 ∈ Rn and a symmetric random variable W ∈ L2 that is independent of
X and has variance σ 2 . Thus, f ∗ = f0 and Ff ∗ ,r = {ht − t0 , ·i : kt − t0 k2 ≤ r}. If W1 , ..., WN
are independent copies of W , then by a standard symmetrization argument and since X is
isotropic,
+
*N
N
X
1
1 X
εi u(Xi ) · (f ∗ (Xi ) − Yi ) ≤ 2E sup √
εi Wi Xi , t
E sup √
N i=1
N i=1
t∈rB2n
u∈Fh,r
N
X
2r
εi Wi Xi
=√ E
N
i=1

2

√
≤ 2rkW kL2 (EkXk22 )1/2 = 2rσ n ,

where B2n is the Euclidean unit ball in Rn . Now (1.3) follows from Theorem 2.11, assuming that the Lq (µ) and L2 (µ) norms are equivalent on span(F); that is, for every t ∈ Rn ,

11

p
k ht, Xi kLq ≤ Lk hX, ti kL2 . Indeed, the above shows that r M (c1 , f ∗ ) ≤ 2c−1
1 σ n/N . A similar argument leads to rE (c1 ) = 0 when N ≥ cn for a constant c that depends only on c1 .
Also, by a volumetric estimate,
log M(Ff ∗ ,r , ηrD) = log M(rB2n , ηrB2n ) ∼ n log(2/η) ;
p
hence, for N ≥ cn, λQ (c1 ) = 0 and λM (c
p1 /σ, c2 ) ∼ σ n/N, implying in particular that the
lower bound on the accuracy edge is cσ n/N .
In other words, when
p N ≥ cn, the procedure exhibits the optimal accuracy/confidence
tradeoff for any r ≥ c3 σ n/N .

In Section 4 we present two more examples, in which we obtain the (previously unknown)
optimal accuracy/confidence tradeoff. The first example studies regression in an arbitrary
convex, centrally symmetric subset of Rn when the underlying measure is sub-Gaussian, but
the target may be heavy-tailed. In the other example we focus on regression in ρB1n =
{t ∈ Rn : ktk1 ≤ ρ}, but under significantly weaker assumptions on the underlying measure.
Regression in ρB1n is of central importance in sparse recovery, specifically, in the study of the
basis pursuit procedure and the LASSO. We refer the reader to the books [22, 16, 40] for
more information on sparse recovery and on these procedures.

3

The median-of-means tournament

The key to obtaining sharp estimates for both the accuracy and the confidence is identifying
a procedure that is not sensitive to atypical values that may occur on a small part of the
given sample. Thus, a natural starting point is the conceptually simple and attractive mean
estimator, the so-called median-of-means estimator. It was proposed, independently, by Nemirovsky and Yudin [35], Jerrum, Valiant, and Vazirani [21], Alon, Matias, and Szegedy [1],
and is defined as follows.
Let Z1 , . . . , ZN be independent, identically distributed real random variables with a finite
second moment. The median-of-means estimator of µ = EZ1 has parameter δ ∈ [e1−N/2 , 1).
Setting n = ⌈ln(1/δ)⌉, one may partition {1, ..., N } into n blocks I1 , . . . , In , each of cardinality
|Ij | ≥ ⌊N/n⌋ ≥ 2. Compute the sample mean in each block
Wj =

1 X
Zi
|Ij |
i∈Ij

(δ)

and define µ
bN as the median of W1 , . . . , Wn . (If the median is not uniquely defined, here,
and in the rest of the paper, we choose the smallest one. Any other choice would work equally
well.) It is straightforward to verify that for any N ≥ 4,
)
(
r
p
(1 + ln(1/δ))
(δ)
≤δ ,
(3.1)
P |b
µN − µ| > 2e 2Var(Z)
N
where Var(Z) denotes the variance of Z. In other words, the median-of-means estimator
achieves a high (sub-Gaussian) confidence under the minimal assumption that the variance
Var(Z) is finite. Note that the high confidence is valid even though Z can be heavy-tailed,
and thus a nontrivial part of the sample (Zi )N
i=1 may be atypical in the sense that Zi is ‘far
away’ from µ.
12

For properties, applications, and extensions of the median-of-means estimator, we refer to
Bubeck, Cesa-Bianchi, and Lugosi [9]. Devroye, Lerasle, Lugosi, and Oliveira [14] Hsu and
Sabato [18], Lerasle and Oliveira [27], Minsker [34], Audibert and
[3].
PCatoni
N
It is tempting to try to replace the empirical means (1/N ) i=1 (f (Xi ) − Yi )2 by some
median-of-means estimate of the risk for each f ∈ F, and select a function in F that minimizes
the estimate. However, due to the nonlinear nature of the median-of-means, it is difficult to
control the process of the estimated losses. Instead, the alternative we propose is to estimate
the difference of the risk for all pairs f, h and organize a two-stage “tournament”.
We mention here that Brownlees, Joly, and Lugosi [8] propose empirical minimization
based on a different robust mean estimator, a carefully designed M-estimator proposed by
Catoni [11]. Under general loss functions they derive analogs of Dudley’s chaining bound
for the excess risk. However, the derived bounds are far from giving the optimal rate of
convergence under the squared loss.
Without loss of generality and for convenience in the notation, we use 3N instead of N
for the sample size and assume that D3N = (Xi , Yi )3N
i=1 is the given sample. The sample is
2N
3N
split into three equal parts (Xi , Yi )N
,
(X
,
Y
)
i i i=N +1 and (Xi , Yi )i=2N +1 . Given the wanted
i=1
degree of accuracy r ≥ r ∗ , the first part of the sample–in fact, just (Xi )N
i=1 –is used to estimate
pairwise distances within F, in a sense that will be clarified below. The second part is used in
the preliminary round of the tournament. We show that the outcome of the preliminary round
is a set H ⊂ F that contains f ∗ and possibly some other functions whose L2 (µ) distance to f ∗
is at most cr. The final part of the tournament is a ‘champions league’ round. Participants
in that final round are the elements in H (the ‘qualifiers’ of the preliminary round), and the
goal of that round is to identify a function fb ∈ H whose predictive capabilities are almost
optimal, in the sense that

E (fb(X) − Y )2 |D3N ≤ E(f ∗ (X) − Y )2 + cr 2 ,

as required. This last round is only needed to guarantee the desired excess risk. The first
two rounds suffice to output a function whose L2 (µ) distance to f ∗ is at most cr: one may
simply select an arbitrary element of H. Also note that in the setup of Theorem 2.11, the
third round is not required as the conditions of the theorem imply that f ∗ (X) = E(Y |X), and
the excess risk equals the mean squared error; thus, any fb ∈ H has the desired performance.
Let us now describe the three stages of the median-of-means tournament is detail.

3.1

The ‘referee’: the distance oracle

Like all good tournaments, ours too requires a ‘referee’, whose role is to decide whether a
match (described below) is allowed to take place. The referee’s decision is based on a distance
oracle–a data dependent functional that allows one to crudely identify distances between
functions in F. The functional is constructed via the median-of-means philosophy. Without
loss of generality and for ease of exposition, we may assume that N is an integer multiple of
ℓ in the next definition.
Definition 3.1. Let 1 ≤ ℓ ≤ N and set Ij′ to be the partition of {1, ..., N } to disjoint
intervals of P
cardinality ℓ. Set k = N/ℓ and for v ∈ RN let Medℓ (v) be the median of the
k
−1
means (ℓ
i∈I ′ vi )j=1 .
j

Recall that one of our assumptions is an Lq -L2 norm equivalence, that is, that there are
q > 2 and L ≥ 1, such that, for every f ∈ span(F), kf kLq ≤ Lkf kL2 . (In Theorem 2.10
13

we only consider q = 4.) Let ℓ = ℓ(q, L) to be specified later. For CN = (Xi )N
i=1 and every
N
f, h ∈ F, set v = (|f (Xi ) − h(Xi )|)i=1 and put
ΦCN (f, h) = Medℓ (v) .
The functional Φ allows one to identify distances in F in a crude (isomorphic) way, as the
next theorem shows:
Proposition 3.2. There exist constants κ, η, ℓ, c > 0 and 0 < α < 1 < β, all of them
depending only on q and L for which the following holds. For a fixed f ∗ ∈ F, let d∗ =
max{λQ (κ, η, f ∗ ), rE (κ, f ∗ )}. For any r ≥ d∗ , with probability at least 1 − 2 exp(−cN ), for
every f ∈ F, one has
• If ΦCN (f, f ∗ ) ≥ βr then β −1 ΦCN (f, f ∗ ) ≤ kf − f ∗ kL2 ≤ α−1 ΦCN (f, f ∗ ).

• If ΦCN (f, f ∗ ) < βr then kf − f ∗ kL2 ≤ (β/α)r.

Remark. Replacing d∗ by the larger max{λQ (κ, η), rE (κ)}, which is independent of f ∗ , a
similar assertion to Proposition 3.2 holds for all the pairs f, h ∈ F. The probability bound
in that case is essentially unchanged: 1 − 2 exp(−c′ N ). However, Proposition 3.2 is sufficient
for our purposes.
Proposition 3.2 is an immediate modification of Theorem 3.3 from [31]. For the sake of
completeness we outline the main components of its proof in the appendix.
Next we introduce the “distance oracle”, denoted by DO. Recall the definition of r ∗ from
(2.7) and note that for the right choice of constants, r ∗ ≥ d∗ . The distance oracle is adapted
to the wanted degree of accuracy, that is, to any fixed r ≥ 2r ∗ .
Definition 3.3. Fix r ≥ 2r ∗ . Using the notation of Proposition 3.2, if ΦCN (f, h) ≥ βr set
DO(f, h) = 1, otherwise set DO(f, h) = 0.

The distance oracle determines if a match between f and h takes place: it does if
DO(f, h) = 1 and it is abandoned if DO(f, h) = 0. Note that Proposition 3.2 only shows
that DO is a realistic indication of the distance between pairs when one of the functions is
the designated function f ∗ . This serves our purposes since the designated function we are
interested in is the minimizer of the true risk in F, and the success of the procedure only
requires having accurate information on matches that involve f ∗ , even if we do not know
which matches those are.
It follows from Proposition 3.2 that with probability at least 1 − 2 exp(−cN ) relative to
∗
∗
(Xi )N
i=1 , if a match between f and f is allowed to proceed then kf − f kL2 ≥ r, while if it
∗
is abandoned then kf − f kL2 ≤ (β/α)r.

3.2

The preliminary round

The goal of the preliminary round is to produce a subset H ⊂ F that, with overwhelming
∗
∗
probability over the samples (Xi , Yi )2N
i=N +1 , contains f and kh − f kL2 ≤ (β/α)r for any
h ∈ H.
The round consists of ‘matches’ between every pair f, h ∈ F, and a match can have three
possible outcomes: a win by either side, or a draw (the latter includes abandoned matches
because of the ruling of the distance oracle).
Each match is ‘played’ using the second part of the sample, (Xi , Yi )2N
i=N +1 . The sub-sample
is partitioned to n blocks (Ij )nj=1 of cardinality m = N/n each, for a choice of n specified
later. Let us note that n depends on the desired degree of accuracy r.
14

• A match between f and h takes place if the distance oracle, using the first part of the
sample (Xi )N
i=1 , declares that DO(f, h) = 1; otherwise, the match is abandoned and
results in a draw.
• Each match is decided according to the n blocks generated by the partition of (Xi , Yi )2N
i=N +1 ,
with the j-th block played on the coordinate block Ij . Put
Bf,h (j) =


1 X
(f (Xi ) − Yi )2 − (h(Xi ) − Yi )2 ,
m
i∈Ij

1≤j≤n.

The function h defeats f on the j-th block if Bf,h (j) < 0, and f defeats h if Bf,h (j) > 0.
• A winner of more than n/2 blocks is the winner of the match. If neither function wins
more than half of the blocks, the match is drawn.
Definition 3.4. A function f ∈ F qualifies from the preliminary round if it has not lost a
single match; that is, it has won or drawn all its matches. The set of “champions” H consists
of all functions qualified from the preliminary round.
The key fact regarding the outcome of the preliminary round is as follows:
Proposition 3.5. Under the assumptions of Theorem 2.10 or of Theorem 2.11, and using
their notation, with probability at least

1 − 2 exp −c0 N min{1, σ −2 r 2 ,

∗
∗
with respect to (Xi , Yi )2N
i=1 , for all h ∈ F, if DO(f , h) = 1 then f defeats h. In particular,
f ∗ ∈ H and for any h ∈ H, DO(f ∗ , h) = 0, and therefore kh − f ∗ kL2 ≤ (β/α)r.

The proof of Proposition 3.5 is presented in Section 5.1. Note that Propositions 3.2 and
3.5 imply Theorem 2.11. In order to prove the general result of Theorem 2.10, another round
of matches is necessary to choose a function from H with small excess risk.

3.3

Champions league

The goal of the second round of the tournament is to choose, among the “champions” selected
in the preliminary round, a function with a small excess risk. This round consists of different
kind of matches, played between functions in H. Since this round consists of matches between
functions in H, conditioned on the ‘good event’ from the preliminary round, every qualifier
satisfies that kh − f ∗ kL2 ≤ (β/α)r.
The modified matches are decided using the third part of the sample (Xi , Yi )3N
i=2N +1 . The
b
aim is to produce a function f ∈ H that has a good excess risk, namely,

∗
2
2
E (fb(X) − Y )2 |(Xi , Yi )3N
i=2N +1 ≤ E(f (X) − Y ) + r1 ,
for some r1 that is bounded by a constant multiple of r.
Setting Ψh,f = (h(X)−f (X))(f (X)−Y ), the significant observation here is that if EΨf ∗ ,f
is not very negative, then the prediction error associated with f is small:
Lemma 3.6. For γ > 0, if f ∈ F satisfies that EΨf ∗ ,f ≥ −γt2 , then
E(f (X) − Y )2 − E(f ∗ (X) − Y )2 ≤ 2γt2 .
15

Proof. Observe that for every f ∈ F
(f (X) − Y )2 − (f ∗ (X) − Y )2 = (f (X) − f ∗ (X))2 + 2(f (X) − f ∗ (X))(f ∗ (X) − Y ) ,
and
(f (X) − f ∗ (X))(f ∗ (X) − Y ) =(f (X) − f ∗ (X)) ((f ∗ (X) − f (X)) + (f (X) − Y ))
= − (f (X) − f ∗ (X))2 − Ψf ∗ ,f .

Therefore,
E(f (X) − Y )2 − E(f ∗ (X) − Y )2 ≤ −2EΨf ∗ ,f ≤ 2γt2 .
The role of the “champions league”
 round2is to use the third part of the sample to select
fb ∈ H for which E Ψf ∗ ,fb|(Xi , Yi )2N
i=1 ≥ −γr1 , for a suitable constant γ > 0 and r1 that is
proportional to r.
The matches in the champions league consist of “home-and-away” legs:
n
Definition 3.7. Given a sample (Xi , Yi )3N
i=2N +1 , let (Ij )j=1 be the partition of {2N + 1, 3N }
to n blocks, for the same value of n as in the preliminary round. Let β and α be as in
Proposition 3.5 and set r1 = 2(β/α)r. The function f wins its home match against h if

2 X
Ψh,f (Xi , Yi ) ≥ −r12 /10
m
i∈Ij

on more than n/2 of the blocks Ij .
We select as fb any “champion” in H that wins all of its home matches.
The main result regarding the champions league is as follows:

Proposition 3.8. Let H ⊂ F as above. Under the assumptions of Theorem 2.10 and using
its notation, with probability at least

1 − 2 exp −c0 N min{1, σ −2 r 2 }
with respect to (Xi , Yi )3N
i=2N +1 , one has:

• f ∗ wins all of its home matches, and
• if EΨf ∗ ,f ≤ −2r12 , then f loses its home match against f ∗ .
Thus, on this event, the set of possible champions is nonempty (since it contains f ∗ ), and
any other champion satisfies that EΨf ∗ ,f ≥ −2r12 and therefore, by Lemma 3.6,

∗
2
2
E (fb(X) − Y )2 |(Xi , Yi )3N
i=2N +1 − E(f (X) − Y ) ≤ 4r1 .

The proof of Proposition 3.8 is presented in Section 5.2.
The combination of Propositions 3.2, 3.5, and 3.8 yields the proof of Theorem 2.10.

16

4

Examples

Before turning to the proofs of our main results, let us present some explicit examples of
applications of Theorem 2.10.
It is an unrealistic hope to obtain a simple characterization of all involved complexity
parameters in every example. Indeed, to get good bounds for λQ and λM , one has to obtain
sharp estimates on covering numbers of what is almost an arbitrary set and with respect to
the L2 (µ) norm for an arbitrary probability measure µ. On the other hand, r M and rE depend
on the oscillation of general multiplier and empirical processes, respectively. Both types of
estimates are of central importance in modern mathematics and have been the subject of
thorough research, but they are by no means completely understood.
Having said this, there are many interesting cases in which sharp estimates may be derived.
In what follows we focus on two such examples. The first is rather general: linear regression
performed in a convex, centrally symmetric set T ⊂ Rn , under the assumption that the
underlying random vector X is L-sub-Gaussian (see the definition below). However, and
unlike the results in [24], the ‘noise’ Y − f ∗ (X) may be heavy-tailed.
The second example is similar to the first one and is motivated by questions in sparse
recovery: linear regression in the set T = ρB1n = {t : ktk1 ≤ ρ}. The difference between
this example and the first one lies in the assumption on X. In the second example X is
not assumed to be L-sub-Gaussian, but rather satisfies a much weaker moment condition,
the same condition that is needed to ensure that the basis pursuit algorithm has a unique
solution with the optimal number of measurements (see [25]).
Both examples lead to explicit estimates on the accuracy and confidence of the median-ofmeans tournament. The estimates are better than the known bounds and hold with optimal
confidence for accuracy larger than cr ∗ (though in general, the true identity of the accuracy
edge is an open question). Moreover, in the second example, of ρB1n , one may show that r ∗
is proportional to the accuracy edge, and the optimal tradeoff holds all the way down to that
value.

4.1

Coverings and Gaussian processes

Let X be an isotropic random vector in Rn , that is, for every t ∈ Rn , E hX, ti2 = ktk22 . The
assumption that X is isotropic only serves clarity of the illustration. Indeed, the L2 (µ) metric
endowed on Rn via the identification of t ∈ Rn with the linear functional h·, ti is the standard
Euclidean metric. Thus, D (the unit ball in L2 (µ)) can be identified with the Euclidean unit
ball in Rn . While it is possible to extend the results presented below to X with a general
covariance structure (in which case, D is identified with an ellipsoid in Rn ), the isotropic
example is interesting enough to serve as a proof of concept.
Thanks to the isotropicity assumption, if T is a convex and centrally-symmetric set and
F = {h·, ti : t ∈ T }, then for every h ∈ F ,
λQ (κ, η, h) ≤ inf{r : log M(2T ∩ rB2n , ηrB2n ) ≤ κ2 N } ,
and
λM (κ, η, h) ≤ inf{r : log M(2T ∩ rB2n , ηrB2n ) ≤ κ2 N r 2 } .
A standard, though sometimes suboptimal, method to estimate covering/packing numbers
relies on the theory of Gaussian processes, specifically, on Sudakov’s inequality. We formulate
17

it only in the case we need here. Denote by G = (gi )ni=1 a standard Gaussian vector in Rn .
For T ⊂ Rn let
ℓ∗ (T ) = E sup hG, ti
t∈T

the mean-width of T with respect to the Gaussian measure.
Proposition 4.1. (Sudakov [36].) There exists an absolute constant c, such that, for any
T ⊂ Rn and every ε > 0,
q
(4.1)
ε log M(T, εB2n ) ≤ cℓ∗ (T ) .
Applying Proposition 4.1 it follows that
log M(2T ∩
Hence,
and

rB2n , ηrB2n )

≤



ℓ∗ (2T ∩ rB2n )
c
ηr

2

.

√
λQ (κ, η, h) ≤ inf{r : ℓ∗ (2T ∩ rB2n ) ≤ (κη/c)r N } ,

(4.2)

√
λM (κ, η, h) ≤ inf{r : ℓ∗ (2T ∩ rB2n ) ≤ (κη/c)r 2 N } .

(4.3)

We emphasize again that replacing λQ and λM with these upper estimates, is, at times,
suboptimal. We refer the reader to [24] for more details on this issue.
The other two parameters involved in Theorem 2.10, namely, rE and r M , measure the
oscillation of multiplier and empirical processes. The analysis of such processes is highly
nontrivial–even when just considering their limits as the sample size N tends to infinity,
and one expects convergence to the limiting Gaussian process (see, for example, the book
[15] for a detailed exposition of such limit theorems). Because the estimates we require are
non-asymptotic, in general they are much harder to obtain.
The following notion makes the task of obtaining such bounds more manageable, though
still nontrivial.
Definition 4.2. A random vector X in Rn is L-sub-Gaussian if for every t ∈ Rn and any
p ≥ 2,
√
k hX, ti kLp ≤ L pk hX, ti kL2 .

Note that if X is L-sub-Gaussian and isotropic, then for every t ∈ Rn , k hX, ti kLp ≤
L pktk2 , because k hX, ti kL2 = ktk2 .
The simplest examples of isotropic, L-sub-Gaussian random vectors are vectors with independent, mean-zero, variance 1 components that are sub-Gaussian. For instance, the standard
Gaussian vector (gi )ni=1 , and (εi )ni=1 , whose components are independent, symmetric random
signs are both L-sub-Gaussian for a constant that is independent of the dimension n. Another
family of examples consists of the random vectors whose density is uniform on sets of the form
{t : ktkp ≤ cn1/p } for some p ≥ 2, normalized to have volume 1. Again, L is an absolute
constant, independent of n and p (see, e.g., [5, 4]).
The reason for considering a sub-Gaussian random vector X is that, by Talagrand’s theory of generic chaining (see the book [37] for an extensive exposition on the subject), the
oscillations in question may be controlled using the oscillation of the corresponding Gaussian
process. For example, the next result describes how the expected supremum of a multiplier
process is upper bounded in terms of the Gaussian mean-width ℓ∗ . Although it is formulated
in Rn , it holds in a far more general context (see [33]).
√

18

Proposition 4.3. Let q > 2 and let X be an isotropic, L-sub-Gaussian random vector in
Rn . There exists a constant c = c(q) such that the following holds. Let ξ ∈ Lq be a random
variable (not necessarily independent of X) and let (Xi , ξi )N
i=1 be independent copies of (X, ξ).
n
Then, for any T ⊂ R ,
N
1 X
E sup √
εi ξi hXi , ti ≤ cLkξkLq ℓ∗ (T ) ,
N i=1
t∈T

(4.4)

N
where (εi )N
i=1 are independent, symmetric signs that are independent of (Xi , ξi )i=1 .

Note that if ξ is heavy-tailed there is no hope of obtaining a high-probability version of
Proposition 4.3. In fact, if all one knows is that ξ belongs to Lq , one cannot hope that
N
1 X
sup √
ξi hXi , ti ≤ cLkξkLq ℓ∗ (T )
N i=1
t∈T

with a probability higher than 1 − c1 /N (q/2)−1 .
This exhibits, yet again, the weakness of Theorem 2.13, which is based on the “inprobability” parameter rM . Setting f ∗ (X) = hX, t∗ i and if ξ = f ∗ (X) − Y is heavy-tailed,
the oscillation is simply too big on an event with the required confidence (2.4), but the mean
oscillation is well behaved.
Applying Proposition 4.3, it is evident that
n
√ o
(4.5)
rE (κ) ≤ inf r : ℓ∗ (2T ∩ rB2n ) ≤ (κ/cL) N r
and

o
n
√
rM (κ, t) = inf r : kY − hX, ti kLq ℓ∗ (2T ∩ rB2n ) ≤ (κ/cL) N r 2 .

(4.6)

Thus, assuming that kY −hX, ti kLq ≤ LkY −hX, ti kL2 , as we do in Assumption 2.1, it follows
that
n
√ o
reM (κ, σ) ≤ inf r : ℓ∗ (2T ∩ rB2n ) ≤ (κ/cL2 σ) N r .
Definition 4.4. For constants c1 , c2 and σ, let
n
√ o
sM (c1 , σ) = inf r : ℓ∗ (2T ∩ rB2n ) ≤ (c1 /σ) N r ,

and

n
√ o
sQ (c2 ) = inf r : ℓ∗ (2T ∩ rB2n ) ≤ c2 N r .

Hence, for every t∗ ∈ T ,

max{λQ (c1 , c2 , t∗ ), λM (c1 /σ, c2 , t∗ ), rE (c1 , t∗ ), r M (c1 , t∗ )} ≤ max{sQ (c3 , σ), sM (c4 /σ)} ,
for constants c1 , c2 , c3 , c4 that depend only on q and L.
We obtain the following consequence of Theorem 2.10:

19

Theorem 4.5. Let X be an isotropic, L-sub-Gaussian random vector in Rn , and let T ⊂ Rn
be a convex, centrally-symmetric set. Let q > 2 and assume that kY − hX, ti kLq ≤ LkY −
hX, ti kL2 for every t ∈ T . Then, with probability at least 1−2 exp(−c1 N min{1, σ −2 s2M (c2 , σ)}),
the median-of-means tournament produces b
t such that

kb
t − t∗ kL2 ≤ c3 s∗ and E ( X, b
t − Y )2 |DN ≤ E(hX, t∗ i − Y )2 + (c4 s∗ )2 ,
where

s∗ = max{sM (c2 , σ), sQ (c5 )} ,

and the constants c1 , ..., c5 depend only on L and q.
Moreover, for any s ≥ s∗ ,


kb
t − t∗ kL2 ≤ c3 s and E ( X, b
t − Y )2 |DN ≤ E(hX, t∗ i − Y )2 + (c4 s)2 ,

with probability at least 1 − 2 exp(−c1 N min{1, σ −2 s2 }), exhibiting the optimal accuracyconfidence tradeoff.
Theorem 4.5 improves Theorem A from [24], where it was shown that ERM produces b
t
with the same accuracy and confidence as in the first part of Theorem 4.5, but only when
√
kY − hX, ti kLq ≤ L qkY − hX, ti kL2 for every q > 2 and every t ∈ T . In other words,
Theorem A from [24] is based on the assumption that each Y − hX, ti is an L-sub-Gaussian
random variable, and holds only for the accuracy level s∗ . In contrast, Theorem 4.5 shows
that the median-of-means tournament performs in an optimal way in heavy-tailed situations
that are totally out of reach for ERM and for the entire range s ≥ cs∗ .
Observe that the only range of accuracies in which Theorem 4.5 is (perhaps) suboptimal,
is when
λ∗ = max{λQ (κ1 , η1 ), λM (κ2 /σ, η2 )} ≤ s ≤ s∗
(4.7)
for well chosen values of κi , ηi , i = 1, 2; that is, for values that are larger than the known
lower estimate on the accuracy edge for such problems. As noted in [24], there are many
examples in which λ∗ and s∗ are equivalent (roughly speaking, this happens when Sudakov’s
inequality is sharp). In such cases the median-of-means tournament is optimal in the entire
range of accessible accuracies.
One important class of sets in which this equivalence is true is ρB1n = {t : ktk1 ≤ ρ} (see
[24] for the proof). In light of Theorem 4.5, the median-of-means tournament performs in an
optimal way in ρB1n . Moreover, it turns out that one may relax the sub-Gaussian assumption
on X and still obtain the optimal behaviour ρB1n , as we show next.

4.2

ρB1n – Sparse recovery sets

It is well understood that classical sparse recovery procedures, such as basis pursuit or LASSO
t, the minimizer in Rn of the
relay heavily on the geometry of B1n . Indeed, LASSO selects b
functional
N
1 X
(Yi − hXi , ti)2 + λktk1 .
t→
N
i=1

Being a penalized version of ERM, the analysis of LASSO is equivalent to the study of ERM
in the sets ρB1n for an arbitrary choice of ρ.
20

While we defer the question of a “LASSO-tournament” procedure to future work, it is
clear that the first step in that direction is to explore the median-of-means tournament in
ρB1n . Instead of the sub-Gaussian assumption used in Theorem 4.5, the assumption we use
follows the path of [25]:
Assumption 4.1. Let X be an isotropic random vector and κ ≥ 1. Assume that for every
√
t ∈ Rn and any 2 ≤ p ≤ κ log n, k hX, ti kLp ≤ L pk hX, ti kL2 .
Note that the coordinates of X need not be independent and X may be far from being
an L-sub-Gaussian random vector. Indeed, it is required that linear functionals h·, ti satisfy
a sub-Gaussian moment growth only up to the logarithm of the dimension, and it is possible
that some do not have any higher moment beyond p = κ log n.
P
It turns out (see [25]) that if X satisfies Assumption 4.1, then N −1/2 N
i=1 hXi , ·i ei , the
random matrix whose rows are independent copies of X, exhibits the best possible sparse
recovery features. For example, one requires N ∼ s log(en/s) random measurements hXi , ti
to recover any s-sparse vector t using basis pursuit, and a similar type of estimate holds
in the “noisy” setup for the LASSO. Moreover, one cannot relax the moment condition in
Assumption 4.1 and still get the same recovery properties.
Of course, since both basis pursuit and LASSO are variations of ERM, they suffer from
the same weaknesses as ERM. As such, when the given measurements are (hXi , ti)N
i=1 for a
heavy-tailed X, the confidence with which the recovery properties hold is suboptimal, and
very different from the confidence one has when X is the standard Gaussian vector in Rn .
We show that as far as regression in ρB1n goes, the median-of-means tournament yields the
optimal, “Gaussian” behaviour even when X only satisfies Assumption 4.1 and Y − ht∗ , Xi
is heavy-tailed. To this end, we need sharp bounds on the parameters that are used to define
r ∗ in Theorem 2.10.
As was noted earlier, λQ and λM depend only on the covariance structure endowed on Rn
by L2 (µ), and since X is isotropic, the L2 (µ) metric corresponds to the standard Euclidean
norm. Therefore, the difficulty lies in bounding rE and rM , and specifically, in extending
Proposition 4.3 beyond the L-sub-Gaussian case. While Theorem 4.3 is general and holds
for any subset of Rn , here it is needed for very specific sets, namely T = ρB1n ∩ rB2n . Such
indexing sets fall within the scope of Theorem 1.6 from [32].
Proposition 4.6. Let q > 2 and let X satisfy Assumption 4.1 for κ = c1 (q). Let ξ ∈ Lq be a
random variable (not necessarily independent of X) and let (Xi , ξi )N
i=1 be independent copies
of (X, ξ). Then
E

sup

t∈ρB1n ∩rB2n

N
1 X
√
εi ξi hXi , ti ≤ c2 (q)LkξkLq ℓ∗ (ρB1n ∩ rB2n ) .
N i=1

(4.8)

Thus, Assumption 4.1 suffices to ensure that rE and reM (κ, σ) may be controlled as if X
were L-sub-Gaussian. All that remains is to estimate
log M(ρB1n ∩ rB2n , ηrB2n ) and ℓ∗ (ρB1n ∩ rB2n )

which are well-understood quantities.
√
To put them in a more familiar form, set s = ρ/r and observe that
√
ℓ∗ (ρB1n ∩ rB2n ) = rℓ∗ ((ρ/r)B1n ∩ B2 ) = rℓ∗ ( sB1n ∩ B2n )
21

and

√
M(ρB1n ∩ rB2n , ηr) = M((ρ/r)B1n ∩ B2n , ηB2n ) = M( sB1n ∩ B2n , ηB2n ) .

Recall that if 1 ≤ s ≤ n and Vs is the set of s-sparse vectors in the Euclidean unit sphere (i.e.,
√
those with at most s nonzero components), then conv(Vs ) ⊂ sB1n ∩ B2n ⊂ C · conv(Vs ) for a
suitable absolute constant C. Using what are by now standard estimates (see, e.g., [24]),
p
√
√
ℓ∗ ( sB1n ∩ B2n ) ∼ s log(en/s), and log M( sB1n ∩ B2n , ηB2n ) ∼ s log(en/ηs) .

The estimates are simpler outside the range 1 ≤ s ≤ n: when ρ/r ≤ 1 then ρB1n ∩ rB2n = ρB1n
√
and when ρ/r ≥ n then ρB1n ∩ rB2n = rB2n . Again, the required estimates on M and ℓ∗ are
standard and may be found, for example, in [24].
Using these observations, and with the same (tedious) computation as in [24], one obtains
the following: let c1 and c2 be well-chosen absolute constants and set

r 


ρσ
2c

√
√1 nσ

log
if N ≤ c1 n2 σ 2 /ρ2
 N
Nρ
2
vM
=



 σ2 n
if N > c1 n2 σ 2 /ρ2 ,
N
and

2
vQ

Then

=

 ρ2

 N log



2c2 n
N

0



if N ≤ c2 n ,

if N > c2 n .

• λ∗ , the lower estimate on the accuracy edge, satisfies λ∗ ≥ c3 max{vQ , vM }; thus, there is no
learning procedure in ρB1n that can perform with a better accuracy than c3 max{vQ , vM }
with a higher confidence than 3/4;
• For any v ≥ c4 max{vQ , vM }, the median-of-means tournament achieves the accuracy v
with the optimal confidence 1−2 exp(−c5 N min{1, σ −2 v 2 }), thus exhibiting the optimal
accuracy/confidence tradeoff up to a level that is proportional to λ∗ .
Formally:
Corollary 4.7. Let q > 2 and assume that X satisfies Assumption 4.1 with a constant
κ = c(q). Assume further that for every t ∈ ρB1n , kY − hX, ti kLq ≤ LkY − hX, ti kL2 . Then
for every v ≥ c4 max{vQ , vM }, with probability at least 1 − 2 exp −c5 N min{1, σ −2 v 2 } , the
median-of-means tournament produces b
t ∈ ρB1n that satisfies

kb
t − t∗ kℓn2 ≤ c6 v and E ( X, b
t − Y )2 |DN ≤ E(hX, t∗ i − Y )2 + (c6 v)2 ,

for constants c4 , c5 , c6 that depend only on q and L.

The advantage of the median-of-means tournament over ERM is clear: it performs in ρB1n
with the optimal accuracy and confidence, starting a constant factor away from the level of
accuracy that can be attained only with constant confidence, and it does so under a heavytailed assumption both on X and on Y . In contrast, ERM (which was the “record holder”
prior to this work) achieves the optimal performance only in a purely sub-Gaussian setup and
does so only for one level of accuracy, of the order of max{vQ , vM }.
22

5

Proofs

Let us begin by considering the structure of the various indexing sets involved in the proofs,
paying particular attention to the way their structure affects the regularity of the parameters
we defined earlier.
For any class F and every h ∈ F, F − h ⊂ F − F, and in particular,
Fr,h = star(F − h, 0) ∩ rD ⊂ star(F − F, 0) ∩ rD.
Thus, for all the complexity parameters defined above, one may avoid the need to take the
supremum over all possible choices of centres by considering a slightly larger indexing set,
namely, star(F −F, 0)∩rD. Moreover, if F is convex, then F −F is both convex and centrally
symmetric, and if F happens to be convex and centrally symmetric then F − F = 2F and
star(F − F, 0) ∩ rD = 2F ∩ rD.
The fact that star(F −h, 0) is star-shaped around 0 leads to important regularity properties
of the parameters we use. Recall that S is the unit sphere in L2 (µ) and observe that if V is
star-shaped around 0 and v ∈ V ∩rS, then for every r ′ ≤ r, V contains a ‘scaled-down’
version
P
ε
v(X
of v, of norm r ′ : for α = r ′ /r < 1, αv ∈ V . Hence, if φ(r) = E supv∈V ∩rD N
i
i ) and
i=1
r ′ ≤ r, then φ(r ′ ) ≥ (r ′ /r)φ(r).
This argument shows that when r > rE (κ, h),
E sup
v∈Fh,r

N
√
1 X
√
εi v(Xi ) ≤ κ N r ,
N i=1

and when r < rE (κ, h), the reverse inequality holds. In a similar fashion, if r ≥ r M (κ, h),
then
N
√
1 X
E sup √
εi v(Xi )(h(Xi ) − Yi ) ≤ κ N r 2 ,
N i=1
v∈Fh,r

whereas if r < r M (κ, h), the reverse inequality holds.
Similar arguments apply for λQ and λM : if V is star-shaped around 0 and if {v1 , ..., vM }
is an ηr-separated subset of V ∩ rD and 0 < α < 1, then {αv1 , ..., αvM } is an η(αr)-separated
subset of V ∩ (αr)D. Therefore,
log M(V ∩ αrD, ηαrD) ≥ log M(V ∩ rD, ηrD) ,

(5.1)

implying that the function r → log M(V ∩ rD, ηrD) is monotone decreasing. Moreover, if
log M(V ∩ r ′ D, ηr ′ D) ≤ κ2 N , or if log M(V ∩ r ′ D, ηr ′ D) ≤ κ2 N (r ′ )2 , the same is true for
every r ≥ r ′ . Therefore, if r > λQ (κ, η, h) then
log M(Fh,r , ηrD) ≤ κ2 N ,
and if r < λQ (κ, η, h), the reverse inequality holds. In a similar fashion, if r > λM (κ, η, h)
then
log M(Fh,r , ηrD) ≤ κ2 N r 2 ,
while if r < λQ (κ, η, h), the reverse inequality holds.
These observations allow one to choose a level of accuracy such as r ∗ by “intersecting” multiple conditions like the ones appearing in the definitions of λQ , λM , rE and r M , simply because
23

each one of the required inequalities holds for any level larger than λQ , λM , rE and r M , respectively. An additional feature is that one may “combine” conditions by decreasing the constants
involved in the definitions. For example, max{rE (κ1 , h), rE (κ2 , h)} = rE (min{κ1 , κ2 }, h) and
similar observations hold for λQ , λM and r M .
For the sake of transparency, we do not specify all the constants involved in the definitions
of the fixed points right from the start. Instead, we collect conditions on these constants and
use the fact that one may “combine” and “intersect” them. It turns out that all the constants
depend on only two parameters: q > 2, for which the Lq norm is equivalent to the L2 norm,
and the constant L. In what follows, we denote by c(q, L) a constant that depends only on
q and L, for the values of q and L in Theorem 2.10 (where only q = 4 is considered) or in
Theorem 2.11, when q can be arbitrarily close to 2–at the price of worse constants, of course.
With this in mind, let κ1 , κ2 , κ3 and η be constants that will be specified later and that
depend only on q and L. Fix f ∗ ∈ F and consider r ∗ for which, for every r > r ∗ ,
N
√
1 X
√
εi (f − f ∗ )(Xi ) ≤ κ1 N r ,
N i=1

(5.2)

N
√
1 X
√
εi (f ∗ (Xi ) − Yi )(f − f ∗ )(Xi ) ≤ κ2 N r 2
N i=1

(5.3)

E sup
f ∈Ff ∗ ,r

E sup
f ∈Ff ∗ ,r

and

log M(Ff ∗ ,r , ηrD) ≤ κ23 N min{1, r 2 /σ 2 } .

(5.4)

The value of r ∗ from (2.7) will be given by selecting right constants κ1 , κ2 , κ3 and η. We
consider an accuracy r ≥ 2r ∗ , and for the rest of this section we fix its value.
Let us introduce the main parameter n used in the tournament, that is, the number of
blocks into which the second part of the sample (Xi , Yi )2N
i=N +1 , and the third part of the
sample (Xi , Yi )3N
are
partitioned.
To
this
end,
let
0
< τ < 1/4, set 0 < θ ≤ τ , to be
i=2N +1
∗
specified later, and put λM = λM (κ3 /σ, η, f ). Set
   
r 2
n = θN min 1,
.
(5.5)
σ
Hence, n depends on the wanted accuracy r. Also, n ≤ τ N and without loss of generality
we may assume that both n and m = N/n are integers. Also, note that m ≥ 1/τ .

5.1

The preliminary round–proof

In this section we prove Proposition 3.5.
Recall that by Proposition 3.2 and the resulting condition on r, one has that, with prob∗
ability at least 1 − 2 exp(−c0 N ) with respect to (Xi )N
i=1 , if a match involving f is allowed to
take place (i.e., if DO(f ∗ , f ) = 1), then kf ∗ − f kL2 ≥ r; and if the match is abandoned (i.e.,
DO(f ∗ , h) = 0), then kf ∗ − f kL2 ≤ (β/α)r. The constants α < 1 < β and c0 depend only on
L and q.
Therefore, to establish Proposition 3.5 it is enough to show that with probability 1 −
2 exp(−cn), if kf − f ∗ kL2 ≥ r, then f ∗ wins its match against f . In other words, that
Bf,f ∗ (j) > 0 for the majority of the blocks in any such match.
Let us begin by exploring the situation in a match between f ∗ and f , knowing that
∗
kf − f kL2 ≥ r ≥ 2r ∗ , as above.
24

Clearly, for every f, h ∈ F,
(f (X) − Y )2 − (h(X) − Y )2 = (f (X) − h(X))2 + 2(f (X) − h(X)) · (h(X) − Y ) .
Set
m

Qf,h =

2 X
1 X
(f (Xi ) − h(Xi ))2 and Mf,h =
(f (Xi ) − h(Xi )) · (h(Xi ) − Yi ) .
m
m
i=1

i=1

We introduce the notation ξ = f ∗ (X) − Y and ξi = f ∗ (Xi ) − Yi . Partitioning the sample
(Xi , Yi )2N
the n blocks (Ij )nj=1 , each one of cardinality m, one has that for 1 ≤ j ≤ n,
i=N +1 into
P
m
2
∗
Mh,f ∗ (j) = m
i∈Ij ξi (f (Xi ) − f (Xi )) and
Bf,f ∗ (j) =

1 X
2 X
(f (Xi ) − f ∗ (Xi ))2 +
ξi (f (Xi ) − f ∗ (Xi )) = Qf,f ∗ (j) + Mf,f ∗ (j) .
m
m
i∈Ij

i∈Ij

It follows that f ∗ defeats f in the j-th block if Qf,f ∗ (j) + Mf,f ∗ (j) > 0, and, because
τ < 1/4, f ∗ wins the match if Qf,f ∗ (j) ≥ Ckf − f ∗ k2L2 on more than (1 − τ )n of the blocks,
while Mf,f ∗ (j) ≤ −Ckf − f ∗ k2L2 on at most τ n of the blocks, .
This is summarized in the following lemma, established in the next two sections, and for
the right choice of the constants κ1 , κ2 , κ3 , η, τ , and θ that depend only on L and q.
Lemma 5.1. There exists an absolute constant c and a constant C1 = C1 (L, q) for which the
following holds. With probability at least 1 − 2 exp(−cτ 2 n), for every f ∈ F with kf − f ∗ kL2 ≥
r,

j : Qf,f ∗ (j) ≥ C1 kf − f ∗ k2L2 ≥ (1 − τ ) n

and



j : Mf,f ∗ (j) ≤ −

3C1
kf − f ∗ k2L2
4



≤ τn .

The analysis takes place in the set
F1 = star(F, f ∗ ) ∩ (f ∗ + rS) ,
consisting of all the functions in the star-shaped hull of F and f ∗ whose distance to f ∗ is
precisely r. Once the estimates in Lemma 5.1 are verified for functions in F1 , extending them
to the set {f ∈ star(F, f ∗ ) : kf − f ∗ kL2 ≥ r}, is straightforward, by invoking homogeneity
properties of Qf,f ∗ and Mf,f ∗ in f − f ∗ , and because star(F, f ∗ ) is star-shaped around f ∗ .
The quadratic component
Here we establish the first part of Lemma 5.1, that states that, on an event of high probability,
whenever kf − f ∗ kL2 is sufficiently large, a significant majority of the (Qf,f ∗ (j))nj=1 are at
least a large fixed proportion of kf − f ∗ k2L2 . The size of the fixed proportion depends only on
the small-ball property satisfied by the class F, which, in turn, follows from the Lq -L2 norm
equivalence in span(F ). Indeed, if kf − f ∗ kLq ≤ Lkf − f ∗ kL2 , then by the Paley-Zygmund
inequality (see, e.g., [12]),
P(|f − f ∗ |(X) ≥ κ0 kf − f ∗ kL2 ) ≥ ρ0
25

(5.6)

for constants κ0 and ρ0 that depend only on L and q.
Recall that (Ij )nj=1 are the n blocks, each one of cardinality m = N/n, that F1 = {f ∈
star(F, f ∗ ) : kf − f ∗ kL2 = r}, and that m ≥ 1/τ . For t > 0 and a function u, set
X
1{|u(Xi )|≥t} .
Rj (u, t) = |{i ∈ Ij : |u(Xi )| ≥ t}| =
i∈Ij

Thanks to (5.6), it is evident that if f ∈ F1 and 1 ≤ j ≤ n then, with probability at least
1 − 2 exp(−c0 ρ0 m),
mρ0
Rj (f − f ∗ , κ0 r) ≥
.
2
Recalling that m ≥ 1/τ , if τ ≤ c1 (ρ0 ) then
1 − 2 exp(−c0 ρ0 m) ≥ 1 − 2 exp(−c0 ρ0 /τ ) ≥ 1 − τ /12 ,
and (1{Rj (f −f ∗ ,κ0 r)≥mρ0 /2} )nj=1 are i.i.d. Bernoulli random variables with mean at least 1 −
τ /12. By standard concentration properties of Binomial distributions, with probability at
least 1 − 2 exp(−c2 τ 2 n),
n

1X
1{Rj (f −f ∗ ,κ0r)≥mρ0 /2} ≥ 1 − τ /6 .
n

(5.7)

j=1

In other words, at least (1 − τ /6)n of the blocks Ij have at least mρ0 /2 coordinates of size at
least κ0 r. Moreover, in light of the high probability estimate with which (5.7) holds, by the
union bound, the same property is satisfied uniformly by any subset of F1 of cardinality at
most exp(c2 τ 2 n/2). The set we consider is a maximal ηr-separated subset of F1 with respect
to the L2 (µ) norm and for a well-chosen η specified later.
Let H1 be such a maximal separated set. Since
F1 ⊂ f ∗ + (star(F − f ∗ , 0) ∩ rD) = f ∗ + Ff ∗ ,r ,
it follows from the translation invariance of packing numbers that
|H1 | ≤ M(Ff ∗ ,r , ηr) .
Thus, to obtain a uniform control over points in H1 , it suffices to show that
log M(Ff ∗ ,r , ηr) ≤ (c2 /2)τ 2 n .
Recalling (5.4) and the choice of n, it suffices to verify that
κ23 N min{1, σ −2 r 2 } = κ23 n/θ ≤ (c2 /2)τ 2 n ,
which is the case as long as
κ23 ≤ (c2 /2)θτ 2 .
Observe that since H1 is maximal, it is also an ηr-net in F1 , that is, every f ∈ F1 has some
πf ∈ H1 for which kf − πf kL2 ≤ ηr. Consider the following event:
(A) (5.7) holds for every f ∈ H1 , and
26

(B) supf ∈F1 (1/n)

Pn

i=1

1{Rj (f −πf,κ0 r/2)≥mρ0 /4} ≤

τ
12 .

On this event, for every f ∈ F1 there are at least (1 − τ /4)n blocks Ij with the following
properties:
• |πf (Xi ) − f ∗ (Xi )| ≥ κ0 r on at least mρ0 /2 coordinates in Ij , and
• |f (Xi ) − πf (Xi )| ≥ κ0 r/2 on at most mρ0 /4 coordinates in Ij .
Hence, in each one of the (1 − τ /4)n well-behaved blocks there are at least mρ0 /4 coordinates
Xi that satisfy
|f (Xi ) − f ∗ (Xi )| ≥ |πf (Xi ) − f ∗ (Xi )| − |f (Xi ) − πf (Xi )| ≥ κ0 r/2 .
In particular, since kf − f ∗ kL2 = r, one has
Qf,f ∗ (j) ≥ (ρ0 κ20 /16)kf − f ∗ k2L2 .

(5.8)

Moreover, (5.8) is positive homogeneous in f − f ∗ and F1 is star-shaped around f ∗ , implying
that (5.8) holds for every f ∈ F1 as long as kf − f ∗ kL2 ≥ r.
All that remains is to establish that (B) holds with a sufficiently high probability. To that
end, let
n
1X
1{Rj (f −πf,κ0 r/2)≥mρ0 /4} .
Ψ(X1 , ..., XN ) = sup
f ∈F1 n
i=1

First note that, by the bounded differences inequality (see, e.g., [7]), with probability at least
1 − exp(−c3 u2 ),
u
Ψ(X1 , ..., XN ) ≤ EΨ + √ .
n
√
Therefore, if EΨ ≤ τ /24 and u ≤ nτ /24, then with probability at least 1 − exp(−c4 τ 2 n),
Ψ(X1 , ..., XN ) ≤ τ /12 as required.
Thus, the final step in the proof is to show that
n

(∗) = E sup
f ∈F1

Using that, for α > 0,

1X
τ
.
1{Rj (f −πf,κ0 r/2)≥mρ0 /4} ≤
n
24
i=1

1{|x|≥α} ≤ α−1 |x|,

1{Rj (f −πf,κ0 r/2)≥mρ0 /4} ≤

4 X
4
Rj (f − πf, κ0 r/2) =
1{|f (Xi )−πf (Xi )|≥κ0 r/2} .
ρ0 m
ρ0 m
i∈Ij

27

Thus, recalling that nm = N ,
(∗) ≤
≤

N
4
1 X
1{|f −πf |(Xi )≥κ0 r/2}
· E sup
ρ0
f ∈F1 N
i=1
N
X

1
8
E sup
ρ0 κ0 r f ∈F1 N

8
≤
ρ0 κ0 r
≤

i=1
N
X

1
E sup
f ∈F1 N

16
1
E sup
ρ0 κ0 r f ∈F1 N
(where

|f (Xi ) − πf (Xi )| (using

(εi )N
i=1

i=1
N
X
i=1

1{|x|≥α} ≤ α−1 |x| again)
!

(|f (Xi ) − πf (Xi )| − E|f (X) − πf (X)|) + sup E|f (X) − πf (X)|
f ∈F1

εi (f (Xi ) − πf (Xi )) +

8
· ηr
ρ0 κ0 r

are independent symmetric random signs) .

In the last step we used a standard symmetrization argument, see, for example, [12]. To
conclude the proof, observe that (8/ρ0 κ0 r) · ηr ≤ τ /48 when
η ≤ c5 ρ0 κ0 τ

(5.9)

and for a suitable absolute constant c5 . The fact that
N
τ
16
1 X
εi (f − f ∗ )(Xi ) ≤
E sup
ρ0 κ0 r f ∈F1 N
48

(5.10)

i=1

follows because r ≥ 2r ∗ and invoking (5.2), as long as
κ1 ≤ c6 ρ0 κ0 τ
for an absolute constant c6 .
The multiplier component
Next we complete the proof of Lemma 5.1 by showing that, with high probability, if kf −
f ∗ kL2 ≥ r, then
Mf,f ∗ (j) ≤ −(3C1 /4)kf − f ∗ k2L2
on at most τ n blocks. In the first step towards this goal, we consider a single function:
Lemma 5.2. There exists an absolute constant C2 for which the following holds. Assume
that for every f ∈ F, E(f ∗ (X) − Y )(f (X) − f ∗ (X)) ≥ 0. If f ∈ F1 , then with probability at
least 1 − 2 exp(−C2 τ 2 n),


C1 r 2
≥ (1 − τ /8)n .
j : Mf,f ∗ (j) ≥ −
2
In particular, the same assertion holds uniformly for any fixed subset H2 ⊂ F1 of cardinality
at most exp(C2 τ 2 n/2).

28

Before proving Lemma 5.2, consider the assumption that
E(f ∗ (X) − Y )(f (X) − f ∗ (X)) ≥ 0 for every

f ∈F .

(5.11)

It is straightforward to verify that (5.11) is satisfied under the assumptions of Theorems 2.10
and 2.11. Indeed, if F is closed and convex then (5.11) is just the characterization of f ∗ as
the nearest point to Y in F in the L2 sense. On the other hand, if Y = f0 (X) + W for
f0 ∈ F and W that is mean-zero and independent of X, then E(f ∗ (X) − Y )(f (X) − f ∗ (X)) =
−EW (f (X) − f0 (X)) = 0 for every f ∈ F. In fact, (5.11) is the only structural assumption
on the ‘location’ of Y relative to F that is required for our analysis.
Another observation is that (5.11) passes to star(F, f ∗ ), simply because any function in
that set is of the form h = λf + (1 − λ)f ∗ for some f ∈ F and 0 ≤ λ ≤ 1 and therefore,
(f ∗ (X) − Y )(h(X) − f ∗ (X)) = λ(f ∗ (X) − Y )(f (X) − f ∗ (X)).

Proof of Lemma 5.2. Set ξ = f ∗ (X) − Y , put U = ξ(f (X) − f ∗ (X)) and observe that by
(5.11), EU ≥ 0. Also note that for every j,
1 X
1 X
ξi (f (Xi ) − f ∗ (Xi )) =
Ui ,
Mf,f ∗ (j) =
m
m
i∈Ij

i∈Ij

N
for (Ui )M
i=1 that are independent copies U . It is straightforward to verify that, with (εi )i=1
defined as independent symmetric random signs,
!
P
P
m
E| m
E| m
1 X
i=1 (Ui − EU )|
i=1 εi Ui |
Ui − EU ≥ t ≤
≤2
P
m
mt
mt
i=1

√ kU kL
kU kL
≤2 √ 2 = 2 n √ 2 = (∗) .
mt
Nt

By the norm equivalence assumption of Theorem 2.10,
kU kL2 ≤ kξkL4 kf − f ∗ kL4 ≤ L2 σr ,
and by the independence assumption of Theorem 2.11,
kU kL2 = kξkL2 kf − f ∗ kL2 = σr .

Hence, setting t = (C1 /2)r 2 and noting that
r
√ r
n
≤ θ ,
N
σ
it follows that
√
√
4L2 nσ
τ
2 rσ n
√
≤
(∗) ≤ 2L √ =
C1 N r
16
t N
whenever
θ ≤ (C1 τ /64L2 )2 .
Therefore, with probability at least 1 − τ /16,
m

1 X
Ui ≥ EU − C1 r 2 /2 ≥ −C1 r 2 /2 .
m
i=1

Finally, consider the independent Bernoulli random variables (1{Mf,f ∗ (j)≤−C1 r2 /2} )nj=1 that
have mean at most τ /16. By concentration of Binomial random variables, there is an absolute
constant C2 such that, with probability at least 1−2 exp(−C2 τ 2 n), there are at least (1−τ /8)
blocks that satisfy Mf,f ∗ (j) ≥ −C1 r 2 /2, as claimed.
29

Just as before, one may select any fixed subset H2 ⊂ F1 of cardinality exp(C2 τ 2 n/2), and
the assertion of Lemma 5.2 holds with high probability and uniformly for every h ∈ H2 . The
choice of H2 requires some care. It cannot be just an arbitrary maximal separated set.
Lemma 5.3. There exists a subset H2 ⊂ F1 of cardinality at most exp(C2 nτ 2 /2) such that
for every f ∈ F1 there is some h ∈ H2 that satisfies
kf − hkL2 ≤ 2ηr, and Eξ(f (X) − h(X)) ≥ 0 .
Proof. Let H ′ be an maximal ηr-separated subset of F1 . Recall that by the choice of r and
(5.4), log |H ′ | ≤ κ23 N min{1, σ −2 r 2 }, which is smaller than (C2 /2)τ 2 n when
κ23 ≤ (C2 /2)θτ 2 .
The class F is a locally compact subset of L2 (µ) and therefore, so is F1 . Thus, for every
h′ ∈ H ′ , the intersections of F1 with the L2 balls B(h′ , ηr) are compact and the continuous
linear functional on L2
f → Eξf (X)

attains its minimum in each one of the sets F1 ∩ B(h′ , ηr). Let h be such a minimizer and set
H2 to be the collection of these minimizers. Hence, for every f ∈ F1 there is some h ∈ H2 for
which kf − hkL2 ≤ 2ηr and Ef (X)ξ ≥ Eh(X)ξ, as claimed.

With Lemma 5.3 at our disposal, for every f ∈ F1 define πf ∈ H2 for which Eξ(f (X) −
πf (X)) ≥ 0 and kf − πf kL2 ≤ 2ηr, as above. By Lemma 5.2, with probability at least
1 − 2 exp(−C2 τ 2 n/2), for every h ∈ H2 there are at least (1 − τ /8)n blocks Ij with
Mh,f ∗ (j) =

2 X
ξi (h(Xi ) − f ∗ (Xi )) ≥ −C1 r 2 /2 .
m
i∈Ij

Hence, to complete the proof it suffices to show that for every f ∈ F1 , there are at most
(7/8)nτ blocks Ij with
Mf,f ∗ (j) ≤ Mπf,f ∗ (j) − C1 r 2 /4 .
Indeed, on that event, for every f ∈ F1 there are at most nτ blocks Ij that satisfy Mf,f ∗ (j) ≤
−(3/4)C1 r 2 , as required.
Again, establishing this estimate for F1 yields that on the same event, if kf − f ∗ k2L2 ≥ r 2 ,
then Mf,f ∗ (j) ≤ −(3/4)C1 kf −f ∗ k2L2 on at most nτ coordinate blocks, since M is homogeneous
in f − f ∗ and F1 is star-shaped around f ∗ .
Lemma 5.4. There exists an absolute constant c for which, with probability at least 1 −
2 exp(−cτ 2 n),
n
1X
7τ
sup
1{Mf,f ∗ (j)−Mπf,f ∗ (j)≤−C1 r2 /4} ≤
.
8
f ∈F1 n
j=1

Proof. Recall that by the definition of πf , Eξf (X) ≥ Eξπf (X). Therefore,
E(Mf,f ∗ − Mπf,f ∗ ) = 2Eξ(f (X) − πf (X)) ≥ 0 .
To simplify notation, set
Wf,πf (j) = Mf,f ∗ (j) − Mπf,f ∗ (j) =
30

1 X
ξi (f (Xi ) − πf (Xi )) ,
m
i∈Ij

and note that EWf,πf (j) ≥ 0.
Consider the supremum of Binomial random variables
n

1X
Ψ = sup
1{Wf,πf (j)≤−C1 r2 /4} .
f ∈F1 n
j=1

By the bounded differences inequality, with probability at least 1 − 2 exp(−cu2 ), Ψ ≤ EΨ +
√
√
u/ n. Setting u = (6/8) nτ , all that remains is to show that
n

1X
τ
EΨ = E sup
1{Wf,πf (j)≤−C1 r2 /4} ≤ .
8
f ∈F1 n
j=1

Since EWf,πf ≥ 0, using

1{|x|≥α} ≤ α−1 |x|,

n

E sup
f ∈F1

n

1X
1X
1{Wf,πf (j)≤−C1 r2 /4} ≤ E sup
1{Wf,πf (j)−EWf,πf (j)≤−C1 r2 /4}
n
f ∈F1 n
j=1

j=1

n
1X
≤ E sup
1{|Wf,πf (j)−EWf,πf (j)|≥C1 r2 /4}
f ∈F1 n
j=1

n

≤

1X
4
|Wf,πf (j) − EWf,πf (j)| .
E sup
2
C1 r f ∈F1 n
j=1

The next step is to centre the process. We show that for every f ∈ F1 , the centring term
satisfies
τ
4
E|Wf,πf (j) − EWf,πf (j)| ≤
.
C1 r 2
16
Indeed, symmetrizing, applying either the assumption of norm equivalence of Theorem 2.10
or the independence assumption of Theorem 2.11, and recalling that kf − πf kL2 ≤ 2ηr, it is
evident that
m

4
8
1 X
E|W
−
EW
|
≤
E
εi ξi (f (Xi ) − πf (Xi ))
f,πf
f,πf
C1 r 2
C1 r 2 m
i=1

16L2

σηr
√
C1
m
√
16L2 ησ n
16L2 √
√ ≤
η θ,
=
C1 r N
C1
≤

again using the fact that

p

n/N ≤

√

r2

θ(r/σ). Clearly,
τ
16L2 √
η θ≤
C1
16

when
θ ≤ (C3 τ /L2 η)2
for a suitable absolute constant C3 .

31

Finally, we need to bound the centred empirical process. This is done by standard techniques of symmetrization, the contraction theorem for Bernoulli processes (for the Lipschitz
function φ(t) = |t|) and then de-symmetrization (see, e.g., [26]):
n

1X
E sup
|Wf,πf (j) − EWf,πf | − E |Wf,πf (j) − EWf,πf |
f ∈F1 n
j=1

n

1X
≤ 2E sup
εj |Wf,πf (j) − EWf,πf |
f ∈F1 n
j=1
n

≤ 2E sup

1X
εj (Wf,πf (j) − EWf,πf )
n

≤ 4E sup

1X
(Wf,πf (j) − EWf,πf ) .
n

f ∈F1

j=1
n

f ∈F1

Since
Wf,πf (j) =

j=1

1 X
ξi (f (Xi ) − πf (Xi ))
m
i∈Ij

one has that
N
1 X
16
ξi (f (Xi ) − πf (Xi )) − Eξ(f (X) − πf (X))
E
sup
C1 r 2 f ∈F1 N
i=1

≤

N
X
τ
32
εi ξi (f (Xi ) − f ∗ (Xi )) ≤
E
sup
2
C1 r f ∈F1
16
i=1

provided that

that is, when

N
√
1 X
√
E sup
εi ξi (f (Xi ) − f ∗ (Xi )) ≤ C4 τ N r 2 ,
N i=1
f ∈F1

(5.12)

κ2 ≤ C4 τ ,
concluding the proof.

5.2

Champions league–proof

Finally, it remains to prove
probability at least 1 −
 Proposition 3.8. Recall that, with
−2
2
2N
2 exp −c0 N min{1, σ r } with respect to the sample (Xi , Yi )i=1 , we have been able to identify a set of “qualifiers” that have not lost a single match in the preliminary round subset; that
is, H ⊂ F, consisting of f ∗ and possibly other functions that satisfy kf − f ∗ kL2 ≤ (β/α)r. In
the rest of this section we work conditionally on this “good” event.
While producing a function that is close to f ∗ solves the estimation problem, the question
of prediction requires an additional step: we would like to choose one of the qualifiers that
has an almost optimal statistical performance: a function fb that satisfies

∗
2
2
E (fb(X) − Y )2 |(Xi , Yi )3N
(5.13)
i=2N +1 ≤ E(f (X) − Y ) + Cr
32

for an appropriate C. We show that this is possible with the required high probability for
C = 16(β/α)2 . To this end, set r1 = (β/α)r.
Recall that for f, h ∈ star(F, f ∗ ), Ψh,f = (h(X) − f (X))(f (X) − Y ) and note that
m

M

f,f ∗

2 X
=
Ψf,f ∗ (Xi , Yi ) .
m
i=1

Also, as noted previously, since EΨf,f ∗ ≥ 0 for every f ∈ F, the same holds for any f ∈
star(F, f ∗ ).
As was stated in Section 3.3, the sub-sample (Xi , Yi )3N
i=2N +1 is used to identify a function
2
b
f ∈ F for which EΨf ∗ ,fb ≥ −2r1 . By Lemma 3.6, this indeed suffices to establish (5.13) for
C = 16(β/α)2 .
The “champions league” round is designed to have “home-and-away” legs. For the partition (Ij )nj=1 of (Xi , Yi )3N
i=2N +1 , f wins its home match against h if
2 X
Ψh,f (Xi , Yi ) ≥ −r12 /10
m
i∈Ij

for more than half of the blocks Ij . We show that f ∗ wins all of its home matches, implying
that the set of possible choices of fb is nonempty, and that if EΨf ∗ ,f ≤ −2r12 , then f loses its
home match against f ∗ . On that event, a function that wins all of its home matches must
satisfy that EΨf ∗ ,fb ≥ −2r12 , and this observation concludes the proof of Theorem 2.10.
The main ingredient in the proof is the following lemma.
Lemma 5.5. Let F2 = star(F, f ∗ ) ∩ (f ∗ + r1 D). Under the conditions of Theorem 2.10, there
is an absolute constant c, such that, with probability at least 1 − 2 exp(−cn),
n

sup
f ∈F2

1X
1
1{|Mf,f ∗ (j)−EMf,f ∗ |≥r12 /10} < .
n
2
j=1

Proof. Using the assumption of norm equivalence of Theorem 2.10, one may verify that
kΨf,f ∗ kL2 ≤ L2 r1 σ. Therefore,
2
2
E |Mf,f ∗ − EMf,f ∗ | ≤ √ kΨf,f ∗ kL2 ≤ √ · L2 r1 σ .
m
m
Setting

n

1X
1{|Mf,f ∗ (j)−EMf,f ∗ |≥r12 /10} ,
Z = sup
f ∈F2 n
j=1

it follows that EZ is at most
E sup
f ∈F2

n
10 X
(|Mf,f ∗ (j) − EMf,f ∗ | − E|Mf,f ∗ (j) − EMf,f ∗ |)
nr12 j=1

+

10
· sup E|Mf,f ∗ (j) − EMf,f ∗ | = (I) + (II) .
nr12 f ∈F2

33

(5.14)

Applying the same argument used in the previous section–namely, symmetrization, followed
by contraction for a Bernoulli process and the Lipschitz function φ(t) = |t| and de-symmetrization–
one has that for absolute constants c1 , c2 , and c3 ,
(I) ≤

n
N
1X
c1
1 X
1
c2
∗
∗
·
E
sup
·
E
sup
(j)
(j)
−
EM
M
εi ξi (f − f ∗ )(Xi ) ≤
≤
f,f
f,f
2
2
8
r1
r1
f ∈F2 n j=1
f ∈F2 N i=1

when
κ2 ≤ c3 .
Also, by (5.14),
10L2 σ
·
(II) ≤
r1

r

1
n
≤ ,
N
8

provided that n ≤ c4 L4 · (r12 /σ 2 )N for an absolute constant c4 . Since r1 = 2(β/α)r, it suffices
that
θ ≤ c4 L4 .
Thus, EZ ≤ 1/4, and by the bounded differences inequality applied to Z, one has that
√
with probability at least 1 − 2 exp(−cu2 ), Z ≤ EZ + u/ n. The claim follows by selecting
√
u = n/8.
Recall that for every f ∈ H, kf − f ∗ kL2 ≤ (β/α)r and consider the “good” event from
Lemma 5.5. For any f ∈ F2 , and, in particular, for any qualifier f ∈ H,
EMf,f ∗ − r12 /10 ≤ Mf,f ∗ (j) ≤ EMf,f ∗ + r12 /10

(5.15)

on more than n/2 blocks. Moreover, if kf −f ∗ kL2 ≤ r1 and EΨf ∗ ,f ≤ −2r12 , then EΨf,f ∗ ≥ r12 .
Indeed,
−2r12 ≥E(f ∗ (X) − f (X)) · (f (X) − Y )

= − kf − f ∗ k2L2 + E(f ∗ (X) − f (X)) · (f ∗ (X) − Y )

≥ − r 2 + E(f ∗ (X) − f (X)) · (f ∗ (X) − Y ) = −r12 − EΨf,f ∗ .
Therefore, EMf,f ∗ ≥ 2r12 , and on the event (5.15),
Mf,f ∗ (j) ≥ EMf,f ∗ − r12 /10 ≥ r12 .
Finally, since Ψf ∗ ,f = −(f ∗ (X) − f (X))2 − Ψf,f ∗ , on that event and the same coordinate
blocks,
m
1 X
2 X ∗
∗
Ψf ,f (j) = −
(f (Xi ) − f (Xi ))2 − Mf,f ∗ ≤ −r12 .
m
m
i=1

i∈Ij

f∗

Thus, f is defeated by
in the majority of the blocks, and in particular, loses its home
∗
match against f . It follows that, with probability at least 1 − 2 exp(−cn), any function fb
selected in the champions league round must satisfy that Ψf ∗ ,fb ≥ −2r12 , and by Lemma 3.6,

∗
2
E (fb(X) − Y )2 |(Xi , Yi )3N
2N +1 ≤ E(f (X) − Y ) + 4r1 .
34

Additional remarks
It should be noted that the difference between r ∗ (f ∗ ) and r ∗ is not a major issue in most
interesting cases. λQ (κ, η, h), λM (κ, η, h), and rE (κ, h) typically do not depend heavily on h
and little is lost by taking the supremum over h ∈ F. reM (c1 , σ) becomes a better estimate of
r M (c1 , f ∗ ) as σ gets closer to kf ∗ − Y kL2 . Even if this value is not known in advance, it is
easy to design a two-stage procedure that constructs a data-dependent estimate of kf ∗ −Y kL2
and then uses the procedure of Theorem 2.10 with a tight upper bound for the value of σ
obtained from the first stage. In particular, it is easy to find a value of σ that is within a
constant factor of the optimum. This is an issue of secondary importance and we omit the
straightforward details.
The major problem that remains open is the identity of the accuracy edge. To date, there
is a single generic example in which one may attain an accuracy smaller than Cr ∗ and in
that case the accuracy attained is proportional to λ∗ and
 with the optimal confidence at that
level, namely, 1 − 2 exp −cN min{1, σ −2 λ2M (κ2 /σ, η2 )} .
This fact has recently been established in [30] in a very special situation: when F is a
convex, L-sub-Gaussian class of functions; all the admissible targets are of the form Y =
f0 (X) + W for f0 ∈ F and W that is sub-Gaussian, zero-mean, independent of X. The
procedure used is a modification of ERM: one replaces F with an appropriate net, thus
‘erasing’ all the fine structure of F at the right level, and then runs ERM on the net. The idea
behind this procedure is straightforward: if one is interested in accuracy r, one is insensitive
to perturbations of that order. From that perspective, a net with a mesh that is proportional
to r is just as good as the entire class. It turns out that r ∗ of the net is proportional to λ∗
the original class F. Unfortunately, all the highly restrictive assumptions are essential to the
proof and cannot be relaxed at all.
It should be noted that the median-of-means tournament may be modified in exactly the
same way as ERM is modified in [30], leading to an accuracy that is proportional to λ∗ when
F is a convex, L-sub-Gaussian class and for an independent noise W that may be heavytailed. We decided not pursue this point further because it is a very special case, and shifts
the emphasis of the article from the question of the optimal accuracy/confidence tradeoff to
the nature of the accuracy edge, a problem of a different nature.
As far as the latter is concerned, it is not clear whether the gap between λ∗ and r ∗ can be
closed in other cases. It is possible that both independent noise and a sub-Gaussian class are
essential in attaining an accuracy proportional to λ∗ , and under weaker assumptions, the true
accuracy edge lies somewhere between λ∗ and r ∗ . We leave that question for future study.
Finally, it should be noted that in this work we completely ignore the algorithmic aspects
of the new procedure. While computing the empirical risk minimizer often leads to thoroughly
studied and well understood convex optimization problems, finding the winner of the medianof-means tournament in a computationally efficient manner is a highly nontrivial–and perhaps
not hopeless–problem that goes beyong the scope of this paper. Techniques of “derivative-free
optimization” with “function comparison oracle” may be useful, see, for example, [20].

References
[1] N. Alon, Y. Matias, and M. Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58:137–147, 2002.
35

[2] M. Anthony and P. L. Bartlett. Neural network learning: theoretical foundations. Cambridge University Press, Cambridge, 1999.
[3] J.-Y. Audibert and O. Catoni. Robust linear least squares regression. The Annals of
Statistics, 39:2766–2794, 2011.
[4] F. Barthe, O. Guédon, S. Mendelson, and A. Naor. A probabilistic approach to the
geometry of the lpn -ball. Ann. Probab., 33(2):480–513, 2005.
[5] F. Barthe and A. Koldobsky. Extremal slabs in the cube and the Laplace transform.
Adv. Math., 174(1):89–114, 2003.
[6] P.L. Bartlett, O. Bousquet, and S. Mendelson. Localized Rademacher complexities.
Annals of Statistics, 33:1497–1537, 2005.
[7] S. Boucheron, G. Lugosi, and P. Massart. Concentration inequalities: A Nonasymptotic
Theory of Independence. Oxford University Press, 2013.
[8] C. Brownlees, E. Joly, and G. Lugosi. Empirical risk minimization for heavy-tailed losses.
Annals of Statistics, 43:2507–2536, 2015.
[9] S. Bubeck, N. Cesa-Bianchi, and G. Lugosi. Badits with heavy tail. IEEE Transactions
on Information Theory, 59:7711–7717, 2013.
[10] P. Bühlmann and S. van de Geer. Statistics for high-dimensional data. Springer Series
in Statistics. Springer, Heidelberg, 2011. Methods, theory and applications.
[11] O. Catoni. Challenging the empirical mean and empirical variance: a deviation study.
Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 48(4):1148–1185, 2012.
[12] V.H. de la Peña and E. Giné. Decoupling: from Dependence to Independence. Springer,
New York, 1999.
[13] L. Devroye, L. Györfi, and G. Lugosi. A probabilistic theory of pattern recognition,
volume 31 of Applications of Mathematics (New York). Springer-Verlag, New York,
1996.
[14] L. Devroye, M. Lerasle, G. Lugosi, and R.I. Oliveira. Sub-gausssian mean estimators.
Annals of Statistics, 2016.
[15] R. M. Dudley. Uniform central limit theorems, volume 142 of Cambridge Studies in
Advanced Mathematics. Cambridge University Press, New York, second edition, 2014.
[16] S. Foucart and H. Rauhut. A mathematical introduction to compressive sensing. Applied
and Numerical Harmonic Analysis. Birkhäuser/Springer, New York, 2013.
[17] L. Györfi, M. Kohler, A. Krzyżak, and H Walk. A Distribution-Free Theory of Nonparametric Regression. Springer, New York, 2002.
[18] D. Hsu and S. Sabato. Approximate loss minimization with heavy tails. Computing
Research Repository, abs/1307.1827, 2013.

36

[19] D. Hsu and S. Sabato. Loss minimization and parameter estimation with heavy tails.
Journal of Machine Learning Research, 17:1–40, 2016.
[20] K. Jamieson, R. Nowak, and B. Recht. Query complexity of derivative-free optimization.
In Advances in Neural Information Processing Systems, pages 2672–2680, 2012.
[21] M. Jerrum, L. Valiant, and V. Vazirani. Random generation of combinatorial structures
from a uniform distribution. Theoretical Computer Science, 43:186–188, 1986.
[22] V. 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].
[23] V. Koltchinskii. Oracle inequalities in empirical risk minimization and sparse recovery
problems: Lecture notes. Springer, 2011.
[24] G. Lecué and S. Mendelson. Learning subgaussian classes: Upper and minimax bounds.
In S. Boucheron and N. Vayatis, editors, Topics in Learning Theory. Societe Mathematique de France, 2016.
[25] G. Lecué and S. Mendelson. Sparse recovery under weak moment assumptions. Journal
of the European Mathematical Society, to appear.
[26] M. Ledoux and M. Talagrand. Probability in Banach Space. Springer-Verlag, New York,
1991.
[27] M. Lerasle and R.I. Oliveira. Robust empirical mean estimators. manuscript, 2012.
[28] P. Massart. Concentration inequalities and model selection. Ecole d’été de Probabilités
de Saint-Flour 2003. Lecture Notes in Mathematics. Springer, 2006.
[29] S. Mendelson. Learning without concentration. Journal of the ACM, 62:21, 2015.
[30] S. Mendelson. Local vs. global parameters breaking the Gaussian complexity barrier.
manuscript, 2015.
[31] S. Mendelson. On aggregation for heavy-tailed classes. Probability Theory and Related
Fields, to appear.
[32] S. Mendelson. On multiplier processes under weak moment assumptions. Geometric
Aspects of Functional Analysis - GAFA Seminar notes, to appear.
[33] S. Mendelson. Upper bounds on product and multiplier empirical processes. Stochastic
Processes and their Applications, to appear.
[34] S. Minsker. Geometric median and robust estimation in Banach spaces. Bernoulli,
21:23082335, 2015.
[35] A.S. Nemirovsky and D.B. Yudin. Problem complexity and method efficiency in optimization. 1983.

37

[36] V.N. Sudakov. Gaussian measures, Cauchy measures and ǫ-entropy. In Soviet Math.
Dokl, volume 10, pages 310–313, 1969.
[37] M. Talagrand. Upper and lower bounds for stochastic processes, volume 60 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in
Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern
Surveys in Mathematics]. Springer, Heidelberg, 2014. Modern methods and classical
problems.
[38] A. B. Tsybakov. Introduction to nonparametric estimation. Springer Series in Statistics. Springer, New York, 2009. Revised and extended from the 2004 French original,
Translated by Vladimir Zaiats.
[39] S. van de Geer. Applications of empirical process theory, volume 6 of Cambridge Series
in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge,
2000.
[40] S. van de Geer. Estimation and Testing Under Sparsity. Springer International Publishing, 2016.
[41] A.W. van der Vaart and J.A. Wellner.
Springer-Verlag, New York, 1996.

Weak convergence and empirical processes.

[42] V.N. Vapnik and A.Ya. Chervonenkis. Theory of Pattern Recognition. Nauka, Moscow,
1974. (in Russian); German translation: Theorie der Zeichenerkennung, Akademie Verlag, Berlin, 1979.

38

A

The distance oracle – outline of the proof

Here, we sketch the proof of Proposition 3.2. The proof is almost identical to that of Theorem
3.3 from [31], and follows the same path as the study of the quadratic component in the proof
of Theorem 2.10.
The first step in the proof involves generating a small-ball estimate that holds with sufficiently high probability, say 9/10. If a random variable Z satisfies kZkLq ≤ LkZkL2 for some
q > 2, then Z automatically satisfies a small-ball estimate, but with constants ρ0 and κ0 that
depend on L and q. In particular, it need not be true that ρ0 is close to 1, for example, that
P(|Z| ≥ κ0 kZkL2 ) ≥ 0.9. However, a combination of the norm equivalence and a Berry-Esseen
type argument suffices to ensure that an average of a small number of independent copies of
Z satisfies such a bound. More accurately, if ℓ is an integer that depends only on q and L
and Z1 , . . . , Zℓ are ℓ independent copies of Z, then
!
ℓ
1X
(A.1)
|Zi | ≥ κ0 kZkL2 ≥ 0.9 .
P
ℓ
i=1

Moreover, combining (A.1) with a straightforward application of Chebyshev’s inequality, one
has that with probability at least 0.8,
ℓ

κ0 kZkL2

1X
≤
|Zi | ≤ κ1 kZkL2
ℓ
i=1

for constants κ0 and κ1 that depend only on q and L.
Now consider a partition
of {1, ..., N } to k blocks I1′ , ..., Ik′ , where each block is of cardiP
nality ℓ. Let MZ,j = 1ℓ i∈I ′ |Zi |. It follows from a standard binomial estimate that, with
j
probability at least 1 − 2 exp(−c1 k), at least 0.7k of the random variables MZ,j satisfy
κ0 kZkL2 ≤ MZ,j ≤ κ1 kZkL2 .
Let us apply this observation to our setup: fix f ∗ ∈ F and consider the set
star(F − f ∗ , 0) ∩ rS ⊂ star(F − f ∗ , 0) ∩ rD = Ff ∗ ,r
for any fixed r > d∗ . By the choice of d∗ , star(F − f ∗ , 0) ∩ rS contains an ηr-net Vr of
cardinality at most exp(c1 k/2). Therefore, with probability at least 1 − 2 exp(−c1 k/2), for
every v ∈ Vr there is Jv ⊂ {1, ..., k} of cardinality at least 0.7k, such that for every j ∈ Jv ,
κ0 r ≤ Mv,j ≤ κ1 r .

(A.2)

Next, for each v ∈ star(F − f ∗ , 0) ∩ rS let πv ∈ Vr satisfy kv − πvkL2 ≤ ηr. Suppose that
one can show that on a high probability event, for every such v there are at most k/10 blocks
Ij′ on which
Mv−πv,j ≥ κ0 r/2 .
Then, on that event, and on at least 0.6k blocks,
(κ0 /2)r ≤ Mv,j ≤ 2κ1 r ,
and in particular, the same holds for the median of means Medℓ (v).
39

This is precisely the isomorphic estimate we require, so far, for elements of star(F − f ∗ , 0)
whose L2 (µ) norm is r. Obtaining the isomorphic estimate for elements with a larger L2 (µ)
norm follows because star(F − f ∗ , 0) is star-shaped around 0 and the required isomorphic
estimate is positive homogeneous.
Therefore, to complete the proof of the first part of Proposition 3.2 it suffices to show that
sup |{j : Mv−πv,j ≥ κ0 r/2}| ≤ k/10,

(A.3)

v

where the supremum is taken in star(F − f ∗ , 0) ∩ rS. The proof of (A.3) is based on an
identical argument to the one we used earlier, in the study of the quadratic component, and
the fact that r > d∗ .
The second claim in Proposition 3.2 is that on a high probability event, a one-sided (upper)
estimate on Medℓ (v) should hold for any v ∈ star(F − f ∗ , 0) ∩ rD. Its proof is almost the
same as the one we have just described.
For each v ∈ Vr′ , with probability at least 0.8,
Mv,j ≤ κ1 kvkL2 ≤ κ1 r ,

(A.4)

and thus, with probability at least 1− 2 exp(−c1 k), at least 0.7k of the random variables Mv,j
are smaller than κ1 r. Next, we consider an ηr-net Vr′ ⊂ Ff ∗ ,r , which, by the choice of r is of
cardinality at most exp(c1 k/2). It follows that, with probability at least 1 − 2 exp(−c1 k/2),
(A.4) holds for every v ∈ Vr′ . The oscillation term is then controlled as we outlined above.
Finally, because k = c(q, L)N , the estimates hold with the claimed probability of 1 −
2 exp(−cN ) for a constant c that depends only on q and L.

40

