Ivanov-Regularised Estimators over RKHSs

Ivanov-Regularised Least-Squares Estimators over Large
RKHSs and Their Interpolation Spaces

arXiv:1706.03678v2 [math.ST] 21 Nov 2017

Stephen Page

s.page@lancaster.ac.uk

STOR-i
Lancaster University
Lancaster, LA1 4YF, United Kingdom

Steffen Grünewälder

s.grunewalder@lancaster.ac.uk

Department of Mathematics and Statistics
Lancaster University
Lancaster, LA1 4YF, United Kingdom

Editor:

Abstract
We study kernel least-squares estimation under a norm constraint. This form of regularisation is known as Ivanov regularisation and it provides better control of the norm of the
estimator than the well-established Tikhonov regularisation. This choice of regularisation
allows us to dispose of the standard assumption that the reproducing kernel Hilbert space
(RKHS) has a Mercer kernel, which is restrictive as it usually requires compactness of the
covariate set. Instead, we assume only that the RKHS is separable with a bounded and
measurable kernel. We provide rates of convergence for the expected squared L2 error of
our estimator under the weak assumption that the variance of the response variables is
bounded and the unknown regression function lies in an interpolation space between L2
and the RKHS. We then obtain faster rates of convergence when the regression function
is bounded by clipping the estimator. In fact, we attain the optimal rate of convergence.
Furthermore, we provide a high-probability bound under the stronger assumption that the
response variables have subgaussian errors and that the regression function lies in an interpolation space between L∞ and the RKHS. Finally, we derive adaptive results for the
settings in which the regression function is bounded.
Keywords: Ivanov Regularisation, RKHSs, Mercer Kernels, Interpolation Spaces, Training and Validation

1. Introduction
One of the key problems to overcome in nonparametric regression is overfitting, due to estimators coming from large hypothesis classes. To avoid this phenomenon, it is common to
ensure that both the empirical risk and some regularisation function are small when defining an estimator. There are three natural ways to achieve this goal. We can minimise the
empirical risk subject to a constraint on the regularisation function, minimise the regularisation function subject to a constraint on the empirical risk or minimise a linear combination
of the two. These techniques are known as Ivanov regularisation, Morozov regularisation
1

Page and Grünewälder

and Tikhonov regularisation respectively (Oneto, Ridella, and Anguita, 2016). Ivanov and
Morozov regularisation can be viewed as dual problems, while Tikhonov regularisation can
be viewed as the Lagrangian relaxation of either.
Tikhonov regularisation has gained popularity as it provides a closed-form estimator in many
situations. In particular, Tikhonov regularisation in which the estimator is selected from a
reproducing kernel Hilbert space (RKHS) has been extensively studied (Steinwart and Christmann,
2008; Caponnetto and de Vito, 2007; Mendelson and Neeman, 2010; Steinwart, Hush, and Scovel,
2009). Although Tikhonov regularisation produces an estimator in closed form, it is Ivanov
regularisation which provides the greatest control over the hypothesis class, and hence over
the estimator it produces. For example, if the regularisation function is the norm of the
RKHS, then the bound forces the estimator to lie in a ball of predefined radius inside
the function space. An RKHS norm measures the smoothness of a function, so the norm
constraint bounds the smoothness of the estimator. By contrast, Tikhonov regularisation
provides no direct bound on the smoothness of the estimator.
The control we have over the Ivanov-regularised estimator is useful in many settings. The
most obvious use of Ivanov regularisation is when the regression function lies in a ball of
known radius in the RKHS. In this case, Ivanov regularisation can be used to constrain
the estimator to lie in the same ball. Ivanov regularisation can also be used within larger
inference methods. It is compatible with validation, allowing us to control an estimator
selected from an uncountable collection. This is because the Ivanov-regularised estimator is
continuous in the size of the ball containing it, so the estimators parametrised by an interval
of ball sizes can be controlled simultaneously using chaining.
The norm bound provided by Ivanov regularisation can also be useful in addressing other
problems. These include the use of optimal transport for the covariate shift problem, in
which we are interested in bounding the squared L2 (Q) error of our estimator where Q is
a probability measure other than the distribution of the covariates P . Having control over
the norm of the estimator means that we can use the reproducing kernel property and the
Cauchy–Schwarz inequality to bound the difference in the value of the estimator at two
different points. When the kernel of the RKHS is Lipschitz continuous, this bound can be
expressed in terms of the distance between the two points. Integrating an expression of
this form with respect to a joint distribution over the two points which has different fixed
marginal distributions gives the transport cost for the induced optimal transport problem.
The squared L2 (Q) error can be bounded by the sum of the squared L2 (P ) error and the
transport cost for the corresponding optimal transport problem.
In addition to the useful properties of the Ivanov-regularised estimator, Ivanov regularisation
can be performed almost as quickly as Tikhonov regularisation. The Ivanov-regularised
estimator is a support vector machine (SVM) with regularisation parameter selected to
match the norm constraint, as discussed in Appendix B. This parameter can be selected
to within a tolerance ε using interval bisection with order log(1/ε) iterations. In general,
Ivanov regularisation requires the calculation of log(1/ε) SVMs.
In this paper, we study the behaviour of the Ivanov-regularised least-squares estimator with
regularisation function equal to the norm of the RKHS. We derive a number of novel results
2

Ivanov-Regularised Estimators over RKHSs

concerning the rate of convergence of the estimator in various settings and under various assumptions. Ivanov regularisation allows us to significantly weaken some of the fundamental
assumptions made when studying Tikhonov-regularised estimators. For example, Ivanov
regularisation allows us to dispose of the restrictive Mercer kernel assumption.
The current theory of RKHS regression for Tikhonov-regularised estimators only applies
when the RKHS has a Mercer kernel. If the RKHS H has a Mercer kernel k with respect
to the covariate distribution P , then there is a simple decomposition of k and succinct
representation of H as a subspace of L2 (P ). These descriptions are in terms of the eigenfunctions and eigenvalues of the kernel operator T on L2 (P ). Many results have assumed
a fixed rate of decay of these eigenvalues in order to produce estimators whose squared
L2 (P ) error decreases quickly with the number of data points (Mendelson and Neeman,
2010; Steinwart et al., 2009). However, the assumptions necessary for H to have a Mercer
kernel are in general quite restrictive. The usual set of assumptions is that the covariate
set S is compact, the kernel k of H is continuous on S × S and the covariate distribution
satisfies supp P = S (see Section 4.5 of Steinwart and Christmann, 2008). In particular,
the assumption that the covariate set S is compact is inconvenient and there has been some
research into how to relax this condition by Steinwart and Scovel (2012).
By contrast, we provide results that hold under the significantly weaker assumption that
the RKHS is separable with a bounded and measurable kernel k. We can remove the Mercer
kernel assumption because we control empirical processes over balls in the RKHS instead
of relying on the representation of the RKHS given by Mercer’s theorem. We first prove an
expectation bound on the squared L2 (P ) error of our estimator of order n−β/2 under the
weak assumption that the response variables have bounded variance. Here, n is the number
of data points and β parametrises the interpolation space between L2 (P ) and H containing
the regression function. The definition of an interpolation space is given in Subsection
1.1. The expected squared L2 (P ) error can be viewed as the expected squared error of our
estimator at a new independent covariate with the same distribution P . If we also assume
that the regression function is bounded, then it makes sense to clip our estimator so that it
takes values in the same interval as the regression function. This further assumption allows
us to achieve an expectation bound on the squared L2 (P ) error of the clipped estimator of
order n−β/(1+β) .
We then move away from the average behaviour of the error towards its behaviour in
the worst case. We obtain high-probability bounds of the same order, under the stronger
assumption that the response variables have subgaussian errors and the interpolation space
is between L∞ and H. The second assumption is quite natural as we already assume that
the regression function is bounded, and H can be continuously embedded in L∞ since it
has a bounded kernel k. This assumption also means that the set of possible regression
functions is independent of the covariate distribution, which may be advantageous in some
scenarios. For example, it makes sense when considering the covariate shift problem, as
discussed above.
When the regression function is bounded, we also analyse an adaptive version of our estimator, which does not require us to know which interpolation space contains the regression
function. This adaptive estimator obtains bounds of the same order as the non-adaptive
3

Page and Grünewälder

one. Furthermore, our results match the order n−β/(β+1) of Steinwart et al. (2009) when
p = 1. In particular, this shows that our expectation results are of optimal order for our
setting.
1.1 RKHSs and Their Interpolation Spaces
A Hilbert space H of real-valued functions on S is an RKHS if the evaluation functional
Lx : H → R by Lx h = h(x) is bounded for all x ∈ S. In this case, Lx ∈ H ∗ the dual
of H and the Riesz representation theorem tells us that there is some kx ∈ H such that
h(x) = hh, kx iH for all h ∈ H. The kernel is then given by k(x1 , x2 ) = hkx1 , kx2 iH for
x1 , x2 ∈ S, and is symmetric and positive-definite.
Now suppose that (S, S) is a measurable space on which P is a probability measure. We
can define a range of spaces between L2 (P ) and H. Let (Z, k·kZ ) be a Banach space and
(V, k·kV ) be a subspace of Z. Then the K-functional of (Z, V ) is
K(z, t) = inf (kz − vkZ + tkvkV )
v∈V

for z ∈ Z and t > 0. For β ∈ (0, 1) and 1 ≤ q < ∞, we define
kzkβ,q =

Z

∞

(t

−β

q −1

K(z, t)) t

dt

0

1/q

and
kzkβ,∞ = sup(t−β K(z, t))
t>0

for z ∈ Z. The interpolation space [Z, V ]β,q is defined to be the set of z ∈ Z such that
kzkβ,q < ∞ for β ∈ (0, 1) and 1 ≤ q ≤ ∞. Smaller values of β give larger spaces. The space
is not much larger than V when β is close to 1, but we obtain spaces which get closer to Z
as β decreases. Hence, we can define the interpolation spaces [L2 (P ), H]β,q , where L2 (P )
is the space of P -almost-sure equivalence classes of measurable functions f on (S, S) such
that f 2 is integrable with respect to P . We will work with q = ∞, which gives the largest
space of functions for a fixed β ∈ (0, 1). Note that although H is not a subspace of L2 (P ),
the above definitions are still valid as there is a natural embedding of H into L2 (P ) as long
as the functions in H are measurable on (S, S). We will also require [L∞ , H]β,q , where L∞
is the space of bounded measurable functions on (S, S).
1.2 Literature Review
The current literature assumes that the RKHS H has a Mercer kernel k, as discussed above.
Earlier research in this area, such as that of Caponnetto and de Vito (2007), assumes that
the regression function is at least as smooth as an element of H. However, their paper still
allows for regression functions of varying smoothness by letting the regression function be
of the form g = T (β−1)/2 h for β ∈ [1, 2] and h ∈ H. Here, T : L2 (P ) → L2 (P ) is the kernel
operator and P is the covariate distribution. By assuming that the ith eigenvalue of T is
4

Ivanov-Regularised Estimators over RKHSs

of order i−1/p for p ∈ (0, 1], the authors achieve a squared L2 (P ) error of order n−β/(β+p)
with high probability by using SMVs. This squared L2 (P ) error is shown to be of optimal
order for β ∈ (1, 2].
Later research focuses on the case in which the regression function is at most as smooth as
an element of H. Often, this research demands that the response variables are bounded.
For example, Mendelson and Neeman (2010) assume that g ∈ T β/2 (L2 (P )) for β ∈ (0, 1) to
obtain a squared L2 (P ) error of order n−β/(1+p) with high probability by using Tikhonovregularised least-squares estimators. The authors also show that if the eigenfunctions of
the kernel operator T are uniformly bounded in L∞ , then the order can be improved to
n−β/(β+p) . Steinwart et al. (2009) relax the condition on the eigenfunctions to the condition
1−p
khk∞ ≤ Cp khkpH khkL
2 (P )

for all h ∈ H and some constant Cp > 0. The same rate is attained by using clipped
Tikhonov-regularised least-squares estimators, including clipped SMVs, and is shown to be
optimal. The authors assume that g is in an interpolation space between L2 (P ) and H,
which is slightly more general than the assumption of Mendelson and Neeman (2010). A
detailed discussion about the image of L2 (P ) under powers of T and interpolation spaces
between L2 (P ) and H is given by Steinwart and Scovel (2012).
Lately, the assumption that the response variables must be bounded has been relaxed to
allow for subexponential errors. However, the assumption that the regression function is
bounded has been maintained. For example, Fischer and Steinwart (2017) assume that
g ∈ T β/2 (L2 (P )) for β ∈ (0, 2] and that g is bounded. The authors also assume that
T α/2 (L2 (P )) is continuously embedded in L∞ with respect to an appropriate norm on
T α/2 (L2 (P )) for some α < β. This gives the same squared L2 (P ) error of order n−β/(β+p)
with high probability by using SVMs.
1.3 Contribution
In this paper, we provide bounds on the squared L2 (P ) error of our Ivanov-regularised leastsquares estimator when the regression function comes from an interpolation space between
L2 (P ) and an RKHS H, which is separable with a bounded and measurable kernel k. We
use the norm of the RKHS as our regularisation function. Under the weak assumption that
the response variables have bounded variance, we prove a bound on the expected squared
L2 (P ) error of order n−β/2 (Theorem 5 on page 12). If we assume that the regression
function is bounded then we can clip the estimator and achieve an expected squared L2 (P )
error of order n−β/(1+β) (Theorem 8 on page 14).
Under the stronger assumption that the response variables have subgaussian errors and the
regression function comes from an interpolation space between L∞ and H, we show that the
squared L2 (P ) error is of order n−β/(1+β) with high probability (Theorem 16 on page 23).
For the settings in which the regression function is bounded, we use training and validation
on the data in order to select the size of the constraint on the norm of our estimator. This
gives us an adaptive estimation result which does not require us to know which interpolation
space contains the regression function. We obtain a squared L2 (P ) error of order n−β/(1+β)
5

Page and Grünewälder

in expectation and with high probability, depending on the setting (Theorems 13 and 19 on
pages 19 and 27). In order to perform training and validation, the response variables in the
validation set must have subgaussian errors. The expectation results are of optimal order.
The results not involving validation are summarised in Table 1. The columns for which there
is an L∞ bound on the regression function also make the L2 (P ) interpolation assumption.
Orders of bounds marked with (∗) are known to be optimal.
Regression Function
Response Variables
Bound Type
Bound Order

L2 (P ) Interpolation
Bounded Variance
Expectation
n−β/2

L∞ Bound
Bounded Variance
Expectation
n−β/(1+β) (∗)

L∞ Interpolation
Subgaussian Errors
High Probability
n−β/(1+β)

Table 1: Orders of bounds on squared L2 (P ) error
The validation results are summarised in Table 2. Again, the columns for which there is an
L∞ bound on the regression function also make the L2 (P ) interpolation assumption. The
assumptions on the response variables relate to those in the validation set, which has ñ data
points. We assume that ñ is at least some multiple of n. Again, orders of bounds marked
with (∗) are known to be optimal.
Regression Function
Response Variables
Bound Type
Bound Order

L∞ Bound
Subgaussian Errors
Expectation
n−β/(1+β) (∗)

L∞ Interpolation
Subgaussian Errors
High Probability
n−β/(1+β)

Table 2: Orders of validation bounds on squared L2 (P ) error

2. Problem Definition and Assumptions
We now formally define our regression problem and the assumptions that we make in this
paper. For a topological space T , let B(T ) be the Borel σ-algebra of T . Let (S, S) be a
measurable space. Assume that (Xi , Yi ) are (S × R, S ⊗ B(R))-valued random variables on
the probability space (Ω, F, P) for 1 ≤ i ≤ n, which are i.i.d. with Xi ∼ P and Yi2 integrable.
We denote integration with respect to P by E. Since E(Yi |Xi ) is σ(Xi )-measurable, where
σ(Xi ) is the σ-algebra generated by Xi , we have that E(Yi |Xi ) = g(Xi ) for some function
g which is measurable on (S, S) (Section A3.2 of Williams, 1991). From the definition of
conditional expectation and the identical distribution of the (Xi , Yi ), it is clear that we can
choose g to be the same for all 1 ≤ i ≤ n. The conditional expectation used is that of
Kolmogorov, defined using the Radon–Nikodym derivative. Its definition is unique almost
surely. Since Yi2 is integrable, g ∈ L2 (P ) by Jensen’s inequality. In addition to
E(Yi |Xi ) = g(Xi ),

(1)

var(Yi |Xi ) ≤ σ 2 .

(2)

we assume

6

Ivanov-Regularised Estimators over RKHSs

We also assume that g ∈ [L2 (P ), H]β,∞ with norm at most B, where H is a separable RKHS
of measurable functions on (S, S) and β ∈ (0, 1). Finally, we assume that H has kernel k
which is bounded and measurable on (S × S, S ⊗ S), with
kkk∞ = sup k(x, x)1/2 < ∞.
x∈S

We can guarantee that H is separable by, for example, assuming that k is continuous and S
is a separable topological space (Lemma 4.33 of Steinwart and Christmann, 2008). The fact
that H has a kernel k which is measurable on (S × S, S ⊗ S) guarantees that all functions
in H are measurable on (S, S) (Lemma 4.24 of Steinwart and Christmann, 2008).
Let BH be the unit ball of H and r > 0. Our assumption that g ∈ [L2 (P ), H]β,∞ with norm
at most B for β ∈ (0, 1) provides us with the following approximation result. Theorem 3.1
of Smale and Zhou (2003) shows that
o
n
B 2/(1−β)
inf kh − gk2L2 (P ) : h ∈ rBH ≤ 2β/(1−β)
r
when H is dense in L2 (P ). This additional condition is present because these are the only
interpolation spaces considered by the authors, and in fact the result holds by the same
proof even when H is not dense in L2 (P ). Hence, for all α > 0 there is some hr,α ∈ rBH
such that
B 2/(1−β)
(3)
khr,α − gk2L2 (P ) ≤ 2β/(1−β) + α.
r
We will estimate hr,α for small α > 0 by
n

ĥr = arg min
f ∈rBH

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

We also define ĥ0 = 0. The estimator ĥr is calculated in Appendix B and shown to be
a (H, B(H))-valued measurable function on (Ω × [0, ∞), F ⊗ B([0, ∞))), where r varies in
[0, ∞). Lemma 21 summarises these results in this appendix.
2.1 Clipping
In the majority of this paper, we will assume that kgk∞ ≤ C. Since g is bounded in
[−C, C], we can make hr,α and ĥr closer to g by constraining them to lie in the same
interval. Similarly to Chapter 7 of Steinwart and Christmann (2008) and Steinwart et al.
(2009), we define the projection V : R → [−C, C] by

for t ∈ R.


 −C if t < −C
V (t) =
t
if |t| ≤ C

C
if t > C
7

Page and Grünewälder

2.2 Validation
Let us assume that we have an independent second data set (X̃i , Ỹi ) which are (S × R, S ⊗
B(R))-valued random variables on the probability space (Ω, F, P) for 1 ≤ i ≤ ñ. Let the
(X̃i , Ỹi ) be i.i.d. with X̃i ∼ P and
E(Ỹi |X̃i ) = g(X̃i ).
Furthermore, we assume that the moment generating function of Ỹi − g(X̃i ) conditional on
X̃i satisfies
E(exp(t(Ỹi − g(X̃i )))|X̃i ) ≤ exp(σ̃ 2 t2 /2)
for all t ∈ R and 1 ≤ i ≤ ñ. The random variable Ỹi − g(X̃i ) is said to be σ̃ 2 -subgaussian
conditional on X̃i . This assumption is made so that we can use chaining in the proofs of
Lemmas 10 and 17. Let ρ ≥ 0 and R ⊆ [0, ρ] be compact. Furthermore, let
F = {V ĥr : r ∈ R}
and


r0 = arg min E kV ĥr − gk2L2 (P ) .
r∈R

The minimum is attained as it is the minimum of a continuous function over a compact set.
In the event of ties, we may take r0 to be the infimum of all points attaining the minimum.
We will estimate r0 by
ñ
1X
(V ĥr (X̃i ) − Ỹi )2 .
r̂ = arg min
ñ
r∈R
i=1

We can uniquely define r̂ in the same way as r0 . Lemma 23 in Appendix B shows that
the estimator r̂ is a random variable on (Ω, F). Hence, ĥr̂ is a (H, B(H))-valued random
variable on (Ω, F).
2.3 Suprema of Stochastic Processes
We require the measurability of certain suprema over subsets of H. Since H is a separable
metric space, its subsets are also separable. For example, rBH has a countable dense subset
Ar . Furthermore, H is continuously embedded in L2 (Pn ) and L2 (P ) because its kernel k is
bounded. Here, Pn is the empirical distribution of the Xi . Hence, for example,
sup
f ∈rBH

kf k2L2 (Pn ) − kf k2L2 (P ) = sup kf k2L2 (Pn ) − kf k2L2 (P ) .
f ∈Ar

This is a random variable on (Ω, F) since the right-hand side is a supremum of countably
many random variables on (Ω, F). Therefore, this quantity has a well-defined expectation
and we can also apply Talagrand’s inequality to it.
8

Ivanov-Regularised Estimators over RKHSs

3. Expectation Bound for Unbounded Regression Function
First, we will bound the difference between ĥr and hr,α in the L2 (Pn ) norm.
Lemma 1 The definition of ĥr shows
n

kĥr − hr,α k2L2 (Pn ) ≤

4X
(Yi − g(Xi ))(ĥr (Xi ) − hr,α (Xi )) + 4khr,α − gk2L2 (Pn ) .
n

(4)

i=1

Proof Since hr,α ∈ rBH , the definition of ĥr gives
n

n

i=1

i=1

1X
1X
(ĥr (Xi ) − Yi )2 ≤
(hr,α (Xi ) − Yi )2 .
n
n
Expanding


2
(ĥr (Xi ) − Yi )2 = (ĥr (Xi ) − hr,α (Xi )) + (hr,α (Xi ) − Yi ) ,

substituting into the above and rearranging gives
n

n

i=1

i=1

1X
2X
(ĥr (Xi ) − hr,α (Xi ))2 ≤
(Yi − hr,α (Xi ))(ĥr (Xi ) − hr,α (Xi )).
n
n
Substituting
Yi − hr,α (Xi ) = (Yi − g(Xi )) + (g(Xi ) − hr,α (Xi ))
into the above and applying the Cauchy–Schwarz inequality to the second term gives
n

kĥr −

hr,α k2L2 (Pn )

2X
(Yi − g(Xi ))(ĥr (Xi ) − hr,α (Xi ))
≤
n
i=1

+ 2kg − hr,α kL2 (Pn ) kĥr − hr,α kL2 (Pn ) .
For constants a, b ≥ 0 we have
x2 ≤ a + 2bx =⇒ x2 ≤ 2a + 4b2

for x ∈ R by completing the square and rearranging. Applying this result to the above
inequality proves the lemma.
We now take the expectation of (4).
Lemma 2 By bounding the expectation of the right-hand side of (4), we have
 4kkk σr 4B 2/(1−β)

∞
+ 2β/(1−β) + 4α.
E kĥr − hr,α k2L2 (Pn ) ≤
n1/2
r
Proof We have


B 2/(1−β)
E khr,α − gk2L2 (Pn ) = khr,α − gk2L2 (P ) ≤ 2β/(1−β) + α
r
9

Page and Grünewälder

by (3) and
!
n
1X
(Yi − g(Xi ))hr,α (Xi ) = E
n

E

!
n
1X
E(Yi − g(Xi )|Xi )hr,α (Xi ) = 0.
n

i=1

i=1

The remainder of this proof method is due to Remark 6.1 of Sriperumbudur (2016). Since
ĥr ∈ rBH , we have
n

n

1X
1X
(Yi − g(Xi ))ĥr (Xi ) ≤ sup
(Yi − g(Xi ))f (Xi )
n
f ∈rBH n i=1
i=1
* n
+
1X
= sup
(Yi − g(Xi ))kXi , f
n
f ∈rBH
i=1

H

n
1X
(Yi − g(Xi ))kXi
=r
n
i=1
H
1/2

n
X
1
(Yi − g(Xi ))(Yj − g(Xj ))k(Xi , Xj )
= r 2
n
i,j=1

by the Cauchy–Schwarz inequality. By Jensen’s inequality and the independence of the
(Xi , Yi ), we have

1/2
!
n
n
X
1X
1
E
cov(Yi , Yj |X)k(Xi , Xj )
(Yi − g(Xi ))ĥr (Xi ) X ≤ r  2
n
n
i,j=1

i=1

≤r

!1/2
n
σ2 X
k(Xi , Xi )
n2
i=1

and again, by Jensen’s inequality, we have
E

!
 2
1/2
n
1X
σ kkk2∞
.
(Yi − g(Xi ))ĥr (Xi ) ≤ r
n
n
i=1

The result follows from Lemma 1.

The next step is to move our bound on the expectation of the squared L2 (Pn ) norm of
ĥr − hr,α to the expectation of the squared L2 (P ) norm of ĥr − hr,α .
Lemma 3 By using Rademacher processes, we can show
!
E

sup

f ∈rBH

kf k2L2 (Pn ) − kf k2L2 (P )

≤

8kkk2∞ r 2
.
n1/2

Proof Let the εi be i.i.d. Rademacher random variables on (Ω, F, P) for 1 ≤ i ≤ n,
independent of the Xi . Lemma 2.3.1 of van der Vaart and Wellner (2013) shows
Z
n
n
1X
1X
2
f (Xi ) − f 2 dP ≤ 2 E sup
εi f (Xi )2
E sup
f ∈rBH n
f ∈rBH n
i=1

i=1

10

Ivanov-Regularised Estimators over RKHSs

by symmetrisation. Since
|f (Xi )| ≤ kkk∞ r
for all f ∈ rBH , we find
f (Xi )2
2kkk∞ r
is a contraction vanishing at 0 as a function of f (Xi ) for all 1 ≤ i ≤ n. By Theorem 3.2.1
of Giné and Nickl (2016), we have
n

E

sup
f ∈rBH

1 X f (Xi )2
εi
n
2kkk∞ r

X

i=1

!

n

≤ 2E

sup
f ∈rBH

1X
εi f (Xi ) X
n
i=1

!

.

We now follow a similar argument to the proof of Lemma 2. We have
n

1X
εi f (Xi ) = sup
n
f ∈rBH

sup
f ∈rBH

i=1

*

n

1X
εi kXi , f
n
i=1

+

H

n
1X
εi kXi
=r
n
i=1
H
1/2

n
X
1
εi εj k(Xi , Xj ) .
= r 2
n
i,j=1

By Jensen’s inequality, we have
n

E

sup
f ∈rBH

1X
εi f (Xi ) X
n
i=1

!

1/2
n
X
1
≤ r 2
cov(εi , εj |X)k(Xi , Xj )
n


i,j=1

!1/2
n
1 X
k(Xi , Xi )
n2

=r

i=1

and again, by Jensen’s inequality, we have
n

E

sup
f ∈rBH

1X
εi f (Xi )
n
i=1

!

≤r



kkk2∞
n

1/2

.

The result follows.
The next result follows as a simple consequence of Lemmas 2 and 3.
Corollary 4 Since ĥr − hr,α ∈ 2rBH , we have
 4kkk σr 4B 2/(1−β)

32kkk2∞ r 2
∞
E kĥr − hr,α k2L2 (P ) ≤
+
+
+ 4α.
n1/2
r 2β/(1−β)
n1/2
11

Page and Grünewälder

All that remains to is to combine Corollary 7 with (3) by using

2
kĥr − gk2L2 (P ) ≤ kĥr − hr,α kL2 (P ) + khr,α − gkL2 (P )
≤ 2kĥr − hr,α k2L2 (P ) + 2khr,α − gk2L2 (P )

and to let α → 0.
Theorem 5 We have
 8kkk σr 10B 2/(1−β)

64kkk2∞ r 2
∞
+
+
.
E kĥr − gk2L2 (P ) ≤
n1/2
r 2β/(1−β)
n1/2
Based on this bound, the asymptotically optimal choice of r is


5β
32(1 − β)

(1−β)/2

kkk−(1−β)
Bn(1−β)/4 ,
∞

which gives a bound of

1−β
 !
32(1 − β) β
5β
2 −β/2
+5
kkk2β
2 32
∞B n
32(1 − β)
5β

(1−β)/2
5β
+8
kkkβ∞ σBn−(1+β)/4 .
32(1 − β)


4. Expectation Bound and Validation for Bounded Regression Function
We will now also assume that kgk∞ ≤ C and clip our estimator. It follows from (3) that
kV hr,α − gk2L2 (P ) ≤

B 2/(1−β)
+α
r 2β/(1−β)

and from Lemma 2 that
 4kkk σr 4B 2/(1−β)

∞
+ 2β/(1−β) + 4α.
E kV ĥr − V hr,α k2L2 (Pn ) ≤
1/2
n
r
4.1 Expectation Bound
As in Section 3, the next step is to move our bound on the expectation of the squared
L2 (Pn ) norm of V ĥr − V hr,α to the expectation of the squared L2 (P ) norm of V ĥr − V hr,α .
Working with clipped functions allows us to achieve a difference between the two squared
norms of order r/n1/2 instead of order r 2 /n1/2 . This is substantially smaller.
Lemma 6 By using Rademacher processes, we can show
E

sup
f ∈rBH

kV f − V

hr,α k2L2 (Pn )

− kV f − V

12

hr,α k2L2 (P )

!

≤

64kkk∞ Cr
.
n1/2

Ivanov-Regularised Estimators over RKHSs

Proof Let the εi be i.i.d. Rademacher random variables on (Ω, F, P) for 1 ≤ i ≤ n,
independent of the Xi . Lemma 2.3.1 of van der Vaart and Wellner (2013) shows
n

E sup
f ∈rBH

1X
(V f (Xi ) − V hr,α (Xi ))2 −
n
i=1

is at most

Z

(V f − V hr,α )2 dP

n

2 E sup
f ∈rBH

1X
εi (V f (Xi ) − V hr,α (Xi ))2
n
i=1

by symmetrisation. Since
|V f (Xi ) − V hr,α (Xi )| ≤ 2C
for all f ∈ rBH , we find
(V f (Xi ) − V hr,α (Xi ))2
4C
is a contraction vanishing at 0 as a function of V f (Xi ) − V hr,α (Xi ) for all 1 ≤ i ≤ n. By
Theorem 3.2.1 of Giné and Nickl (2016), we have
n

E

sup
f ∈rBH

1 X (V f (Xi ) − V hr,α (Xi ))2
εi
n
4C

X

i=1

is at most

n

2E

sup
f ∈rBH

1X
εi (V f (Xi ) − V hr,α (Xi )) X
n
i=1

!

!

.

Therefore,
n

E sup
f ∈rBH

1X
(V f (Xi ) − V hr,α (Xi ))2 −
n
i=1

Z

(V f − V hr,α )2 dP

is at most
n

16C E

sup
f ∈rBH

1X
εi (V f (Xi ) − V hr,α (Xi ))
n
i=1

!

n

≤ 32C E

sup
f ∈rBH

1X
εi V f (Xi )
n
i=1

!

by the triangle inequality, since hr,α ∈ rBH . Again, by Theorem 3.2.1 of Giné and Nickl
(2016), we have
n

E sup
f ∈rBH

1X
(V f (Xi ) − V hr,α (Xi ))2 −
n
i=1

is at most

n

64C E

sup
f ∈rBH

Z

(V f − V hr,α )2 dP

1X
εi f (Xi )
n
i=1

13

!

Page and Grünewälder

since V is a contraction vanishing at 0. We now follow a similar argument to the proof of
Lemma 2. We have
* n
+
n
1X
1X
sup
εi f (Xi ) = sup
εi kXi , f
n
f ∈rBH n
f ∈rBH
i=1

i=1

H

n
1X
εi kXi
=r
n
i=1
H

1/2
n
X
1
= r 2
εi εj k(Xi , Xj ) .
n
i,j=1

By Jensen’s inequality, we have
n

E

sup
f ∈rBH

1X
εi f (Xi ) X
n
i=1

!

1/2
n
X
1
≤ r 2
cov(εi , εj |X)k(Xi , Xj )
n


i,j=1

!1/2
n
1 X
k(Xi , Xi )
n2

=r

i=1

and again, by Jensen’s inequality, we have
n

E

sup
f ∈rBH

1X
εi f (Xi )
n
i=1

!

≤r



kkk2∞
n

1/2

.

The result follows.
The next result follows as a simple consequence of Lemmas 2 and 6.
Corollary 7 We have
 4kkk (σ + 16C)r 4B 2/(1−β)

∞
E kV ĥr − V hr,α k2L2 (P ) ≤
+ 2β/(1−β) + 4α.
n1/2
r
All that remains to is to combine Corollary 7 with (3) by using

2
kV ĥr − gk2L2 (P ) ≤ kV ĥr − V hr,α kL2 (P ) + kV hr,α − gkL2 (P )
≤ 2kV ĥr − V hr,α k2L2 (P ) + 2kV hr,α − gk2L2 (P )

and to let α → 0.
Theorem 8 We have
 8kkk (σ + 16C)r 10B 2/(1−β)

∞
E kV ĥr − gk2L2 (P ) ≤
+ 2β/(1−β) .
n1/2
r

Based on this bound, the optimal choice of r is
(1−β)/(1+β)

5β
−(1−β)/(1+β)
kkk∞
(σ + 16C)−(1−β)/(1+β) B 2/(1+β) n(1−β)/(2(1+β)) ,
2(1 − β)
14

Ivanov-Regularised Estimators over RKHSs

which gives a bound of
2 · 5(1−β)/(1+β) · 42β/(1+β)



2β
1−β

(1−β)/(1+β)

+



1−β
2β

2β/(1+β) !

2β/(1+β)
× kkk∞
(σ + 16C)2β/(1+β) B 2/(1+β) n−β/(1+β) .

4.2 Validation Bound
The proof method for the validation bound is similar to that of the expectation bound.
First, we will bound the difference between V ĥr̂ and V ĥr0 in the L2 (P̃ñ ) norm, where P̃ñ is
the empirical distribution of the X̃i .
Lemma 9 The definition of r̂ shows
ñ

kV ĥr̂ − V ĥr0 k2L2 (P̃

ñ )

≤

4X
(Ỹi − g(X̃i ))(V ĥr̂ (X̃i ) − V ĥr0 (X̃i )) + 4kV ĥr0 − gk2L2 (P̃ ) . (5)
ñ
ñ
i=1

Proof Since r0 ∈ R, the definition of r̂ gives
ñ

ñ

i=1

i=1

1X
1X
(V ĥr̂ (X̃i ) − Ỹi )2 ≤
(V ĥr0 (X̃i ) − Ỹi )2 .
ñ
ñ
Expanding

2
(V ĥr̂ (X̃i ) − Ỹi )2 = (V ĥr̂ (X̃i ) − V ĥr0 (X̃i )) + (V ĥr0 (X̃i ) − Ỹi ) ,

substituting into the above and rearranging gives
ñ

ñ

i=1

i=1

2X
1X
(V ĥr̂ (X̃i ) − V ĥr0 (X̃i ))2 ≤
(Ỹi − V ĥr0 (X̃i ))(V ĥr̂ (X̃i ) − V ĥr0 (X̃i )).
ñ
ñ
Substituting
Ỹi − V ĥr0 (X̃i ) = (Ỹi − g(X̃i )) + (g(X̃i ) − V ĥr0 (X̃i ))
into the above and applying the Cauchy–Schwarz inequality to the second term gives
ñ

kV ĥr̂ − V ĥr0 k2L2 (P̃

ñ )

≤

2X
(Ỹi − g(X̃i ))(V ĥr̂ (X̃i ) − V ĥr0 (X̃i ))
ñ
i=1

+ 2kg − V ĥr0 kL2 (P̃ñ ) kV ĥr̂ − V ĥr0 kL2 (P̃ñ ) .
For constants a, b ≥ 0 we have
x2 ≤ a + 2bx =⇒ x2 ≤ 2a + 4b2

for x ∈ R by completing the square and rearranging. Applying this result to the above
inequality proves the lemma.
15

Page and Grünewälder

A stochastic process W on (Ω, F) indexed by a metric space (M, d) is d2 -subgaussian if
it is centred and W (s) − W (t) is d(s, t)2 -subgaussian for all s, t ∈ M . W is separable if
there exists a countable set M0 ⊆ M such that the following holds for all ω ∈ Ω0 , where
P(Ω0 ) = 1. For all s ∈ M and ε > 0, W (s) is in the closure of
{W (t) : t ∈ M0 , d(s, t) ≤ ε}.
We also need to introduce the concept of covering numbers for the next result. The covering
number N (M, d, ε) is the minimum number of d-balls of size ε > 0 needed to cover M .
Whenever we require the covering number to be measurable in ε, such as when integrating
over ε, we will replace the covering number with a measurable upper bound. We now take
the expectation of (5).
Lemma 10 By bounding the expectation of the right-hand side of (5), we have


E kV ĥr̂ − V ĥr0 k2L2 (P̃ )
ñ

is at most

16σ̃C
ñ1/2
Proof We have



kkk2∞ ρ2
2 log 2 +
C2


1/2

+ π 1/2

!



+ 4 E kV ĥr0 − gk2L2 (P ) .





E kV ĥr0 − gk2L2 (P̃ ) = E kV ĥr0 − gk2L2 (P ) .
ñ

Let f0 = V ĥr0 and

ñ

W (f ) =

1X
Wi (f ),
ñ
i=1

where

Wi (f ) = (Ỹi − g(X̃i ))(f (X̃i ) − f0 (X̃i ))
for 1 ≤ i ≤ ñ and f ∈ F . Note that the Wi are independent and centred. It is clear that
Wi (f1 ) − Wi (f2 ) is σ̃ 2 kf1 − f2 k2∞ -subgaussian given X̃i for 1 ≤ i ≤ ñ and f1 , f2 ∈ F , so the
process W is σ̃ 2 k·k2∞ /ñ-subgaussian given X̃. By Lemma 22, we have that (F, σ̃k·k∞ /ñ1/2 )
is separable. Hence, W is separable on (F, σ̃k·k∞ /ñ1/2 ) since it is continuous. The diameter
of (F, σ̃k·k∞ /ñ1/2 ) is
D = sup σ̃kf1 − f2 k∞ /ñ1/2 ≤ 2σ̃C/ñ1/2 .
f1 ,f2 ∈F

From Lemma 28 in Appendix D, we have
Z ∞
Z
(log(N (F, σ̃k·k∞ /ñ1/2 , ε)))1/2 dε =
0

∞

(log(N (F, k·k∞ , ñ1/2 ε/σ̃)))1/2 dε
0
Z ∞
σ̃
(log(N (F, k·k∞ , u)))1/2 du
= 1/2
ñ
0

16

Ivanov-Regularised Estimators over RKHSs

is finite. Hence, by Theorem 2.3.7 of Giné and Nickl (2016) and Lemma 28, we have
!
E sup|W (f )| X̃, X, Y
f ∈F

is at most
5/2

E(|W (f0 )| |X̃, X, Y ) + 2
5/2

=2

Z

σ̃C/ñ1/2

Z

σ̃C/ñ1/2

(log(2N (F, σ̃k·k∞ /ñ1/2 , ε)))1/2 dε

0

(log(2N (F, k·k∞ , ñ1/2 ε/σ̃)))1/2 dε

0

25/2 σ̃
= 1/2
ñ
25/2 σ̃
≤ 1/2
ñ
=

Z

4σ̃C
ñ1/2

C

(log(2N (F, k·k∞ , u)))1/2 du

0

!
1/2
 π 1/2
kkk2∞ ρ2
C+
C
log 2 +
C2
2
!


1/2
kkk2∞ ρ2
1/2
.
2 log 2 +
+π
C2




In particular, the above bounds
E

!
ñ
1X
(Ỹi − g(X̃i ))(V ĥr̂ (X̃i ) − V ĥr0 (X̃i )) .
ñ
i=1

The result follows.
The next step is to move our bound on the expectation of the squared L2 (P̃ñ ) norm of
V ĥr̂ − V ĥr0 to the expectation of the squared L2 (P ) norm of V ĥr̂ − V ĥr0 .
Lemma 11 By using Rademacher processes, we can show
ñ

1X
E sup
(f (X̃i ) − V ĥr0 (X̃i ))2 −
ñ
f ∈F
i=1

is at most
64C 2
ñ1/2



kkk2∞ ρ2
2 log 2 +
C2


Z

2

(f − V ĥr0 ) dP

1/2

+π

1/2

!

!

.

Proof Let f0 = V ĥr0 and the εi be i.i.d. Rademacher random variables on (Ω, F, P) for
1 ≤ i ≤ ñ, independent of X̃, X and Y . Lemma 2.3.1 of van der Vaart and Wellner (2013)
shows
!
Z
ñ
1X
(f (X̃i ) − f0 (X̃i ))2 − (f − f0 )2 dP X, Y
E sup
f ∈F ñ
i=1

is at most

ñ

1X
2 E sup
εi (f (X̃i ) − f0 (X̃i ))2 X, Y
f ∈F ñ
i=1

17

!

Page and Grünewälder

by symmetrisation. Since
|f (X̃i ) − f0 (X̃i )| ≤ 2C
for all f ∈ F , we find
(f (X̃i ) − f0 (X̃i ))2
4C
is a contraction vanishing at 0 as a function of f (X̃i )−f0 (X̃i ) for all 1 ≤ i ≤ ñ. By Theorem
3.2.1 of Giné and Nickl (2016), we have
ñ

1 X (f (X̃i ) − f0 (X̃i ))2
εi
E sup
4C
f ∈F ñ

X̃, X, Y

i=1

is at most

ñ

1X
εi (f (X̃i ) − f0 (X̃i )) X̃, X, Y
2 E sup
f ∈F ñ
i=1

Therefore,

ñ

1X
E sup
(f (X̃i ) − f0 (X̃i ))2 −
ñ
f ∈F
i=1

is at most

Z

2

(f − f0 ) dP

ñ

1X
16C E sup
εi (f (X̃i ) − f0 (X̃i )) X, Y
f ∈F ñ
i=1

!
!

.

X, Y

!

!

.

We now follow a similar argument to the proof of Lemma 10. Let
ñ

W (f ) =

1X
Wi (f )
ñ
i=1

where
Wi (f ) = εi (f (X̃i ) − f0 (X̃i ))
for 1 ≤ i ≤ ñ and f ∈ F . Note that the Wi are independent and centred. We see that
Wi (f1 ) − Wi (f2 ) is kf1 − f2 k2∞ -subgaussian given X̃i for 1 ≤ i ≤ ñ and f1 , f2 ∈ F by
Hoeffding’s lemma, so the process W is k·k2∞ /ñ-subgaussian given X̃. By Lemma 22, we
have that (F, k·k∞ /ñ1/2 ) is separable. Hence, W is separable on (F, k·k∞ /ñ1/2 ) since it is
continuous. The diameter of (F, k·k∞ /ñ1/2 ) is
D = sup kf1 − f2 k∞ /ñ1/2 ≤ 2C/ñ1/2 .
f1 ,f2 ∈F

From Lemma 28 in Appendix D, we have
Z ∞
Z
(log(N (F, k·k∞ /ñ1/2 , ε)))1/2 dε =
0

∞

(log(N (F, k·k∞ , ñ1/2 ε)))1/2 dε
0
Z ∞
1
(log(N (F, k·k∞ , u)))1/2 du
= 1/2
ñ
0

18

Ivanov-Regularised Estimators over RKHSs

is finite. Hence, by Theorem 2.3.7 of Giné and Nickl (2016) and Lemma 28 in Appendix D,
we have
!
E sup|W (f )| X̃, X, Y
f ∈F

is at most
5/2

E(|W (f0 )| |X̃, X, Y ) + 2
= 25/2

Z

C/ñ1/2

Z

C/ñ1/2

(log(2N (F, k·k∞ /ñ1/2 , ε)))1/2 dε

0

(log(2N (F, k·k∞ , ñ1/2 ε)))1/2 dε

0

25/2
= 1/2
ñ
≤
=

25/2

Z

ñ1/2
4C
ñ1/2

C

(log(2N (F, k·k∞ , u)))1/2 du

0

!
1/2
 π 1/2
kkk2∞ ρ2
C+
log 2 +
C
C2
2
!


1/2
kkk2∞ ρ2
1/2
.
+π
2 log 2 +
C2




The result follows.
The next result follows as a simple consequence of Lemmas 10 and 11.
Corollary 12 We have


E kV ĥr̂ − V ĥr0 k2L2 (P )

is at most
16(σ̃ + 4C)C
ñ1/2



kkk2∞ ρ2
2 log 2 +
C2


1/2

+ π 1/2

!



+ 4 E kV ĥr0 − gk2L2 (P ) .

All that remains is to combine Corollary 12 with a bound on


E kV ĥr0 − gk2L2 (P )
from Theorem 8 and to let α → 0.
Theorem 13 We have



E kV ĥr̂ − gk2L2 (P )

is at most
32(σ̃ + 4C)C
ñ1/2



kkk2∞ ρ2
2 log 2 +
C2


1/2

+ π 1/2

!



+ 10 E kV ĥr0 − gk2L2 (P ) .

If R = [0, ρ] for ρ = an1/2 and a > 0, then r = an(1−β)/(2(1+β)) ∈ R. Therefore, by the
definition of r0 , we have




E kV ĥr0 − gk2L2 (P ) ≤ E kV ĥr − gk2L2 (P ) .
19

Page and Grünewälder

By Theorem 8, this gives a bound of on


E kV ĥr̂ − gk2L2 (P )

of order

log(n)1/2 /ñ1/2 + n−β/(1+β) ,
which is of order
n−β/(1+β)
when ñ is at least a multiple of n.
If R = {si = bi : 0 ≤ i ≤ I −1}∪{sI = an1/2 } and ρ = an1/2 for a, b > 0 and I = ⌈an1/2 /b⌉,
then there is a unique 0 ≤ i ≤ I such that an(1−β)/(2(1+β)) ≤ si < an(1−β)/(2(1+β)) + b. By
the definition of r0 , we have




E kV ĥr0 − gk2L2 (P ) ≤ E kV ĥsi − gk2L2 (P ) .

By Theorem 8, this gives a bound of on


E kV ĥr̂ − gk2L2 (P )

of order

log(n)1/2 /ñ1/2 + n−β/(1+β) ,
which is of order
n−β/(1+β)
when ñ is at least a multiple of n.

5. High-Probability Bound and Validation for L∞ Interpolation
Regression Function
We will now assume that g ∈ [L∞ , H]β,∞ with norm at most B instead of g ∈ [L2 (P ), H]β,∞
with norm at most B. This assumption is stronger as it implies that the norm of g ∈
[L2 (P ), H]β,∞ is
sup(t−β inf (kg − hkL2 (P ) + tkhkH )) ≤ sup(t−β inf (kg − hkL∞ + tkhkH )) ≤ B.
t>0

h∈H

t>0

h∈H

We will still assume that kgk∞ ≤ C. Hence, the results of Section 4 continue to apply.
Again, by Theorem 3.1 of Smale and Zhou (2003), we have

B 2/(1−β)
inf kh − gk2∞ : h ∈ rBH ≤ 2β/(1−β) .
r

Hence, for all α > 0 there is some hr,α ∈ rBH such that
khr,α − gk2∞ ≤

B 2/(1−β)
+ α.
r 2β/(1−β)

20

(6)

Ivanov-Regularised Estimators over RKHSs

This implies
B 2/(1−β)
+α
r 2β/(1−β)
and so in this setting we can allow hr,α from Section 4 to be the same as the one defined
here. This assumption means that we do not have to consider the variability of
khr,α − gk2L2 (P ) ≤

khr,α − gk2L2 (Pn )
around its mean in the proof of Lemma 14. This would add a term of order r 2 /n1/2 to
the bound in that lemma, substantially increasing its size. We also now assume that the
moment generating function of Yi − g(Xi ) conditional on Xi satisfies
E(exp(t(Yi − g(Xi )))|Xi ) ≤ exp(σ 2 t2 /2)
for all t ∈ R and 1 ≤ i ≤ n. The random variable Yi − g(Xi ) is said to be σ 2 -subgaussian
conditional on Xi . This condition implies (1) and our weaker assumption (2). It allows us
to analyse a quadratic form evaluated at the Yi − g(Xi ) in the proof of Lemma 14 by using
Lemma 26 in Appendix C. All probabilities mentioned in this section will be taken with
respect to P on (Ω, F) unless otherwise stated.
5.1 High-Probability Bound
We first bound the squared L2 (Pn ) norm of ĥr − hr,α .
Lemma 14 Let t > 0. With probability at least 1 − 3e−t , we have
kĥr −

hr,α k2L2 (Pn )


4kkk∞ σr (1 + t + 2(t2 + t)1/2 )1/2 + (2t)1/2
4B 2/(1−β)
+
+ 4α.
≤
n1/2
r 2β/(1−β)

Proof From the proof of Lemma 2, we have
1/2

n
n
X
X
1
1
(Yi − g(Xi ))(Yj − g(Xj ))k(Xi , Xj ) .
(Yi − g(Xi ))ĥr (Xi ) ≤ r  2
n
n
i,j=1

i=1

Let K be the n × n matrix with Ki,j = k(Xi , Xj ) and let ε be the vector of the Yi − g(Xi ).
Then
n
1 X
(Yi − g(Xi ))(Yj − g(Xj ))k(Xi , Xj ) = εT (n−2 K)ε.
n2
i,j=1

Furthermore, since k is a measurable function on (S × S, S ⊗ S), we have that n−2 K is
measurable on (Ω, F) and non-negative-definite. Let ai be the eigenvalues of n−2 K for
1 ≤ i ≤ n. Then
max ai ≤ tr(n−2 K) ≤ n−1 kkk2∞
i

and
tr((n−2 K)2 ) = kak22 ≤ kak21 ≤ n−2 kkk4∞ .
21

Page and Grünewälder

Therefore, by Lemma 26 in Appendix C, we have
εT (n−2 K)ε ≤ kkk2∞ σ 2 n−1 (1 + t + 2(t2 + t)1/2 )
and

n

1X
kkk∞ σr(1 + t + 2(t2 + t)1/2 )1/2
(Yi − g(Xi ))ĥr (Xi ) ≤
n
n1/2
i=1

with probability at least 1 − e−t . Furthermore,
n

−

1X
(Yi − g(Xi ))hr,α (Xi )
n
i=1

is subgaussian given X with parameter
n
kkk2∞ σ 2 r 2
1 X 2
2
σ
h
(X
)
≤
.
r,α
i
n2
n
i=1

So we have

n

−

1X
kkk∞ σr(2t)1/2
(Yi − g(Xi ))hr,α (Xi ) ≤
n
n1/2
i=1

with probability at least 1 − e−t by Chernoff bounding. Finally,
khr,α − gk2L2 (Pn ) ≤

B 2/(1−β)
+α
r 2β/(1−β)

by (6). The result follows.
We will now apply V again. It follows from (6) that
kV hr,α − gk2L2 (P ) ≤

B 2/(1−β)
+α
r 2β/(1−β)

and from Lemma 14 that for t > 0 we have
kV ĥr − V

hr,α k2L2 (Pn )


4kkk∞ σr (1 + t + 2(t2 + t)1/2 )1/2 + (2t)1/2
4B 2/(1−β)
+
+ 4α
≤
n1/2
r 2β/(1−β)

with probability at least 1−3e−t .We now move our probability bound on the squared L2 (Pn )
norm of V ĥr − V hr,α to the squared L2 (P ) norm of V ĥr − V hr,α .
Lemma 15 Let t > 0. With probability at least 1 − e−t we have
sup
f ∈rBH

kV f − V hr,α k2L2 (Pn ) − kV f − V hr,α k2L2 (P )

is at most
64kkk∞ Cr
+
n1/2



32C 4 1024kkk∞ C 3 r
+
n
n3/2
22

1/2

t1/2 +

8C 2 t
.
3n

Ivanov-Regularised Estimators over RKHSs

Proof Let
kV f − V hr,α k2L2 (Pn ) − kV f − V hr,α k2L2 (P )

Z = sup
f ∈rBH

n
X

= sup

f ∈rBH i=1

We have



n−1 (V f (Xi ) − V hr,α (Xi ))2 − kV f − V hr,α k2L2 (P ) .




= 0,
E n−1 (V f (Xi ) − V hr,α (Xi ))2 − kV f − V hr,α k2L2 (P )

4C 2
n−1 (V f (Xi ) − V hr,α (Xi ))2 − kV f − V hr,α k2L2 (P ) ≤
,
n

2  16C 4

≤
E n−2 (V f (Xi ) − V hr,α (Xi ))2 − kV f − V hr,α k2L2 (P )
n2

for all 1 ≤ i ≤ n and f ∈ rBH . Furthermore, rBH is separable since H is, so Z is
a random variable on (Ω, F) and we can use Talagrand’s inequality (Theorem A.9.1 of
Steinwart and Christmann, 2008) to show
1/2
 
8tC 2
16C 4 8C 2 E(Z)
+
+
Z > E(Z) + 2t
n
n
3n

with probability at most e−t . From Lemma 6, we have
E(Z) ≤

64kkk∞ Cr
.
n1/2

The result follows.
We obtain a bound on the L2 (P ) norm of V ĥr − V hr,α as a simple consequence of Lemmas
14 and 15. All that remains is to combine this bound with (6) in the same way as the proof
of Theorem 8 and to let α → 0.
Theorem 16 Let t > 0. With probability at least 1 − 4e−t , we have
kV̂ hr −

gk2L2 (P )


8kkk∞ σr (1 + t + 2(t2 + t)1/2 )1/2 + (2t)1/2
10B 2/(1−β)
≤
+
n1/2
r 2β/(1−β)
 4

1/2
64kkk∞ C 3 r
16C 2 t
2C
128kkk∞ Cr
1/2
+
.
t
+
+
+
8
n
3n
n1/2
n3/2

For t ≥ 1, this bound can be simplified to
1/2

8(2C 4 + 8kkk∞ C 3/2 r 1/2 + kkk∞ (5σ + 16C)r)t1/2 10B 2/(1−β)
16C 2 t
+
+
.
3n
n1/2
r 2β/(1−β)
Based on this bound, the asymptotically optimal choice of r is

(1−β)/(1+β)
5β
−(1−β)/(1+β)
kkk∞
2(1 − β)
× (5σ + 16C)−(1−β)/(1+β) B 2/(1+β) t−(1−β)/(2(1+β)) n(1−β)/(2(1+β)) ,

which, ignoring factors involving only β, gives a bound of asymptotic order
2β/(1+β)
kkk∞
(5σ + 16C)2β/(1+β) B 2/(1+β) tβ/(1+β) n−β/(1+β) .

23

Page and Grünewälder

5.2 Validation Bound
Before continuing, we will redefine r0 to be the minimiser over R of the 1 − 4e−t quantile of
kV̂ hr − gk2L2 (P ) .
The minimum is attained as it is the minimum of a continuous function over a compact set.
In the event of ties, we may take r0 to be the infimum of all points attaining the minimum.
We will also introduce some new notation. Let U and V be random variables on (Ω, F).
Then
kU kψ2 = inf{c > 0 : E ψ2 (|U |/c) ≤ 1},
kU |V kψ2 = inf{c > 0 : E(ψ2 (|U |/c)|V ) ≤ 1},
where
ψ2 (x) = exp(x2 ) − 1
for x ∈ R. We first bound the squared L2 (P̃ñ ) norm of V ĥr̂ − V ĥr0 .
Lemma 17 Let t > 0. With probability at least 1 − 2e−t , we have
kV ĥr̂ − V ĥr0 k2L2 (P̃

ñ )

is at most
28 · 3σ̃C
ñ1/2



!

1/2
kkk2∞ ρ2
29/2 C 2 t1/2
1/2
1/2
+ 4kV ĥr0 − gk2L2 (P ) .
t
+
2 log 1 +
+
π
8C 2
ñ1/2

Proof We first reintroduce the process from the proof of Lemma 10. Let f0 = V ĥr0 and
ñ

W (f ) =

1X
Wi (f ),
ñ
i=1

where
Wi (f ) = (Ỹi − g(X̃i ))(f (X̃i ) − f0 (X̃i ))
for 1 ≤ i ≤ ñ and f ∈ F . Note that the Wi are independent and centred. It is clear that
Wi (f1 ) − Wi (f2 ) is σ̃ 2 kf1 − f2 k2∞ -subgaussian given X̃i for 1 ≤ i ≤ ñ and f1 , f2 ∈ F , so the
process W is σ̃ 2 k·k2∞ /ñ-subgaussian given X̃. By Lemma 22, we have that (F, σ̃k·k∞ /ñ1/2 )
is separable. Hence, W is separable on (F, σ̃k·k∞ /ñ1/2 ) since it is continuous. The diameter
of (F, σ̃k·k∞ /ñ1/2 ) is
D = sup σ̃kf1 − f2 k∞ /ñ1/2 ≤ 2σ̃C/ñ1/2 .
f1 ,f2 ∈F

From Lemma 28 in Appendix D, we have
Z ∞
Z
(log(N (F, σ̃k·k∞ /ñ1/2 , ε)))1/2 dε =
0

∞

(log(N (F, k·k∞ , ñ1/2 ε/σ̃)))1/2 dε
0
Z ∞
σ̃
(log(N (F, k·k∞ , u)))1/2 du
= 1/2
ñ
0

24

Ivanov-Regularised Estimators over RKHSs

is finite. Hence, by Exercise 1 of Section 2.3 of Giné and Nickl (2016) and Lemma 28, we
have
sup|W (f )| X̃, X, Y
f ∈F

ψ2

is at most
W (f0 ) X̃, X, Y
= 29/2 · 31/2
=
≤
=

Z

29/2

31/2 σ̃

29/2

31/2 σ̃

·
ñ1/2
·
ñ1/2

25 · 31/2 σ̃C
ñ1/2

+ 29/2 · 31/2

ψ2

2σ̃C/ñ1/2

Z

2σ̃C/ñ1/2

(log N (F, σ̃k·k∞ /ñ1/2 , ε))1/2 dε

0

(log N (F, k·k∞ , ñ1/2 ε/σ̃))1/2 dε

0

Z

2C

(log N (F, k·k∞ , u))1/2 du

0

!
1/2
kkk2∞ ρ2
1/2
2 log 1 +
C + (2π) C
8C 2
!


1/2
kkk2∞ ρ2
2 log 1 +
+ π 1/2 .
8C 2




By Lemma 24 in Appendix C, we have
sup|W (f )|
f ∈F

is subgaussian with parameter
211 · 32 σ̃ 2 C 2
ñ



kkk2∞ ρ2
2 log 1 +
8C 2


1/2

+ π 1/2

!2

and so is at most
26 · 3σ̃C
ñ1/2



kkk2∞ ρ2
2 log 1 +
8C 2


1/2

+π

1/2

!

t1/2

with probability at least 1 − e−t by Chernoff bounding. In particular,
ñ

1X
(Ỹi − g(X̃i ))(V ĥr̂ (X̃i ) − V ĥr0 (X̃i ))
ñ
i=1

is at most
26 · 3σ̃C
ñ1/2



kkk2∞ ρ2
2 log 1 +
8C 2


1/2

+π

1/2

!

t1/2

with probability at least 1 − e−t . Furthermore,
ñ

kV ĥr0 − gk2L2 (P̃

ñ )

=


1 X
(V ĥr0 (X̃i )2 − g(X̃i ))2 − kV ĥr0 − gk2L2 (P ) + kV ĥr0 − gk2L2 (P ) .
ñ
i=1

25

Page and Grünewälder

Since
(V ĥr0 (X̃i )2 − g(X̃i ))2 − kV ĥr0 − gk2L2 (P ) ≤ 4C 2
for all 1 ≤ i ≤ ñ, we find
kV ĥr0 − gk2L2 (P̃
with probability at most

ñ )

− kV ĥr0 − gk2L2 (P ) > t

ñt2
exp −
32C 4




.

by Hoeffding’s inequality. Therefore, we have
kV ĥr0 − gk2L2 (P̃

ñ

− kV ĥr0 − gk2L2 (P ) ≤
)

25/2 C 2 t1/2
ñ1/2

with probability at least 1 − e−t . The result follows.
We now move our probability bound on the squared L2 (P̃ñ ) norm of V ĥr̂ − V ĥr0 to the
squared L2 (P ) norm of V ĥr̂ − V ĥr0 .
Lemma 18 Let t > 0. With probability at least 1 − e−t , we have
ñ

1X
(f (X̃i ) − V ĥr0 (X̃i ))2 −
sup
f ∈F ñ
i=1

Z

(f − V ĥr0 )2 dP

is at most
64C 2
ñ1/2
4C 2
+ 1/2
ñ



kkk2∞ ρ2
2 log 2 +
C2


64
2 + 1/2
ñ



1/2

+ π 1/2

kkk2∞ ρ2
2 log 2 +
C2


!

1/2

+π

1/2

!!1/2

t1/2 +

8C 2 t
.
3ñ

Proof Let
Z = sup kf − V ĥr0 k2L2 (P̃
f ∈F

= sup

ñ
X

f ∈F i=1

ñ )

− kf − V ĥr0 k2L2 (P )



ñ−1 (f (X̃i ) − V ĥr0 (X̃i ))2 − kf − V ĥr0 k2L2 (P ) .

We have



= 0,
E ñ−1 (f (X̃i ) − V ĥr0 (X̃i ))2 − kf − V ĥr0 k2L2 (P )

4C 2
ñ−1 (f (X̃i ) − V ĥr0 (X̃i ))2 − kf − V ĥr0 k2L2 (P ) ≤
,
ñ


2

16C 4
≤
E ñ−2 (f (X̃i ) − V ĥr0 (X̃i ))2 − kf − V ĥr0 k2L2 (P )
ñ2
26

Ivanov-Regularised Estimators over RKHSs

for all 1 ≤ i ≤ ñ and f ∈ F . Furthermore, F is separable by Lemma 22, so Z is
a random variable on (Ω, F) and we can use Talagrand’s inequality (Theorem A.9.1 of
Steinwart and Christmann, 2008) to show


Z > E(Z) + 2t



16C 4 8C 2 E(Z)
+
ñ
ñ

1/2

+

8tC 2
3ñ

with probability at most e−t . From Lemma 11, we have
64C 2
E(Z) ≤ 1/2
ñ



kkk2∞ ρ2
2 log 2 +
C2


1/2

+π

1/2

!

.

The result follows.
We obtain a bound on the L2 (P ) norm of V ĥr̂ − V ĥr0 as a simple consequence of Lemmas
17 and 18. All that remains to is to combine this bound with a bound on the 1 − 4e−t
quantile of
kV ĥr0 − gk2L2 (P )
from Theorem 16 and to let α → 0.
Theorem 19 Let t > 0. With probability at least 1 − 3e−t , we have
kV ĥr̂ − V ĥr0 k2L2 (P )
is at most
!


1/2
211/2 C 2 t1/2
kkk2∞ ρ2
29 · 3σ̃C
1/2
1/2
t
+
2
log
1
+
+
π
8C 2
ñ1/2
ñ1/2
!


1/2
27 C 2
kkk2∞ ρ2
1/2
+ 1/2
+π
2 log 2 +
C2
ñ
!!1/2
1/2


24 C 2 t
27/2 C 2
25
kkk2∞ ρ2
1/2
1/2
t
+
+
π
+
1
+
2
log
2
+
C2
3ñ
ñ1/2
ñ1/2
+ 10kV ĥr0 − gk2L2 (P ) .
If R = [0, ρ] for ρ = an1/2 and a > 0, then r = an(1−β)/(2(1+β)) ∈ R. Therefore, by the
definition of r0 , we have that the 1 − 4e−t quantile of
kV ĥr0 − gk2L2 (P )
is at most that of
kV ĥr − gk2L2 (P ) ,
which is bounded in Theorem 16. For t ≥ 1, we obtain a bound on
kV ĥr̂ − gk2L2 (P )
27

Page and Grünewälder

of order
t1/2 log(n)1/2 /ñ1/2 + t1/2 n−β/(1+β)
with probability at least 1 − 7e−t , which is of order
t1/2 n−β/(1+β)
when ñ is at least a multiple of n.
If R = {si = bi : 0 ≤ i ≤ I −1}∪{sI = an1/2 } and ρ = an1/2 for a, b > 0 and I = ⌈an1/2 /b⌉,
then there is a unique 0 ≤ i ≤ I such that an(1−β)/(2(1+β)) ≤ si < an(1−β)/(2(1+β)) + b. By
the definition of r0 , we have that the 1 − 4e−t quantile of
kV ĥr0 − gk2L2 (P )
is at most that of
kV ĥsi − gk2L2 (P ) ,
which is bounded in Theorem 16. For t ≥ 1, we obtain a bound on
kV ĥr̂ − gk2L2 (P )
of order
t1/2 log(n)1/2 /ñ1/2 + t1/2 n−β/(1+β)
with probability at least 1 − 7e−t , which is of order
t1/2 n−β/(1+β)
when ñ is at least a multiple of n.

6. Discussion
In this paper, we show how Ivanov regularisation can be used to produce smooth estimators
which have a small squared L2 (P ) error. We consider the case in which the regression function lies in an interpolation space between L2 (P ) and an RKHS. We achieve these bounds
without the standard assumption that the RKHS has a Mercer kernel, which means that
our results apply even when the covariate set is not compact. In fact, our only assumption
on the RKHS is that it is separable, with a bounded and measurable kernel. Under the
weak assumption that the response variables have bounded variance, we prove an expectation bound on the squared L2 (P ) error of our estimator of order n−β/2 . If we assume
that the regression function is bounded, then we can clip the estimator and show that this
has an expected squared L2 (P ) error of order n−β/(1+β) . Under the stronger assumption
that the response variables have subgaussian errors and that the regression function comes
from an interpolation space between L∞ and H, we show that the squared L2 (P ) error is of
order n−β/(1+β) with high probability. For the settings in which the regression function is
bounded, we can use training and validation on the data set. This allows us to select the size
of the norm constraint for our Ivanov regularisation without knowing which interpolation
28

Ivanov-Regularised Estimators over RKHSs

space contains the regression function. The response variables in the validation set must
have subgaussian errors.
The order n−β/(β+1) matches that of Steinwart et al. (2009) when p = 1. In particular,
this shows that our expectation results are of optimal order. However, we do not make
the restrictive assumption that k is a Mercer kernel of H, as discussed above. This is because we use Ivanov regularisation instead of Tikhonov regularisation and control empirical
processes over balls in the RKHS. By contrast, the current theory uses the embedding of
H in L2 (P ) from Mercer’s theorem to achieve bounds on Tikhonov-regularised estimators
(Mendelson and Neeman, 2010; Steinwart et al., 2009). For this reason, it seems unlikely
that Tikhonov-regularised estimators such as SVMs would perform well in the absence of
a Mercer kernel, although it would be interesting to investigate whether or not this is the
case.
It would be useful to extend the lower bound of order n−β/(β+1) to the case in which the
regression function lies in an interpolation space between L∞ and the RKHS. This would
show that our high-probability bound is also of optimal order. However, it is possible that
estimation can be performed with a high-probability bound on the squared L2 (P ) error of
smaller order.

Appendix A. RKHSs and the Empirical Distribution
In this appendix, we will provide a decomposition of H based on Pn . Recall that the
evaluation functional Lx : H → R by Lx h = h(x) is bounded for all x ∈ S. Since Lx is a
bounded linear functional, it is also continuous. Therefore,
L−1
x {0} = {f ∈ H : f (x) = 0}
is a closed subspace of H. Let
Z = {f ∈ H : kf kL2 (Pn ) = 0} =

n
\

L−1
Xi {0},

i=1

which is a closed subspace of H. There exists a projection Q : H → Z which is orthogonal
with respect to the inner product on H.
We now consider f − Qf for f ∈ H. Let us define the integral operator T̂ : H → H by
n

1X
f (Xi )kXi .
T̂ f =
n
i=1

The operator T̂ is clearly linear and is bounded because H is an RKHS. Furthermore, im T̂
is finite-dimensional, so T̂ is compact. Finally,
hT̂ f1 , f2 iH = hf1 , f2 iL2 (Pn )
29

Page and Grünewälder

is symmetric in f1 , f2 ∈ H, so T̂ is self-adjoint. Hence, the spectral theorem (Corollary 4
in Chapter 14 of Bollobás, 1999) tells us that
m
X
hf, âi iH âi ∈ ker T̂ ,
f−
i=1

where the âi ∈ (ker T̂ )⊥ for 1 ≤ i ≤ m are orthonormal in H and eigenvectors of T̂ with
corresponding eigenvalues λ̂i 6= 0 and m = rk T̂ ≤ n. In fact,
λ̂i = hλ̂i âi , âi iH = hT̂ âi , âi iH = hâi , âi iL2 (Pn ) ≥ 0
and λ̂i 6= 0, so λ̂i > 0 for 1 ≤ i ≤ m. Order the λ̂i so that they are non-increasing. More
generally, the âi have the useful property that
hâi , f iL2 (Pn ) = hT̂ âi , f iH = hλ̂i âi , f iH = λ̂i hâi , f iH
−1/2

âi ∈ (ker T̂ )⊥ for 1 ≤ i ≤ m are orthonormal in L2 (Pn ) and
for any f ∈ H. So êi = λ̂i
eigenvectors of T̂ with corresponding eigenvalues λ̂i . Furthermore,
f−

m
X

hf, êi iL2 (Pn ) êi ∈ ker T̂

i=1

for all f ∈ H.
Let us examine ker T̂ . Recall that
Z = {f ∈ H : kf kL2 (Pn ) = 0}.
Clearly Z ⊆ ker T̂ , but we also have that if f ∈ ker T̂ , then
kf k2L2 (Pn ) = hf, f iL2 (Pn ) = hT̂ f, f iH = 0.
Hence, ker T̂ ⊆ Z and therefore ker T̂ = Z. This means êi ∈ Z ⊥ for 1 ≤ i ≤ m and
f−

m
X
hf, êi iL2 (Pn ) êi ∈ Z
i=1

for all f ∈ H. Recall that Q is the orthogonal projection from H onto Z, so Qf is the
unique element in Z such that f − Qf ∈ Z ⊥ for f ∈ H. Since
m
X
hf, êi iL2 (Pn ) êi ∈ Z
f−
i=1

and

m
X

hf, êi iL2 (Pn ) êi ∈ Z ⊥ ,

i=1

30

Ivanov-Regularised Estimators over RKHSs

we find

m
X
hf, êi iL2 (Pn ) êi
Qf = f −
i=1

or

f=

m
X

hf, êi iL2 (Pn ) êi + Qf.

i=1

Finally, since the êi ∈ sp{kXj : 1 ≤ j ≤ n}, we have Z ⊥ ⊆ sp{kXj : 1 ≤ j ≤ n}. On the other
hand, if f ∈ sp{kXj : 1 ≤ j ≤ n} and z ∈ Z, then hf, ziH = 0. So sp{kXj : 1 ≤ j ≤ n} ⊆ Z ⊥ .
Therefore, Z ⊥ = sp{kXj : 1 ≤ j ≤ n} and
H = sp{kXj : 1 ≤ j ≤ n} ⊕ Z.
A.1 Eigenvectors and Eigenvalues of T̂ and n−1 K
We will now investigate the êj and λ̂j . We can write T̂ êj = λ̂j êj as
n

1X
êj (Xi )kXi = λ̂j êj .
n
i=1

Since λ̂j > 0, we see that the values of êj (Xi ) for 1 ≤ i ≤ n uniquely define êj . By evaluating
this expression at Xl for 1 ≤ l ≤ n, we obtain
n

1X
êj (Xi )k(Xi , Xl ) = λ̂j êj (Xl ),
n
i=1

or

n

1X
k(Xl , Xi )êj (Xi ) = λ̂j êj (Xl )
n
i=1

since k is symmetric. If we let K be the n × n symmetric matrix with Kl,j = k(Xl , Xj ), E
be the n × m matrix with Ei,j = n−1/2 êj (Xi ) and Λ be the m × m diagonal matrix with
Λj,j = λ̂j , then this can be written as
n−1 KE = EΛ.
So the columns of E are eigenvectors of n−1 K, with eigenvalues found in Λ. Furthermore,
since the êj are orthonormal in L2 (Pn ), we find E T E = I. We also find
m = rk T̂ ≤ rk(n−1 K).
Now let us consider a diagonalisation of the symmetric matrix
n−1 K = ADAT ,
where A is an orthogonal matrix and D is a diagonal matrix with non-increasing entries.
The columns of A are eigenvectors of n−1 K with eigenvalues found in D. Since the kernel
31

Page and Grünewälder

k is non-negative definite, n−1 K is non-negative definite and Dj,j ≥ 0 for 1 ≤ j ≤ n. For
1 ≤ j ≤ rk(n−1 K), let
n
X
−1 −1/2
Ai,j kXi .
fj = Dj,j
n
i=1

Then
T̂ fj =

−1 −1/2
Dj,j
n

−1 −1/2
= Dj,j
n

n
X

i=1
n
X

Ai,j T̂ kXi
Ai,j n−1

j=1

= n−1/2
= n−1/2

n
X

l=1
n
X

n
X

k(Xi , Xl )kXl

l=1

n−1

n
X

−1
k(Xl , Xi )Ai,j Dj,j

i=1

!

kXl

Al,j kXl

l=1

= Dj,j fj ,

so fj is an eigenvector of T̂ with eigenvalue Dj,j > 0. Furthermore,
−1 −1/2
fj (Xi ) = Dj,j
n

n
X

Al,j k(Xl , Xi )

l=1

= n−1/2

n
X

−1
k(Xi , Xl )Al,j Dj,j

l=1

=n

1/2

Ai,j .

Since A is orthogonal, we find that the fj for 1 ≤ j ≤ rk(n−1 K) are orthonormal in L2 (Pn ).
Hence,
rk(n−1 K) ≤ rk T̂ = m.
Combining this with m ≤ rk(n−1 K), we find that rk T̂ = m = rk(n−1 K). Furthermore, we
have
m
X
hf, fj iL2 (Pn ) fj + Qf
f=
j=1

for all f ∈ H because the fj form a basis of sp{kXi : 1 ≤ i ≤ n} which is orthonormal in
L2 (Pn ).
A.2 Correspondence Between T̂ and n−1 K
We have shown a bijection between sets of eigenvalues and eigenvectors of T̂ and n−1 K. Let
êj be eigenvectors of T̂ for 1 ≤ j ≤ m which are orthonormal in L2 (Pn ) with non-increasing
32

Ivanov-Regularised Estimators over RKHSs

eigenvalues λ̂j and

m
X
hf, êj iL2 (Pn ) êj + Qf
f=
j=1

for all f ∈ H. Also, let
n−1 K = ADAT
where A is an orthogonal matrix and D is a diagonal matrix with non-increasing nonnegative entries, rk(n−1 K) of which are non-zero. Then the bijection is given by rk(n−1 K) =
m, Dj,j = λ̂j for 1 ≤ j ≤ m and
Ai,j = n−1/2 êj (Xi )
for 1 ≤ i ≤ n and
−1/2
êj = λ̂−1
j n

n
X

Ai,j kXi .

i=1

By Lemma 4.25 of Steinwart and Christmann (2008), the function Φ : S → H by Φ(x) = kx
is a (H, B(H))-valued measurable function on (S, S). Hence, kXi is a (H, B(H))-valued
random variable on (Ω, F) for 1 ≤ i ≤ n. This means that the êj being (H, B(H))-valued
random variables and the λ̂j and m being random variables on (Ω, F) is equivalent to
Q, D and rk(n−1 K) being measurable on (Ω, F). Quintana and Rodrı́guez (2014) show
that a strictly-positive-definite matrix which is measurable on (Ω, F) can be diagonalised
by an orthogonal matrix and a diagonal matrix which are both measurable on (Ω, F).
The result holds for non-negative-definite matrices by adding the identity matrix before
diagonalisation. Hence, the non-negative definite matrix n−1 K, which is measurable on
(Ω, F), can be diagonalised in such a way that A, D and rk(n−1 K) are measurable on
(Ω, F). It follows that for this diagonalisation of n−1 K, the êj are (H, B(H))-valued random
variables and the λ̂j and m are random variables on (Ω, F). We choose the above quantities
so that they satisfy these measurability conditions. We collect the key results from this
appendix in one lemma.
Lemma 20 There exist eigenvectors êj of T̂ for 1 ≤ j ≤ m which are orthonormal in
L2 (Pn ) and (H, B(H))-valued random variables on (Ω, F) with non-increasing eigenvalues
λ̂j which are random variables on (Ω, F), as is m, such that
f=

m
X
hf, êj iL2 (Pn ) êj + Qf
j=1

for all f ∈ H. Here, Q is the orthogonal projection of H onto
Z = {f ∈ H : kf kL2 (Pn ) = 0}
with Z ⊥ = sp{kXi : 1 ≤ i ≤ n} and T̂ : H → H is the integral operator
n

T̂ f =

1X
f (Xi )kXi .
n
i=1

33

Page and Grünewälder

Let
n−1 K = ADAT
where A is an orthogonal matrix and D is a diagonal matrix with non-increasing entries
which are both measurable on (Ω, F). Such a diagonalisation exists. Then m = rk(n−1 K)
and λ̂j = Dj,j for 1 ≤ j ≤ m and we can choose
êj =

−1/2
λ̂−1
j n

n
X

Ai,j kXi .

i=1

Appendix B. Estimator Calculation and Measurability
We will now look at how to calculate ĥr . Lemma 20 shows that any f ∈ H can be represented
as
m
X
hf, êj iL2 (Pn ) êj + Qf,
f=
j=1

where the projection Q : H → Z is orthogonal with respect to the inner product on H and
Z = {f ∈ H : kf kL2 (Pn ) = 0},
with Z ⊥ = sp{kXi : 1 ≤ i ≤ n}. The êj ∈ H for 1 ≤ j ≤ m are orthonormal in L2 (Pn ) and
orthogonal in H with kêj k2H = λ̂−1
j for λ̂j > 0 non-increasing. They are also eigenvectors
of the integral operator T̂ : H → H by
n

T̂ f =

1X
f (Xi )kXi ,
n
i=1

with corresponding eigenvalues λ̂j . Let K be the n × n matrix with Ki,j = k(Xi , Xj ), E
be the n × m matrix with Ei,j = n−1/2 êj (Xi ) and Λ be the m × m diagonal matrix with
Λj,j = λ̂j . The columns of E are eigenvectors of n−1 K with eigenvalues found in Λ and
E T E = I.
We have


2
n
m
X
X
1
 hf, êj iL2 (P ) êj (Xi ) − Yi  .
ĥr = arg min
n
f ∈rBH n
i=1

j=1

Let aj = hf, êj iL2 (Pn ) for 1 ≤ j ≤ m. Then

kf k2H = aT Λ−1 a + kQf k2H
and
ĥr = arg min(Ea − n−1/2 Y )T (Ea − n−1/2 Y ),
f ∈rBH

so we will let Qf = 0. We can then write the norm constraint as
aT Λ−1 a + s = r 2
34

Ivanov-Regularised Estimators over RKHSs

where s ≥ 0 is a slack variable. The Lagrangian of this problem can be written as
L(a, s; µ) = (Ea − n−1/2 Y )T (Ea − n−1/2 Y ) + µ(aT Λ−1 a + s − r 2 )
= aT (I + µΛ−1 )a − 2n−1/2 Y T Ea + µs + n−1 Y T Y − µr 2
where µ is the Lagrangian multiplier for the norm constraint. We seek to minimise the
Lagrangian for a fixed value of µ. Note that we require µ ≥ 0 for the Lagrangian to have a
finite minimum due to the term in s. We have
∂L
= 2(I + µΛ−1 )a − 2n−1/2 E T Y,
∂a
so the minimising value of a is given by
a = n−1/2 (I + µΛ−1 )−1 E T Y.
We now search for a value of µ such that a and s satisfy the norm constraint. We will call
this value µ(r). There are two cases. If
r 2 ≤ n−1 Y T EΛ−1 E T Y,
then
a = n−1/2 (I + µ(r)Λ−1 )−1 E T Y, s = 0
minimises L for µ = µ(r) ≥ 0 and satisfies the norm constraint, where µ(r) satisfies
n−1 Y T E(I + µ(r)Λ−1 )−1 Λ−1 (I + µ(r)Λ−1 )−1 E T Y = r 2 .
Otherwise,
a = n−1/2 E T Y, s = r 2 − n−1 Y T EΛ−1 E T Y
minimises L for µ = µ(r) = 0 and satisfies the norm constraint. Hence, the Lagrangian
sufficiency theorem shows
ĥr = n

−1/2

m
X
j=1

λ̂j
λ̂j + µ(r)

(E T Y )j êj

for r > 0. We also have ĥ0 = 0.
Since µ(r) is strictly decreasing for
r 2 ≤ n−1 Y T EΛ−1 E T Y,
we find
{µ(r) ≤ µ} = {n−1 Y T E(I + µΛ−1 )−1 Λ−1 (I + µΛ−1 )−1 E T Y ≤ r 2 }
for µ ∈ [0, ∞). So µ(r) is measurable on (Ω × [0, ∞), F ⊗ B([0, ∞))), where r varies in
[0, ∞). Hence, ĥr is a (H, B(H))-valued measurable function on (Ω × [0, ∞), F ⊗ B([0, ∞))),
where r varies in [0, ∞).
35

Page and Grünewälder

To calculate µ(r), we first use that µ(r) = 0 if
r ≥ (n−1 Y T EΛ−1 E T Y )1/2 .
Otherwise, µ(r) > 0 and
r 2 = n−1 Y T E(I + µ(r)Λ−1 )−1 Λ−1 (I + µ(r)Λ−1 )−1 E T Y
≤ n−1 Y T EΛE T Y µ(r)−2 .
Hence,
µ(r) ≤ (n−1 Y T EΛE T Y )1/2 r −1 .
Since µ(r) is strictly decreasing when µ(r) > 0, we can use interval bisection to calculate
µ(r) for a fixed r > 0 to within a given tolerance.
B.1 Large n
When n is large, it may be quicker to avoid diagonalising n−1 K and to instead solve a
system of n linear equations at each iteration of interval bisection. As noted above, we
restrict our search for the estimator
n

ĥr = arg min
f ∈rBH

to Z ⊥ = sp{kXi : 1 ≤ i ≤ n}. Let
f=

1X
(f (Xi ) − Yi )2
n
i=1

n
X

bj kXj

j=1

for b ∈ Rn . The Lagrangian can be written as

L(b, s; µ) = n−1 (Kb − Y )T (Kb − Y ) + µ(bT Kb + s − r 2 )
= bT (n−1 K 2 + µK)b − 2n−1 Y T Kb + µs + n−1 Y T Y − µr 2 .
We have

∂L
= 2(n−1 K 2 + µK)b − 2n−1 KY.
∂b
This being 0 is equivalent to
b = (K + nµI)−1 Y + w
for some w ∈ ker K. However, the same f is produced for all w ∈ ker K because the squared
H norm of
n
X
wj kXj ,
j=1

is

wT Kw

= 0, so we are free to take w = 0. The solution to the problem is given by
b = (K + nµ(r)I)−1 Y
36

Ivanov-Regularised Estimators over RKHSs

when µ(r) > 0 or µ(r) = 0 and K is invertible, where µ(r) is the same as above.
To calculate µ(r), note that if µ(r) > 0 then
r 2 = Y T (K + nµ(r)I)−1 K(K + nµ(r)I)−1 Y
≤ n−2 Y T KY µ(r)−2 .
Hence,
µ(r) ≤ n−1 (Y T KY )1/2 r −1 .
Since µ(r) is strictly decreasing when µ(r) > 0, we can use interval bisection to calculate
µ(r) for a fixed r > 0 to within a given tolerance. When K is invertible, we can also use
that µ(r) = 0 if
r ≥ (Y T K −1 Y )1/2 .
We summarise the calculation of ĥr in the following lemma.
Lemma 21 We have
ĥr = n−1/2

m
X
j=1

λ̂j
λ̂j + µ(r)

(E T Y )j êj

for r > 0 and ĥ0 = 0. If
r 2 ≤ n−1 Y T EΛ−1 E T Y,
then µ(r) ≥ 0 satisfies
n−1 Y T E(I + µ(r)Λ−1 )−1 Λ−1 (I + µ(r)Λ−1 )−1 E T Y = r 2 .
Otherwise, µ(r) = 0. We have that µ(r) is strictly decreasing when µ(r) > 0, and µ(r) is
measurable and ĥr is a (H, B(H))-valued measurable function on (Ω×[0, ∞), F ⊗B([0, ∞))),
where r varies in [0, ∞).
When µ(r) > 0 or µ(r) = 0 and K is invertible, we have
n
X
((K + nµ(r)I)−1 Y )j kXj .
ĥr =
j=1

If µ(r) > 0, then
Y T (K + nµ(r)I)−1 K(K + nµ(r)I)−1 Y = r 2 .
When K is invertible, µ(r) = 0 if
r 2 ≥ Y T K −1 Y.
37

Page and Grünewälder

B.2 Continuity
We will prove a continuity result about our estimator.
Lemma 22 Let r, s ∈ [0, ∞). We have
kĥr − ĥs k2H ≤ |r 2 − s2 |.
Proof Let s > r. If r > 0 then
hĥr , ĥs iH = n

−1

≥ n−1

m
X

j=1
m
X
j=1

λ̂j
(λ̂j + µ(r))(λ̂j + µ(s))
λ̂j
(λ̂j + µ(r))2

(E T Y )2j

(E T Y )2j

= kĥr k2H .

Furthermore, if µ(r) > 0 then kĥr k2H = r 2 and
kĥr − ĥs k2H = kĥr k2H + kĥs k2H − 2hĥr , ĥs iH
≤ kĥs k2H − kĥr k2H
= kĥs k2H − r 2
≤ s2 − r 2 .
Otherwise, µ(r) = 0 and so µ(s) = 0, which means ĥr = ĥs . If r = 0 then ĥr = 0 and
kĥr − ĥs k2H = kĥs k2H ≤ s2 .
Hence, whenever r < s we have
kĥr − ĥs k2H ≤ s2 − r 2 .
The result follows.

B.3 Validation
We also have the estimator r̂ of r0 when performing validation.
Lemma 23 We have that r̂ is a random variable on (Ω, F).
Proof Let

ñ

W (s) =

1X
(V ĥs (X̃i ) − Ỹi )2
ñ
i=1

38

Ivanov-Regularised Estimators over RKHSs

for s ∈ R. Note that W (s) is a random variable on (Ω, F) and continuous in s by Lemma
22. Since R ⊆ R, it is separable. Let R0 be a countable dense subset of R. Then
inf W (s) = inf W (s)

s∈R

s∈R0

is a random variable on (Ω, F) as the right-hand side is the infimum of countably many
random variables on (Ω, F). Let r ∈ [0, ρ]. By the definition of r̂, we have
[
{r̂ ≤ r} =
{W (s) ≤ inf W (t)}.
s∈R∩[0,r]

t∈R

Since R ∩ [0, r] ⊆ R, it is separable. Let Ar be a countable dense subset of R ∩ [0, r]. By
the sequential compactness of R ∩ [0, r] and continuity of W (s), we have
\ [
{W (s) ≤ inf W (t) + a−1 }.
{r̂ ≤ r} =
t∈R

a∈N s∈Ar

This set is an element of F.

Appendix C. Subgaussian Random Variables
The following result is Lemma 2.3.1 from Giné and Nickl (2016).
Lemma 24 Let U and V be random variables. If kU kψ2 < ∞ and E U = 0, then U is
6kU k2ψ2 -subgaussian. If U is σ 2 -subgaussian, then kU k2ψ2 ≤ 6σ 2 . If kU |V kψ2 < ∞ and
E(U |V ) = 0, then U is 6kU |V k2ψ2 -subgaussian given V . If U is σ 2 -subgaussian given V ,
then kU |V k2ψ2 ≤ 6σ 2 .
The following result relates a quadratic form of subgaussians to that of centred normal
random variables.
Lemma 25 Let εi for 1 ≤ i ≤ n be random variables on (Ω, F, P) which are independent
conditional on some sub-σ-algebra G ⊆ F and let
E(exp(tεi )|G) ≤ exp(σ 2 t2 /2)
for all t ∈ R. Also, let δi for 1 ≤ i ≤ n be random variables on (Ω, F, P) which are
independent of each other and G with δi ∼ N(0, σ 2 ). If A is an n × n non-negative-definite
matrix which is measurable on (Ω, G), then
E(exp(tεT Aε)|G) ≤ E(exp(tδT Aδ)|G)
for all t ≥ 0.
Proof This proof method uses techniques from the proof of Lemma 9 of Abbasi-Yadkori, Pál, and Szepesvári
(2011). We have
E(exp(ti εi /σ)|G) ≤ exp(t2i /2)
39

Page and Grünewälder

for all 1 ≤ i ≤ n and ti ∈ R. Furthermore, the εi are independent conditional on G, so
E(exp(tT ε/σ)|G) ≤ exp(ktk22 /2).
Quintana and Rodrı́guez (2014) show that a strictly-positive-definite matrix which is measurable on (Ω, G) can be diagonalised by an orthogonal matrix and a diagonal matrix which
are both measurable on (Ω, G). The result holds for non-negative-definite matrices by
adding the identity matrix before diagonalisation, so let A have the square root A1/2 which
is measurable on (Ω, G). We can then replace t with sA1/2 u for s ∈ R and u ∈ Rn to get
E(exp(suT A1/2 ε/σ)|G) ≤ exp(s2 kA1/2 uk22 /2).
Integrating over u with respect to the distribution of δ gives
E(exp(s2 εT Aε/2)|G) ≤ E(exp(s2 δT Aδ/2)|G).
The result follows.
Having established this relationship, we can now obtain a probability bound on a quadratic
form of subgaussians by using Chernoff bounding. The following is a conditional subgaussian
version of the Hanson–Wright inequality. It is similar to Theorem 2.1 of Hsu, Kakade, and Zhang
(2012). All probabilities mentioned will be taken with respect to P on (Ω, F) unless otherwise stated.
Lemma 26 Let εi for 1 ≤ i ≤ n be random variables on (Ω, F, P) which are independent
conditional on some sub-σ-algebra G ⊆ F and let
E(exp(tεi )|G) ≤ exp(σ 2 t2 /2)
for all t ∈ R. If A is an n × n non-negative-definite matrix which is measurable on (Ω, G)
and t ≥ 0, then
εT Aε ≤ σ 2 tr(A) + 2σ 2 kAkt + 2σ 2 (kAk2 t2 + tr(A2 )t)1/2
with probability at least 1 − e−t conditional on G. Here, kAk is the operator norm of A,
which is measurable on (Ω, G).
Proof This proof method follows that of Theorem 3.1.9 of Giné and Nickl (2016). Quintana and Rodrı́guez
(2014) show that a strictly-positive-definite matrix which is measurable on (Ω, G) can be
diagonalised by an orthogonal matrix and a diagonal matrix which are both measurable on
(Ω, G). The result holds for non-negative-definite matrices by adding the identity matrix
before diagonalisation, so let
A = QDQT ,
where Q is an n × n orthogonal matrix and D is an n × n diagonal matrix with non-negative
entries which are both measurable on (Ω, G). Also, let δi for 1 ≤ i ≤ n be random variables
on (Ω, F, P) which are independent of each other and G, with δi ∼ N(0, σ 2 ). Then, by
Lemma 25 and the fact that QT δ has the same distribution as δ, we have
E(exp(tεT Aε)|G) ≤ E(exp(tδT Aδ)|G) = E(exp(tδT Dδ)|G)
40

Ivanov-Regularised Estimators over RKHSs

for all t ≥ 0. Furthermore,
E(exp(tδi2 /σ 2 ))

=

Z

∞
−∞

1
1
exp(tx2 − x2 /2)dx =
,
1/2
(2π)
(1 − 2t)1/2

so
E(exp(t(δi2 /σ 2 − 1))) = exp(−(log(1 − 2t) + 2t)/2).
We have
−2(log(1 − 2t) + 2t) ≤

∞
X
(2t)i (2/i) ≤ 4t2 /(1 − 2t)
i=2

for 0 ≤ t ≤ 1/2. Therefore,

E(exp(tDi,i (δi2 − σ 2 ))|G) ≤ exp

2 t2
σ 4 Di,i
1 − 2σ 2 Di,i t

!

for 0 ≤ t ≤ 1/(2σ 2 Di,i ) and 1 ≤ i ≤ n, and
T

2

E(exp(t(δ Dδ − σ tr(D)))|G) ≤ exp



σ 4 tr(D 2 )t2
1 − 2σ 2 (maxi Di,i )t

for 0 ≤ t ≤ 1/(2σ 2 (maxi Di,i )). By Chernoff bounding, we have
εT Aε − σ 2 tr(A) > s
for s ≥ 0 with probability at most
exp



σ 4 tr(A2 )t2
− ts
1 − 2σ 2 kAkt



conditional on G for 0 ≤ t ≤ 1/(2σ 2 kAk). Letting
t=
gives the bound

Rearranging gives the result.

2σ 4

tr(A2 )

s
+ 2σ 2 kAks

s2
exp − 4
4σ tr(A2 ) + 4σ 2 kAks




.

Appendix D. Covering Numbers
The following result gives a bound on the covering numbers of F .
Lemma 27 From Lemma 22, we have
N (F, k·k∞ , ε) ≤ 1 +
41

kkk2∞ ρ2
.
2ε2



Page and Grünewälder

Proof Let a ∈ N and ri ∈ R and fi = V ĥri ∈ F for 1 ≤ i ≤ a. Also, let f = V ĥr ∈ F for
r ∈ R. Since V is a contraction,
kĥr − ĥri k∞ ≤ ε =⇒ kf − fi k∞ ≤ ε.
Lemma 22 shows
|r 2 − ri2 | ≤ ε2 /kkk2∞ =⇒ kĥr − ĥri k∞ ≤ ε.
Hence, if we let
ri2 = ε2 (2i − 1)/kkk2∞
and
ρ2 − ε2 (2a − 1)/kkk2∞ ≤ ε2 /kkk2∞ ,
then we find N (F, k·k∞ , ε) ≤ a. Rearranging the above shows that we can choose
kkk2∞ ρ2
a=
2ε2




and the result follows.
We will also calculate integrals of these covering numbers.
Lemma 28 Let a ≥ 1. From Lemma 27, we have
Z

L

1/2

(log(aN (F, k·k∞ , ε)))

dε ≤

0



log



kkk2∞ ρ2
1+
2L2

 1/2
 π 1/2
L+
L
a
2

for L ∈ (0, ∞). When a = 1, we have
Z

L

1/2

(log(N (F, k·k∞ , ε)))
0

kkk2∞ ρ2
dε ≤ 2 log 1 +
8C 2




1/2

C + (2π)1/2 C

for L ∈ (0, ∞].
Proof Let L ∈ (0, ∞). Then
Z

L

(log(aN (F, k·k∞ , ε)))1/2 dε ≤

0

Z

0

L

 
1/2
kkk2∞ ρ2
log a 1 +
dε
2ε2

by Lemma 27. Changing variables to u = ε/L gives
 
1/2
kkk2∞ ρ2
L
log a 1 +
du
2L2 u2
0
 1/2
Z 1  
kkk2∞ ρ2 1
≤L
log a 1 +
du
2L2
u2
0

 1/2
Z 1  
1
kkk2∞ ρ2
du.
+ log
=L
log a 1 +
2
2
2L
u
0
Z

1

42

Ivanov-Regularised Estimators over RKHSs

For a, b ≥ 0 we have (a + b)1/2 ≤ a1/2 + b1/2 , so the above is at most
 
1/2
Z 1   1/2
1
kkk2∞ ρ2
L
du + L
du
log a 1 +
log
2
2L
u2
0
0
  
1/2
Z 1   1/2
1
kkk2∞ ρ2
= L log a 1 +
+L
du.
log
2
2L2
u
0
Z

1

Changing variables to
s=
shows
Z

0

1

log



1
u2



1/2

log



du =
=

1
u2

Z

1/2

∞

s2 exp(−s2 /2)ds
0

1
2

Z

∞

s2 exp(−s2 /2)ds

−∞

(2π)1/2
=
2
 π 1/2
,
=
2

since the last integral is a multiple of the variance of a N(0, 1) random variable. The first
result follows. Note that N (F, k·k∞ , ε) = 1 whenever ε ≥ 2C, as the ball of radius 2C about
any point in F is the whole of F . Hence, when a = 1, we have
Z ∞
Z L
1/2
(log(N (F, k·k∞ , ε)))1/2 dε
(log(N (F, k·k∞ , ε))) dε ≤
0
0
Z 2C
(log(N (F, k·k∞ , ε)))1/2 dε
=
0

kkk2∞ ρ2
≤ 2 log 1 +
8C 2




1/2

C + (2π)1/2 C

for L ∈ (0, ∞].

References
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear
stochastic bandits. In Proceedings of the 24th International Conference on Neural Information Processing Systems, pages 2312–2320, 2011.
Béla Bollobás. Linear Analysis. Cambridge University Press, second edition, 1999.
Andrea Caponnetto and Ernesto de Vito. Optimal rates for the regularized least-squares
algorithm. Foundations of Computational Mathematics, 7(3):331–368, 2007.
43

Page and Grünewälder

Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamonjy. Joint distribution optimal transportation for domain adaptation. arXiv preprint arXiv:1705.08848,
2017.
Simon Fischer and Ingo Steinwart. Sobolev norm learning rates for regularized least-squares
algorithm. arXiv preprint arXiv:1702.07254, 2017.
Evarist Giné and Richard Nickl. Mathematical Foundations of Infinite-Dimensional Statistical Models. Cambridge University Press, 2016.
Daniel Hsu, Sham M. Kakade, and Tong Zhang. A tail inequality for quadratic forms of
subgaussian random vectors. Electronic Communications in Probability, 17(52):1–6, 2012.
Shahar Mendelson and Joseph Neeman. Regularization in kernel learning. The Annals of
Statistics, 38(1):526–565, 2010.
Luca Oneto, Sandro Ridella, and Davide Anguita. Tikhonov, Ivanov and Morozov regularization for support vector machine learning. Machine Learning, 103(1):103–136, 2016.
Yamilet Quintana and José M. Rodrı́guez. Measurable diagonalization of positive definite
matrices. Journal of Approximation Theory, 185:91–97, 2014.
Steve Smale and Ding-Xuan Zhou. Estimating the approximation error in learning theory.
Analysis and Applications, 1(1):17–41, 2003.
Bharath Sriperumbudur. On the optimal estimation of probability measures in weak and
strong topologies. Bernoulli, 22(3):1839–1893, 2016.
Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer New York,
2008.
Ingo Steinwart and Clint Scovel. Mercer’s theorem on general domains: On the interaction
between measures, kernels, and RKHSs. Constructive Approximation, 35(3):363–417,
2012.
Ingo Steinwart, Don R. Hush, and Clint Scovel. Optimal rates for regularized least squares
regression. In The 22nd Conference on Learning Theory, 2009.
Aad W. van der Vaart and Jon A. Wellner. Weak Convergence and Empirical Processes:
With Applications to Statistics. Springer New York, 2013.
David Williams. Probability with martingales. Cambridge University Press, 1991.

44

