The LIL for U -statistics in Hilbert spaces
Rados law Adamczak∗ Rafa l Lata la†
November 13, 2018
Abstract
We give necessary and sufficient conditions for the (bounded) law
of the iterated logarithm for U -statistics in Hilbert spaces. As a tool
we also develop moment and tail estimates for canonical Hilbert-space
valued U -statistics of arbitrary order, which are of independent inter-
Keywords: U -statistics, law of the iterated logarithm, tail and moment
estimates.
AMS 2000 Subject Classification: Primary: 60F15, Secondary: 60E15
1 Introduction
In the last two decades we have witnessed a rapid development in the asymp-
totic theory of U -statistics, boosted by the introduction of the so called
’decoupling’ techniques (see [5, 6, 7]), which allow to treat U -statistics con-
ditionally as sums of independent random variables. This approach yielded
better understanding of U -statistics versions of the classical limit theorems
of probability. Necessary and sufficient conditions were found for the strong
law of large numbers [17], the central limit theorem [19, 10] and the law
of the iterated logarithm [11, 2]. Also some sharp exponential inequalities
for canonical U -statistics have been found [8, 1, 14]. Analysis of the afore-
mentioned results shows an interesting phenomenon. Namely, the natural
counterparts of the necessary and sufficient conditions for sums of i.i.d. ran-
dom variables (U -statistics of degree 1), remain sufficient for U -statistics
Institute of Mathematics, Polish Academy of Sciences, Warsaw, Poland. Email:
R.Adamczak@impan.gov.pl. Research partially supported by MEiN Grant 2 PO3A 019
†Institute of Mathematics, Warsaw University, Warsaw, Poland. Email:
RLatala@mimuw.edu.pl. Research partially supported by MEiN Grant 1 PO3A 012 29.
http://arxiv.org/abs/0704.1643v1
of arbitrary degree, but with an exception for the CLT, they cease to be
necessary. The correct conditions turn out to be much more involved and
are expressed for instance in terms of convergence of some series (LLN) or
as growth conditions for some functions (LIL).
A natural problem is an extension of the above results to the infinite-
dimensional setting. There has been some progress in this direction, and
partial answers have been found, usually under the assumption on the geo-
metrical structure of the space in which the values of a U -statistic are taken.
In general however the picture is far from being complete and the necessary
and sufficient conditions are known only in the case of the CLT for Hilbert
space valued U -statistics (see [5, 10] for the proof of sufficiency in type 2
spaces and necessity in cotype 2 spaces respectively).
In this article we generalize to separable Hilbert spaces the results from
[2] on necessary and sufficient conditions for the LIL for real valued U -
statistics. The conditions are expressed only in terms of the U -statistic
kernel and the distribution of the underlying i.i.d. sequence and can be also
considered a generalization of results from [13], where the LIL for i.i.d. sums
in Hilbert spaces was characterized. We consider only the bounded version
of the LIL and do not give the exact value of the lim sup nor determine the
limiting set. Except for the classical case of sums of i.i.d. random variables,
the problem of finding the lim sup is at the moment open even in the one
dimensional case (see [3, 5, 15] for some partial results) and the problem of
the geometry of the limiting set and the compact LIL is solved only under
suboptimal integrability conditions [3].
The organization of the paper is as follows. First, in Section 3 we prove
sharp exponential inequalities for canonical U -statistics, which generalize
the results of [1, 8] for the real-valued case. Then, after recalling some
basic facts about the LIL we give necessary and sufficient condition for the
LIL for decoupled, canonical U -statistics (Theorem 2). The quite involved
proof is given in the two subsequent sections. Finally we conclude with
our main result (Theorem 4), which gives a characterization of the LIL for
undecoupled U -statistics and follows quite easily from Theorem 2 and the
one dimensional result.
2 Notation
For an integer d, let (Xi)i∈N, (X
i )i∈N,1≤k≤d be independent random vari-
ables with values in a Polish space Σ, equipped with the Borel σ-field F .
Let also (εi)i∈N, (ε
i )i∈N,1≤k≤d be independent Rademacher variables, in-
dependent of (Xi)i∈N, (X
i )i∈N,1≤k≤d.
Consider moreover measurable functions hi : Σ
d → H, where (H, | · |) is a
separable Hilbert space (we will denote both the norm in H and the absolute
value of a real number by | · |, the context will however prevent ambiguity).
To shorten the notation, we will use the following convention. For i =
(i1, . . . , id) ∈ {1, . . . , n}d we will write Xi (resp. Xdeci ) for (Xi1 , . . . ,Xid),
(resp. (X
, . . . ,X
)) and ǫi (resp. ǫ
i ) for the product εi1 · . . . · εid (resp.
· . . . · ε(d)id ), the notation being thus slightly inconsistent, which however
should not lead to a misunderstanding. The U -statistics will therefore be
denoted
i∈Idn
hi(Xi) (an undecoupled U -statistic)
|i|≤n
i ) (a decoupled U -statistic)
i∈Idn
ǫihi(Xi) (an undecoupled randomized U -statistic)
|i|≤n
ǫdeci hi(X
i ) (a decoupled randomized U -statistic),
where
|i| = max
k=1,...,d
Idn = {i : |i| ≤ n, ij 6= ik for j 6= k}.
Since in this notation {1, . . . , d} = I1d we will write
Id = {1, 2, . . . , d}.
Throughout the article we will write Ld, L to denote constants depending
only on d and universal constants respectively. In all those cases the values
of a constant may differ at each occurrence.
For I ⊆ Id, we will write EI to denote integration with respect to vari-
ables (X
i )i∈N,j∈I . We will consider mainly canonical (or completely de-
generated) kernels, i.e. kernels hi, such that for all j ∈ Id, Ejhi(Xdeci ) = 0
3 Moment inequalities for U-statistics in Hilbert
space
In this section we will present sharp moment and tail inequalities for Hilbert
space valued U -statistics, which in the sequel will constitute an important
ingredient in the analysis of the LIL. These estimates are a natural general-
ization of inequalities for real valued U-statistics presented in [1].
Let us first introduce some definitions.
Definition 1. For a nonempty, finite set I let PI be the family consisting of
all partitions J = {J1, . . . , Jk} of I into nonempty, pairwise disjoint subsets.
Let us also define for J as above deg(J ) = k. Additionally let P∅ = {∅}
with deg(∅) = 0.
Definition 2. For a nonempty set I ⊆ Id consider J = {J1, . . . , Jk} ∈ PI .
For an array (hi)i∈Idn of H-valued kernels and fixed value of iI
c, define
‖(hi)iI‖J = sup
EI [hi(X
deg(J )
(XdeciJj
: ΣJj → R
|f (j)iJj (X
)|2 ≤ 1 for j = 1, . . . ,deg(J )
Let moreover ‖(hi)i∅‖∅ = |hi|.
Remark It is worth mentioning that for I = Id, ‖ · ‖J is a deterministic
norm, whereas for I ( Id it is a random variable, depending on X
Quantities given by the above definition suffice to obtain precise moment
estimates for real valued U -statistics. However, to bound the moments of
U -statistics with values in general Hilbert spaces, we will need to introduce
one more definition.
Definition 3. For nonempty sets K ⊆ I ⊆ Id consider J = {J1, . . . , Jk} ∈
PI\K . For an array (hi)i∈Idn of H-valued kernels and fixed value of iIc, define
‖(hi)iI‖K,J = sup
EI [〈hi(Xdeci ), giK (XdeciK )〉
deg(J )
(XdeciJj
)]| :
: ΣJj → R, giK : ΣK → H ,E
|giK (XdeciK )|
2 ≤ 1
|f (j)iJj (X
)|2 ≤ 1 for j = 1, . . . ,deg(J )
Remark One can see that the only difference between the above definition
and Definition 2 is that the latter distinguishes one set of coordinates and
allows functions corresponding to this set to take values in H. Moreover,
since the norm in H satisfies | · | = sup|φ|≤1〈φ, ·〉, we can treat Definition 2
as a counterpart of Definition 3 for K = ∅. We will use this convention to
simplify the statements of the subsequent theorems. Thus, from now on, we
will write
‖ · ‖∅,J := ‖ · ‖J .
Example For d = 2 and I = {1, 2}, the above definition gives
‖(hij(Xi, Yj))i,j‖∅,{{1,2}} = sup
hij(Xi, Yj)fij(Xi, Yj)
f(Xi, Yj)
2 ≤ 1
= sup
φ∈H,|φ|≤1
〈φ, hij(Xi, Yj)〉2,
‖(hij(Xi, Yj))i,j‖∅,{{1}{2}} = sup
hij(Xi, Yj)fi(Xi)gj(Yj)
Ef(Xi)
Eg(Yj)
2 ≤ 1
‖(hij(Xi, Yj))i,j‖{1},{{2}} = sup
〈fi(Xi), hij(Xi, Yj)〉gj(Yj) :
|f(Xi)|2,E
g(Yj)
2 ≤ 1
‖(hij(Xi, Yj))i,j‖{1,2},∅ = sup
〈fij(Xi, Yj), hij(Xi, Yj)〉 :
|f(Xi, Yj)|2 ≤ 1
E|hij(Xi, Yj)|2.
We can now present the main result of this section.
Theorem 1. For any array of H-valued, completely degenerate kernels (hi)i
and any p ≥ 2, we have
h(Xdeci )
p ≤ Lpd
K⊆I⊆Id
J∈PI\K
pp(#I
c+degJ /2)
EIc max
‖(hi)iI‖
The proof of the above theorem proceeds along the lines of arguments
presented in [1, 8]. In particular we will need the following moment estimates
for suprema of empirical processes [8].
Lemma 1 ([8, Proposition 3.1], see also [4, Theorem 12]). Let X1, . . . ,Xn
be independent random variables with values in (Σ,F) and T be a countable
class of measurable real functions on Σ, such that for all f ∈ T and i ∈
In, Ef(Xi) = 0 and Ef(Xi)
2 < ∞. Consider the random variable S :=
supf∈T |
i f(Xi)|. Then for all p ≥ 1,
ESp ≤ Lp
(ES)p + pp/2σp + ppEmax
|f(Xi)|p
where
σ2 = sup
Ef(Xi)
We will also need the following technical lemma.
Lemma 2 (Lemma 5 in [1]). For α > 0 and arbitrary nonnegative kernels
gi : Σ
d → R+ and p > 1 we have
i ≤ L
pαpEmax
I({1,...,d}
p#IpEI max
EIcgi)
Before stating the next lemma, let us introduce some more definitions,
concerning J –norms of deterministic matrices
Definition 4. Let (ai)i∈Idn be a d-indexed array of real numbers. For J =
{J1, . . . , Jk} ∈ PId define
‖(ai)i‖J = sup
· · · x(k)iJk :
)2 ≤ 1, . . . ,
)2 ≤ 1
We will also need
Definition 5. For i ∈ Nd−1 × In let ai : Σ → R be measurable functions
and Z1, . . . , Zn be independent random variables with values in Σ. For a
partition J = {J1, . . . , Jk} ∈ PId (d ∈ J1), let us define
‖(ai(Zid))i‖J = sup
iId\J1
ai(Zid)x
· · · x(k)iJk
)2 ≤ 1, . . . ,
)2 ≤ 1
Remark All the definitions of norms presented so far, seem quite similar
and indeed they can be all interpreted as injective tensor-product norms on
proper spaces. We have decided to introduce them separately by explicit
formulas, because this form appears in our applications.
The next lemma is crucial for obtaining moment inequalities for canon-
ical real-valued U -statistics of order greater than 2. In the context of U -
statistics in Hilbert spaces we will need it already for d = 2.
Lemma 3 (Theorem 5 in [1]). Let Z1, . . . , Zn be independent random vari-
ables with values in (Σ,F). For i ∈ Nd−1 × In let ai : Σ → R be measurable
functions, such that EZai(Zid) = 0. Then, for all p ≥ 2 we have
ai(Zid))iId−1
‖ ≤ Ld
J∈PId
p(1+deg (J )−d)/2‖(ai(Zid))i‖J
J∈PId−1
p1+(1+deg(J )−d)/2
‖(ai(Zid))iId−1‖
where ‖·‖ denotes the norm of a (d−1)-indexed matrix, regarded as a (d−1)-
linear operator on (l2)
d−1 (thus the ‖ · ‖{1}...{d−1}–norm in our notation).
To prove Theorem 1, we will need to adapt the above lemma to be able
to bound the (K,J )-norms of sums of independent kernels.
Definition 6. We define a partial order ≺ on PI as
I ≺ J
if and only if for all I ∈ I, there exists J ∈ J , such that I ⊆ J .
Lemma 4. Assume that
i E|hi(Xdeci )|2 < ∞. Then for any K ⊆ Id−1 and
J = {J1, . . . , Jk} ∈ PId−1\K and all p ≥ 2,
i ))iId−1
‖K,J (1)
K⊆L⊆Id, K∈PId\L
J∪{K,{d}}≺K∪{L}
p(degK−degJ )/2‖(hi)iId‖L,K
K⊆L⊆Id−1, K∈PId−1\L
J∪{K}≺K∪{L}
p1+(degK−degJ )/2
Edmax
‖(hi)iId−1‖
Remark In the above lemma we slightly abuse the notation, by identifying
for K = ∅ the partition {∅} ∪ J with J .
Given Lemma 3, the proof of Lemma 4 is not complicated, the main idea
is just a change of basis, however due to complicated notation it is quite
difficult to write it directly. We find it more convenient to write the proof
in terms of tensor products of Hilbert spaces.
Let us begin with a classical fact.
Lemma 5. Let H be a separable Hilber space and X a Σ-valued random
variable. Then H ⊗ L2(X) ≃ L2(X,H), where L2(X,H) is the space of
square integrable random variables of the form f(X), f : Σ → H-measurable.
With the above identification, for h ∈ H, f(X) ∈ L2(X), we have h⊗f(X) =
hf(X) ∈ L2(X,H).
Proof of Lemma 4. To avoid problems with notation, which would lengthen
an intuitively easy proof, we will omit some technical details, related to
obvious identification of some tensor product of Hilbert spaces (in the spirit
of Lemma 5). Similarly, when considering linear functionals on a space,
which can be written as a tensor product in several ways, we will switch to
the most convenient notation, without further explanations.
H0 = H ⊗
⊗l∈K (⊕ni=1L2(X
i )] ≃ ⊕|iK |≤nL
2(XdeciK ,H)
and, for j = 1, . . . , k,
Hi = ⊗l∈Jj(⊕ni=1L2(X
i )) ≃ ⊕|iJj |≤nL
2(XdeciJj
In the case K = ∅, we have (using the common convention for empty
products) H0 ≃ H.
For id = 1, . . . , n and fixed value of X
, let Aid be a linear functional on
H̃ = ⊕|iId−1 |≤nL
2(XdeciId−1
,H) ≃ ⊗kj=0Hk, given by (hi(Xdeci ))|iId−1 |≤n ∈ H̃,
with the formula
Aid((giId−1
(XdeciId−1
))iId−1
) = 〈(giId−1 (X
iId−1
))iId−1
, (hi(X
i ))iId−1
|iId−1 |≤n
E{1,...,d−1}〈giId−1 (X
iId−1
), hi(X
i )〉H .
As functions of X
, Aid = Aid(X
) are independent random linear func-
tionals. Thus they determine also random (k + 1)-linear functionals on
⊕kj=0Hk, given by
(h0, h1, . . . , hk) 7→ Aid(h0 ⊗ h1 ⊗ . . .⊗ hk).
If we denote by ‖·‖ the norm of a (k+1)-linear functional, the left hand-side
of (1), can be written as
Aid(X
Moreover, denoting by ‖Aid‖HS the norm of Aid seen as a linear operator on
⊗kj=0Hj (by analogy with the Hilbert-Schmidt norm of a matrix), we have
E‖Aid(X
)‖2HS = ‖(hi)i‖2Id,∅ < ∞,
so the sequence Aid(X
), determines a linear functional A on H̃⊗[⊕nid=1L
⊕|i|≤nL2(Xdeci ,H) ≃ ⊕nid=1L
, H̃), given by the formula
A(g1(X
1 ), . . . , gn(X
n )) =
E[Aid(X
)(gid(X
It is easily seen, that if we interpret the domain of this functional as⊕|i|≤nL2(Xdeci ,H),
then it corresponds to the multimatrix (hi(X
i ))i.
Let us now introduce the following notation, consistent with the defini-
tion of ‖ · ‖J . If T is a linear functional on ⊗mj=0Ej for some Hilbert spaces
Ej , and I = {L1, . . . , Lr} ∈ PIm∪{0}, then let ‖T‖I denote the norm of T
as a r-linear functional on ⊕ri=1[⊗j∈LiEj ], given by
(e1, . . . , er) 7→ T (e1 ⊗ . . .⊗ er).
Now, denotingHk+1 = ⊕nid=1L
), we can apply the above definition
to H̃ ⊗ [⊕nid=1L
)] ≃ ⊗k+1j=0Hj and use Lemma 3 to obtain
Aid(X
∥ ≤Ld
I∈PIk+1∪{0}
p(1+deg (I)−(k+2))/2‖A‖I
I∈PIk∪{0}
p1+(1+deg(I)−(k+2))/2
‖Aid(X
)‖2I .
This inequality is just the statement of the Lemma, which follows from
,,associativity” of the tensor product and its ,,distributivity” with respect
to the simple sum of Hilbert spaces. Indeed, denoting Jk+1 = {d}, we have
for 0 /∈ Li and U =
⊗j∈LiHj ≃ ⊗j∈Li ⊗l∈Jj (⊕ns=1L2(X(l)s )) ≃ ⊗l∈U (⊕ns=1L2(X(l)s )) ≃ ⊕|iU |≤nL
2(XdeciU ).
Similarly, if 0 ∈ Li,
⊗j∈LiHj ≃ [⊕|iK |≤nL
2(XdeciK ,H)]× [⊗06=j∈Li ⊗l∈Jj (⊕
2(X(l)s ))]
≃ ⊕|iU |≤nL
2(XdeciU ,H),
where U = (
06=j∈Li
Jj) ∪ K. Using the fact that for fixed X(d)id , Aid
corresponds to the multimatrix (hi(X
i ))|iId−1 |≤n
, and A corresponds to
(hi(X
i ))|i|≤n, we can see, that each summand ‖ · ‖I on the right hand side
of (2) is equal to some summand ‖ · ‖L,K on the right hand side of (1). In-
formally speaking and abusing slightly the notation (in the case K = ∅), we
,,merge” the elements of the partition {{d}, J1, . . . , Jk,K} or {J1, . . . , Jk,K}
in a way described by the partition I, thus obtaining the partition {L}∪K,
where L is the set corresponding in the new partition to the set Li ∈ I,
containing 0 (in particular, if K = ∅ and {0} ∈ I, then L = ∅). Let us also
notice, that deg(I) = deg(K) + 1, hence
1 + deg(I)− (k + 2) = deg(K)− deg(J ),
which shows, that also the powers of p on the right hand sides of (1) and
(2) are the same, completing the proof.
Proof of Theorem 1. For d = 1, the theorem is an obvious consequence of
Lemma 1. Indeed, since | · | = sup|φ|≤1 |φ(·)|, and we can restrict the supre-
mum to a countable set of functionals, we have
hi(Xi)|p ≤ Lp
hi(Xi)|)p + pp/2 sup
|φ|≤1
E〈φ, hi(Xi)〉2)p/2
+ ppEmax
|hi(Xi)|p
But E|
i hi(Xi)| ≤
i hi(Xi)|2 =
i E|hi(Xi)|2 = ‖(hi)i‖{1},∅
and we also have sup|φ|≤1(
i E〈φ, hi(Xi)〉2)1/2 = ‖(hi)i‖∅,{1} and maxi |hi(Xi)| =
maxi ‖hi‖∅,∅.
We will now proceed by induction with respect to d. Assume that the
theorem is true for all integers smaller than d ≥ 2 and denote Ĩc = Ic\{d}
for I ⊆ Id. Then, applying it for fixed X(d)id to the array of functions
hi(x1, . . . , xd−1,X
)iId−1
, we get by the Fubini theorem
i )|p
K⊆I⊆Id−1
J∈PI\K
pp(#Ĩ
c+degJ /2)
EIc‖(
hi)iI‖
where we have replaced the maxima in iIc by sums (we can afford this
apparent loss, since we will be able to fix it with Lemma 2). Now, from
Lemma 1 (applied to Ed) it follows that
hi)iI‖
K,J ≤ L
(Ed‖(
hi)iI‖K,J )p + pp/2‖(hi)iI∪{d}‖
K,J∪{{d}}
Ed‖(hi)iI‖
Since Ĩc = (I ∪ {d})c, degJ ∪ {{d}} = degJ + 1 and #Ic = #Ĩc + 1,
combining the above inequalities gives
i )|p ≤ L
K⊆I⊆Id
J∈PI\K
pp(#I
c+degJ /2)
‖(hi)iI‖
K⊆I⊆Id−1
J∈PI\K
pp(#Ĩ
c+degJ /2)
(Ed‖(
hi)iI‖K,J )p
By applying Lemma 4 to the second sum on the right hand side, we get
i )|p ≤ L
K⊆I⊆Id
J∈PI\K
pp(#I
c+degJ /2)
‖(hi)iI‖
We can now finish the proof using Lemma 2. We apply it to EIc for
I 6= Id, with #Ic instead of d and p/2 instead of p (for p = 2 the theorem is
trivial, so we can assume that p > 2) and α = 2#Ic + degJ +#Ic. Using
the fact that (p/2)α#I
c ≤ Lpd and E‖(hi)iI‖2K,J ≤
EI |hi|2, we get
‖(hi)iI‖
K,J ≤ p
−αp/2L̃
pαp/2EIc max
‖(hi)iI‖
p#Jp/2EJ max
iIc\J
EIc\J‖(hi)iI‖2K,J
≤ L̄pd
EIc max
‖(hi)iI‖
+ p−(#I
c+degJ /2)p max
EJ max
EJc |h(Xdeci )|2)p/2
EIc max
‖(hi)iI‖
K,J + p
−(#Ic+degJ /2)p max
EJ max
‖(hi)iJc‖
which allows us to replace the sums in iIc on the right-hand side of (3) by
the corresponding maxima, proving the inequality in question.
Theorem 1 gives a precise estimate for moments of canonical Hilbert
space valued U -statistics. In the sequel however we will need a weaker
estimate, using the ‖·‖K,J norms only for I = Id and specialized to the case
hi = h. Before we formulate a proper corollary, let us introduce
Definition 7. Let h : Σd → H be a canonical kernel. Let moreover X1,X2, . . . ,Xd
be i.i.d random variables with values in Σ. Denote X = (X1, . . . ,Xd) and
for J ⊆ Id, XJ = (Xj)j∈J . For K ⊆ I ⊆ Id and J = {J1, . . . , Jk} ∈ PI\K ,
we define
‖h‖K,J = sup
EI〈h(X), g(XK )〉
fj(XJj ) : g : Σ
#K → H, E|g(XK)|2 ≤ 1,
fj : Σ
#Jj → R, Efj(XJj ))2 ≤ 1, j = 1, . . . , k
In other words ‖h‖K,J is the ‖ · ‖K,J of an array (hi)|i|=1, with h(1,...,1) = h.
Remark For I = Id, ‖h‖K,J is a norm, whereas for I ( Id, it is a random
variable, depending on XIc .
It is also easy to see that if all the variables X
i are i.i.d. and for all
|i| ≤ n we have hi = h, then for any fixed value of iIc ,
‖(hi)|iI |≤n‖K,J = ‖h‖K,Jn
#I/2,
where ‖h‖K,J is defined with respect to any i.i.d. sequence X1, . . . ,Xd of
the form Xj = X
for j ∈ Ic.
We also have ‖h‖K,J ≤
EI |h(X)|2, which together with the above
observations allows us to derive the following
Corollary 1. For all p ≥ 2, we have
h(Xdeci )|p ≤L
J∈PId\K
ppdegJ /2ndp/2‖h‖pK,J
pp(d+#I
c)/2n#Ip/2EIc max
(EI |h(Xdeci )|2)p/2
The Chebyshev inequality gives the following corollary for bounded ker-
Corollary 2. If h is bounded, then for all t ≥ 0,
h(Xdeci )| ≥ Ld(nd/2(E|h|2)1/2 + t)
Ld exp
K(Id,J∈PId\K
nd/2‖h‖K,J
)2/deg(J ))
n#I/2‖(EI |h|2)1/2‖∞
)2/(d+#Ic))]
Before we formulate the version of exponential inequalities that will be
useful for the analysis of the LIL, let us recall the classical definition of
Hoeffding projections.
Definition 8. For an integrable kernel h : Σd → H, define πdh : Σk → R
with the formula
πdh(x1, . . . , xk) = (δx1 −P)× (δx2 −P)× . . .× (δxd −P)h,
where P is the law of X1.
Remark It is easy to see that πkh is canonical. Moreover πdh = h iff h is
canonical.
The following Lemma was proven for H = R in [2] (Lemma 1). The
proof given there works for an arbitrary Banach space.
Lemma 6. Consider an arbitrary family of integrable kernels hi : Σ
d → H,
|i| ≤ n. For any p ≥ 1 we have
|i|≤n
πdhi(X
|i|≤n
ǫdeci hi(X
In the sequel we will use exponential inequalities to U -statistics gener-
ated by πdh, where h will be a non-necessarily canonical kernel of order
d. Since the kernel h̃((ε1,X1), . . . , (εd,Xd)) = ε1 · · · εdh(X1, . . . ,Xd), where
εi’s are i.i.d. Rademacher variables independent of Xi’s is always canoni-
cal, Corollary 1, Lemma 6 and the Chebyshev inequality give us also the
following corollary (note that ‖h̃‖K,J = ‖h‖K,J )
Corollary 3. If h is bounded, then for all p ≥ 0,
πdh(X
≥ Ld(nd/2(E|h|2)1/2 + t)
Ld exp
K(Id,J∈PId\K
nd/2‖h‖K,J
)2/ deg(J ))
n#I/2‖(EI |h|2)1/2‖∞
)2/(d+#Ic))]
4 The equivalence of several LIL statements
In this section we will recall general results on the correspondence of various
statements of the LIL. We will state them without proofs, since all of them
have been proven in [9] and [2] in the real case and the proofs can be directly
transferred to the Hilbert space case, with some simple modifications that
we will indicate.
Before we proceed, let us introduce the assumptions and notation com-
mon for the remaining part of the article.
• We assume that (Xi)i∈N, (X(k)i )i∈N,1≤k≤d are i.i.d. and h : Σd → H is
a measurable function.
• Recall that (εi)i∈N, (ε(k)i )i∈N,1≤k≤d are independent Rademacher vari-
ables, independent of (Xi)i∈N, (X
i )i∈N,1≤k≤d.
• To avoid technical problems with small values of h let us also define
LLx = loglog (x ∨ ee).
• We will also occasionally write X for (X1, . . . ,Xd) and for I ⊆ Id,
XI = (Xi)i∈I . Sometimes we will write simply h instead of h(X).
• We will use the letter K to denote constants depending only on the
function h.
We will need the following simple fact
Lemma 7. If E|h|2/(LL|h|)d = K < ∞ then E(|h|2∧u) ≤ L(loglog u)d with
L depending only on K and d.
The next lemma comes from [9]. It is proven there for H = R but the
argument is valid also for general Banach spaces.
Lemma 8. Let h : Σd → H be a symmetric function. There exist constants
Ld, such that if
lim sup
(nloglog n)d/2
i∈Idn
h(Xi)
∣ < C a.s., (4)
|i|≤2n
ǫdeci h(X
∣ ≥ D2nd/2 logd/2 n
< ∞ (5)
for D = LdC.
Lemma 9. For a symmetric function h : Σd → H, the LIL (4) is equivalent
to the decoupled LIL
lim sup
(nloglog n)d/2
i∈Idn
h(Xdeci )
∣ < D a.s., (6)
meaning that (4) implies (6) with D = LdC, and conversely (6) implies (4)
with C = LdD.
Proof. This is Lemma 8 in [2]. The proof is the same as there, one needs only
to replace l∞ with l∞(H) – the space of bounded H-valued sequences.
The next lemma also comes from [2] (Lemma 9). Although stated for real
kernels, its proof relies on an inductive argument with a stronger, Banach-
valued hypothesis.
Lemma 10. There exists a universal constant L < ∞, such that for any
kernel h : Σd → H we have
|j|≤n
i : ik≤jk,k=1...d
h(Xdeci )
∣ ≥ t
≤ LdP
|i|≤n
h(Xdeci )
∣ ≥ t/Ld
Corollary 4. Consider a kernel h : Σd → H and α > 0. If
|i|≤2n
h(Xdeci )| ≥ C2nα logα n) < ∞,
lim sup
(nloglog n)α
|i|≤2n
h(Xdeci )
∣ ≤ Ld,αC a.s.
Proof. Given Lemma 10, the proof is the same as the one for real kernels,
presented in [2] (Corollary 1 therein).
The next lemma shows that the contribution to a decoupled U-statistic
from the ’diagonal’, i.e. from the sum over multiindices i /∈ Idn is negligible.
The proof given in [2] (Lemma 10) is still valid, since the only part which
cannot be directly transferred to the Banach space setting is the estimate of
variance of canonical U-statistics, which is the same in the real and general
Hilbert space case.
Lemma 11. If h : Σd → H is canonical and satisfies
E(|h|2 ∧ u) = O((loglog u)β),
for some β, then
lim sup
(nloglog n)d/2
|i|≤n
∃j 6=kij=ik
h(Xdeci )
∣ = 0 a.s. (7)
Corollary 5. The randomized decoupled LIL
lim sup
(nloglog n)d/2
|i|≤n
ǫdeci h(X
∣ < C (8)
is equivalent to (5), meaning then if (8) holds then so does (5) with D = LdC
and (5) implies (8) with C = LdD.
The proof is the same as for the real-valued case, given in [2] (Corollary
2), one only needs to replace h2 by |h|2 and use the formula for the second
moments in Hilbert spaces.
Corollary 6. For a symmetric, canonical kernel h : Σd → H, the LIL (4)
is equivalent to the decoupled LIL ’with diagonal’
lim sup
(nloglog n)d/2
|i|≤n
h(Xdeci )
∣ < D (9)
again meaning that there are constants Ld such that if (4) holds for some D
then so does (9) for D = LdC, and conversely, (9) implies (4) for C = LdD.
Proof. The proof is the same as in the real case (see [2], Corollary 3). Al-
though the integrability of the kernel guaranteed by the LIL is worse in the
Hilbert space case, it still allows one to use Lemma 11.
5 The canonical decoupled case
Before we formulate the necessary and sufficient conditions for the bounded
LIL in Hilbert spaces, we need
Definition 9. For a canonical kernel h : Σd → H, K ⊆ Id, J = {J1, . . . , Jk} ∈
PId\K and u > 0 we define
‖h‖K,J ,u = sup{E〈h(X), g(XK )〉
fi(XJi) : g : Σ
K → H,
fi : Σ
Ji → R, ‖g‖2, ‖fi‖2 ≤ 1, ‖g‖∞, ‖fi‖∞ ≤ u},
where for K = ∅ by g(XK) we mean an element g ∈ H, and ‖g‖2 denotes
just the norm of g in H (alternatively we may think of g as of a random
variable measurable with respect to σ((Xi)i∈∅), hence constant). Thus the
condition on g becomes in this case just |g| ≤ 1.
Example For d = 2, the above definition reads as
‖h(X1,X2)‖∅,{{1,2}},u = sup{|Eh(X1,X2)f(X1,X2)| :
Ef(X1,X2)
2 ≤ 1, ‖f‖∞ ≤ u},
‖h(X1,X2)‖∅,{{1}{2}},u = sup{|Eh(X1,X2)f(X1)g(X2)| :
Ef(X1)
2,Eg(X2)
2 ≤ 1
‖f‖∞, ‖g‖∞ ≤ u},
‖h(X1,X2)‖{1},{{2}},u = sup{E〈f(X1), h(X1,X2)〉g(X2) :
E|f(X1)|2,Eg(X2)2 ≤ 1
‖f‖∞, ‖g‖∞,≤ u}
‖h(X1,X2)‖{1,2},∅,u = sup{E〈f(X1,X2), h(X1,X2)〉 :
E|f(X1,X2)|2 ≤ 1, ‖f‖∞ ≤ u}.
Theorem 2. Let h be a canonical H-valued symmetric kernel in d variables.
Then the decoupled LIL
lim sup
nd/2(loglog n)d/2
|i|≤n
h(Xdeci )| < C (10)
holds if and only if
(LL|h|)d < ∞ (11)
and for all K ⊆ Id,J ∈ PId\K
lim sup
(loglog u)(d−deg J )/2
‖h‖K,J ,u < D. (12)
More precisely, if (10) holds for some C then (12) is satisfied for D = LdC
and conversely, (11) and (12) implies (10) with C = LdD.
Remark Using Lemma 7 one can easily check that the condition (12) with
D < ∞ for I = Id is implied by (11).
6 Necessity
The proof is a refinement of ideas from [16], used to study random matrix
approximations of the operator norm of kernel integral operators.
Lemma 12. If a, t > 0 and h is a nonnegative d-dimensional kernel such
that NdEh(X) ≥ ta and ‖EIh(X)‖∞ ≤ N−#Ia for all ∅ ⊆ I ( {1, . . . , d},
∀λ∈(0,1) P(
|i|≤N
h(Xdeci ) ≥ λta) ≥ (1−λ)2
t+ 2d − 1 ≥ (1−λ)
22−d min(1, t).
Proof. We have
|i|≤N
h(Xdeci )
|i|≤N
|j|≤N
Eh(Xdeci )h(X
|i|≤N
|j|≤N :
{k : ik=jk}=I
Eh(Xdeci )h(X
|i|≤N
|j|≤N :
{k : ik=jk}=I
E[h(Xdeci )EIch(X
≤ N2d(Eh(X))2 +
∅6=I⊆Id
Nd+#I
Eh(X)‖EIch(X)‖∞
≤ N2d(Eh(X))2 + (2d − 1)NdaEh(X)
≤ N2d(Eh(X))2 + (2d − 1)t−1N2d(Eh(X))2
≤ t+ 2
d − 1
|i|≤n
h(Xdeci )
The lemma follows now from the Paley-Zygmund inequality (see e.g. [5],
Corollary 3.3.2.), which says that for an arbitrary nonnegative random vari-
able S,
P(S ≥ λS) ≥ (1− λ)2 (ES)
Corollary 7. Let A ⊆ Σd be a measurable set, such that
∀∅(I({1,...,d}∀xIc∈ΣIc PI((xIc ,XI) ∈ A) ≤ N
−#I .
P(∃|i|≤N Xdeci ∈ A) ≥ 2−d min(NdP(X ∈ A), 1).
Proof. We apply Lemma 12 with h = IA, a = 1, t = N
dP(X ∈ A) and
λ → 0+.
Lemma 13. Suppose that Zj are nonnegative r.v.’s, p > 0 and aj ∈ R are
such that P(Zj ≥ aj) ≥ p for all j. Then
Zj ≥ p
aj/2) ≥ p/2.
Proof. Let α := P(
j Zj ≥ p
j aj/2), then
aj ≤ E(
min(Zj , aj)) ≤ α
aj + p
aj/2.
Theorem 3. Let Y be a r.v. independent of X
i . Suppose that for each n,
an ∈ R, hn is a d+ 1-dimensional nonnegative kernel such that
|i|≤2n
i , Y ) ≥ an
Let p > 0, then there exists a constant Cd(p) depending only on p and d
such that the sets
An :=
x ∈ Sd : ∀n≤m≤2d−1n PY (hm(x, Y ) ≥ Cd(p)2d(n−m)am) ≥ p
satisfy
2dnP(X ∈ An) < ∞.
Proof. We will show by induction on d, that the assertion holds with C1(p) :=
1, C2(p) := 12/p and
Cd(p) := 12p
−1 max
1≤l≤d−1
Cd−l(2
−l−4p/3) for d = 3, 4, . . . .
For d = 1 we have
min(2nP(X ∈ An), 1) ≤ P(∃|i|≤2n Xdeci ∈ An)
= P(∃|i|≤2n PY (hn(Xdeci , Y ) ≥ an) ≥ p)
≤ P(PY (
|i|≤2n
i , Y ) ≥ an) ≥ p)
≤ p−1P(
|i|≤2n
i , Y ) ≥ an).
Before investigating the case d > 1 let us define
Ãn := An \
The sets Ãn are pairwise disjoint and obviously Ãn ⊂ An. Notice that
since Cd(p) ≥ 1,
P(X ∈ An) ≤ P(PY (hn(X,Y ) ≥ an)) ≤ p−1P(
|i|≤2n
i , Y ) ≥ an).
Hence
n P(X ∈ An) < ∞, so P(X ∈ lim supAn) = 0. But if x /∈
lim supAn, then
ndIAn(x) ≤
nd+1I
(x). So it is enough to show
2dnP(X ∈ Ãn) < ∞.
Induction step Suppose that the statement holds for all d′ < d, we will
show it for d. First we will inductively construct sets
Ãn = A
n ⊃ A1n ⊃ . . . ⊃ Ad−1n
such that for 1 ≤ l ≤ d− 1,
∀∅(I({1,...,d−1}, #I≤l ∀xIc PI((xIc ,XI) ∈ A
n) ≤ 2−n#I (13)
2ndP(X ∈ Al−1n \Aln) < ∞. (14)
Suppose that 1 ≤ l ≤ d − 1 and the set Al−1n was already defined. Let
I ⊂ {1, . . . , d} be such that #I = l and let j ∈ I. Notice that
PI((xIc ,XI) ∈ Al−1n ) = EjPI\{j}((xIc ,Xj ,XI\{j}) ∈ Al−1n ) ≤ 2−n(l−1)
by the property (13) of the set Al−1n . Let us define for n(l− 1)+1 ≤ k ≤ nl,
BIn,k := {xIc : PI((xIc ,XI) ∈ Al−1n ) ∈ (2−k, 2−k+1]}
BIn :=
k=n(l−1)+1
BIn,k = {xIc : PI((xIc ,XI) ∈ Al−1n ) > 2−nl}.
We have
2dnP(X ∈ Al−1n ,XIc ∈ BIn) ≤ 2
k=n(l−1)+1
2dn−kP(XIc ∈ BIn)
= 2EkI1(XIc),
where
kI1(xIc) :=
k=n(l−1)+1
2dn−kIBI
(xIc).
Let m ≥ 1 and
CIm := {xIc : 2(m+1)(d−l) > k1(xIc) ≥ 2m(d−l)}.
Notice that for n > m and k ≤ nl, 2dn−k ≥ 2(d−l)(m+1), moreover
n<m/2
k=n(l−1)+1
2dn−k ≤
n<m/2
2(d−l+1)n ≤ 4
2(d−l+1)(m−1)/2 ≤ 2
2(d−l)m.
Hence
xIc ∈ CIm ⇒
m/2≤n≤m
k=n(l−1)+1
2dn−kIBI
(xIc) ≥
2(d−l)m. (15)
Let m ≤ r ≤ 2d−2m, if m/2 ≤ n ≤ m, then since Al−1n ⊂ An we have for all
x ∈ Sd,
PY (hr(x, Y ) ≥ Cd(p)2d(n−r)arIAl−1n (x)) ≥ p,
therefore, since Al−1n ⊂ Ãn are pairwise disjoint,
hr(x, Y ) ≥ Cd(p)2−drar
m/2≤n≤m
Al−1n
Hence, by Lemma 13,
|iI |≤2r
hr(xIc ,X
, Y ) ≥ p
Cd(p)2
−drar
|iI |≤2r
k2,xIc (X
, (16)
where
k2,xIc (xI) :=
m/2≤n≤m
(xIc , xI).
We have ‖k2,xIc‖∞ ≤ 2dm and for ∅ 6= J ( I, by the property (13) of
Al−1n ,
EJk2,xIc (xI\J ,XJ ) =
m/2≤n≤m
2dnPJ
(xIc , xI\J ,XJ) ∈ Al−1n
m/2≤n≤m
2(d−#J)n ≤ 2(d−#J)m+1.
Moreover for xIc ∈ CIm, by the definition of BIn,k and (15),
Ek2,xIc (XI) ≥
m/2≤n≤m
k=n(l−1)+1
2dnPI((xIc ,XI) ∈ Al−1n )IBI
(xIc)
m/2≤n≤m
k=n(l−1)+1
2dn−kIBI
(xIc) ≥
2(d−l)m.
Therefore by Lemma 12 (with l instead of d and a = 2(d−l)m+rl+1, t =
1/6, N = 2r, λ = 1/2), for m ≤ r ≤ 2d−2m,
|iI |≤2r
k2,xIc (X
) ≥ 1
2(d−l)m+rl
2−l−3.
Combining the above estimate with (16) we get (for xIc ∈ CIm and m ≤ r ≤
2d−2m),
|iI |≤2r
hr(xIc ,X
, Y ) ≥ p
Cd(p)2
(d−l)(m−r)ar
2−l−4p.
Let us define Ỹ := ((X
i )j∈I , Y ) and h̃n(xIc , Ỹ ) :=
|iI |≤2n
hn(xIc ,X
, Y ).
|iIc |≤2
h̃n(X
, Ỹ ) ≥ an) =
|i|≤2n
i , Y ) ≥ an) < ∞.
Moreover (since Cd(p) ≥ 12p−1Cd−l(2−l−4p/3)),
CIm ⊆
∀m≤r≤2d−2m PỸ (h̃r(xIc , Ỹ ) ≥ Cd−l(2
−l−4p/3)2(d−l)(m−r)ar) ≥ 2−l−4p/3
Hence by the induction assumption,
2(d−l)mP(XIc ∈ CIm) < ∞,
so EkI1(XIc) < ∞ and thus
∀#I=l
2dnP(X ∈ Al−1n ,XIc ∈ BIn) < ∞. (17)
We set
Aln := {x ∈ Al−1n : xIc /∈ BIn for all I ⊂ {1, . . . , d},#I = l}.
The set Aln satisfies the condition (13) by the definition of B
n and the
property (13) for Al−1n . The condition (14) follows by (17).
Notice that the set Ad−1n satisfies the assumptions of Corollary 7 with
N = 2n, therefore if Cd(p) ≥ 1,
2−d min(1, 2ndP(X ∈ Ad−1n )) ≤ P(∃|i|≤2n Xdeci ∈ Ad−1n ) ≤ P(∃|i|≤2n Xdeci ∈ Ãn)
≤ P(∃|i|≤2n PY (hn(Xdeci , Y ) ≥ Cd(p)an) ≥ p)
≤ P(PY (
|i|≤2n
i , Y ) ≥ an) ≥ p)
≤ p−1P(
|i|≤2n
i , Y ) ≥ an).
Therefore
ndP(X ∈ Ad−1n ) < ∞, so by (14) we get
X ∈ Ãn) =
P(X ∈ Al−1n \ Aln) + P(X ∈ Ad−1n )
Corollary 8. If
|i|≤2n
h2(Xdeci ) ≥ ε2nd(log n)α
for some ε > 0 and α ∈ R,
then E h
(LL|h|)α
Proof. We apply Theorem 3 with hn = h
2 and an = ε2
nd logd n in the
degenerate case when Y is deterministic. It is easy to notice that h2 ≥
C̃d(p, ε)2
dn logd n implies that
∀n≤m≤2d−1n h2 ≥ Cd(p)2d(n−m)am.
To prove the necessity part of Theorem 2 we will also need the following
Lemmas
Lemma 14 ([2], Lemma 12). Let g : Σd → R be a square integrable function.
|i|≤n
g(Xdeci )) ≤ (2d − 1)n2d−1Eg(X)2.
Lemma 15 ([2], Lemma 5). If E(|h|2 ∧ u) = O((loglog u)β) then
E|h|1{|h|≥s} = O(
(loglog s)β
Lemma 16. Let (ai)i∈Idn be a d–indexed array of vectors from a Hilbert space
H. Consider a random variable
|i|≤n
|i|≤n
For any set K ⊆ Id and a partition J = {J1, . . . , Jm} ∈ PId\K let us define
‖(ai)‖∗K,J ,p := sup
|i|≤n
〈ai, α(0)iK 〉
|α(0)iK |
2 ≤ 1,
)2 ≤ p,
∀imaxJk∈In
)2 ≤ 1, k = 1, . . . ,m
where ⋄J = J\{max J} (here
ai = ai).
Then, for all p ≥ 1,
‖S‖p ≥
K⊆Id,J∈PId\K
‖(ai)‖∗K,J ,p.
In particular for some constant cd
P(S ≥ cd
K⊆Id,J∈PId\K
‖(ai)‖∗K,J ,p) ≥ cd ∧ e−p.
Remark For K = ∅, we define
‖(ai)‖∗∅,J ,p := sup
|i|≤n
∈ R(I
)2 ≤ p,
∀imaxJk∈In
)2 ≤ 1, k = 1, . . . ,m
It is also easy to see that for a d-indexed matrix, ‖(ai)i‖Id,{∅},p =
i |ai|2 =
‖S‖2 and thus does not depend on p. Since it will not be important in the
applications, we keep a uniform notation with the subscript p.
Examples For d = 1, we have
‖(ai)i≤n‖∗∅,{{1}},p = sup
α2i ≤ p, |αi| ≤ 1, i = 1, . . . , n
‖(ai)i≤n‖∗{1},∅,p = sup
〈ai, αi〉 :
|αi|2 ≤ 1
|ai|2,
whereas for d = 2, we get
‖(aij)i,j≤n‖∗∅,{{1},{2}},p = sup
i,j=1
aijαiβj
α2i ≤ p,
β2j ≤ p,
∀i∈In |αi| ≤ 1,∀j∈In |βj | ≤ 1
‖(aij)i,j≤n‖∗∅,{I2},p = sup
i,j=1
aijαij
i,j=1
α2ij ≤ p,∀j∈In
α2ij ≤ 1
‖(aij)i,j≤n‖∗{1},{{2}},p = sup
i,j=1
〈aij , αi〉βj
|αi|2 ≤ 1,
β2j ≤ p,∀j∈In|βj | ≤ 1
‖(aij)i,j≤n‖∗I2,∅,p = sup
i,j=1
〈aij , αij〉
i,j=1
α2ij ≤ 1
|aij |2.
Proof of Lemma 16. We will combine the classical hypercontractivity prop-
erty of Rademacher chaoses (see e.g. [5], p. 110-116) with Lemma 3 in [2],
which says that for H = R we have
‖S‖p ≥
J∈PId
‖(ai)‖∅,J ,p. (18)
Since ‖(ai)‖Id,{∅},p =
i |ai|2 = ‖S‖2, the inequality ‖S‖p ≥ L−1‖(ai)‖Id,{∅},p
is just Jensen’s inequality (p ≥ 2) or the aforesaid hypercontractivity of
Rademacher chaos (p ∈ (1, 2)). On the other hand, for K 6= Id and
J ∈ PId\K , we have
‖S‖p =
EId\KEK
iId\K
p)1/p
EId\K
iId\K
2)p/2)1/p
EId\K sup
iId\K
〈α(0)iK , ai〉
p)1/p
EId\K
iId\K
〈α(0)iK , ai〉
p)1/p
L#KLd−#K
〈α(0)iK , ai〉)iId\K
∅,J ,p
L#KLd−#K
‖(ai)‖K,J ,p,
where the first inequality follows from hypercontractivity applied condition-
ally on (ε
i )k/∈K,i∈In, the second is Jensen’s inequality and the third is (18)
applied for a chaos of order d−#K.
The tail estimate follows from moment estimates by the Paley-Zygmund
inequality and the inequality ‖(ai)‖K,J ,tp ≤ tdegJ ‖(ai)‖K,J ,p for t ≥ 1 just
like in [12, 18].
Proof of necessity. First we will prove the integrability condition (11). Let
us notice that by classical hypercontractive estimates for Rademacher chaoses
and the Paley-Zygmund inequality (or by Lemma 16), we have
|i|≤2n
ǫdeci h(X
|i|≤2n
h(Xdeci )
for some constant cd > 0. By the Fubini theorem it gives
|i|≤2n
ǫdeci h(X
≥ D2nd/2 logd/2 n
≥ cdP
|i|≤2n
h(Xdeci )
2 ≥ D2c−2d 2
nd logd n
which together with Lemma 8 yields
|i|≤2n
h(Xdeci )
2 ≥ D2c−2
2nd logd n
The integrability condition (11) follows now from Corollary 8.
Before we proceed to the proof of (12), let us notice that (11) and Lemma
7 imply that
E(|h|2 ∧ u) ≤ K(loglog u)d (19)
for n large enough. The proof of (12) can be now obtained by adapting the
argument for the real valued case.
Since limn→∞
= log 2, (5) implies that there exists N0, such that
for all N > N0, there exists N ≤ n ≤ 2N , satisfying
|i|≤2n
ǫdeci h(X
> LdC2
nd/2 logd/2 n
. (20)
Let us thus fix N > N0 and consider n as above. Let K ⊆ Id, J =
{J1, . . . , Jk} ∈ PId\K . Let us also fix functions g : Σ#K → H, fj : Σ#Jj → R,
j = 1, . . . , k, such that
‖g(Xk)‖2 ≤ 1, ‖g(XK )‖∞ ≤ 2n/(2k+3),
‖fj(XJj )‖2 ≤ 1, ‖fj(XJj)‖∞ ≤ 2n/(2k+3).
The Chebyshev inequality gives
|iJj |≤2
)2 log n ≤ 10 · 2d2#Jjn log n) ≥ 1− 1
10 · 2d . (21)
Similarly, if K 6= ∅,
|iK |≤2n
|g(XdeciK )|
2 ≤ 10 · 2d2#Kn) ≥ 1− 1
10 · 2d (22)
and for K = ∅, |g| ≤ 1 (recall that for K = ∅, the function g is constant).
Moreover for j = 1, . . . , k and sufficiently large N ,
|i⋄Jj |≤2
2n#Jj
)2 · log n ≤ 2
n#⋄Jj22n/(2k+3) log n
2n#Jj
2n/(2k+3) log n
Without loss of generality we may assume that the sequences (X
i )i,j
and (ε
i )i,j are defined as coordinates of a product probability space. If for
each j = 1, . . . , k we denote the set from (21) by Ak, and the set from (22)
by A0, we have P(
j=0Ak) ≥ 0.9. Recall now Lemma 16. On
j=0Ak we
can estimate the ‖ · ‖∗K,J ,logn norms of the matrix (h(Xdeci ))|i|≤2n by using
the test sequences
log n
101/22d/22n#Jj/2
for j = 1, . . . , k and
g(XdeciK )
101/22d/22n#K/2
Therefore with probability at least 0.9 we have
‖(h(Xdeci ))|i|≤2n‖∗K,J ,logn (23)
≥ (log n)
2d(k+1)/210(k+1)/22
j #Jj)n/2
|i|≤2n
〈g(XdeciK ), h(X
(log n)k/2
2d(k+1)/210(k+1)/22dn/2
|i|≤2n
〈g(XdeciK ), h(X
Our aim is now to further bound from below the right hand side of
the above inequality, to have, via Lemma 16, control from below on the
conditional tail probability of
|i|≤2n ǫ
i h(X
i ), given the sample (X
From now on let us assume that
|E〈g(XK), h(X)〉
fj(XJj )| > 1. (24)
The Markov inequality, (19) and Lemma 15 give
|i|≤2n
〈g(XK), h(XdeciK )〉1{|h(Xdeci )|>2n}
2nd|E〈g, h〉
j=1 fj|
2nd(‖g‖∞
j=1 ‖fj‖∞) · E|h|1{|h|>2n}
2nd|E〈g, h〉
j=1 fj|
≤ 42n(k+1)/(2k+3)E|h|1{|h|>2n}
≤ 4K (log n)
n(k+2)
. (25)
Let now hn = h1{|h|≤2n}. By the Chebyshev inequality, Lemma 14 and (19)
|i|≤2n
〈g(XdeciK ),hn(X
)− 2ndE〈g, hn〉
|E〈g, hn〉
|i|≤2n〈g(XdeciK ), hn(X
j=1 fj(X
22nd|E〈g, hn〉
j=1 fj|2
≤ 25 (2
d − 1)2n(2d−1)
22nd|E〈g, hn〉
j=1 fj|2
E|〈g, hn〉
≤ 25(2d − 1) 2
2n(k+1)/(2k+3)E|hn|2
2n|E〈g, hn〉
j=1 fj|2
≤ 25K(2d − 1) log
2n/(2k+3)|E〈g, hn〉
j=1 fj|2
. (26)
Let us also notice that for large n, by (19), Lemma 15 and (24)
|E〈g, hn〉
fj| ≥ |E〈g, h〉
fj| − |E〈g, h〉1{|h|>2n}
≥ |E〈g, h〉
fj| − 2n(k+1)/(2k+3)K
(log n)d
|E〈g, h〉
fj| ≥
Inequalities (25), (26) and (27) imply, that for large n with probability
at least 0.9 we have
|i|≤2n
〈g(XdeciK ), h(X
|i|≤2n
〈g(XdeciK ), hn(X
|i|≤2n
〈g(XdeciK ), h(X
i )〉1{|h(Xdec
)|>2n}
≥ 2nd
|E〈g, hn〉
fj| −
|E〈g, h〉
≥ 2nd
|E〈g, h〉
fj| −
|E〈g, h〉
|E〈g, h〉
fj |.
Together with (23) this yields that for large n with probability at least
‖(hi)|i|≤2n‖∗K,J ,logn ≥
2nd/2 logk/2 n
4 · 2d(k+1)/210(k+1)/2
|E〈g, h〉
Thus, by Lemma 16, for large n
|i|≤2n
ǫdeci h(X
∣ ≥ cd
2nd/2 logk/2 n
4 · 2d(k+1)/210(k+1)/2
|E〈g, h〉
which together with (20) gives
|E〈g, h〉
fj| ≤ LdC
4 · 2d(k+1)/210(k+1)/2
log(d−k)/2 n.
In particular for sufficiently large N , for arbitrary functions g : Σ#K → H,
fj : Σ
#Jj → R, j = 1, . . . , k, such that
‖g(XK)‖∞, ‖fj(XJj )‖2 ≤ 1,
‖g(XK)‖2, ‖fj(XJj )‖∞ ≤ 2N/(2k+3)
we have
|E〈g, h〉
fj| ≤ LdC
4 · 2d(k+1)/210(k+1)/2
log(d−k)/2 n ≤ L̃dC log(d−k)/2 N,
which clearly implies (12).
7 Sufficiency
Lemma 17. Let H = H(X1, . . . ,Xd) be a nonnegative random variable,
such that EH2 < ∞. Then for I ⊆ Id, I 6= ∅,Id,
2l+#I
PIc(EIH
2 ≥ 22l+#Icn) < ∞.
Proof.
2l+#I
PIc(EIH
2 ≥ 22l+#Icn) =
2lEIc
1{EI |H|2≥22l+#I
21−lEIcEIH
2 ≤ 4EH2 < ∞.
Lemma 18. Let X = (X1, . . . ,Xd) and X̃(I) = ((Xi)i∈I , (X
i )i∈Ic). De-
note H = |h|/(LL|h|)d/2. If E|H|2 < ∞ and hn = h1An , where
x : |h(x)|2 ≤ 2nd logd n and ∀I 6=∅,Id EIH
2 ≤ 2#Icn
then for I ⊆ Id, I 6= ∅, we have
2−n#I
log2d n
E[|hn(X)|2|hn(X̃(I))|2] < ∞.
Proof. a) I = Id
E|hn|4
2nd log2d n
≤ E|h|4
2nd log2d n
1{|h|2≤2nd logd n}
≤ LdE|h|4
|h|2(LL|h|)d < ∞.
b) I 6= Id, ∅. Let us denote by EI ,EIc , ẼIc respectively, the expectation
with respect to (Xi)i∈I , (Xi)i∈Ic and (X
i )i∈Ic . Let also h̃, h̃n stand
for h(X̃(I)), hn(X̃(I)) respectively. Then
E(|hn|2 · |h̃n|2)
2n#I log2d n
E(|hn|2 · |h̃n|21{|h|≤|h̃|})
2n#I log2d n
|h|2|h̃|21
{|h|≤|h̃|}
2n#I log2d n
{EIc |h|
{|h|2≤22nd}
#In logd n, |h̃|2≤22nd}
|h|2|h̃|21
{|h|≤|h̃|}
2n#I log2d n
1{EIc |h|21{|h|2≤|h̃|2}≤Ld2
#In logd n, |h̃|2≤22nd}
≤ L̃dE
|h|2|h̃|21
{|h|≤|h̃|}
(EIc |h|21{|h|2≤|h̃|2})(LL|h̃|)d
= L̃dEI ẼIc
|h̃|2EIc
|h|21
{|h|≤|h̃|}
(EIc |h|21{|h|2≤|h̃|2})(LL|h̃|)d
≤ L̃dE
|h̃|2
(LL|h̃|)d
where to obtain the second inequality, we used the fact that
EIc |h|21{|h|2≤22nd,EIcH2≤2#In}
≤ EIc
(LL|h|)d (loglog 2
nd)d1{EIcH2≤2#In}
≤ LdEIcH21{EIcH2≤2#In} log
d n ≤ Ld2#In logd n.
Lemma 19. Consider a square integrable, nonnegative random variable Y .
Let Yn = Y 1Bn , with Bn =
k∈K(n)Ck, where C0, C1, C2, . . . are pairwise
disjoint subsets of Ω and
K(n) = {k ≤ n : E(Y 21Ck) ≤ 2
k−n}.
(EY 2n )
2 < ∞
Proof. Let us first notice that by the Schwarz inequality, we have
k∈K(n)
E(Y 21Ck)
k∈K(n)
2(n−k)/22(k−n)/2E(Y 21Ck)
k∈K(n)
[2n−k(E(Y 21Ck))
k∈K(n)
[2n−k(E(Y 21Ck))
(EY 2n )
k∈K(n)
[2n−k(E(Y 21Ck))
k : E(Y 21Ck )>0
(E(Y 21Ck))
n : k∈K(n)
k : E(Y 21Ck )>0
(E(Y 21Ck))
2 max
n : k∈K(n)
k : E(Y 21Ck )>0
(E(Y 21Ck))
E(Y 21Ck)
E(Y 21Ck) = 4EY
2 < ∞.
Proof of sufficiency. The proof consists of several truncation arguments.
The first part of it follows the proofs presented in [11] and [2] for the real-
valued case. Then some modifications are required, reflecting the diminished
integrability condition in the Hilbert space case. At each step we will show
|i|≤2n
πdhn(X
∣ ≥ C2nd/2 logd/2 n
< ∞, (28)
with hn = h1An for some sequence of sets An. In the whole proof we keep
the notation H = |h|/(LL|h|)d/2.
Let us also fix ηd ∈ (0, 1), such that the following implication holds
∀n=1,2,... |h|2 ≤ η2d2nd logd n =⇒ H2 ≤ 2nd. (29)
Step 1 Inequality (28) holds for any C > 0 if
x : |h(x)|2 ≥ η2d2nd logd n
We have, by the Chebyshev inequality and the inequality E|πdhn| ≤ 2dE|hn|
(which follows directly from the definition of πd or may be considered a
trivial case of Lemma 6),
|i|≤2n
πdhn(X
∣ ≥ C2nd/2 logd/2 n
|i|≤2n πdhn(X
C2nd/2 logd/2 n
2ndE|h|1
{|h|>ηd2
nd/2 logd/2 n}
C2nd/2 logd/2 n
= 2dC−1E
2nd/2
logd/2 n
{|h|>ηd2
nd/2 logd/2 n}
≤ LdC−1E
(LL|h|)d < ∞.
Step 2 Inequality (28) holds for any C > 0 if
x : |h(x)|2 ≤ η2d2nd logd n, ∃I 6=∅,Id EIH
2 ≥ 2#Icn
As in the previous step, it is enough to prove that
|i|≤2n ǫ
i hn(X
2nd/2 logd/2 n
The set An can be written as
I⊆Id,I 6=Id,∅
An(I),
where the sets An(I) are pairwise disjoint and
An(I) ⊆ {x : |h(x)|2 ≤ 22nd, EIH2 ≥ 2#I
Therefore it suffices to prove that
|i|≤2n ǫ
i h(X
i )1An(I)(X
2nd/2 logd/2 n
< ∞. (30)
Let for l ∈ N,
An,l(I) := {x : |h(x)|2 ≤ 22nd,
22l+2+#I
cn > EIH
2 ≥ 22l+#Icn} ∩An(I).
Then hn1An(I) =
l=0 hn,l, where hn,l := hn1An,l(I) (notice that the sum is
actually finite in each point x ∈ Σd as for large l, x /∈ An,l(I)).
We have
|i|≤2n
ǫdeci hn,l(X
i )| ≤
|iIc |≤2
EIcEI |
|iI |≤2n
ǫdeciI hn,l(X
|iIc |≤2
EIc(EI |
|iI |≤2n
ǫdeciI hn,l(X
i )|2)1/2
≤ 2(#Ic+#I/2)nEIc(EI |hn,l|2)1/2
≤ Ld[2(#I
c+d/2)n+l+1 logd/2 n]PIc(EIH
2 ≥ 22l+#Icn),
where in the last inequality we used the estimate
n,l ≤LdEI [(log n)dH21{22l+2+#Icn>EIH2≥22l+#Icn}]
≤Ld22l+2+#I
cn(log n)d1{EIH2≥22l+#I
Therefore to get (30) it is enough to show that
2l+#I
PIc(EIH
2 ≥ 22l+#Icn) < ∞.
But this is just the statement of Lemma 17.
Step 3 Inequality (28) holds for any C > 0 if
x : |h(x)|2 ≤ η2d2nd logd n, ∀I 6=∅,Id EIH
2 ≤ 2#Icn} ∩
with BIn =
k∈K(I,n)C
k and C
0 = {x : EIH2 ≤ 1}, CIk = {x : 2#I
c(k−1) <
2 ≤ 2#Ick}, k ≥ 1, K(I, n) = {k ≤ n : E(H21CI
) ≤ 2k−n}.
By Lemma 6 and the Chebyshev inequality, it is enough to show that
|i|≤2n ǫ
i hn(X
i )|4
22nd log2d n
The Khintchine inequality for Rademacher chaoses gives
|i|≤2n
ǫdeci hn(X
i )|4 ≤ E(
|i|≤2n
|hn(Xdeci )|2)2
|i|≤2n
|j|≤2n :
{k : ik=jk}=I
E|[hn(Xdeci )|2|hn(Xdecj )|2]
2nd2n(d−#I)E[|hn(X)|2 · |hn(X̃(I))|2],
where X = (X1, . . . ,Xd) and X̃(I) = ((Xi)i∈I , (X
i )i∈Ic).
To prove the statement of this step it thus suffices to show that for all
I ⊆ Id,
S(I) :=
2−n#I
log2d n
E[|hn(X)|2|hn(X̃(I))|2] < ∞. (31)
The case of nonempty I follows from Lemma 18. It thus remains to consider
the case I = ∅. Set H2I = EIH2. We have
S(∅) =
(E|hn|2)2
log2d n
logd n
1An))
2 ≤ Ld
(E(H21An))
(E(H2
))2 ≤ L̃d
(E(H21BIn))
= L̃d
(E(H2I1BIn))
2 < ∞
by Lemma 19, applied for Y 2 = EIH
2, since EH2I = EH
2 < ∞.
Step 4 Inequality (28) holds for some C ≤ LdD if
x : |h(x)|2 ≤ η2d2nd logd n, ∀I 6=∅,IdEIH
2 ≤ 2#Icn} ∩
(BIn)
where BIn is defined as in the previous step.
Let us first estimate ‖(EI |hn|2)1/2‖∞ for I ( Id. We have
EI |hn|2 ≤ EI
|h|21{|h|2≤ηd2nd logd n}
k≤n,k/∈K(I,n)
≤ Ld logd n
k≤n,k/∈K(I,n)
The fact that we can restrict the summation to k ≤ n follows directly from
the definition of An for I 6= ∅ and for I = ∅ from (29).
The sets CIk are pairwise disjoint and thus
‖EI |hn|2‖∞ ≤ (Ld logd n) max
k≤n,k/∈K(I,n)
ck = Ld2
#IckI(n) logd n, (32)
where
kI(n) = max{k ≤ n : k /∈ K(I, n)}.
Therefore for C > 0,
( C2nd/2 logd/2 n
2#In/2‖(EI |hn|2)1/2‖∞
)2/(d+#Ic)]
k≤n,k/∈K(I,n)
( C2nd/2 logd/2 n
2#In/22#I
ck/2 logd/2 n
)2/(d+#Ic)]
n≥k, k /∈K(I,n)
c(n−k)/2
)2/(d+#Ic)]
Notice that for each k the inner series is bounded by a geometric series
with the ratio smaller than some qd,C < 1 (qd,C depending only on d and
C). Therefore the right hand side of the above inequality is bounded by
n≥k, k /∈K(I,n)
c(n−k)/2
)2/(d+#Ic)]
with the convention sup ∅ = 0. But k /∈ K(I, n) implies that 2#Ic(n−k)/2 ≥
(E(H21CI
))−#I
c/2. Therefore the above quantity is further bounded by
C−2/#I
E(H21CI
)−#Ic/(d+#Ic)]
≤ L̄dC−2/#I
E(H21CI
= L̄dC
−2/#IcEH2 < ∞,
where we used the inequality ex ≥ cdxα for all x ≥ 0 and 0 ≤ α ≤ 2d. We
have thus proven that for all I ( Id and C,Ld > 0,
n : An 6=∅
( C2nd/2 logd/2 n
2#In/2‖(EI |hn|2)1/2‖∞
)2/(d+#Ic)]
< ∞. (33)
Now we will turn to the estimation of ‖hn‖J0,J . Let us consider J0 ⊆ Id,
J = {J1, . . . , Jl} ∈ PId\J0 and denote as before X = (X1, . . . ,Xd), XI =
(Xi)i∈I . Recall that
‖hn‖J0,J = sup
E〈hn(X), f0(XJ0)〉
fi(XJi) : E|f0(XJ0)|2 ≤ 1,
Ef2i (XJi) ≤ 1, i ≥ 1
In what follows, to simplify the already quite complicated notation, let
us suppress the arguments of all the functions and write just h instead of
h(X) and fi instead of fi(XJi).
Let us also remark that although f0 plays special role in the definition
of ‖ · ‖J0,J , in what follows the same arguments will apply to all fi’s with
the obvious use of Schwarz inequality for the scalar product in H. We will
therefore not distinguish the case i = 0 and f2i will denote either the usual
power or 〈f0, f0〉, whereas ‖fi‖2 for i = 0 will be the norm in L2(H,XJ0),
which may happen to be equal just H if J0 = ∅.
Since E|fi|2 ≤ 1, i = 0, . . . , l, then for each j = 0, . . . , l and J ( Jj by
the Schwarz inequality applied conditionally to XJj\J
E|〈hn, f0〉
fi1{EJf2j >a
≤ EJj\J
(E(Jj\J)c
f2i )
1{EJf2j ≥a
2}(E(Jj\J)c |hn|
2)1/2
≤ EJj\J
1{EJf2j ≥a
2}(E(Jj\J)c |hn|
2)1/2
≤ Ld2
k(Jj\J)
c(n)#(Jj\J)/2 logd/2 nEJj\J [(EJf
1{EJf2j ≥a
≤ Ld[2
k(Jj\J)
c(n)#(Jj\J)/2 logd/2 n]a−1,
where the third inequality follows from (32) and the last one from the ele-
mentary fact E|X|1{|X|≥a} ≤ a−1E|X|2. This way we obtain
‖hn‖J0,J (34)
≤ sup{E[〈hn, f0〉
fi] : ‖fi‖2 ≤ 1,∀J(Ji ‖(EJf2i )1/2‖∞ ≤ 2n#(Ji\J)/2}
2(k(Ji\J)c(n)−n)#(Ji\J)/2 logd/2 n
≤ sup{E[〈hn, f0〉
fi] : ‖fi‖2 ≤ 1,∀J(Ji ‖(EJf2i )1/2‖∞ ≤ 2n#(Ji\J)/2}
2(kI (n)−n)#I
c/2 logd/2 n.
Let us thus consider arbitrary fi, i = 0, . . . , k such that ‖fi‖2 ≤ 1,
‖(EJf2i )1/2‖∞ ≤ 2n#(Ji\J)/2 for all J ( Ji (note that the latter condition
means in particular that ‖fi‖∞ ≤ 2n#Ji/2).
We have by assumption (12) for sufficiently large n,
|E[〈h, f0〉
fi]| ≤ ‖h‖K,J ,2nd/2 ≤ LdD log(d−degJ )/2 n.
We have also
E|〈h, f0〉1{|h|2≥ηd2nd logd n}
fi| ≤ E[|h|1{|h|2≥ηd2nd logd n}]
‖fi‖∞
≤ 2nd/2E[|h|1{|h|2≥ηd2nd logd n}] =: αn.
Also for I ⊆ Id, I 6= ∅, Id, denoting h̃n = h1{|h|2≤ηd2nd logd n}, we get
E|〈h̃n,f0〉
fi1{EIH2≥2n#I
≤ EIc
(EI |h̃n|2)1/21{EIH2≥2n#Ic}
(EJi∩I |fi|2)1/2
2n#(Ji∩I
c)/2]EIc [(EI |h̃n|2)1/21{EIH2≥2n#Ic}]
≤ Ld2n#I
EIc[(EIH
2 logd n)1/21{EIH2≥2n#I
≤ Ld[2n#I
c/2 logd/2 n]EIc[(EIH
2)1/21{EIH2≥2n#I
}] =: β
Let us denote h̄n = h̃n
∅6=I(Id
1{EIH2≤2#I
cn} and γ
n = E|h̄n1BIn |
Combining the three last inequalities we obtain
|E〈hn, f0〉
fi| ≤|E〈h, f0〉
fi|+ |E〈hn1Acn , f0〉
≤LdD log(d−deg J )/2 n+ E|〈h1{|h|2≥2nd logd n}, f0〉
∅6=I(Id
E|〈h̃n1{EIH2≥2n#Ic}, f0〉
E|〈h̄n1BIn , f0〉
≤LdD log(d−deg J )/2 n+ αn +
∅6=I(Id
βIn +
Now, combining the above estimate with (34), we obtain
‖hn‖J0,J ≤ Ld
2(kI (n)−n)#I
c/2 logd/2 n+ LdD log
(d−degJ )/2 n (35)
+ αn +
∅6=I(Id
βIn +
Let us notice that
logd/2 n
∀I 6=∅,Id
logd/2 n
< ∞, (36)
∀I 6=∅,Id
(γIn)
log2d n
The first inequality was proved in Step 1. The proof of the second one
is straightforward. Indeed, we have
logd/2 n
= LdEIc[(EIH
2)1/2
1{EIH2≥2n#I
≤ L̃dEIcEIH2 = L̃dEH2 < ∞.
The third inequality is implicitly proved in Step 3. Let us however present
an explicit argument.
(γIn)
log2d n
|h|21
{|h|≤ηd2
nd/2 logd/2 n}
logd n
(EIcEI(H
))2 < ∞
by Lemma 19 applied to the random variable
EIH2.
We are now in position to finish the proof. Let us notice that we have
either E(|h|21{|h|2≤22nd}) ≤ 1, or we can use the function
h1{‖h|2≤22nd}
(E(|h|21{|h|2≤22nd}))1/2
as a test function in the definition of ‖h‖Id,∅,2nd , obtaining
(E(|h|21{|h|2≤22nd}))1/2 = E〈h, g〉 ≤ ‖h‖Id,∅,2nd < D log
for large n. Combining this estimate with Corollary 3, we can now write
|i|≤2n
πdhn(X
i )| ≥ L̃d(D + C)2nd/2 logd/2 n
≤ L̃d
J0(Id
J∈PId\J0
(C2nd/2 logd/2 n
2nd/2‖hn‖Jo,J
)2/degJ ]
+ L̃d
( C2nd/2 logd/2 n
2n#I/2‖(EI |hn|2)1/2‖∞
)2/(d+#Ic)]
The second series is convergent by (33).
Thus it remains to prove the convergence of the first series. By (35), we
have for all J0,J
(C logd/2 n
‖hn‖Jo,J
)2/degJ ]
( C logd/2 n
2(kI (n)−n)#I
c/2 logd/2 n
)2/degJ ]
+ exp
( C logd/2 n
D log(d−deg J )/2 n
)2/degJ ]
+ exp
(C logd/2 n
)2/degJ ]
+ exp
( C logd/2 n
∅6=I(Id
)2/degJ ]
+ exp
( C logd/2 n
)2/ degJ ]
(under our permanent convention that the values of Ld in different equations
need not be the same). The series determined by the three last components
at the right-hand side are convergent by (36) since e−x ≤ Lrx−r for r > 0.
The series corresponding to the second component is convergent for C large
enough and we can take C = LdD. As for the series corresponding to the
first term, we have, just as in the proof of (33) for any I ( Id,
( C logd/2 n
(kI (n)−n)#Ic/2 logd/2 n
)2/degJ ]
n≥k,k /∈K(I,n)
C2(n−k)#I
)2/degJ ]
n≥k,k /∈K(I,n)
C2(n−k)#I
)2/degJ ]
E(H21CI
) = K̄EH2 < ∞.
We have thus proven the convergence of the series at the left-hand side of
(37) with C ≤ LdD, which ends Step 5.
Now to finish the proof, we just split Σd for each n into four sets, described
by steps 1–4 and use the triangle inequality, to show that
|i|≤2n
h(Xdeci )| ≥ LdD2nd/2 logd/2 n
which proves the sufficiency part of the theorem by Corollary 4.
8 The undecoupled case
Theorem 4. For any function h : Σd → H and a sequence X1,X2, . . . of
i.i.d., Σ-valued random variables, the LIL (4) holds if and only if h
(LL|h|)d < ∞,
h is completely degenerate for the law of X1 and the growth conditions (12)
are satisfied.
More precisely, if (4) holds, then (12) is satisfied with D = LdC and
conversely, (12) together with complete degeneration and the integrability
condition imply (4) with C = LdD.
Proof. Sufficiency follows from Corollary 6 and Theorem 2. To prove the
necessity assume that (4) holds and observe that from Lemma 8 and Corol-
lary 5, h satisfies the randomized decoupled LIL (8) and thus, by Theo-
rem 2, (11) holds and the growth conditions (12) on functions ‖h‖K,J ,u
are satisfied (note that the ‖ · ‖J ,u norms of the kernel h(X1, . . . ,Xd) and
ε1 · · · εdh(X1, . . . ,Xd) are equal). The complete degeneracy of 〈ϕ, h〉 for any
ϕ ∈ H follows from the necessary conditions for real-valued kernels. Since
by (11), Eih is well defined in the Bochner sense, we must have Eih = 0.
References
[1] Adamczak, R. (2005). Moment Inequalities for U -statistics. Ann.
Probab. 34, No. 6, 2288-2314.
[2] Adamczak, R., Lata la, R. (2006) LIL for canonical U-statistics. Sub-
mitted
[3] Arcones, M. and Giné, E. (1995). On the law of the iterated logarithm
for canonical U -statistics and processes. Stochastic Process. Appl. 58
217–245. MR1348376.
[4] Bousquet O., Boucheron S., Lugosi G., Massart P.(2005). Mo-
ment inequalities for functions of independent random variables. Ann.
Probab. 33, no. 2, 514-560. MR2123200.
[5] de la Peña, V.H. and Giné, E. (1999). Decoupling. From Dependence
to Independence. Springer, New York. MR1666908.
[6] de la Peña, V.H. and Montgomery-Smith, S. (1994). Bounds for
the tail probabilities of U -statistics and quadratic forms. Bull. Amer.
Math. Soc. 31 223–227. MR1261237.
[7] de la Peña, V. H., Montgomery-Smith, S. J. (1995) Decoupling
inequalities for the tail probabilities of multivariate U -statistics. Ann.
Probab. 23, no. 2, 806–816. MR1334173.
[8] Giné E., Lata la, R. and Zinn, J. (2000). Exponential and moment in-
equalities for U -statistics. High Dimensional Probability II, 13–38. Progr.
Probab., 47, Birkhauser, Boston. MR1857312.
[9] Giné, E. and Zhang, C.-H. (1996). On integrability in the LIL for
degenerate U -statistics. J. Theoret. Probab. 9 385–412. MR1385404.
[10] Giné, E., Zinn, J. (1994). A remark on convergence in distribution of
U -statistics. Ann. Probab. 22 117–125. MR1258868.
[11] Giné E., Kwapień, S., Lata la, R. and Zinn, J. (2001). The LIL for
canonical U -statistics of order 2, Ann. Probab. 29 520–557. MR1825163.
[12] Gluskin, E.D., Kwapień, S. (1995). Tail and moment estimates for
sums of independent random variables with logarithmically concave tails.
Studia Math. 114 , no. 3, 303–309. MR1338834.
[13] Goodman, V., Kuelbs, J., Zinn, J. (1981). Some results on the LIL
in Banach space with applications to weighted empirical processes. Ann.
Probab. 9 , no. 5, 713–752. MR0628870.
[14] Houdré, C. and Reynaud-Bouret, P. (2003). Exponential Inequal-
ities, with Constants, for U -statistics of Order Two. Stochastic inequal-
ities and applications, 55–69. Progr. Probab., 56, Birkhauser, Basel.
MR2073426.
[15] Kwapień, S., Lata la, R., Oleszkiewicz, K. and Zinn, J. (2003).
On the limit set in the law of the iterated logarithm for U -statistics of
order two. High dimensional probability, III (Sandjberg), 111–126. Progr.
Probab., 55, Birkhauser, Basel. MR2033884.
[16] Lata la, R. (1998) On the almost sure boundedness of norms of
some empirical operators. Statist. Probab. Lett. 38 , no. 2, 177–182.
MR1627869.
[17] Lata la, R. and Zinn, J. (2000). Necessary and sufficient conditions
for the strong law of large numbers for U -statistics. Ann. Probab. 28
1908–1924. MR1813848.
[18] Lata la, R. (2006). Estimation of moments and tails of Gaussian
chaoses. Ann. Probab. 34, No. 6. 2061-2440.
[19] Rubin, H. and Vitale, R.A. (1980). Asymptotic distribution of sym-
metric statistics. Ann. Statist. 8 165–170. MR0557561.
	Introduction
	Notation
	Moment inequalities for U-statistics in Hilbert space 
	The equivalence of several LIL statements
	The canonical decoupled case
	Necessity
	Sufficiency
	The undecoupled case

  We give necessary and sufficient conditions for the (bounded) law of the
iterated logarithm for $U$-statistics in Hilbert spaces. As a tool we also
develop moment and tail estimates for canonical Hilbert-space valued
$U$-statistics of arbitrary order, which are of independent interest.

Introduction
In the last two decades we have witnessed a rapid development in the asymp-
totic theory of U -statistics, boosted by the introduction of the so called
’decoupling’ techniques (see [5, 6, 7]), which allow to treat U -statistics con-
ditionally as sums of independent random variables. This approach yielded
better understanding of U -statistics versions of the classical limit theorems
of probability. Necessary and sufficient conditions were found for the strong
law of large numbers [17], the central limit theorem [19, 10] and the law
of the iterated logarithm [11, 2]. Also some sharp exponential inequalities
for canonical U -statistics have been found [8, 1, 14]. Analysis of the afore-
mentioned results shows an interesting phenomenon. Namely, the natural
counterparts of the necessary and sufficient conditions for sums of i.i.d. ran-
dom variables (U -statistics of degree 1), remain sufficient for U -statistics
Institute of Mathematics, Polish Academy of Sciences, Warsaw, Poland. Email:
R.Adamczak@impan.gov.pl. Research partially supported by MEiN Grant 2 PO3A 019
†Institute of Mathematics, Warsaw University, Warsaw, Poland. Email:
RLatala@mimuw.edu.pl. Research partially supported by MEiN Grant 1 PO3A 012 29.
http://arxiv.org/abs/0704.1643v1
of arbitrary degree, but with an exception for the CLT, they cease to be
necessary. The correct conditions turn out to be much more involved and
are expressed for instance in terms of convergence of some series (LLN) or
as growth conditions for some functions (LIL).
A natural problem is an extension of the above results to the infinite-
dimensional setting. There has been some progress in this direction, and
partial answers have been found, usually under the assumption on the geo-
metrical structure of the space in which the values of a U -statistic are taken.
In general however the picture is far from being complete and the necessary
and sufficient conditions are known only in the case of the CLT for Hilbert
space valued U -statistics (see [5, 10] for the proof of sufficiency in type 2
spaces and necessity in cotype 2 spaces respectively).
In this article we generalize to separable Hilbert spaces the results from
[2] on necessary and sufficient conditions for the LIL for real valued U -
statistics. The conditions are expressed only in terms of the U -statistic
kernel and the distribution of the underlying i.i.d. sequence and can be also
considered a generalization of results from [13], where the LIL for i.i.d. sums
in Hilbert spaces was characterized. We consider only the bounded version
of the LIL and do not give the exact value of the lim sup nor determine the
limiting set. Except for the classical case of sums of i.i.d. random variables,
the problem of finding the lim sup is at the moment open even in the one
dimensional case (see [3, 5, 15] for some partial results) and the problem of
the geometry of the limiting set and the compact LIL is solved only under
suboptimal integrability conditions [3].
The organization of the paper is as follows. First, in Section 3 we prove
sharp exponential inequalities for canonical U -statistics, which generalize
the results of [1, 8] for the real-valued case. Then, after recalling some
basic facts about the LIL we give necessary and sufficient condition for the
LIL for decoupled, canonical U -statistics (Theorem 2). The quite involved
proof is given in the two subsequent sections. Finally we conclude with
our main result (Theorem 4), which gives a characterization of the LIL for
undecoupled U -statistics and follows quite easily from Theorem 2 and the
one dimensional result.
2 Notation
For an integer d, let (Xi)i∈N, (X
i )i∈N,1≤k≤d be independent random vari-
ables with values in a Polish space Σ, equipped with the Borel σ-field F .
Let also (εi)i∈N, (ε
i )i∈N,1≤k≤d be independent Rademacher variables, in-
dependent of (Xi)i∈N, (X
i )i∈N,1≤k≤d.
Consider moreover measurable functions hi : Σ
d → H, where (H, | · |) is a
separable Hilbert space (we will denote both the norm in H and the absolute
value of a real number by | · |, the context will however prevent ambiguity).
To shorten the notation, we will use the following convention. For i =
(i1, . . . , id) ∈ {1, . . . , n}d we will write Xi (resp. Xdeci ) for (Xi1 , . . . ,Xid),
(resp. (X
, . . . ,X
)) and ǫi (resp. ǫ
i ) for the product εi1 · . . . · εid (resp.
· . . . · ε(d)id ), the notation being thus slightly inconsistent, which however
should not lead to a misunderstanding. The U -statistics will therefore be
denoted
i∈Idn
hi(Xi) (an undecoupled U -statistic)
|i|≤n
i ) (a decoupled U -statistic)
i∈Idn
ǫihi(Xi) (an undecoupled randomized U -statistic)
|i|≤n
ǫdeci hi(X
i ) (a decoupled randomized U -statistic),
where
|i| = max
k=1,...,d
Idn = {i : |i| ≤ n, ij 6= ik for j 6= k}.
Since in this notation {1, . . . , d} = I1d we will write
Id = {1, 2, . . . , d}.
Throughout the article we will write Ld, L to denote constants depending
only on d and universal constants respectively. In all those cases the values
of a constant may differ at each occurrence.
For I ⊆ Id, we will write EI to denote integration with respect to vari-
ables (X
i )i∈N,j∈I . We will consider mainly canonical (or completely de-
generated) kernels, i.e. kernels hi, such that for all j ∈ Id, Ejhi(Xdeci ) = 0
3 Moment inequalities for U-statistics in Hilbert
space
In this section we will present sharp moment and tail inequalities for Hilbert
space valued U -statistics, which in the sequel will constitute an important
ingredient in the analysis of the LIL. These estimates are a natural general-
ization of inequalities for real valued U-statistics presented in [1].
Let us first introduce some definitions.
Definition 1. For a nonempty, finite set I let PI be the family consisting of
all partitions J = {J1, . . . , Jk} of I into nonempty, pairwise disjoint subsets.
Let us also define for J as above deg(J ) = k. Additionally let P∅ = {∅}
with deg(∅) = 0.
Definition 2. For a nonempty set I ⊆ Id consider J = {J1, . . . , Jk} ∈ PI .
For an array (hi)i∈Idn of H-valued kernels and fixed value of iI
c, define
‖(hi)iI‖J = sup
EI [hi(X
deg(J )
(XdeciJj
: ΣJj → R
|f (j)iJj (X
)|2 ≤ 1 for j = 1, . . . ,deg(J )
Let moreover ‖(hi)i∅‖∅ = |hi|.
Remark It is worth mentioning that for I = Id, ‖ · ‖J is a deterministic
norm, whereas for I ( Id it is a random variable, depending on X
Quantities given by the above definition suffice to obtain precise moment
estimates for real valued U -statistics. However, to bound the moments of
U -statistics with values in general Hilbert spaces, we will need to introduce
one more definition.
Definition 3. For nonempty sets K ⊆ I ⊆ Id consider J = {J1, . . . , Jk} ∈
PI\K . For an array (hi)i∈Idn of H-valued kernels and fixed value of iIc, define
‖(hi)iI‖K,J = sup
EI [〈hi(Xdeci ), giK (XdeciK )〉
deg(J )
(XdeciJj
)]| :
: ΣJj → R, giK : ΣK → H ,E
|giK (XdeciK )|
2 ≤ 1
|f (j)iJj (X
)|2 ≤ 1 for j = 1, . . . ,deg(J )
Remark One can see that the only difference between the above definition
and Definition 2 is that the latter distinguishes one set of coordinates and
allows functions corresponding to this set to take values in H. Moreover,
since the norm in H satisfies | · | = sup|φ|≤1〈φ, ·〉, we can treat Definition 2
as a counterpart of Definition 3 for K = ∅. We will use this convention to
simplify the statements of the subsequent theorems. Thus, from now on, we
will write
‖ · ‖∅,J := ‖ · ‖J .
Example For d = 2 and I = {1, 2}, the above definition gives
‖(hij(Xi, Yj))i,j‖∅,{{1,2}} = sup
hij(Xi, Yj)fij(Xi, Yj)
f(Xi, Yj)
2 ≤ 1
= sup
φ∈H,|φ|≤1
〈φ, hij(Xi, Yj)〉2,
‖(hij(Xi, Yj))i,j‖∅,{{1}{2}} = sup
hij(Xi, Yj)fi(Xi)gj(Yj)
Ef(Xi)
Eg(Yj)
2 ≤ 1
‖(hij(Xi, Yj))i,j‖{1},{{2}} = sup
〈fi(Xi), hij(Xi, Yj)〉gj(Yj) :
|f(Xi)|2,E
g(Yj)
2 ≤ 1
‖(hij(Xi, Yj))i,j‖{1,2},∅ = sup
〈fij(Xi, Yj), hij(Xi, Yj)〉 :
|f(Xi, Yj)|2 ≤ 1
E|hij(Xi, Yj)|2.
We can now present the main result of this section.
Theorem 1. For any array of H-valued, completely degenerate kernels (hi)i
and any p ≥ 2, we have
h(Xdeci )
p ≤ Lpd
K⊆I⊆Id
J∈PI\K
pp(#I
c+degJ /2)
EIc max
‖(hi)iI‖
The proof of the above theorem proceeds along the lines of arguments
presented in [1, 8]. In particular we will need the following moment estimates
for suprema of empirical processes [8].
Lemma 1 ([8, Proposition 3.1], see also [4, Theorem 12]). Let X1, . . . ,Xn
be independent random variables with values in (Σ,F) and T be a countable
class of measurable real functions on Σ, such that for all f ∈ T and i ∈
In, Ef(Xi) = 0 and Ef(Xi)
2 < ∞. Consider the random variable S :=
supf∈T |
i f(Xi)|. Then for all p ≥ 1,
ESp ≤ Lp
(ES)p + pp/2σp + ppEmax
|f(Xi)|p
where
σ2 = sup
Ef(Xi)
We will also need the following technical lemma.
Lemma 2 (Lemma 5 in [1]). For α > 0 and arbitrary nonnegative kernels
gi : Σ
d → R+ and p > 1 we have
i ≤ L
pαpEmax
I({1,...,d}
p#IpEI max
EIcgi)
Before stating the next lemma, let us introduce some more definitions,
concerning J –norms of deterministic matrices
Definition 4. Let (ai)i∈Idn be a d-indexed array of real numbers. For J =
{J1, . . . , Jk} ∈ PId define
‖(ai)i‖J = sup
· · · x(k)iJk :
)2 ≤ 1, . . . ,
)2 ≤ 1
We will also need
Definition 5. For i ∈ Nd−1 × In let ai : Σ → R be measurable functions
and Z1, . . . , Zn be independent random variables with values in Σ. For a
partition J = {J1, . . . , Jk} ∈ PId (d ∈ J1), let us define
‖(ai(Zid))i‖J = sup
iId\J1
ai(Zid)x
· · · x(k)iJk
)2 ≤ 1, . . . ,
)2 ≤ 1
Remark All the definitions of norms presented so far, seem quite similar
and indeed they can be all interpreted as injective tensor-product norms on
proper spaces. We have decided to introduce them separately by explicit
formulas, because this form appears in our applications.
The next lemma is crucial for obtaining moment inequalities for canon-
ical real-valued U -statistics of order greater than 2. In the context of U -
statistics in Hilbert spaces we will need it already for d = 2.
Lemma 3 (Theorem 5 in [1]). Let Z1, . . . , Zn be independent random vari-
ables with values in (Σ,F). For i ∈ Nd−1 × In let ai : Σ → R be measurable
functions, such that EZai(Zid) = 0. Then, for all p ≥ 2 we have
ai(Zid))iId−1
‖ ≤ Ld
J∈PId
p(1+deg (J )−d)/2‖(ai(Zid))i‖J
J∈PId−1
p1+(1+deg(J )−d)/2
‖(ai(Zid))iId−1‖
where ‖·‖ denotes the norm of a (d−1)-indexed matrix, regarded as a (d−1)-
linear operator on (l2)
d−1 (thus the ‖ · ‖{1}...{d−1}–norm in our notation).
To prove Theorem 1, we will need to adapt the above lemma to be able
to bound the (K,J )-norms of sums of independent kernels.
Definition 6. We define a partial order ≺ on PI as
I ≺ J
if and only if for all I ∈ I, there exists J ∈ J , such that I ⊆ J .
Lemma 4. Assume that
i E|hi(Xdeci )|2 < ∞. Then for any K ⊆ Id−1 and
J = {J1, . . . , Jk} ∈ PId−1\K and all p ≥ 2,
i ))iId−1
‖K,J (1)
K⊆L⊆Id, K∈PId\L
J∪{K,{d}}≺K∪{L}
p(degK−degJ )/2‖(hi)iId‖L,K
K⊆L⊆Id−1, K∈PId−1\L
J∪{K}≺K∪{L}
p1+(degK−degJ )/2
Edmax
‖(hi)iId−1‖
Remark In the above lemma we slightly abuse the notation, by identifying
for K = ∅ the partition {∅} ∪ J with J .
Given Lemma 3, the proof of Lemma 4 is not complicated, the main idea
is just a change of basis, however due to complicated notation it is quite
difficult to write it directly. We find it more convenient to write the proof
in terms of tensor products of Hilbert spaces.
Let us begin with a classical fact.
Lemma 5. Let H be a separable Hilber space and X a Σ-valued random
variable. Then H ⊗ L2(X) ≃ L2(X,H), where L2(X,H) is the space of
square integrable random variables of the form f(X), f : Σ → H-measurable.
With the above identification, for h ∈ H, f(X) ∈ L2(X), we have h⊗f(X) =
hf(X) ∈ L2(X,H).
Proof of Lemma 4. To avoid problems with notation, which would lengthen
an intuitively easy proof, we will omit some technical details, related to
obvious identification of some tensor product of Hilbert spaces (in the spirit
of Lemma 5). Similarly, when considering linear functionals on a space,
which can be written as a tensor product in several ways, we will switch to
the most convenient notation, without further explanations.
H0 = H ⊗
⊗l∈K (⊕ni=1L2(X
i )] ≃ ⊕|iK |≤nL
2(XdeciK ,H)
and, for j = 1, . . . , k,
Hi = ⊗l∈Jj(⊕ni=1L2(X
i )) ≃ ⊕|iJj |≤nL
2(XdeciJj
In the case K = ∅, we have (using the common convention for empty
products) H0 ≃ H.
For id = 1, . . . , n and fixed value of X
, let Aid be a linear functional on
H̃ = ⊕|iId−1 |≤nL
2(XdeciId−1
,H) ≃ ⊗kj=0Hk, given by (hi(Xdeci ))|iId−1 |≤n ∈ H̃,
with the formula
Aid((giId−1
(XdeciId−1
))iId−1
) = 〈(giId−1 (X
iId−1
))iId−1
, (hi(X
i ))iId−1
|iId−1 |≤n
E{1,...,d−1}〈giId−1 (X
iId−1
), hi(X
i )〉H .
As functions of X
, Aid = Aid(X
) are independent random linear func-
tionals. Thus they determine also random (k + 1)-linear functionals on
⊕kj=0Hk, given by
(h0, h1, . . . , hk) 7→ Aid(h0 ⊗ h1 ⊗ . . .⊗ hk).
If we denote by ‖·‖ the norm of a (k+1)-linear functional, the left hand-side
of (1), can be written as
Aid(X
Moreover, denoting by ‖Aid‖HS the norm of Aid seen as a linear operator on
⊗kj=0Hj (by analogy with the Hilbert-Schmidt norm of a matrix), we have
E‖Aid(X
)‖2HS = ‖(hi)i‖2Id,∅ < ∞,
so the sequence Aid(X
), determines a linear functional A on H̃⊗[⊕nid=1L
⊕|i|≤nL2(Xdeci ,H) ≃ ⊕nid=1L
, H̃), given by the formula
A(g1(X
1 ), . . . , gn(X
n )) =
E[Aid(X
)(gid(X
It is easily seen, that if we interpret the domain of this functional as⊕|i|≤nL2(Xdeci ,H),
then it corresponds to the multimatrix (hi(X
i ))i.
Let us now introduce the following notation, consistent with the defini-
tion of ‖ · ‖J . If T is a linear functional on ⊗mj=0Ej for some Hilbert spaces
Ej , and I = {L1, . . . , Lr} ∈ PIm∪{0}, then let ‖T‖I denote the norm of T
as a r-linear functional on ⊕ri=1[⊗j∈LiEj ], given by
(e1, . . . , er) 7→ T (e1 ⊗ . . .⊗ er).
Now, denotingHk+1 = ⊕nid=1L
), we can apply the above definition
to H̃ ⊗ [⊕nid=1L
)] ≃ ⊗k+1j=0Hj and use Lemma 3 to obtain
Aid(X
∥ ≤Ld
I∈PIk+1∪{0}
p(1+deg (I)−(k+2))/2‖A‖I
I∈PIk∪{0}
p1+(1+deg(I)−(k+2))/2
‖Aid(X
)‖2I .
This inequality is just the statement of the Lemma, which follows from
,,associativity” of the tensor product and its ,,distributivity” with respect
to the simple sum of Hilbert spaces. Indeed, denoting Jk+1 = {d}, we have
for 0 /∈ Li and U =
⊗j∈LiHj ≃ ⊗j∈Li ⊗l∈Jj (⊕ns=1L2(X(l)s )) ≃ ⊗l∈U (⊕ns=1L2(X(l)s )) ≃ ⊕|iU |≤nL
2(XdeciU ).
Similarly, if 0 ∈ Li,
⊗j∈LiHj ≃ [⊕|iK |≤nL
2(XdeciK ,H)]× [⊗06=j∈Li ⊗l∈Jj (⊕
2(X(l)s ))]
≃ ⊕|iU |≤nL
2(XdeciU ,H),
where U = (
06=j∈Li
Jj) ∪ K. Using the fact that for fixed X(d)id , Aid
corresponds to the multimatrix (hi(X
i ))|iId−1 |≤n
, and A corresponds to
(hi(X
i ))|i|≤n, we can see, that each summand ‖ · ‖I on the right hand side
of (2) is equal to some summand ‖ · ‖L,K on the right hand side of (1). In-
formally speaking and abusing slightly the notation (in the case K = ∅), we
,,merge” the elements of the partition {{d}, J1, . . . , Jk,K} or {J1, . . . , Jk,K}
in a way described by the partition I, thus obtaining the partition {L}∪K,
where L is the set corresponding in the new partition to the set Li ∈ I,
containing 0 (in particular, if K = ∅ and {0} ∈ I, then L = ∅). Let us also
notice, that deg(I) = deg(K) + 1, hence
1 + deg(I)− (k + 2) = deg(K)− deg(J ),
which shows, that also the powers of p on the right hand sides of (1) and
(2) are the same, completing the proof.
Proof of Theorem 1. For d = 1, the theorem is an obvious consequence of
Lemma 1. Indeed, since | · | = sup|φ|≤1 |φ(·)|, and we can restrict the supre-
mum to a countable set of functionals, we have
hi(Xi)|p ≤ Lp
hi(Xi)|)p + pp/2 sup
|φ|≤1
E〈φ, hi(Xi)〉2)p/2
+ ppEmax
|hi(Xi)|p
But E|
i hi(Xi)| ≤
i hi(Xi)|2 =
i E|hi(Xi)|2 = ‖(hi)i‖{1},∅
and we also have sup|φ|≤1(
i E〈φ, hi(Xi)〉2)1/2 = ‖(hi)i‖∅,{1} and maxi |hi(Xi)| =
maxi ‖hi‖∅,∅.
We will now proceed by induction with respect to d. Assume that the
theorem is true for all integers smaller than d ≥ 2 and denote Ĩc = Ic\{d}
for I ⊆ Id. Then, applying it for fixed X(d)id to the array of functions
hi(x1, . . . , xd−1,X
)iId−1
, we get by the Fubini theorem
i )|p
K⊆I⊆Id−1
J∈PI\K
pp(#Ĩ
c+degJ /2)
EIc‖(
hi)iI‖
where we have replaced the maxima in iIc by sums (we can afford this
apparent loss, since we will be able to fix it with Lemma 2). Now, from
Lemma 1 (applied to Ed) it follows that
hi)iI‖
K,J ≤ L
(Ed‖(
hi)iI‖K,J )p + pp/2‖(hi)iI∪{d}‖
K,J∪{{d}}
Ed‖(hi)iI‖
Since Ĩc = (I ∪ {d})c, degJ ∪ {{d}} = degJ + 1 and #Ic = #Ĩc + 1,
combining the above inequalities gives
i )|p ≤ L
K⊆I⊆Id
J∈PI\K
pp(#I
c+degJ /2)
‖(hi)iI‖
K⊆I⊆Id−1
J∈PI\K
pp(#Ĩ
c+degJ /2)
(Ed‖(
hi)iI‖K,J )p
By applying Lemma 4 to the second sum on the right hand side, we get
i )|p ≤ L
K⊆I⊆Id
J∈PI\K
pp(#I
c+degJ /2)
‖(hi)iI‖
We can now finish the proof using Lemma 2. We apply it to EIc for
I 6= Id, with #Ic instead of d and p/2 instead of p (for p = 2 the theorem is
trivial, so we can assume that p > 2) and α = 2#Ic + degJ +#Ic. Using
the fact that (p/2)α#I
c ≤ Lpd and E‖(hi)iI‖2K,J ≤
EI |hi|2, we get
‖(hi)iI‖
K,J ≤ p
−αp/2L̃
pαp/2EIc max
‖(hi)iI‖
p#Jp/2EJ max
iIc\J
EIc\J‖(hi)iI‖2K,J
≤ L̄pd
EIc max
‖(hi)iI‖
+ p−(#I
c+degJ /2)p max
EJ max
EJc |h(Xdeci )|2)p/2
EIc max
‖(hi)iI‖
K,J + p
−(#Ic+degJ /2)p max
EJ max
‖(hi)iJc‖
which allows us to replace the sums in iIc on the right-hand side of (3) by
the corresponding maxima, proving the inequality in question.
Theorem 1 gives a precise estimate for moments of canonical Hilbert
space valued U -statistics. In the sequel however we will need a weaker
estimate, using the ‖·‖K,J norms only for I = Id and specialized to the case
hi = h. Before we formulate a proper corollary, let us introduce
Definition 7. Let h : Σd → H be a canonical kernel. Let moreover X1,X2, . . . ,Xd
be i.i.d random variables with values in Σ. Denote X = (X1, . . . ,Xd) and
for J ⊆ Id, XJ = (Xj)j∈J . For K ⊆ I ⊆ Id and J = {J1, . . . , Jk} ∈ PI\K ,
we define
‖h‖K,J = sup
EI〈h(X), g(XK )〉
fj(XJj ) : g : Σ
#K → H, E|g(XK)|2 ≤ 1,
fj : Σ
#Jj → R, Efj(XJj ))2 ≤ 1, j = 1, . . . , k
In other words ‖h‖K,J is the ‖ · ‖K,J of an array (hi)|i|=1, with h(1,...,1) = h.
Remark For I = Id, ‖h‖K,J is a norm, whereas for I ( Id, it is a random
variable, depending on XIc .
It is also easy to see that if all the variables X
i are i.i.d. and for all
|i| ≤ n we have hi = h, then for any fixed value of iIc ,
‖(hi)|iI |≤n‖K,J = ‖h‖K,Jn
#I/2,
where ‖h‖K,J is defined with respect to any i.i.d. sequence X1, . . . ,Xd of
the form Xj = X
for j ∈ Ic.
We also have ‖h‖K,J ≤
EI |h(X)|2, which together with the above
observations allows us to derive the following
Corollary 1. For all p ≥ 2, we have
h(Xdeci )|p ≤L
J∈PId\K
ppdegJ /2ndp/2‖h‖pK,J
pp(d+#I
c)/2n#Ip/2EIc max
(EI |h(Xdeci )|2)p/2
The Chebyshev inequality gives the following corollary for bounded ker-
Corollary 2. If h is bounded, then for all t ≥ 0,
h(Xdeci )| ≥ Ld(nd/2(E|h|2)1/2 + t)
Ld exp
K(Id,J∈PId\K
nd/2‖h‖K,J
)2/deg(J ))
n#I/2‖(EI |h|2)1/2‖∞
)2/(d+#Ic))]
Before we formulate the version of exponential inequalities that will be
useful for the analysis of the LIL, let us recall the classical definition of
Hoeffding projections.
Definition 8. For an integrable kernel h : Σd → H, define πdh : Σk → R
with the formula
πdh(x1, . . . , xk) = (δx1 −P)× (δx2 −P)× . . .× (δxd −P)h,
where P is the law of X1.
Remark It is easy to see that πkh is canonical. Moreover πdh = h iff h is
canonical.
The following Lemma was proven for H = R in [2] (Lemma 1). The
proof given there works for an arbitrary Banach space.
Lemma 6. Consider an arbitrary family of integrable kernels hi : Σ
d → H,
|i| ≤ n. For any p ≥ 1 we have
|i|≤n
πdhi(X
|i|≤n
ǫdeci hi(X
In the sequel we will use exponential inequalities to U -statistics gener-
ated by πdh, where h will be a non-necessarily canonical kernel of order
d. Since the kernel h̃((ε1,X1), . . . , (εd,Xd)) = ε1 · · · εdh(X1, . . . ,Xd), where
εi’s are i.i.d. Rademacher variables independent of Xi’s is always canoni-
cal, Corollary 1, Lemma 6 and the Chebyshev inequality give us also the
following corollary (note that ‖h̃‖K,J = ‖h‖K,J )
Corollary 3. If h is bounded, then for all p ≥ 0,
πdh(X
≥ Ld(nd/2(E|h|2)1/2 + t)
Ld exp
K(Id,J∈PId\K
nd/2‖h‖K,J
)2/ deg(J ))
n#I/2‖(EI |h|2)1/2‖∞
)2/(d+#Ic))]
4 The equivalence of several LIL statements
In this section we will recall general results on the correspondence of various
statements of the LIL. We will state them without proofs, since all of them
have been proven in [9] and [2] in the real case and the proofs can be directly
transferred to the Hilbert space case, with some simple modifications that
we will indicate.
Before we proceed, let us introduce the assumptions and notation com-
mon for the remaining part of the article.
• We assume that (Xi)i∈N, (X(k)i )i∈N,1≤k≤d are i.i.d. and h : Σd → H is
a measurable function.
• Recall that (εi)i∈N, (ε(k)i )i∈N,1≤k≤d are independent Rademacher vari-
ables, independent of (Xi)i∈N, (X
i )i∈N,1≤k≤d.
• To avoid technical problems with small values of h let us also define
LLx = loglog (x ∨ ee).
• We will also occasionally write X for (X1, . . . ,Xd) and for I ⊆ Id,
XI = (Xi)i∈I . Sometimes we will write simply h instead of h(X).
• We will use the letter K to denote constants depending only on the
function h.
We will need the following simple fact
Lemma 7. If E|h|2/(LL|h|)d = K < ∞ then E(|h|2∧u) ≤ L(loglog u)d with
L depending only on K and d.
The next lemma comes from [9]. It is proven there for H = R but the
argument is valid also for general Banach spaces.
Lemma 8. Let h : Σd → H be a symmetric function. There exist constants
Ld, such that if
lim sup
(nloglog n)d/2
i∈Idn
h(Xi)
∣ < C a.s., (4)
|i|≤2n
ǫdeci h(X
∣ ≥ D2nd/2 logd/2 n
< ∞ (5)
for D = LdC.
Lemma 9. For a symmetric function h : Σd → H, the LIL (4) is equivalent
to the decoupled LIL
lim sup
(nloglog n)d/2
i∈Idn
h(Xdeci )
∣ < D a.s., (6)
meaning that (4) implies (6) with D = LdC, and conversely (6) implies (4)
with C = LdD.
Proof. This is Lemma 8 in [2]. The proof is the same as there, one needs only
to replace l∞ with l∞(H) – the space of bounded H-valued sequences.
The next lemma also comes from [2] (Lemma 9). Although stated for real
kernels, its proof relies on an inductive argument with a stronger, Banach-
valued hypothesis.
Lemma 10. There exists a universal constant L < ∞, such that for any
kernel h : Σd → H we have
|j|≤n
i : ik≤jk,k=1...d
h(Xdeci )
∣ ≥ t
≤ LdP
|i|≤n
h(Xdeci )
∣ ≥ t/Ld
Corollary 4. Consider a kernel h : Σd → H and α > 0. If
|i|≤2n
h(Xdeci )| ≥ C2nα logα n) < ∞,
lim sup
(nloglog n)α
|i|≤2n
h(Xdeci )
∣ ≤ Ld,αC a.s.
Proof. Given Lemma 10, the proof is the same as the one for real kernels,
presented in [2] (Corollary 1 therein).
The next lemma shows that the contribution to a decoupled U-statistic
from the ’diagonal’, i.e. from the sum over multiindices i /∈ Idn is negligible.
The proof given in [2] (Lemma 10) is still valid, since the only part which
cannot be directly transferred to the Banach space setting is the estimate of
variance of canonical U-statistics, which is the same in the real and general
Hilbert space case.
Lemma 11. If h : Σd → H is canonical and satisfies
E(|h|2 ∧ u) = O((loglog u)β),
for some β, then
lim sup
(nloglog n)d/2
|i|≤n
∃j 6=kij=ik
h(Xdeci )
∣ = 0 a.s. (7)
Corollary 5. The randomized decoupled LIL
lim sup
(nloglog n)d/2
|i|≤n
ǫdeci h(X
∣ < C (8)
is equivalent to (5), meaning then if (8) holds then so does (5) with D = LdC
and (5) implies (8) with C = LdD.
The proof is the same as for the real-valued case, given in [2] (Corollary
2), one only needs to replace h2 by |h|2 and use the formula for the second
moments in Hilbert spaces.
Corollary 6. For a symmetric, canonical kernel h : Σd → H, the LIL (4)
is equivalent to the decoupled LIL ’with diagonal’
lim sup
(nloglog n)d/2
|i|≤n
h(Xdeci )
∣ < D (9)
again meaning that there are constants Ld such that if (4) holds for some D
then so does (9) for D = LdC, and conversely, (9) implies (4) for C = LdD.
Proof. The proof is the same as in the real case (see [2], Corollary 3). Al-
though the integrability of the kernel guaranteed by the LIL is worse in the
Hilbert space case, it still allows one to use Lemma 11.
5 The canonical decoupled case
Before we formulate the necessary and sufficient conditions for the bounded
LIL in Hilbert spaces, we need
Definition 9. For a canonical kernel h : Σd → H, K ⊆ Id, J = {J1, . . . , Jk} ∈
PId\K and u > 0 we define
‖h‖K,J ,u = sup{E〈h(X), g(XK )〉
fi(XJi) : g : Σ
K → H,
fi : Σ
Ji → R, ‖g‖2, ‖fi‖2 ≤ 1, ‖g‖∞, ‖fi‖∞ ≤ u},
where for K = ∅ by g(XK) we mean an element g ∈ H, and ‖g‖2 denotes
just the norm of g in H (alternatively we may think of g as of a random
variable measurable with respect to σ((Xi)i∈∅), hence constant). Thus the
condition on g becomes in this case just |g| ≤ 1.
Example For d = 2, the above definition reads as
‖h(X1,X2)‖∅,{{1,2}},u = sup{|Eh(X1,X2)f(X1,X2)| :
Ef(X1,X2)
2 ≤ 1, ‖f‖∞ ≤ u},
‖h(X1,X2)‖∅,{{1}{2}},u = sup{|Eh(X1,X2)f(X1)g(X2)| :
Ef(X1)
2,Eg(X2)
2 ≤ 1
‖f‖∞, ‖g‖∞ ≤ u},
‖h(X1,X2)‖{1},{{2}},u = sup{E〈f(X1), h(X1,X2)〉g(X2) :
E|f(X1)|2,Eg(X2)2 ≤ 1
‖f‖∞, ‖g‖∞,≤ u}
‖h(X1,X2)‖{1,2},∅,u = sup{E〈f(X1,X2), h(X1,X2)〉 :
E|f(X1,X2)|2 ≤ 1, ‖f‖∞ ≤ u}.
Theorem 2. Let h be a canonical H-valued symmetric kernel in d variables.
Then the decoupled LIL
lim sup
nd/2(loglog n)d/2
|i|≤n
h(Xdeci )| < C (10)
holds if and only if
(LL|h|)d < ∞ (11)
and for all K ⊆ Id,J ∈ PId\K
lim sup
(loglog u)(d−deg J )/2
‖h‖K,J ,u < D. (12)
More precisely, if (10) holds for some C then (12) is satisfied for D = LdC
and conversely, (11) and (12) implies (10) with C = LdD.
Remark Using Lemma 7 one can easily check that the condition (12) with
D < ∞ for I = Id is implied by (11).
6 Necessity
The proof is a refinement of ideas from [16], used to study random matrix
approximations of the operator norm of kernel integral operators.
Lemma 12. If a, t > 0 and h is a nonnegative d-dimensional kernel such
that NdEh(X) ≥ ta and ‖EIh(X)‖∞ ≤ N−#Ia for all ∅ ⊆ I ( {1, . . . , d},
∀λ∈(0,1) P(
|i|≤N
h(Xdeci ) ≥ λta) ≥ (1−λ)2
t+ 2d − 1 ≥ (1−λ)
22−d min(1, t).
Proof. We have
|i|≤N
h(Xdeci )
|i|≤N
|j|≤N
Eh(Xdeci )h(X
|i|≤N
|j|≤N :
{k : ik=jk}=I
Eh(Xdeci )h(X
|i|≤N
|j|≤N :
{k : ik=jk}=I
E[h(Xdeci )EIch(X
≤ N2d(Eh(X))2 +
∅6=I⊆Id
Nd+#I
Eh(X)‖EIch(X)‖∞
≤ N2d(Eh(X))2 + (2d − 1)NdaEh(X)
≤ N2d(Eh(X))2 + (2d − 1)t−1N2d(Eh(X))2
≤ t+ 2
d − 1
|i|≤n
h(Xdeci )
The lemma follows now from the Paley-Zygmund inequality (see e.g. [5],
Corollary 3.3.2.), which says that for an arbitrary nonnegative random vari-
able S,
P(S ≥ λS) ≥ (1− λ)2 (ES)
Corollary 7. Let A ⊆ Σd be a measurable set, such that
∀∅(I({1,...,d}∀xIc∈ΣIc PI((xIc ,XI) ∈ A) ≤ N
−#I .
P(∃|i|≤N Xdeci ∈ A) ≥ 2−d min(NdP(X ∈ A), 1).
Proof. We apply Lemma 12 with h = IA, a = 1, t = N
dP(X ∈ A) and
λ → 0+.
Lemma 13. Suppose that Zj are nonnegative r.v.’s, p > 0 and aj ∈ R are
such that P(Zj ≥ aj) ≥ p for all j. Then
Zj ≥ p
aj/2) ≥ p/2.
Proof. Let α := P(
j Zj ≥ p
j aj/2), then
aj ≤ E(
min(Zj , aj)) ≤ α
aj + p
aj/2.
Theorem 3. Let Y be a r.v. independent of X
i . Suppose that for each n,
an ∈ R, hn is a d+ 1-dimensional nonnegative kernel such that
|i|≤2n
i , Y ) ≥ an
Let p > 0, then there exists a constant Cd(p) depending only on p and d
such that the sets
An :=
x ∈ Sd : ∀n≤m≤2d−1n PY (hm(x, Y ) ≥ Cd(p)2d(n−m)am) ≥ p
satisfy
2dnP(X ∈ An) < ∞.
Proof. We will show by induction on d, that the assertion holds with C1(p) :=
1, C2(p) := 12/p and
Cd(p) := 12p
−1 max
1≤l≤d−1
Cd−l(2
−l−4p/3) for d = 3, 4, . . . .
For d = 1 we have
min(2nP(X ∈ An), 1) ≤ P(∃|i|≤2n Xdeci ∈ An)
= P(∃|i|≤2n PY (hn(Xdeci , Y ) ≥ an) ≥ p)
≤ P(PY (
|i|≤2n
i , Y ) ≥ an) ≥ p)
≤ p−1P(
|i|≤2n
i , Y ) ≥ an).
Before investigating the case d > 1 let us define
Ãn := An \
The sets Ãn are pairwise disjoint and obviously Ãn ⊂ An. Notice that
since Cd(p) ≥ 1,
P(X ∈ An) ≤ P(PY (hn(X,Y ) ≥ an)) ≤ p−1P(
|i|≤2n
i , Y ) ≥ an).
Hence
n P(X ∈ An) < ∞, so P(X ∈ lim supAn) = 0. But if x /∈
lim supAn, then
ndIAn(x) ≤
nd+1I
(x). So it is enough to show
2dnP(X ∈ Ãn) < ∞.
Induction step Suppose that the statement holds for all d′ < d, we will
show it for d. First we will inductively construct sets
Ãn = A
n ⊃ A1n ⊃ . . . ⊃ Ad−1n
such that for 1 ≤ l ≤ d− 1,
∀∅(I({1,...,d−1}, #I≤l ∀xIc PI((xIc ,XI) ∈ A
n) ≤ 2−n#I (13)
2ndP(X ∈ Al−1n \Aln) < ∞. (14)
Suppose that 1 ≤ l ≤ d − 1 and the set Al−1n was already defined. Let
I ⊂ {1, . . . , d} be such that #I = l and let j ∈ I. Notice that
PI((xIc ,XI) ∈ Al−1n ) = EjPI\{j}((xIc ,Xj ,XI\{j}) ∈ Al−1n ) ≤ 2−n(l−1)
by the property (13) of the set Al−1n . Let us define for n(l− 1)+1 ≤ k ≤ nl,
BIn,k := {xIc : PI((xIc ,XI) ∈ Al−1n ) ∈ (2−k, 2−k+1]}
BIn :=
k=n(l−1)+1
BIn,k = {xIc : PI((xIc ,XI) ∈ Al−1n ) > 2−nl}.
We have
2dnP(X ∈ Al−1n ,XIc ∈ BIn) ≤ 2
k=n(l−1)+1
2dn−kP(XIc ∈ BIn)
= 2EkI1(XIc),
where
kI1(xIc) :=
k=n(l−1)+1
2dn−kIBI
(xIc).
Let m ≥ 1 and
CIm := {xIc : 2(m+1)(d−l) > k1(xIc) ≥ 2m(d−l)}.
Notice that for n > m and k ≤ nl, 2dn−k ≥ 2(d−l)(m+1), moreover
n<m/2
k=n(l−1)+1
2dn−k ≤
n<m/2
2(d−l+1)n ≤ 4
2(d−l+1)(m−1)/2 ≤ 2
2(d−l)m.
Hence
xIc ∈ CIm ⇒
m/2≤n≤m
k=n(l−1)+1
2dn−kIBI
(xIc) ≥
2(d−l)m. (15)
Let m ≤ r ≤ 2d−2m, if m/2 ≤ n ≤ m, then since Al−1n ⊂ An we have for all
x ∈ Sd,
PY (hr(x, Y ) ≥ Cd(p)2d(n−r)arIAl−1n (x)) ≥ p,
therefore, since Al−1n ⊂ Ãn are pairwise disjoint,
hr(x, Y ) ≥ Cd(p)2−drar
m/2≤n≤m
Al−1n
Hence, by Lemma 13,
|iI |≤2r
hr(xIc ,X
, Y ) ≥ p
Cd(p)2
−drar
|iI |≤2r
k2,xIc (X
, (16)
where
k2,xIc (xI) :=
m/2≤n≤m
(xIc , xI).
We have ‖k2,xIc‖∞ ≤ 2dm and for ∅ 6= J ( I, by the property (13) of
Al−1n ,
EJk2,xIc (xI\J ,XJ ) =
m/2≤n≤m
2dnPJ
(xIc , xI\J ,XJ) ∈ Al−1n
m/2≤n≤m
2(d−#J)n ≤ 2(d−#J)m+1.
Moreover for xIc ∈ CIm, by the definition of BIn,k and (15),
Ek2,xIc (XI) ≥
m/2≤n≤m
k=n(l−1)+1
2dnPI((xIc ,XI) ∈ Al−1n )IBI
(xIc)
m/2≤n≤m
k=n(l−1)+1
2dn−kIBI
(xIc) ≥
2(d−l)m.
Therefore by Lemma 12 (with l instead of d and a = 2(d−l)m+rl+1, t =
1/6, N = 2r, λ = 1/2), for m ≤ r ≤ 2d−2m,
|iI |≤2r
k2,xIc (X
) ≥ 1
2(d−l)m+rl
2−l−3.
Combining the above estimate with (16) we get (for xIc ∈ CIm and m ≤ r ≤
2d−2m),
|iI |≤2r
hr(xIc ,X
, Y ) ≥ p
Cd(p)2
(d−l)(m−r)ar
2−l−4p.
Let us define Ỹ := ((X
i )j∈I , Y ) and h̃n(xIc , Ỹ ) :=
|iI |≤2n
hn(xIc ,X
, Y ).
|iIc |≤2
h̃n(X
, Ỹ ) ≥ an) =
|i|≤2n
i , Y ) ≥ an) < ∞.
Moreover (since Cd(p) ≥ 12p−1Cd−l(2−l−4p/3)),
CIm ⊆
∀m≤r≤2d−2m PỸ (h̃r(xIc , Ỹ ) ≥ Cd−l(2
−l−4p/3)2(d−l)(m−r)ar) ≥ 2−l−4p/3
Hence by the induction assumption,
2(d−l)mP(XIc ∈ CIm) < ∞,
so EkI1(XIc) < ∞ and thus
∀#I=l
2dnP(X ∈ Al−1n ,XIc ∈ BIn) < ∞. (17)
We set
Aln := {x ∈ Al−1n : xIc /∈ BIn for all I ⊂ {1, . . . , d},#I = l}.
The set Aln satisfies the condition (13) by the definition of B
n and the
property (13) for Al−1n . The condition (14) follows by (17).
Notice that the set Ad−1n satisfies the assumptions of Corollary 7 with
N = 2n, therefore if Cd(p) ≥ 1,
2−d min(1, 2ndP(X ∈ Ad−1n )) ≤ P(∃|i|≤2n Xdeci ∈ Ad−1n ) ≤ P(∃|i|≤2n Xdeci ∈ Ãn)
≤ P(∃|i|≤2n PY (hn(Xdeci , Y ) ≥ Cd(p)an) ≥ p)
≤ P(PY (
|i|≤2n
i , Y ) ≥ an) ≥ p)
≤ p−1P(
|i|≤2n
i , Y ) ≥ an).
Therefore
ndP(X ∈ Ad−1n ) < ∞, so by (14) we get
X ∈ Ãn) =
P(X ∈ Al−1n \ Aln) + P(X ∈ Ad−1n )
Corollary 8. If
|i|≤2n
h2(Xdeci ) ≥ ε2nd(log n)α
for some ε > 0 and α ∈ R,
then E h
(LL|h|)α
Proof. We apply Theorem 3 with hn = h
2 and an = ε2
nd logd n in the
degenerate case when Y is deterministic. It is easy to notice that h2 ≥
C̃d(p, ε)2
dn logd n implies that
∀n≤m≤2d−1n h2 ≥ Cd(p)2d(n−m)am.
To prove the necessity part of Theorem 2 we will also need the following
Lemmas
Lemma 14 ([2], Lemma 12). Let g : Σd → R be a square integrable function.
|i|≤n
g(Xdeci )) ≤ (2d − 1)n2d−1Eg(X)2.
Lemma 15 ([2], Lemma 5). If E(|h|2 ∧ u) = O((loglog u)β) then
E|h|1{|h|≥s} = O(
(loglog s)β
Lemma 16. Let (ai)i∈Idn be a d–indexed array of vectors from a Hilbert space
H. Consider a random variable
|i|≤n
|i|≤n
For any set K ⊆ Id and a partition J = {J1, . . . , Jm} ∈ PId\K let us define
‖(ai)‖∗K,J ,p := sup
|i|≤n
〈ai, α(0)iK 〉
|α(0)iK |
2 ≤ 1,
)2 ≤ p,
∀imaxJk∈In
)2 ≤ 1, k = 1, . . . ,m
where ⋄J = J\{max J} (here
ai = ai).
Then, for all p ≥ 1,
‖S‖p ≥
K⊆Id,J∈PId\K
‖(ai)‖∗K,J ,p.
In particular for some constant cd
P(S ≥ cd
K⊆Id,J∈PId\K
‖(ai)‖∗K,J ,p) ≥ cd ∧ e−p.
Remark For K = ∅, we define
‖(ai)‖∗∅,J ,p := sup
|i|≤n
∈ R(I
)2 ≤ p,
∀imaxJk∈In
)2 ≤ 1, k = 1, . . . ,m
It is also easy to see that for a d-indexed matrix, ‖(ai)i‖Id,{∅},p =
i |ai|2 =
‖S‖2 and thus does not depend on p. Since it will not be important in the
applications, we keep a uniform notation with the subscript p.
Examples For d = 1, we have
‖(ai)i≤n‖∗∅,{{1}},p = sup
α2i ≤ p, |αi| ≤ 1, i = 1, . . . , n
‖(ai)i≤n‖∗{1},∅,p = sup
〈ai, αi〉 :
|αi|2 ≤ 1
|ai|2,
whereas for d = 2, we get
‖(aij)i,j≤n‖∗∅,{{1},{2}},p = sup
i,j=1
aijαiβj
α2i ≤ p,
β2j ≤ p,
∀i∈In |αi| ≤ 1,∀j∈In |βj | ≤ 1
‖(aij)i,j≤n‖∗∅,{I2},p = sup
i,j=1
aijαij
i,j=1
α2ij ≤ p,∀j∈In
α2ij ≤ 1
‖(aij)i,j≤n‖∗{1},{{2}},p = sup
i,j=1
〈aij , αi〉βj
|αi|2 ≤ 1,
β2j ≤ p,∀j∈In|βj | ≤ 1
‖(aij)i,j≤n‖∗I2,∅,p = sup
i,j=1
〈aij , αij〉
i,j=1
α2ij ≤ 1
|aij |2.
Proof of Lemma 16. We will combine the classical hypercontractivity prop-
erty of Rademacher chaoses (see e.g. [5], p. 110-116) with Lemma 3 in [2],
which says that for H = R we have
‖S‖p ≥
J∈PId
‖(ai)‖∅,J ,p. (18)
Since ‖(ai)‖Id,{∅},p =
i |ai|2 = ‖S‖2, the inequality ‖S‖p ≥ L−1‖(ai)‖Id,{∅},p
is just Jensen’s inequality (p ≥ 2) or the aforesaid hypercontractivity of
Rademacher chaos (p ∈ (1, 2)). On the other hand, for K 6= Id and
J ∈ PId\K , we have
‖S‖p =
EId\KEK
iId\K
p)1/p
EId\K
iId\K
2)p/2)1/p
EId\K sup
iId\K
〈α(0)iK , ai〉
p)1/p
EId\K
iId\K
〈α(0)iK , ai〉
p)1/p
L#KLd−#K
〈α(0)iK , ai〉)iId\K
∅,J ,p
L#KLd−#K
‖(ai)‖K,J ,p,
where the first inequality follows from hypercontractivity applied condition-
ally on (ε
i )k/∈K,i∈In, the second is Jensen’s inequality and the third is (18)
applied for a chaos of order d−#K.
The tail estimate follows from moment estimates by the Paley-Zygmund
inequality and the inequality ‖(ai)‖K,J ,tp ≤ tdegJ ‖(ai)‖K,J ,p for t ≥ 1 just
like in [12, 18].
Proof of necessity. First we will prove the integrability condition (11). Let
us notice that by classical hypercontractive estimates for Rademacher chaoses
and the Paley-Zygmund inequality (or by Lemma 16), we have
|i|≤2n
ǫdeci h(X
|i|≤2n
h(Xdeci )
for some constant cd > 0. By the Fubini theorem it gives
|i|≤2n
ǫdeci h(X
≥ D2nd/2 logd/2 n
≥ cdP
|i|≤2n
h(Xdeci )
2 ≥ D2c−2d 2
nd logd n
which together with Lemma 8 yields
|i|≤2n
h(Xdeci )
2 ≥ D2c−2
2nd logd n
The integrability condition (11) follows now from Corollary 8.
Before we proceed to the proof of (12), let us notice that (11) and Lemma
7 imply that
E(|h|2 ∧ u) ≤ K(loglog u)d (19)
for n large enough. The proof of (12) can be now obtained by adapting the
argument for the real valued case.
Since limn→∞
= log 2, (5) implies that there exists N0, such that
for all N > N0, there exists N ≤ n ≤ 2N , satisfying
|i|≤2n
ǫdeci h(X
> LdC2
nd/2 logd/2 n
. (20)
Let us thus fix N > N0 and consider n as above. Let K ⊆ Id, J =
{J1, . . . , Jk} ∈ PId\K . Let us also fix functions g : Σ#K → H, fj : Σ#Jj → R,
j = 1, . . . , k, such that
‖g(Xk)‖2 ≤ 1, ‖g(XK )‖∞ ≤ 2n/(2k+3),
‖fj(XJj )‖2 ≤ 1, ‖fj(XJj)‖∞ ≤ 2n/(2k+3).
The Chebyshev inequality gives
|iJj |≤2
)2 log n ≤ 10 · 2d2#Jjn log n) ≥ 1− 1
10 · 2d . (21)
Similarly, if K 6= ∅,
|iK |≤2n
|g(XdeciK )|
2 ≤ 10 · 2d2#Kn) ≥ 1− 1
10 · 2d (22)
and for K = ∅, |g| ≤ 1 (recall that for K = ∅, the function g is constant).
Moreover for j = 1, . . . , k and sufficiently large N ,
|i⋄Jj |≤2
2n#Jj
)2 · log n ≤ 2
n#⋄Jj22n/(2k+3) log n
2n#Jj
2n/(2k+3) log n
Without loss of generality we may assume that the sequences (X
i )i,j
and (ε
i )i,j are defined as coordinates of a product probability space. If for
each j = 1, . . . , k we denote the set from (21) by Ak, and the set from (22)
by A0, we have P(
j=0Ak) ≥ 0.9. Recall now Lemma 16. On
j=0Ak we
can estimate the ‖ · ‖∗K,J ,logn norms of the matrix (h(Xdeci ))|i|≤2n by using
the test sequences
log n
101/22d/22n#Jj/2
for j = 1, . . . , k and
g(XdeciK )
101/22d/22n#K/2
Therefore with probability at least 0.9 we have
‖(h(Xdeci ))|i|≤2n‖∗K,J ,logn (23)
≥ (log n)
2d(k+1)/210(k+1)/22
j #Jj)n/2
|i|≤2n
〈g(XdeciK ), h(X
(log n)k/2
2d(k+1)/210(k+1)/22dn/2
|i|≤2n
〈g(XdeciK ), h(X
Our aim is now to further bound from below the right hand side of
the above inequality, to have, via Lemma 16, control from below on the
conditional tail probability of
|i|≤2n ǫ
i h(X
i ), given the sample (X
From now on let us assume that
|E〈g(XK), h(X)〉
fj(XJj )| > 1. (24)
The Markov inequality, (19) and Lemma 15 give
|i|≤2n
〈g(XK), h(XdeciK )〉1{|h(Xdeci )|>2n}
2nd|E〈g, h〉
j=1 fj|
2nd(‖g‖∞
j=1 ‖fj‖∞) · E|h|1{|h|>2n}
2nd|E〈g, h〉
j=1 fj|
≤ 42n(k+1)/(2k+3)E|h|1{|h|>2n}
≤ 4K (log n)
n(k+2)
. (25)
Let now hn = h1{|h|≤2n}. By the Chebyshev inequality, Lemma 14 and (19)
|i|≤2n
〈g(XdeciK ),hn(X
)− 2ndE〈g, hn〉
|E〈g, hn〉
|i|≤2n〈g(XdeciK ), hn(X
j=1 fj(X
22nd|E〈g, hn〉
j=1 fj|2
≤ 25 (2
d − 1)2n(2d−1)
22nd|E〈g, hn〉
j=1 fj|2
E|〈g, hn〉
≤ 25(2d − 1) 2
2n(k+1)/(2k+3)E|hn|2
2n|E〈g, hn〉
j=1 fj|2
≤ 25K(2d − 1) log
2n/(2k+3)|E〈g, hn〉
j=1 fj|2
. (26)
Let us also notice that for large n, by (19), Lemma 15 and (24)
|E〈g, hn〉
fj| ≥ |E〈g, h〉
fj| − |E〈g, h〉1{|h|>2n}
≥ |E〈g, h〉
fj| − 2n(k+1)/(2k+3)K
(log n)d
|E〈g, h〉
fj| ≥
Inequalities (25), (26) and (27) imply, that for large n with probability
at least 0.9 we have
|i|≤2n
〈g(XdeciK ), h(X
|i|≤2n
〈g(XdeciK ), hn(X
|i|≤2n
〈g(XdeciK ), h(X
i )〉1{|h(Xdec
)|>2n}
≥ 2nd
|E〈g, hn〉
fj| −
|E〈g, h〉
≥ 2nd
|E〈g, h〉
fj| −
|E〈g, h〉
|E〈g, h〉
fj |.
Together with (23) this yields that for large n with probability at least
‖(hi)|i|≤2n‖∗K,J ,logn ≥
2nd/2 logk/2 n
4 · 2d(k+1)/210(k+1)/2
|E〈g, h〉
Thus, by Lemma 16, for large n
|i|≤2n
ǫdeci h(X
∣ ≥ cd
2nd/2 logk/2 n
4 · 2d(k+1)/210(k+1)/2
|E〈g, h〉
which together with (20) gives
|E〈g, h〉
fj| ≤ LdC
4 · 2d(k+1)/210(k+1)/2
log(d−k)/2 n.
In particular for sufficiently large N , for arbitrary functions g : Σ#K → H,
fj : Σ
#Jj → R, j = 1, . . . , k, such that
‖g(XK)‖∞, ‖fj(XJj )‖2 ≤ 1,
‖g(XK)‖2, ‖fj(XJj )‖∞ ≤ 2N/(2k+3)
we have
|E〈g, h〉
fj| ≤ LdC
4 · 2d(k+1)/210(k+1)/2
log(d−k)/2 n ≤ L̃dC log(d−k)/2 N,
which clearly implies (12).
7 Sufficiency
Lemma 17. Let H = H(X1, . . . ,Xd) be a nonnegative random variable,
such that EH2 < ∞. Then for I ⊆ Id, I 6= ∅,Id,
2l+#I
PIc(EIH
2 ≥ 22l+#Icn) < ∞.
Proof.
2l+#I
PIc(EIH
2 ≥ 22l+#Icn) =
2lEIc
1{EI |H|2≥22l+#I
21−lEIcEIH
2 ≤ 4EH2 < ∞.
Lemma 18. Let X = (X1, . . . ,Xd) and X̃(I) = ((Xi)i∈I , (X
i )i∈Ic). De-
note H = |h|/(LL|h|)d/2. If E|H|2 < ∞ and hn = h1An , where
x : |h(x)|2 ≤ 2nd logd n and ∀I 6=∅,Id EIH
2 ≤ 2#Icn
then for I ⊆ Id, I 6= ∅, we have
2−n#I
log2d n
E[|hn(X)|2|hn(X̃(I))|2] < ∞.
Proof. a) I = Id
E|hn|4
2nd log2d n
≤ E|h|4
2nd log2d n
1{|h|2≤2nd logd n}
≤ LdE|h|4
|h|2(LL|h|)d < ∞.
b) I 6= Id, ∅. Let us denote by EI ,EIc , ẼIc respectively, the expectation
with respect to (Xi)i∈I , (Xi)i∈Ic and (X
i )i∈Ic . Let also h̃, h̃n stand
for h(X̃(I)), hn(X̃(I)) respectively. Then
E(|hn|2 · |h̃n|2)
2n#I log2d n
E(|hn|2 · |h̃n|21{|h|≤|h̃|})
2n#I log2d n
|h|2|h̃|21
{|h|≤|h̃|}
2n#I log2d n
{EIc |h|
{|h|2≤22nd}
#In logd n, |h̃|2≤22nd}
|h|2|h̃|21
{|h|≤|h̃|}
2n#I log2d n
1{EIc |h|21{|h|2≤|h̃|2}≤Ld2
#In logd n, |h̃|2≤22nd}
≤ L̃dE
|h|2|h̃|21
{|h|≤|h̃|}
(EIc |h|21{|h|2≤|h̃|2})(LL|h̃|)d
= L̃dEI ẼIc
|h̃|2EIc
|h|21
{|h|≤|h̃|}
(EIc |h|21{|h|2≤|h̃|2})(LL|h̃|)d
≤ L̃dE
|h̃|2
(LL|h̃|)d
where to obtain the second inequality, we used the fact that
EIc |h|21{|h|2≤22nd,EIcH2≤2#In}
≤ EIc
(LL|h|)d (loglog 2
nd)d1{EIcH2≤2#In}
≤ LdEIcH21{EIcH2≤2#In} log
d n ≤ Ld2#In logd n.
Lemma 19. Consider a square integrable, nonnegative random variable Y .
Let Yn = Y 1Bn , with Bn =
k∈K(n)Ck, where C0, C1, C2, . . . are pairwise
disjoint subsets of Ω and
K(n) = {k ≤ n : E(Y 21Ck) ≤ 2
k−n}.
(EY 2n )
2 < ∞
Proof. Let us first notice that by the Schwarz inequality, we have
k∈K(n)
E(Y 21Ck)
k∈K(n)
2(n−k)/22(k−n)/2E(Y 21Ck)
k∈K(n)
[2n−k(E(Y 21Ck))
k∈K(n)
[2n−k(E(Y 21Ck))
(EY 2n )
k∈K(n)
[2n−k(E(Y 21Ck))
k : E(Y 21Ck )>0
(E(Y 21Ck))
n : k∈K(n)
k : E(Y 21Ck )>0
(E(Y 21Ck))
2 max
n : k∈K(n)
k : E(Y 21Ck )>0
(E(Y 21Ck))
E(Y 21Ck)
E(Y 21Ck) = 4EY
2 < ∞.
Proof of sufficiency. The proof consists of several truncation arguments.
The first part of it follows the proofs presented in [11] and [2] for the real-
valued case. Then some modifications are required, reflecting the diminished
integrability condition in the Hilbert space case. At each step we will show
|i|≤2n
πdhn(X
∣ ≥ C2nd/2 logd/2 n
< ∞, (28)
with hn = h1An for some sequence of sets An. In the whole proof we keep
the notation H = |h|/(LL|h|)d/2.
Let us also fix ηd ∈ (0, 1), such that the following implication holds
∀n=1,2,... |h|2 ≤ η2d2nd logd n =⇒ H2 ≤ 2nd. (29)
Step 1 Inequality (28) holds for any C > 0 if
x : |h(x)|2 ≥ η2d2nd logd n
We have, by the Chebyshev inequality and the inequality E|πdhn| ≤ 2dE|hn|
(which follows directly from the definition of πd or may be considered a
trivial case of Lemma 6),
|i|≤2n
πdhn(X
∣ ≥ C2nd/2 logd/2 n
|i|≤2n πdhn(X
C2nd/2 logd/2 n
2ndE|h|1
{|h|>ηd2
nd/2 logd/2 n}
C2nd/2 logd/2 n
= 2dC−1E
2nd/2
logd/2 n
{|h|>ηd2
nd/2 logd/2 n}
≤ LdC−1E
(LL|h|)d < ∞.
Step 2 Inequality (28) holds for any C > 0 if
x : |h(x)|2 ≤ η2d2nd logd n, ∃I 6=∅,Id EIH
2 ≥ 2#Icn
As in the previous step, it is enough to prove that
|i|≤2n ǫ
i hn(X
2nd/2 logd/2 n
The set An can be written as
I⊆Id,I 6=Id,∅
An(I),
where the sets An(I) are pairwise disjoint and
An(I) ⊆ {x : |h(x)|2 ≤ 22nd, EIH2 ≥ 2#I
Therefore it suffices to prove that
|i|≤2n ǫ
i h(X
i )1An(I)(X
2nd/2 logd/2 n
< ∞. (30)
Let for l ∈ N,
An,l(I) := {x : |h(x)|2 ≤ 22nd,
22l+2+#I
cn > EIH
2 ≥ 22l+#Icn} ∩An(I).
Then hn1An(I) =
l=0 hn,l, where hn,l := hn1An,l(I) (notice that the sum is
actually finite in each point x ∈ Σd as for large l, x /∈ An,l(I)).
We have
|i|≤2n
ǫdeci hn,l(X
i )| ≤
|iIc |≤2
EIcEI |
|iI |≤2n
ǫdeciI hn,l(X
|iIc |≤2
EIc(EI |
|iI |≤2n
ǫdeciI hn,l(X
i )|2)1/2
≤ 2(#Ic+#I/2)nEIc(EI |hn,l|2)1/2
≤ Ld[2(#I
c+d/2)n+l+1 logd/2 n]PIc(EIH
2 ≥ 22l+#Icn),
where in the last inequality we used the estimate
n,l ≤LdEI [(log n)dH21{22l+2+#Icn>EIH2≥22l+#Icn}]
≤Ld22l+2+#I
cn(log n)d1{EIH2≥22l+#I
Therefore to get (30) it is enough to show that
2l+#I
PIc(EIH
2 ≥ 22l+#Icn) < ∞.
But this is just the statement of Lemma 17.
Step 3 Inequality (28) holds for any C > 0 if
x : |h(x)|2 ≤ η2d2nd logd n, ∀I 6=∅,Id EIH
2 ≤ 2#Icn} ∩
with BIn =
k∈K(I,n)C
k and C
0 = {x : EIH2 ≤ 1}, CIk = {x : 2#I
c(k−1) <
2 ≤ 2#Ick}, k ≥ 1, K(I, n) = {k ≤ n : E(H21CI
) ≤ 2k−n}.
By Lemma 6 and the Chebyshev inequality, it is enough to show that
|i|≤2n ǫ
i hn(X
i )|4
22nd log2d n
The Khintchine inequality for Rademacher chaoses gives
|i|≤2n
ǫdeci hn(X
i )|4 ≤ E(
|i|≤2n
|hn(Xdeci )|2)2
|i|≤2n
|j|≤2n :
{k : ik=jk}=I
E|[hn(Xdeci )|2|hn(Xdecj )|2]
2nd2n(d−#I)E[|hn(X)|2 · |hn(X̃(I))|2],
where X = (X1, . . . ,Xd) and X̃(I) = ((Xi)i∈I , (X
i )i∈Ic).
To prove the statement of this step it thus suffices to show that for all
I ⊆ Id,
S(I) :=
2−n#I
log2d n
E[|hn(X)|2|hn(X̃(I))|2] < ∞. (31)
The case of nonempty I follows from Lemma 18. It thus remains to consider
the case I = ∅. Set H2I = EIH2. We have
S(∅) =
(E|hn|2)2
log2d n
logd n
1An))
2 ≤ Ld
(E(H21An))
(E(H2
))2 ≤ L̃d
(E(H21BIn))
= L̃d
(E(H2I1BIn))
2 < ∞
by Lemma 19, applied for Y 2 = EIH
2, since EH2I = EH
2 < ∞.
Step 4 Inequality (28) holds for some C ≤ LdD if
x : |h(x)|2 ≤ η2d2nd logd n, ∀I 6=∅,IdEIH
2 ≤ 2#Icn} ∩
(BIn)
where BIn is defined as in the previous step.
Let us first estimate ‖(EI |hn|2)1/2‖∞ for I ( Id. We have
EI |hn|2 ≤ EI
|h|21{|h|2≤ηd2nd logd n}
k≤n,k/∈K(I,n)
≤ Ld logd n
k≤n,k/∈K(I,n)
The fact that we can restrict the summation to k ≤ n follows directly from
the definition of An for I 6= ∅ and for I = ∅ from (29).
The sets CIk are pairwise disjoint and thus
‖EI |hn|2‖∞ ≤ (Ld logd n) max
k≤n,k/∈K(I,n)
ck = Ld2
#IckI(n) logd n, (32)
where
kI(n) = max{k ≤ n : k /∈ K(I, n)}.
Therefore for C > 0,
( C2nd/2 logd/2 n
2#In/2‖(EI |hn|2)1/2‖∞
)2/(d+#Ic)]
k≤n,k/∈K(I,n)
( C2nd/2 logd/2 n
2#In/22#I
ck/2 logd/2 n
)2/(d+#Ic)]
n≥k, k /∈K(I,n)
c(n−k)/2
)2/(d+#Ic)]
Notice that for each k the inner series is bounded by a geometric series
with the ratio smaller than some qd,C < 1 (qd,C depending only on d and
C). Therefore the right hand side of the above inequality is bounded by
n≥k, k /∈K(I,n)
c(n−k)/2
)2/(d+#Ic)]
with the convention sup ∅ = 0. But k /∈ K(I, n) implies that 2#Ic(n−k)/2 ≥
(E(H21CI
))−#I
c/2. Therefore the above quantity is further bounded by
C−2/#I
E(H21CI
)−#Ic/(d+#Ic)]
≤ L̄dC−2/#I
E(H21CI
= L̄dC
−2/#IcEH2 < ∞,
where we used the inequality ex ≥ cdxα for all x ≥ 0 and 0 ≤ α ≤ 2d. We
have thus proven that for all I ( Id and C,Ld > 0,
n : An 6=∅
( C2nd/2 logd/2 n
2#In/2‖(EI |hn|2)1/2‖∞
)2/(d+#Ic)]
< ∞. (33)
Now we will turn to the estimation of ‖hn‖J0,J . Let us consider J0 ⊆ Id,
J = {J1, . . . , Jl} ∈ PId\J0 and denote as before X = (X1, . . . ,Xd), XI =
(Xi)i∈I . Recall that
‖hn‖J0,J = sup
E〈hn(X), f0(XJ0)〉
fi(XJi) : E|f0(XJ0)|2 ≤ 1,
Ef2i (XJi) ≤ 1, i ≥ 1
In what follows, to simplify the already quite complicated notation, let
us suppress the arguments of all the functions and write just h instead of
h(X) and fi instead of fi(XJi).
Let us also remark that although f0 plays special role in the definition
of ‖ · ‖J0,J , in what follows the same arguments will apply to all fi’s with
the obvious use of Schwarz inequality for the scalar product in H. We will
therefore not distinguish the case i = 0 and f2i will denote either the usual
power or 〈f0, f0〉, whereas ‖fi‖2 for i = 0 will be the norm in L2(H,XJ0),
which may happen to be equal just H if J0 = ∅.
Since E|fi|2 ≤ 1, i = 0, . . . , l, then for each j = 0, . . . , l and J ( Jj by
the Schwarz inequality applied conditionally to XJj\J
E|〈hn, f0〉
fi1{EJf2j >a
≤ EJj\J
(E(Jj\J)c
f2i )
1{EJf2j ≥a
2}(E(Jj\J)c |hn|
2)1/2
≤ EJj\J
1{EJf2j ≥a
2}(E(Jj\J)c |hn|
2)1/2
≤ Ld2
k(Jj\J)
c(n)#(Jj\J)/2 logd/2 nEJj\J [(EJf
1{EJf2j ≥a
≤ Ld[2
k(Jj\J)
c(n)#(Jj\J)/2 logd/2 n]a−1,
where the third inequality follows from (32) and the last one from the ele-
mentary fact E|X|1{|X|≥a} ≤ a−1E|X|2. This way we obtain
‖hn‖J0,J (34)
≤ sup{E[〈hn, f0〉
fi] : ‖fi‖2 ≤ 1,∀J(Ji ‖(EJf2i )1/2‖∞ ≤ 2n#(Ji\J)/2}
2(k(Ji\J)c(n)−n)#(Ji\J)/2 logd/2 n
≤ sup{E[〈hn, f0〉
fi] : ‖fi‖2 ≤ 1,∀J(Ji ‖(EJf2i )1/2‖∞ ≤ 2n#(Ji\J)/2}
2(kI (n)−n)#I
c/2 logd/2 n.
Let us thus consider arbitrary fi, i = 0, . . . , k such that ‖fi‖2 ≤ 1,
‖(EJf2i )1/2‖∞ ≤ 2n#(Ji\J)/2 for all J ( Ji (note that the latter condition
means in particular that ‖fi‖∞ ≤ 2n#Ji/2).
We have by assumption (12) for sufficiently large n,
|E[〈h, f0〉
fi]| ≤ ‖h‖K,J ,2nd/2 ≤ LdD log(d−degJ )/2 n.
We have also
E|〈h, f0〉1{|h|2≥ηd2nd logd n}
fi| ≤ E[|h|1{|h|2≥ηd2nd logd n}]
‖fi‖∞
≤ 2nd/2E[|h|1{|h|2≥ηd2nd logd n}] =: αn.
Also for I ⊆ Id, I 6= ∅, Id, denoting h̃n = h1{|h|2≤ηd2nd logd n}, we get
E|〈h̃n,f0〉
fi1{EIH2≥2n#I
≤ EIc
(EI |h̃n|2)1/21{EIH2≥2n#Ic}
(EJi∩I |fi|2)1/2
2n#(Ji∩I
c)/2]EIc [(EI |h̃n|2)1/21{EIH2≥2n#Ic}]
≤ Ld2n#I
EIc[(EIH
2 logd n)1/21{EIH2≥2n#I
≤ Ld[2n#I
c/2 logd/2 n]EIc[(EIH
2)1/21{EIH2≥2n#I
}] =: β
Let us denote h̄n = h̃n
∅6=I(Id
1{EIH2≤2#I
cn} and γ
n = E|h̄n1BIn |
Combining the three last inequalities we obtain
|E〈hn, f0〉
fi| ≤|E〈h, f0〉
fi|+ |E〈hn1Acn , f0〉
≤LdD log(d−deg J )/2 n+ E|〈h1{|h|2≥2nd logd n}, f0〉
∅6=I(Id
E|〈h̃n1{EIH2≥2n#Ic}, f0〉
E|〈h̄n1BIn , f0〉
≤LdD log(d−deg J )/2 n+ αn +
∅6=I(Id
βIn +
Now, combining the above estimate with (34), we obtain
‖hn‖J0,J ≤ Ld
2(kI (n)−n)#I
c/2 logd/2 n+ LdD log
(d−degJ )/2 n (35)
+ αn +
∅6=I(Id
βIn +
Let us notice that
logd/2 n
∀I 6=∅,Id
logd/2 n
< ∞, (36)
∀I 6=∅,Id
(γIn)
log2d n
The first inequality was proved in Step 1. The proof of the second one
is straightforward. Indeed, we have
logd/2 n
= LdEIc[(EIH
2)1/2
1{EIH2≥2n#I
≤ L̃dEIcEIH2 = L̃dEH2 < ∞.
The third inequality is implicitly proved in Step 3. Let us however present
an explicit argument.
(γIn)
log2d n
|h|21
{|h|≤ηd2
nd/2 logd/2 n}
logd n
(EIcEI(H
))2 < ∞
by Lemma 19 applied to the random variable
EIH2.
We are now in position to finish the proof. Let us notice that we have
either E(|h|21{|h|2≤22nd}) ≤ 1, or we can use the function
h1{‖h|2≤22nd}
(E(|h|21{|h|2≤22nd}))1/2
as a test function in the definition of ‖h‖Id,∅,2nd , obtaining
(E(|h|21{|h|2≤22nd}))1/2 = E〈h, g〉 ≤ ‖h‖Id,∅,2nd < D log
for large n. Combining this estimate with Corollary 3, we can now write
|i|≤2n
πdhn(X
i )| ≥ L̃d(D + C)2nd/2 logd/2 n
≤ L̃d
J0(Id
J∈PId\J0
(C2nd/2 logd/2 n
2nd/2‖hn‖Jo,J
)2/degJ ]
+ L̃d
( C2nd/2 logd/2 n
2n#I/2‖(EI |hn|2)1/2‖∞
)2/(d+#Ic)]
The second series is convergent by (33).
Thus it remains to prove the convergence of the first series. By (35), we
have for all J0,J
(C logd/2 n
‖hn‖Jo,J
)2/degJ ]
( C logd/2 n
2(kI (n)−n)#I
c/2 logd/2 n
)2/degJ ]
+ exp
( C logd/2 n
D log(d−deg J )/2 n
)2/degJ ]
+ exp
(C logd/2 n
)2/degJ ]
+ exp
( C logd/2 n
∅6=I(Id
)2/degJ ]
+ exp
( C logd/2 n
)2/ degJ ]
(under our permanent convention that the values of Ld in different equations
need not be the same). The series determined by the three last components
at the right-hand side are convergent by (36) since e−x ≤ Lrx−r for r > 0.
The series corresponding to the second component is convergent for C large
enough and we can take C = LdD. As for the series corresponding to the
first term, we have, just as in the proof of (33) for any I ( Id,
( C logd/2 n
(kI (n)−n)#Ic/2 logd/2 n
)2/degJ ]
n≥k,k /∈K(I,n)
C2(n−k)#I
)2/degJ ]
n≥k,k /∈K(I,n)
C2(n−k)#I
)2/degJ ]
E(H21CI
) = K̄EH2 < ∞.
We have thus proven the convergence of the series at the left-hand side of
(37) with C ≤ LdD, which ends Step 5.
Now to finish the proof, we just split Σd for each n into four sets, described
by steps 1–4 and use the triangle inequality, to show that
|i|≤2n
h(Xdeci )| ≥ LdD2nd/2 logd/2 n
which proves the sufficiency part of the theorem by Corollary 4.
8 The undecoupled case
Theorem 4. For any function h : Σd → H and a sequence X1,X2, . . . of
i.i.d., Σ-valued random variables, the LIL (4) holds if and only if h
(LL|h|)d < ∞,
h is completely degenerate for the law of X1 and the growth conditions (12)
are satisfied.
More precisely, if (4) holds, then (12) is satisfied with D = LdC and
conversely, (12) together with complete degeneration and the integrability
condition imply (4) with C = LdD.
Proof. Sufficiency follows from Corollary 6 and Theorem 2. To prove the
necessity assume that (4) holds and observe that from Lemma 8 and Corol-
lary 5, h satisfies the randomized decoupled LIL (8) and thus, by Theo-
rem 2, (11) holds and the growth conditions (12) on functions ‖h‖K,J ,u
are satisfied (note that the ‖ · ‖J ,u norms of the kernel h(X1, . . . ,Xd) and
ε1 · · · εdh(X1, . . . ,Xd) are equal). The complete degeneracy of 〈ϕ, h〉 for any
ϕ ∈ H follows from the necessary conditions for real-valued kernels. Since
by (11), Eih is well defined in the Bochner sense, we must have Eih = 0.
References
[1] Adamczak, R. (2005). Moment Inequalities for U -statistics. Ann.
Probab. 34, No. 6, 2288-2314.
[2] Adamczak, R., Lata la, R. (2006) LIL for canonical U-statistics. Sub-
mitted
[3] Arcones, M. and Giné, E. (1995). On the law of the iterated logarithm
for canonical U -statistics and processes. Stochastic Process. Appl. 58
217–245. MR1348376.
[4] Bousquet O., Boucheron S., Lugosi G., Massart P.(2005). Mo-
ment inequalities for functions of independent random variables. Ann.
Probab. 33, no. 2, 514-560. MR2123200.
[5] de la Peña, V.H. and Giné, E. (1999). Decoupling. From Dependence
to Independence. Springer, New York. MR1666908.
[6] de la Peña, V.H. and Montgomery-Smith, S. (1994). Bounds for
the tail probabilities of U -statistics and quadratic forms. Bull. Amer.
Math. Soc. 31 223–227. MR1261237.
[7] de la Peña, V. H., Montgomery-Smith, S. J. (1995) Decoupling
inequalities for the tail probabilities of multivariate U -statistics. Ann.
Probab. 23, no. 2, 806–816. MR1334173.
[8] Giné E., Lata la, R. and Zinn, J. (2000). Exponential and moment in-
equalities for U -statistics. High Dimensional Probability II, 13–38. Progr.
Probab., 47, Birkhauser, Boston. MR1857312.
[9] Giné, E. and Zhang, C.-H. (1996). On integrability in the LIL for
degenerate U -statistics. J. Theoret. Probab. 9 385–412. MR1385404.
[10] Giné, E., Zinn, J. (1994). A remark on convergence in distribution of
U -statistics. Ann. Probab. 22 117–125. MR1258868.
[11] Giné E., Kwapień, S., Lata la, R. and Zinn, J. (2001). The LIL for
canonical U -statistics of order 2, Ann. Probab. 29 520–557. MR1825163.
[12] Gluskin, E.D., Kwapień, S. (1995). Tail and moment estimates for
sums of independent random variables with logarithmically concave tails.
Studia Math. 114 , no. 3, 303–309. MR1338834.
[13] Goodman, V., Kuelbs, J., Zinn, J. (1981). Some results on the LIL
in Banach space with applications to weighted empirical processes. Ann.
Probab. 9 , no. 5, 713–752. MR0628870.
[14] Houdré, C. and Reynaud-Bouret, P. (2003). Exponential Inequal-
ities, with Constants, for U -statistics of Order Two. Stochastic inequal-
ities and applications, 55–69. Progr. Probab., 56, Birkhauser, Basel.
MR2073426.
[15] Kwapień, S., Lata la, R., Oleszkiewicz, K. and Zinn, J. (2003).
On the limit set in the law of the iterated logarithm for U -statistics of
order two. High dimensional probability, III (Sandjberg), 111–126. Progr.
Probab., 55, Birkhauser, Basel. MR2033884.
[16] Lata la, R. (1998) On the almost sure boundedness of norms of
some empirical operators. Statist. Probab. Lett. 38 , no. 2, 177–182.
MR1627869.
[17] Lata la, R. and Zinn, J. (2000). Necessary and sufficient conditions
for the strong law of large numbers for U -statistics. Ann. Probab. 28
1908–1924. MR1813848.
[18] Lata la, R. (2006). Estimation of moments and tails of Gaussian
chaoses. Ann. Probab. 34, No. 6. 2061-2440.
[19] Rubin, H. and Vitale, R.A. (1980). Asymptotic distribution of sym-
metric statistics. Ann. Statist. 8 165–170. MR0557561.
	Introduction
	Notation
	Moment inequalities for U-statistics in Hilbert space 
	The equivalence of several LIL statements
	The canonical decoupled case
	Necessity
	Sufficiency
	The undecoupled case
