Upper bounds on product and multiplier empirical processes

Introduction

Empirical processes appear frequently in diverse branches of Mathematics, Statistics and Computer Science.

In its most standard form, an empirical process is indexed by a class of functions defined on a probability space $(\Omega,\mu)$. If $X_{1},...,X_{N}$ are independent and distributed according to $\mu$, the centred empirical process indexed by $F$ is

One would like to obtain upper and lower bounds on

either in high probability or in expectation. The hope is that the supremum (1.1) may be controlled using some geometric features of the class $F$, similar to the ones used in the theory of gaussian processes (for more information on gaussian processes and their connection to the geometry of the underlying class see the books and ).

Let $F\subset L_{2}$ and set $\{G_{f}:f\in F\}$ to be the centred canonical gaussian process indexed by $F$; that is, the gaussian process indexed by $F$ whose covariance structure is endowed by the inner product in $L_{2}$.

To avoid the (well understood) issue of measurability, set

(1) Let $\xi\in L_{q}$ for some $q>2$ ($\xi$ need not be independent of $X$) and set $\xi_{1},...,\xi_{N}$ to be independent copies of $\xi$. Consider

which is the supremum of the multiplier process indexed by $F$ and associated with the multiplier $\xi$.

Note that unlike the standard notion of a multiplier process, here $(\xi_{i})_{i=1}^{N}$ need not be independent of $(X_{i})_{i=1}^{N}$.

Besides being a natural object from the theoretical point of view, the significance of multiplier processes may be seen in numerous applications. For example, multiplier processes play a central role in Statistics, when studying prediction and estimation problems (see, e.g. and references therein, and also ), but that is only the tip of the iceberg as far as applications go.

(2) Let $F$ and $H$ be classes of functions defined on the probability space $(\Omega,\mu)$ and consider the supremum of the product process indexed by $F$ and $H$,

Clearly, (1.3) is a natural object when trying to analyze, for example, empirical correlation, or, what is arguably the most important process as far as applications are concerned, the quadratic empirical process

Although the product process may be viewed as the standard empirical process indexed by the product class $F\cdot H=\{f\cdot h:f\in F,h\in H\}$, and the multiplier process as the standard empirical process indexed by the class $\xi\cdot F=\{\xi f:f\in F\}$ (at least when $(\xi_{i},X_{i})_{i=1}^{N}$ are independent), the type of result one is looking for here is rather different. When studying the two processes, one would like to bound the supremum of (1.2) and of (1.3) using some geometric structures of the indexing classes $F$ and $F,H$ respectively, rather than the structures of $\xi\cdot F$ and $F\cdot H$, which, in most cases, are hard to handle.

Before we continue exploring the two problems, let us explain what is meant by “some geometric structures of the indexing classes”.

Motivated by chaining methods that have had tremendous impact on the theory of gaussian processes, the geometric parameters we shall focus on are ‘relatives’ of Talagrand’s $\gamma$ functionals.

Let $(T,d)$ be a metric space. An admissible sequence of $T$ is a collection of subsets, $T_{s}\subset T$, whose cardinality satisfies $|T_{s}|\leq 2^{2^{s}}$ for $s\geq 1$, and $|T_{0}|=1$. For $\alpha\geq 1$ and $s_{0}\geq 0$ set

where the infimum is taken with respect to all admissible sequences of $T$. When $s_{0}=0$ we shall write $\gamma_{\alpha}(T,d)$ instead of $\gamma_{0,\alpha}(T,d)$.

For more information on chaining methods we refer the reader to M. Talagrand’s book , which contains an extensive and illuminating survey on the topic.

There exist absolute constants $c$ and $C$ for which the following holds. Let $F\subset L_{2}$, $|F|>1$, and consider $\{G_{f}:f\in F\}$, the centred, canonical gaussian process indexed by $F$.

The upper bound in Theorem 1.3 is due to Fernique while the lower one is Talagrand’s Majorizing Measures Theorem . The proof of both parts may be found in . It should be noted that the original proofs of both results are based on the majorizing measures mechanism which preceded the modern generic chaining scheme.

Chaining arises as a way of relating the supremum of a random process $\{Z_{f}:f\in F\}$ to the structure of the indexing set $F$. An upper estimate is obtained by combining individual tail bounds that ensure that if $f$ and $h$ are close in some sense, the probability that $Z_{f}$ is very different from $Z_{h}$ is small. For example, if $\{G_{f}:f\in F\}$ is the centred, canonical gaussian process indexed by $F\subset L_{2}$, and if $f,h\in F$, then

which is precisely the sort of tail estimate one would like to have (but unfortunately, analogous versions of (1.4) are not as simple for many interesting processes).

The increment condition (1.4) hints towards a fundamental fact: the supremum of a gaussian process $\{G_{f}:f\in F\}$ is determined by a single metric, endowed by the $L_{2}$ norm In fact, Theorem 1.3 implies a two-sided control using the $L_{2}$ metric, but since our focus is on obtaining upper bounds, we will focus only on that direction.. However, when it comes to empirical processes, the situation is rather different. To explain this substantial difference between empirical and gaussian processes it is convenient to use the notion of an Orlicz norm.

Let $f$ be defined on the probability space $(\Omega,\mu)$. For $\alpha\geq 1$ set

and let $L_{\psi_{\alpha}}$ be the space of functions for which $\|f\|_{\psi_{\alpha}}<\infty$.

It is well known that $\|f\|_{\psi_{\alpha}}$ is equivalent to the smallest constant $c$ for which $Pr(|f|>t)\leq 2\exp(-t^{\alpha}/c^{\alpha})$ for every $t>0$, and also to $\sup_{p\geq 1}\|f\|_{L_{p}}/p^{1/\alpha}$.

A class $F$ is $L$-subgaussian if for every $f,h\in F\cup\{0\}$,

Using the moment characterization of the $\psi_{2}$ norm, it is evident that if $F$ is $L$-subgaussian then

for every $f,h\in F\cup\{0\}$ and for a suitable absolute constant $c$.

Observe that if $F\subset L_{2}$, the centred, canonical gaussian process $\{G_{f}:f\in F\}$ satisfies that $\|G_{f}-G_{h}\|_{L_{2}}=\|f-h\|_{L_{2}}$ and

but there is no reason why $\|f-h\|_{\psi_{2}}$ should be equivalent to $\|f-h\|_{L_{2}}$ unless the class is subgaussian. And though one may show that there is an absolute constant $c_{4}$ for which

the underlying metric in (1.5) is the $\psi_{2}$ metric, which is simply too large to be of any use in most applications.

It turns out that this rather unsatisfactory upper bound may be improved by examining the chaining process more closely.

Let $\{Z_{f}:f\in F\}$ be a random process, set $s_{0}\geq 0$ and consider an admissible sequence $(F_{s})_{s\geq 0}$ and a collection of functions $\pi_{s}:F\to F_{s}$. Under mild assumptions (for example, that for every $f\in F$, $\pi_{s}f\to f$ in an appropriate sense), each $Z_{f}$ may be written as a ‘chain’, which is simply a telescopic sum of the ‘links’ $Z_{\pi_{s+1}f}-Z_{\pi_{s}f}$:

Obtaining uniform control over all chains requires balancing the tail estimates for each link that appears at the $s$-stage with the total number of links that are involved at that stage. And, since there are at most

links at the $s$-stage, it suffices to find levels $t(f,s)$ for which

and obtain a similar estimate for the ‘starting points’ of each chain, $Z_{\pi_{s_{0}}f}$, to ensure the required uniform control over all possible chains. Such a uniform control results in a high probability upper estimate on $\sup_{f\in F}Z_{f}$.

A trivial yet crucial observation is that by Chebychev’s inequality, a possible choice of $t(f,s)$ is

for $p\sim 2^{s}$, where here and throughout the article we write $a\sim b$ if there are absolute constants $c_{1}$ and $c_{2}$ for which $c_{1}a\leq b\leq c_{2}a$.

Thus, an obvious alternative to the $\gamma$-functionals is

where the infimum is taken with respect to all admissible sequences of $F$ and for $\pi_{s}:F\to F_{s}$ which is the nearest point map with respect to the norm $\|\ \|_{L_{u^{2}2^{s}}}$.

It immediately follows from the decomposition to chains in (1.6) that for $u\geq 4$, with probability at least $1-2\exp(-c_{0}u^{2}2^{s_{0}})$,

where $c_{0}$ and $c_{1}$ are absolute constants.

The idea of using a complexity parameter that takes into account all the $L_{p}$ structures endowed by the process has been introduced in and independently by R. Latała (see, for example, and Exercise 2.2.15 in ).

Let us study two examples in which the way the complexity parameter in (1.7) depends on $F$ takes a rather simple form.

$\bullet$ When considering the centred, canonical gaussian process indexed by $F$, the parameter in (1.7) is not new. Indeed, recall that

hence, for an almost optimal admissible sequence (1.7) becomes

and the relations between (1.8) and the upper estimate in Theorem 1.3 via the $\gamma_{2}$ functional are clear.

$\bullet$ Next, one may consider (1.7) for the standard empirical process,

Applying Latała’s sharp bound on the moments of sums of independent random variables (see also Theorem 3.5, below), one may show that for every $f,h\in F$ and every $p\geq 2$,

The last example leads to the introduction of the following norms and to a ‘graded version’ of the $\gamma$ functionals.

For a random variable $Z$ and $p\geq 1$, set

Thus, if $Z_{f}$ is the empirical process from (1.10), it follows that

Given a class of functions $F$, $u\geq 1$ and $s_{0}\geq 0$, put

where the infimum is taken with respect to all admissible sequences $(F_{s})_{s\geq 0}$, and $\pi_{s}f$ is the nearest point in $F_{s}$ to $f$ with respect to the $(u^{2}2^{s})$ norm.

Again, a straightforward chaining argument shows that for every $s_{0}\geq 0$ and $u\geq 4$, with probability at least $1-2\exp(-c_{0}u^{2}2^{s_{0}})$,

Observe that if $F$ happens to be $L$-subgaussian and $u\geq 2$ then $\Lambda_{s_{0},u}(F)$ is equivalent to $\gamma_{s_{0},2}(F,L_{2})$. Indeed, by the moment characterization of the $\psi_{2}$ norm, there is an absolute constant $c$ for which, for every $p\geq 2$, $\|f\|_{L_{p}}\leq c\sqrt{p}\|f\|_{\psi_{2}}$. Therefore,

This leads to the next corollary, which may also be established directly, using a standard chaining argument.

Let $F$ be an $L$-subgaussian class. Then for every $u\geq 4$ and $s_{0}\geq 0$, with probability at least $1-2\exp(-c_{0}2^{s_{0}}u^{2})$,

As an example, let $d_{2}(F)=\sup_{f\in F}\|f\|_{L_{2}}$ and set $s_{0}\geq 0$ be the largest integer for which

However, and unlike subgaussian examples, there are natural examples in which ${\Lambda}_{s_{0},u}(F)$ may be significantly smaller than its $\psi_{2}$ counterpart. This should not come as a surprise, as both $\|\ \|_{L_{2^{s}}}/2^{s/2}$ and $\|\ \|_{(2^{s})}$ are ‘local’ versions of the $\psi_{2}$ metric: they measure the subgaussian behaviour of the functions involved, but only up to a fixed level, rather than at every level.

Clearly, if $T$ contains any one of the coordinate directions $\{e_{1},...,e_{n}\}$, then $F_{T}$ is not a subset of $L_{\psi_{2}}$ and $\gamma_{2}(F,\psi_{2})$ is not even well defined.

Talagrand showed in (see also ) that (1.1) has a geometric interpretation:

2 The main results

Up to now, we have only examined the standard empirical process. Unfortunately, the simple chaining argument used in (1.12) to control that process is rather useless when it comes to dealing with multiplier processes or with product processes. We will show in what follows how the suprema of these two types of processes may be bounded from above in terms of the $\Lambda$-functionals.

Let us begin by formulating the estimate for multiplier processes.

For $q>2$, there are constants $c_{0}$, $c_{1},c_{2}$ and $c_{3}$ that depend only on $q$, for which the following holds. Let $\xi\in L_{q}$ and set $\xi_{1},...,\xi_{N}$ to be independent copies of $\xi$. Fix an integer $s_{0}\geq 0$ and $w,u>c_{0}$. Then, with probability at least

One simple outcome of Theorem 1.9 is when the class $F$ happens to be $L$-subgaussian.

Recall that $d_{2}(F)=\sup_{f\in F}\|f\|_{L_{2}}$ and set $s_{0}\geq 0$ to satisfy that

As noted previously, since $F$ is $L$-subgaussian,

Thus, it follows from Theorem 1.9 that with probability at least

Turning to the question of product processes, recall the following fact from (see also Theorem 9.3.1 in ).

For every $q>4$ there exists a constant $c(q)$ that depends only on $q$ for which the following holds. Let $F\subset L_{q}$ be a class of functions on $(\Omega,\mu)$. Assume that for every $t>0$ and every $f,h\in F\cup\{0\}$,

where $d_{1}$ and $d_{2}$ are metrics on $F\cup\{0\}$. If $d_{q}(F)=\sup_{f\in F}\|f\|_{L_{q}}$ and $\gamma=\gamma_{2}(F,d_{2})+\gamma_{1}(F,d_{1})$, then

Theorem 1.11 is demonstrated by integrating a high-probability bound. However, the probability estimate established in is far from optimal. Recently, Dirksen obtained the optimal probability estimate under the assumption that $F\subset L_{\psi_{2}}$, improving earlier results from , and a few months later, Bednorz gave a different proof of the same fact. The following formulation is from .

There exist absolute constants $c_{1}$ and $c_{2}$ for which the following holds. Let $F$ be a class of functions on $(\Omega,\mu)$ and set $\gamma=\gamma_{2}(F,\psi_{2})$ and $d_{\psi_{2}}(F)=\sup_{f\in F}\|f\|_{\psi_{2}}$. For every $u>0$, with probability at least $1-2\exp(-c_{1}\min\{\sqrt{N}u,u^{2}\})$,

The probability estimate in Theorem 1.12 is indeed optimal, as may be seen by setting $t=ud_{\psi_{2}}^{2}(F)/\sqrt{N}$ in Bernstein’s inequality applied to $f^{2}$.

In comparison, below is our estimate on the supremum of a product process, and in particular, on the supremum of the quadratic process.

There exists an absolute constant $c_{0}$ and for every $q>4$ there exists a constant $c_{1}(q)$ that depends only on $q$ for which the following holds. Let $F$ and $H$ be classes of functions on $(\Omega,\mu)$, set $u\geq\max\{8,\sqrt{q}\}$ and consider an integer $s_{0}\geq 0$. Then, with probability at least $1-2\exp(-c_{0}u^{2}2^{s_{0}})$, for every $f\in F$ and $h\in H$,

In particular, if $F=H$, then with probability at least $1-2\exp(-c_{0}u^{2}2^{s_{0}})$,

Let us present some of the outcomes of Theorem 1.13 for the quadratic process.

$\bullet$ Since $\|\ \|_{(p)}\leq c\|\ \|_{\psi_{2}}$, it is evident that $\Lambda_{s_{0},u}(F)\leq c\gamma_{2}(F,\psi_{2})$. Thus,

if $|F|>1$ and one sets $2^{s_{0}}\sim(\gamma_{2}(F,\psi_{2})/d_{\psi_{2}}(F))^{2}$. Also, since $\|f\|_{\psi_{2}}\sim\sup_{q\geq 2}\|f\|_{L_{q}}/\sqrt{q}$, it is evident that $d_{q}(F)\leq c_{2}\sqrt{q}d_{\psi_{2}}(F)$, and (1.17) recovers Theorem 1.12.

The proofs of Theorem 1.9 and Theorem 1.13 are based on symmetrization, which has been one of the most influential tools in empirical processes theory. The most well-known symmetrization inequalities for empirical processes are the celebrated Giné-Zinn inequalities , but we will use an earlier, “in-probability” version of those inequalities (see, e.g., ).

Thanks to Theorem 1.14, one may prove Theorem 1.9 via a high-probability upper bound on the supremum of the Bernoulli process

where the set $V$ is a typical coordinate projection of the class $F$; that is, for $\sigma=(X_{1},...,X_{N})$,

In a similar fashion, Theorem 1.13 follows from a high-probability upper bound on

for typical coordinate projections $V=P_{\sigma}F$ and $W=P_{\sigma}H$.

This observation dictates the structure of the article. We will first study

Finally, a word about notation. Throughout, $c_{0},c_{1},...$ denote absolute constants. Their value may change from line to line. $c(q)$ or $c_{q}$ are constants that depend only on the parameter $q$, and $a\lesssim_{q}b$ means that $a\leq c(q)b$.

Chaining and Bernoulli processes

As we noted earlier, our method of analysis consists of two main components. First, gathering accurate information on the structure of a typical coordinate projection of $F$ (and in the case of the product process, of a typical coordinate projection of $H$ as well); and second, for a typical $\sigma=(X_{1},...,X_{N})$ and $(\xi_{i})_{i=1}^{N}$, analyzing the suprema of the conditioned Bernoulli processes

Moreover, by , this estimate is optimal when $k\sim t^{2}$.

Therefore, the effect $x$ has on the Bernoulli process depends on

When dealing with products, as we have to, $x_{i}=w_{i}v_{i}$ and the decomposition requires additional care. Let $I$ be the union of the sets of the $k$ largest coordinates of $(|w_{i}|)_{i=1}^{N}$ and the $k$ largest coordinates of $(|v_{i}|)_{i=1}^{N}$; thus $|I|\leq 2k$. Fix $r>1$, set $r^{\prime}$ to be its conjugate index (i.e., $1/r+1/r^{\prime}=1$) and observe that with probability at least $1-2\exp(-t^{2}/2)$,

As (2.1) is meant to play a part in a chaining argument, the bound should hold uniformly for all the links that appear at the $s$-stage; hence, a likely choice in (2.1) at the $s$-stage is $t\sim 2^{s/2}$.

Let us present a chaining process aimed at bounding

Let $(V_{s})_{s\geq 0}$ be an admissible sequence of $V$, and note that under very mild assumptions (for example, that for every $v\in V$, $\pi_{s}v\to v$ in an appropriate sense as $s$ tends to infinity), for every $s_{0}\geq 0$,

Set $\Delta_{s}v=\pi_{s+1}v-\pi_{s}v$; thus

Let $r,r^{\prime}>1$ be conjugate indices, for every $s\geq s_{0}$ set an integer $j_{s}\geq 1$ to be determined later and assume that $(j_{s})_{s\geq s_{0}}$ is non-decreasing in $s$. Finally, let $I=I_{v,s}$ be the union of the $j_{s}-1$ largest coordinates of $(|\Delta_{s}v|_{i})_{i=1}^{N}$ and the $j_{s}-1$ largest coordinates of $(|z_{i}|)_{i=1}^{N}$. Applying (2.1) for $t\geq 4$, it is evident that with probability at least $1-2\exp(-t^{2}2^{s}/2)$

Repeating this argument for the vectors $\pi_{s_{0}}v$ and summing the probabilities, it follows that with probability at least $1-2\exp(-ct^{2}2^{s_{0}})$, for every $v\in V$,

Motivated by this chaining argument, consider the following structural assumption on $V$:

$\bullet$ Let $(j_{s})_{s\geq s_{0}}$ be a non-decreasing sequence of integers, and for every $s\geq s_{0}$, $1\leq j_{s}\leq N+1$.

Assume that for every $s\geq s_{0}$ and every $v\in V$,

$\bullet$ $\left(\sum_{i<j_{s}}\left((\Delta_{s}v)_{i}^{*}\right)^{2}\right)^{1/2}\leq\|\Delta_{s}v\|_{[s]}$, $\left(\sum_{i\geq j_{s}}\left((\Delta_{s}v)_{i}^{*}\right)^{2p}\right)^{1/2p}\leq\|\Delta_{s}v\|N^{1/2p}$,

$\bullet$ $\left(\sum_{i<j_{s}}\left((\pi_{s}v)_{i}^{*}\right)^{2}\right)^{1/2}\leq\|\pi_{s}v\|_{[s]}$, $\left(\sum_{i\geq j_{s}}\left((\pi_{s}v)_{i}^{*}\right)^{2p}\right)^{1/2p}\leq\|\pi_{s}v\|N^{1/2p}$.

Observe that if $V$ satisfies Assumption 2.1 for $p=r^{\prime}$, then by (2.2), with probability at least $1-2\exp(-ct^{2}2^{s_{0}})$, for every $v\in V$,

Using the same notation as above, with probability at least $1-2\exp(-ct^{2}2^{s_{0}})$, for every $v\in V$

Seemingly, there is plenty of freedom in the choices of $j_{s}$, $r$ and the admissible sequence of $V$. However, our main interest is when $z$ and $V$ are typical realizations of $(\xi_{i})_{i=1}^{N}$ and $V=P_{\sigma}F$ respectively, and the natural choice of an admissible sequence of $V$ should be endowed by an admissible sequence of the underlying class $F$. Thus, one must have adequate control on all the ‘monotone sums’

where $\Delta_{s}f=\pi_{s+1}f-\pi_{s}f$, $I_{s}$ is the set of the $j_{s}-1$ largest coordinates of $\left(|\Delta_{s}f|(X_{i})\right)_{i=1}^{N}$. In a similar fashion, one must be able to control

Since $\{\Delta_{s}f:f\in F\}$ contains at most $2^{2^{s+2}}$ points that must be controlled uniformly, the individual probability estimate that is required in (2.4) and in (2.5) is $\exp(-u^{2}2^{s})$ for a large enough $u$ (a choice of $u\geq 4$ will do). In what follows, we will show that this almost forces the choice of $j_{s}$.

In addition, obtaining sufficient control on $\left(\sum_{i=j_{s}}^{N}(\xi_{i}^{*})^{2r}\right)^{1/2r}$ for every $j_{s}$ restricts the choice of $r$; it will depend on the $L_{q}$ space to which $\xi$ belongs.

for $N$ independent copies of a random variable $Z$ will be derived in Section 3.

2 Bernoulli product processes

Chaining for a Bernoulli product process is more involved than the one outlined above. However, the two share a common feature: structural assumptions on the indexing sets.

$\bullet$ Let $(j_{s})_{s\geq s_{0}}$ be an non-decreasing sequence of integers and for every $s\geq s_{0}$, $1\leq j_{s}\leq N+1$.

$\bullet$ Let $(\nu_{s})_{s\geq s_{0}}$ be a sequence of nonnegative numbers.

Assume that for every $s\geq s_{0}$ and every $v\in V$,

$\bullet$ $\left(\sum_{i<j_{s}}\left((\Delta_{s}v)_{i}^{*}\right)^{2}\right)^{1/2}\leq\|\Delta_{s}v\|_{[s]}$, $\left(\sum_{i\geq j_{s-1}}\left((\Delta_{s}v)_{i}^{*}\right)^{2p}\right)^{1/2p}\leq\|\Delta_{s}v\|N^{1/2p}$,

$\bullet$ $\left(\sum_{i<j_{s}}\left((\pi_{s}v)_{i}^{*}\right)^{2}\right)^{1/2}\leq\|\pi_{s}v\|_{[s]}$, $\left(\sum_{i\geq j_{s-1}}\left((\pi_{s}v)_{i}^{*}\right)^{2p}\right)^{1/2p}\leq\|\pi_{s}v\|N^{1/2p}$.

$\bullet$ $\left(\sum_{i=j_{s-1}}^{j_{s}-1}\left((\pi_{s}v)_{i}^{*}\right)^{2}\right)^{1/2}\leq d(V)\nu_{s}$, where we set $j_{s_{0}-1}=j_{s_{0}}$ and recall that $d(V)=\sup_{v\in V}\|v\|$.

There is a slight overlap between the sets of large and small coordinates: one set contains the $j_{s}-1$ largest coordinates, while the other contains the $N-j_{s-1}+1$ smallest coordinates – rather than the more natural set, consisting of the $N-j_{s}+1$ smallest coordinates. The reason for this overlap is a minor technicality that will be used in the proof of Lemma 2.3.

In particular, if $\sum_{s=s_{0}}^{s_{1}-1}\nu_{s}\leq c\sqrt{N}$ then

Proof. We will only consider the case $s_{1}>s_{0}+1$, as the proof of the case $s_{1}=s_{0}+1$ is simpler, and is actually contained in the proof of the former.

Fix $\pi_{s_{1}}v$ and let $I_{s_{1}-1}$ be the set of the $j_{s_{1}-1}-1$ largest coordinates of $(|(\pi_{s_{1}}v)_{i}|)_{i=1}^{N}$. Therefore,

Repeating this argument for $s_{0}<s<s_{1}$, it follows that for every $v\in V$, and for the choice of $I_{s}$ as the set of the $j_{s}-1$ largest coordinates of $(|\pi_{s+1}v|_{i})_{i=1}^{N}$,

Next, recall that $v=\sum_{s\geq s_{1}}\Delta_{s}v+\pi_{s_{1}}v$ and that $j_{s}=N+1$ for $s\geq s_{1}$. Therefore, by Assumption 2.2 for $p=1$,

There exist absolute constants $c_{1}$ and $c_{2}$ for which the following holds. If $V$, $W$, $j_{s}$ and $s_{0}$ are as above, then for every $t>4$, with probability at least $1-2\exp(-c_{1}t^{2}2^{s_{0}})$,

Note that by Assumption 2.2, Lemma 2.3 and since $j_{s-1}\leq j_{s}$,

Let $I$ be the union of the $j_{s}-1$ largest coordinates of $(|\Delta_{s}v|_{i})_{i=1}^{N}$ and the $j_{s}-1$ largest coordinates of $(|\pi_{s+1}w|_{i})_{i=1}^{N}$. Since $|\{\Delta_{s}v:v\in V\}|\leq 2^{2^{s+2}}$ and $|\{\pi_{s+1}w:w\in W\}|\leq 2^{2^{s+1}}$, it follows that for $t\geq 4$, with probability at least $1-2\exp(-ct^{2}2^{s})$, for every $v\in V$ and $w\in W$,

Repeating the argument for $((\pi_{s}v)_{i}\cdot(\Delta_{s}w)_{i})_{i=1}^{N}$ and summing over $s\geq s_{0}$, one has that with probability at least $1-2\exp(-c_{1}t^{2}2^{s_{0}})$, for every $v\in V$ and $w\in W$

it is evident that with probability at least $1-2\exp(-c_{2}t^{2}2^{s})$,

Corollary 2.1 and Theorem 2.4 are the first component in the proofs of Theorem 1.9 and Theorem 1.13, respectively. For the other component, one has to show that typical coordinate projections of the indexing classes are well-behaved in the sense of Assumption 2.1 or of Assumption 2.2. To that end, one has to identify the norms $\|\ \|_{[s]}$ and $\|\ \|$, the sequences $(j_{s})_{s\geq s_{0}}$ and $(\nu_{s})_{s\geq s_{0}}$ and estimate the resulting complexity terms, $\Lambda(P_{\sigma}F)$, $\Theta(P_{\sigma}F)$ and $d(P_{\sigma}F)$. The main step towards that goal is presented in the next section.

Structural results - preliminary estimates

Let $Z$ be a random variable. Our primary goal is to study the monotone nonincreasing rearrangement of $N$ independent copies of $Z$. We will show that the norms

There exist absolute constants $c_{0},c_{1},c_{2}$ for which the following holds. Let $1\leq r<q$ and set $0<\beta<(q/r)-1$. Consider $Z\in L_{q}$, and let $Z_{1},...,Z_{N}$ be independent copies of $Z$. Put $1\leq p\leq N$ and set

$\bullet$ For every $t>2$ with probability at least $1-t^{-2p}\exp(-p)$,

$\bullet$ For every $t>2$, with probability at least $1-t^{-j_{0}q}\exp(-p)$,

$\bullet$ For $t>2$ with probability at least $1-c_{2}t^{-q}N^{-\beta}$,

We will show that the vector $U$ consists of the $j_{0}-1$ largest coordinates of $(|Z_{i}|)_{i=1}^{N}$ and that $V=(Z_{i})_{i=1}^{N}-U$. The key is to determine correctly the ‘cut-off’ point in that decomposition – which happens to be $j_{0}$.

As the formulation of Theorem 3.1 indicates, the treatment depends on whether or not the decomposition is trivial (i.e., if $U=0$), and on the required probability estimate.

We begin with the smaller coordinates of $(|Z_{i}|)_{i=1}^{N}$, which will be used to define the vector $V$ in the decomposition of $(Z_{i})_{i=1}^{N}$.

There exist absolute constants $c_{0},c_{1}$ and $c_{2}$ for which the following holds. Let $1\leq r<q$, set $Z\in L_{q}$ and put $Z_{1},...,Z_{N}$ to be independent copies of $Z$. Fix $1\leq p\leq N$, let

If $j_{0}>1$, then with probability at least $1-2t^{-j_{0}q}\exp(-p)$,

And, if $j_{0}=1$ and $0<\beta<(q/r)-1$ then with probability at least $1-c_{2}t^{-q}N^{-\beta}$,

Proof. Fix $\rho\geq 1$ to be named later and observe that by a binomial estimate and Markov’s inequality, for every $u>0$,

Therefore, if $u=t\|Z\|_{L_{q}}(eN/j)^{\rho/q}$ then for any $j\leq N$,

Note that $\left({eN}/{j}\right)^{-j(\rho-1)}\leq\exp(-p)$ when

Set $\alpha=\rho r/q$ and observe that if $\alpha<1$, that is, if $\rho<q/r$, then

for an absolute constant $c_{3}$. The first part of the claim now follows by setting $\rho=1+(q/r-1)/2$, implying that $1-\alpha=(q-r)/2q$.

The second part follows an identical path to the first one, by setting $0<\beta<(q/r)-1$, $\rho=\beta+1$ and $\alpha=(\beta+1)r/q<1$.

Let $q>4$ and $r=2$. Set $\beta=1/2<(q/r)-1$ and thus $\alpha<3/4$. As noted in the proof of Lemma 3.2, with probability at least $1-\exp(-p)$, for every $i\geq j_{0}$

This simple fact will play a role in verifying the third part of Assumption 2.2 for a typical coordinate projection.

Next, let us show how the norms $\|\ \|_{(p)}$ may be used to upper bound the larger coordinates in a monotone rearrangement of $Z_{1},...,Z_{N}$.

Let $Z_{1},...,Z_{N}$ be independent copies of a random variable $Z$, set $p\geq\log N$ and put $1\leq m\leq N/2e$ for which $\binom{N}{m}\leq\exp(p)$. Then, for every $t>1$, with probability at least $1-t^{-2p}\exp(-p)$, one has

The proof of Lemma 3.4 is based on the following fact, due to Latała .

Let $W$ be a nonnegative random variable. If $W_{1},...,W_{m}$ are independent copies of $W$, then

Proof of Lemma 3.4. Since $\binom{N}{m}\geq(\frac{N}{m}-1)^{m}\geq\exp(m)$, it follows that $p\geq m$; thus, by Theorem 3.5 for $W=Z^{2}$ and $r=p$,

and $\|\sum_{i=1}^{m}Z_{i}^{2}\|_{L_{p}}\lesssim 2p\|Z\|_{(2p)}^{2}$. Therefore,

for the choice of $u\sim t\sqrt{2p}\|Z\|_{(2p)}$ and since $\binom{N}{m}\leq\exp(p)$.

The proof of Theorem 3.1 is simply the combination of Lemma 3.2 and Lemma 3.4.

Let us turn to the main application of Theorem 3.1.

From here on, fix $u\geq 4$ and for every $s\geq 0$ and $r<q$ set

for a suitable absolute constant $c_{0}$ as in Theorem 3.1. Consider a finite class of functions $H$, whose cardinality is at most $2^{2^{s+3}}$.

Writing $j_{s}$ instead of $j_{s}(r,q)$, let us examine three different cases: $j_{s}=N+1$, $2\leq j_{s}\leq N$ and $j_{s}=1$. Motivated by the requirements of the chaining arguments outlined earlier, in all three cases one would like to obtain uniform control over all the functions in $H$; thus, the probability estimate with which one must control the decomposition from Theorem 3.1 for each individual function should be at least $1-\exp(-2^{s+3})$.

$\bullet$ When $j_{s}=N+1$, the decomposition is trivial, in the sense that for each function $h$, $U=(h(X_{i}))_{i=1}^{N}$ and $V=0$. Hence, setting $2p=u^{2}2^{s}$, it follows that with probability at least $1-\exp(-u^{2}2^{s}/2)$, for every $h\in H$, $(h(X_{i}))_{i=1}^{N}=U$, and

$\bullet$ When $1<j_{s}\leq N$, and setting $2p=u^{2}2^{s}$ once again, it follows that with probability at least $1-2\exp(-u^{2}2^{s}/2)$, for every $h\in H$, $(h(X_{i}))_{i=1}^{N}=U+V$, where

$\bullet$ When $j_{s}=1$, $(h(X_{i}))_{i=1}^{N}=V$ and $U=0$. Moreover, because $j_{s}=1$,

for constants $c_{1}$ and $c_{2}$ that depend only on $r$ and $q$.

Let $0<\beta\leq(q/r)-1$ and note that by Theorem 3.1, with probability at least $1-c_{3}N^{-\beta}$,

Therefore, (3.4) holds with probability of $1-2\exp(-\theta u^{2}2^{s})$ for every $h\in H$ if

which is the case when $u\geq c_{4}(q,r)/\sqrt{\beta}$ and $\theta\leq c_{5}(q,r)\beta$.

Combining these observations yields the following outcome:

There exist absolute constants $c_{0},c_{1}$ and for every $1\leq r<q$ there exist constants $c_{2}$ and $c_{3}$ that depend only on $q$ and $r$ for which the following holds. Set

for $0<\beta\leq(q/r)-1$ and $u\geq c_{2}/\sqrt{\beta}$. If $H\subset L_{q}$ is of cardinality at most $2^{2^{s+2}}$, then with probability at least $1-2\exp(-c_{3}\beta u^{2}2^{s})$, for every $h\in H$, $(h(X_{i}))_{i=1}^{N}=U_{h}+V_{h}$; the support of each $U_{h}$ is the set of the largest $j_{s}-1$ coordinates of $(|h(X_{i})|)_{i=1}^{N}$ while $V_{h}$ is supported on its complement;

Proofs of the main results

Let us turn to the implications of Corollary 3.6 in the contexts of Assumption 2.1 and Assumption 2.2.

Let $F$ be a class of functions and set $(F_{s})_{s\geq 0}$ to be an admissible sequence of $F$. Fix $s_{0}$ to be named later and set $s\geq s_{0}$. Clearly,

and thus Corollary 3.6 holds for both $F_{s}$ and $\{\Delta_{s}f:f\in F\}$.

For every $s\geq s_{0}$, denote by $\left[(\Delta_{s}f)(X_{i})\right]^{*}$ the $i$-th largest coordinate of the vector $\left(|\Delta_{s}f|(X_{i})\right)_{i=1}^{N}$, and put $\left[(\pi_{s}f)(X_{i})\right]^{*}$ to be the $i$-th largest coordinate of the vector $\left(|\pi_{s}f|(X_{i})\right)_{i=1}^{N}$. Finally, recall that

Let us see how Corollary 3.6 may be used to prove Theorem 1.9.

Let $q>2$, $r=\min\{1/2+q/4,2\}$ and $r_{1}=2r^{\prime}$, where $r^{\prime}$ is the conjugate index of $r$. Put $q_{1}=2r_{1}$ and set $\beta=1/2<(q_{1}/r_{1})-1$. Also, let

Below is the summary of the outcome of Corollary 3.6 when applied to the classes $\{\Delta_{s}f:f\in F\}$ and $F_{s}$ for $s\geq s_{0}$, $q_{1}$ and $r_{1}$ as above, and for $u>\max\{\sqrt{q_{1}},4\}$.

There are constants $c_{1}$ and $c_{2}$ that depend only on $q$ and an event of probability at least $1-2\exp(-c_{1}u^{2}2^{s_{0}})$ on which the following holds. For every $f\in F$ and $s\geq s_{0}$,

Observe that if $q\geq 4$ then $r=2$, and thus $2r=2r^{\prime}=4$ and $q_{1}=8$. Therefore, all the constants in Corollary 4.1 are absolute constants and one may take any $u\geq 8$.

$\bullet$ $\|\ \|_{[s]}=c_{2}u2^{s/2}\|\ \|_{(u^{2}2^{s})}$,

$\bullet$ $\|\ \|=c_{2}\|\ \|_{L_{q_{1}}}$,

Hence, for an almost optimal admissible sequence in $F$,

Recall that $u^{2}\geq q_{1}$, and thus, for every $s\geq 0$,

Combining these observations with Corollary 2.1, it follows that for every $(X_{i})_{i=1}^{N}$ for which Corollary 4.1 holds (i.e., with probability at least $1-2\exp(-c_{1}u^{2}2^{s_{0}})$ with respect to $\mu^{N}$), and for every $(\xi_{i})_{i=1}^{N}$, one has that with $(\varepsilon_{i})_{i=1}^{N}$ probability at least $1-2\exp(-c_{1}t^{2}2^{s_{0}})$, for every $f\in F$