# A uniform Dvoretzky-Kiefer-Wolfowitz inequality

Daniel Bartl  University of Vienna, Faculty of Mathematics
<EMAIL_ADDRESS>and  Shahar Mendelson  The Australian National
University, Mathematical Sciences Institute<EMAIL_ADDRESS>
###### Abstract.

We show that under minimal assumption on a class of functions $\mathcal{H}$
defined on a probability space $(\mathcal{X},\mu)$, there is a threshold
$\Delta_{0}$ satisfying the following: for every $\Delta\geq\Delta_{0}$, with
probability at least $1-2\exp(-c\Delta m)$ with respect to $\mu^{\otimes m}$,

$\sup_{h\in\mathcal{H}}\sup_{t\in\mathbb{R}}\left|\mathbb{P}(h(X)\leq
t)-\frac{1}{m}\sum_{i=1}^{m}1_{(-\infty,t]}(h(X_{i}))\right|\leq\sqrt{\Delta};$

here $X$ is distributed according to $\mu$ and $(X_{i})_{i=1}^{m}$ are
independent copies of $X$.

The value of $\Delta_{0}$ is determined by an unexpected complexity parameter
of the class $\mathcal{H}$ that captures the set’s geometry (Talagrand’s
$\gamma_{1}$-functional). The bound, the probability estimate and the value of
$\Delta_{0}$ are all optimal up to a logarithmic factor.

##  1\. Introduction

The Dvoretzky-Kiefer-Wolfowitz inequality is a classical result in probability
theory that establishes the speed of convergence of the empirical distribution
function of a random variable to its true counterpart. More accurately, let
$X$ be a real-valued random variable and set $F(t)=\mathbb{P}(X\leq t)$ to be
its distribution function. Let $X_{1},\dots,X_{m}$ be independent copies of
$X$, and denote the _empirical distribution function_ by

$F_{m}(t)=\mathbb{P}_{m}(X\leq
t)=\frac{1}{m}\sum_{i=1}^{m}1_{(-\infty,t]}(X_{i}).$

The celebrated _Glivenko-Cantelli_ theorem [11, 17, 30] implies that

$\|F_{m}-F\|_{L_{\infty}}=\sup_{t\in\mathbb{R}}|F_{m}(t)-F(t)|\to 0$

almost surly as $m$ tends to infinity. The _Dvoretzky-Kiefer-Wolfowitz_ (DKW)
inequality [13] extends the Glivenko-Cantelli theorem by specifying the
correct speed of convergence. The following formulation of the DKW inequality
is from [24].

######  Theorem 1.1.

For every $\Delta>0$, with probability at least $1-2\exp(-2\Delta m)$,

(1.1) $\displaystyle\|F_{m}-F\|_{L_{\infty}}\leq\sqrt{\Delta}.$

The estimate (1.1) is optimal: roughly put, if $X$ is a ‘non-trivial’ random
variable111For instance, if there is no $t\in\mathbb{R}$ for which
$\mathbb{P}(X=t)>0.99$., there are absolute constants $c_{1},c_{2},c_{3}$ that
satisfy for every $\Delta\leq\frac{1}{2}$ and $m\geq 4$,

$\displaystyle\mathbb{P}\left(\|F_{m}-F\|_{L_{\infty}}\geq
c_{1}\sqrt{\Delta}\right)\geq c_{2}\exp(-c_{3}\Delta m).$

Note that as absolute constants, $c_{1},c_{2},c_{3}$ are strictly positive and
do not depend on the random variable $X$ (as long as $X$ is ‘non-trivial’ in a
reasonable sense). For more information on this lower bound, see, e.g., [8].

While Theorem 1.1 is a characterisation of the speed of convergence of
$\|F_{m}-F\|_{L_{\infty}}$ in the case of a single random variable, modern
applications often require dealing with a collection of random variables
_simultaneously_. Understanding the uniform behaviour of
$\|F_{m}-F\|_{L_{\infty}}$ is the goal of this article.

To formulate the question at hand, let $(\mathcal{X},\mu)$ be a probability
space and let $X$ be distributed as $\mu$. Set $X_{1},\dots,X_{m}$ to be
independent copies of $X$, and let $\mathcal{H}$ be a class of real valued
functions defined on $\mathcal{X}$. For $h\in\mathcal{H}$, let
$F_{h}(t)=\mathbb{P}(h(X)\leq t)$ be the distribution function of $h(X)$ and
put

$F_{m,h}(t)=\mathbb{P}_{m}(h(X)\leq
t)=\frac{1}{m}\sum_{i=1}^{m}1_{(-\infty,t]}(h(X_{i}))$

to be the corresponding empirical distribution function.

######  Question 1.2.

Under what conditions on $X$ and for what values of $\Delta$ does a version of
the DKW inequality hold uniformly in $\mathcal{H}$: that with probability at
least $1-2\exp(-c\Delta m)$,
$\sup_{h\in\mathcal{H}}\|F_{m,h}-F_{h}\|_{L_{\infty}}\leq\sqrt{\Delta}?$

As a starting point, consider the case where $\mathcal{X}=\mathbb{R}^{d}$ and
$X$ is an isotropic222That is, $X$ is centred and its covariance is the
identity. random vector. Let $A\subset S^{d-1}$ and set

$\mathcal{H}=\\{\left\langle\cdot,x\right\rangle:x\in A\\}.$

Thus, $\mathcal{H}$ is the class of _liner functionals_ associated with $A$.
Let $F_{x}(t)=F_{\left\langle\cdot,x\right\rangle}(t)=\mathbb{P}(\left\langle
X,x\right\rangle\leq t)$ and set $F_{m,x}(t)=\mathbb{P}_{m}(\left\langle
X,x\right\rangle\leq t)$.

###  1.1. The current state of the art

Let us begin by describing (known) restrictions on $\Delta$. The trivial case,
$|A|=1$ is fully understood thanks to the optimality of Theorem 1.1. In that
case, a nontrivial estimate is possible only when $\Delta\gtrsim\frac{1}{m}$.

The other extreme case, $A=S^{d-1}$, was explored in [6] using Talagrand’s
concentration inequality and standard methods from VC-theory. The following
formulation is an immediate outcome of [6, Corollary 2.8].

######  Theorem 1.3.

There are absolute constants $c_{1}$ and $c_{2}$ such that the following
holds. If $m\geq d$ and

(1.2) $\Delta\geq c_{1}\frac{d}{m},$

then with probability at least $1-2\exp(-c_{2}\Delta m)$,

(1.3) $\sup_{x\in
S^{d-1}}\left\|F_{m,x}-F_{x}\right\|_{L_{\infty}}\leq\sqrt{\Delta}.$

Theorem 1.3 is clearly optimal for $\Delta$ that satisfies (1.2), simply
because (1.3) is the best one can expect even for a single random variable.
Moreover, one can show (e.g. using Proposition 6.1 below) that the restriction
on $\Delta$ in (1.2) is _optimal_ : for example, if $X$ is the standard
gaussian random vector then

$\mathbb{P}\left(\sup_{x\in
S^{d-1}}\left\|F_{m,x}-F_{x}\right\|_{L_{\infty}}\geq
c\sqrt{\frac{d}{m}}\right)\geq 0.9.$

Thus, Question 1.2 is fully understood in the two extreme cases: $|A|=1$ and
$A=S^{d-1}$. At the same time, the situation for an _arbitrary_ set $A\subset
S^{d-1}$ is far more subtle. Indeed, while Theorem 1.3 still applies, the
restriction that $\Delta\gtrsim\frac{d}{m}$ (and $m\gtrsim d$) is independent
of $A$ and therefore cannot be optimal. One would expect a ‘continuous shift’
from $\Delta\sim\frac{d}{m}$ for the entire sphere to $\Delta\sim\frac{1}{m}$
for a singleton—that takes into account some appropriate notion of
_complexity_ of the set $A$.

There are various notions of complexity that one typically considers (e.g. the
gaussian mean-width, see [5, 29, 31]), but the correct notation of complexity
here turns out to be rather surprising: _Talagrand’s $\gamma_{1}$-functional_.

######  Definition 1.4.

An _admissible sequence_ of $A$ is a collection of subsets $(A_{s})_{s\geq 0}$
that satisfy $|A_{0}|=1$ and $|A_{s}|\leq 2^{2^{s}}$ for $s\geq 1$. For $x\in
A$ let $\pi_{s}x\in A_{s}$ be the nearest element to $x$ with respect to the
Euclidean distance. For $\alpha=1,2$ define _Talagrand’s
$\gamma_{\alpha}$-functional_ by

$\gamma_{\alpha}(A)=\inf\sup_{x\in A}\sum_{s\geq
0}2^{s/\alpha}\|x-\pi_{s}x\|_{2},$

with the infimum taken over all admissible sequences of $A$.

We will assume without loss of generality that $A$ is a symmetric set, that
is, $A=-A$; in particular, it is standard to verify that
$\gamma_{\alpha}(A)\geq 1$.

The $\gamma_{2}$-functional is a natural complexity parameter of $A$, seeing
that is equivalent to the set’s gaussian mean-width. Indeed, if $G$ is the
standard gaussian random vector in $\mathbb{R}^{d}$, then by Talagrand’s
majorizing measures theorem [28, 29], for any $A\subset\mathbb{R}^{d}$,

$c\,\gamma_{2}(A)\leq\mathbb{E}\sup_{x\in A}\left\langle G,x\right\rangle\leq
c^{\prime}\,\gamma_{2}(A),$

for absolute constants $c$ and $c^{\prime}$.

An indication why $\gamma_{2}(A)$ is likely to be the wrong choice in the
context of Question 1.2 is the fact that with high probability,

$\displaystyle(\ast)=\sup_{x\in A}\left|\frac{1}{m}\sum_{i=1}^{m}\left\langle
G_{i},x\right\rangle-\mathbb{E}\left\langle
G,x\right\rangle\right|\sim\frac{\gamma_{2}(A)}{\sqrt{m}}.$

Using tail integration it is evident that

$(\ast)=\sup_{x\in
A}\left|\int_{\mathbb{R}}\big{(}F_{m,x}(t)-F_{x}(t)\big{)}\,dt\right|,$

which can be significantly smaller than $\sup_{x\in
A}\|F_{m,x}-F_{x}\|_{L_{\infty}}$.

At the same time, there is no apparent reason why $\gamma_{1}(A)$ determines
$\sup_{x\in A}\|F_{m,x}-F_{x}\|_{L_{\infty}}$.

######  Remark 1.5.

It worth noting that there are several situations where $\gamma_{1}$ and
$\gamma_{2}^{2}$ are equivalent. For instance,
$\gamma_{1}(S^{d-1})\sim\gamma_{2}^{2}(S^{d-1})\sim d$; and if $A$ is the set
of $s$-sparse vectors in $S^{d-1}$ then
$\gamma_{1}(A)\sim\gamma_{2}^{2}(A)\sim s\log(\frac{ed}{s})$. However, in
general there can be a substantial difference between the two: for example, if
$A$ is a well-chosen spherical cap, $\gamma_{1}(A)\sim\sqrt{d}$ and
$\gamma_{2}^{2}(A)\sim 1$.

The following answer to Question 1.2 when the random vector $X$ is the
standard gaussian was recently established in [7]—it is an immediate outcome
of Theorem 1.7 there.

######  Theorem 1.6 ($A\subset S^{d-1}$, $X$=gaussian).

There are absolute constants $c_{1}$ and $c_{2}$ for which the following
holds. Let $X=G$ be the standard gaussian vector in $\mathbb{R}^{d}$. If
$A\subset S^{d-1}$ is a symmetric set, $m\geq\gamma_{1}(A)$, and

(1.4) $\Delta\geq
c_{1}\frac{\gamma_{1}(A)}{m}\log^{3}\left(\frac{em}{\gamma_{1}(A)}\right),$

then with probability at least $1-2\exp(-c_{2}\Delta m)$,

$\displaystyle\sup_{x\in
A}\left\|F_{m,x}-F_{x}\right\|_{L_{\infty}}\leq\sqrt{\Delta}.$

Just as in Theorem 1.3, the probability estimate is clearly optimal. The only
question is whether the restriction on $\Delta$ in (1.4) can be improved, and
it turns out that it cannot (up to, perhaps, logarithmic factors): There is an
absolute constant $c$ and for every $A\subset S^{d-1}$ and any $m$ large
enough, with probability at least $0.9$,

(1.5) $\sup_{x\in
A}\|F_{m,x}-F_{x}\|_{L_{\infty}}\geq\frac{c}{\sqrt{\log(d)}}\cdot\sqrt{\frac{\gamma_{1}(A)}{m}}.$

More details on (1.5) can be found in Section 6.1.

###  1.2. General random vectors

Although Theorem 1.6 is (almost) a complete answer to Question 1.2 when $X$ is
the standard gaussian random vector, it does not reveal what happens for more
general isotropic random vectors (nor what happens when considering an
arbitrary class of functions for that matter). When trying to extend Theorem
1.6 one immediately encounters a surprise: The proof of Theorem 1.6 is based
on a chaining argument, and it stands to reason that its assertion should
remain true under a suitable tail-assumption on the random vector $X$ (e.g. if
$X$ is subgaussian333An isotropic random vector $X$ is subgaussian with
constant $L$ if for every $x\in S^{d-1}$ and $t\geq 0$,
$\mathbb{P}(|\left\langle X,x\right\rangle|\geq Lt)\leq 2\exp(-t^{2})$.).
However, as we show in what follows, a strong tail assumption is not enough.
In fact, it turns out that:

For a uniform DKW inequality to hold, the marginal distributions of $X$ must
$\cdot$ exhibit a fast tail decay _and_ $\cdot$ satisfy a suitable small ball
condition.

The obvious choice of random vectors that will be used as a benchmark in our
analysis are isotropic with iid coordinates. As it happens, the necessity of
the two conditions (the fast tail decay and the small ball condition) are
already exhibited on such random vectors.

Let $w$ be a symmetric random variable with variance 1, and consider the
random vector $X$ in $\mathbb{R}^{d}$ whose coordinates are independent copies
of $w$. In particular, $X$ is isotropic. We also assume that $w$ is ‘non-
trivial’, e.g. in the sense that $\mathbb{P}(|w|\geq 0.1)\geq 0.1$.

######  Lemma 1.7.

Suppose that $w$ has an atom of size $\eta>0$ (i.e.,
$\mathbb{P}(w=t_{0})=\eta$ for some $t_{0}\in\mathbb{R}$). Then for every
$m\geq\frac{c_{1}}{\eta^{2}}$ there is $d\in\mathbb{N}$ and a set $A\subset
S^{d-1}$ satisfying $\gamma_{1}(A)\leq 10$ and

(1.6) $\displaystyle\mathbb{P}\left(\sup_{x\in
A}\|F_{m,x}-F_{x}\|_{L_{\infty}}\geq c_{2}\cdot\eta\right)\geq 0.9.$

If Theorem 1.6 were true for the random vector $X=(w_{1},\dots,w_{d})$, then
it would follow that with high (polynomial) probability,

$\sup_{x\in A}\left\|F_{m,x}-F_{x}\right\|_{L_{\infty}}\leq
c\sqrt{\frac{\log^{3}(m)}{m}},$

which is far from the true behaviour as seen in (1.6). As an example, let $w$
be the symmetric $\\{-1,1\\}$-valued random variable, and thus $X$ is the
standard Bernoulli random vector in $\mathbb{R}^{d}$. Then $\eta=\frac{1}{2}$,
and it follows from Lemma 1.7 that the Bernoulli random vector does not
satisfy any reasonable uniform version of the DKW inequality.

The obvious conclusion is that once one moves from the gaussian to the
subgaussian realm, the best possible bound on $\sup_{x\in
A}\left\|F_{m,x}-F_{x}\right\|_{L_{\infty}}$ is far weaker than in the
gaussian case—unless one imposes more assumptions on $X$—starting with not
having significant atoms.

######  Remark 1.8.

  1. (a)

As it happens, the situation is even worse than what is indicated by Lemma
1.7: The set $A$ from the lemma can be chosen to have an Euclidean diameter
that is arbitrarily small. Hence, a satisfactory estimate on $\sup_{x\in
A}\left\|F_{m,x}-F_{x}\right\|_{L_{\infty}}$ that is based on _any_ reasonable
complexity parameter of $A$ cannot follow from a tail assumption.

  2. (b)

It is possible to show that Lemma 1.7 remains valid even if $w$ has a density,
but that density is unbounded in a suitable sense (roughly put, e.g. if there
is an interval with length proportional to $\frac{\eta}{m}$ on which the
density is of order $m$).

Following Lemma 1.7, a uniform DKW inequality cannot be true if $w$ has
significant atoms or a density that is unbounded in a suitable sense—and that
cannot be remedied by a subgaussian tail behaviour. The next result shows that
some (relatively strong) tail assumption is also needed: without a
_subexponential tail decay_ 444An isotropic random vector $X$ has a
subexponential tail decay with constant $L$ if for every $x\in S^{d-1}$ and
$t\geq 0$, $\mathbb{P}(|\left\langle X,x\right\rangle|\geq Lt)\leq 2\exp(-t)$.
a uniform DKW inequality cannot be true.

######  Lemma 1.9.

Let $X$ be an isotropic random vector with independent coordinates distributed
according to a symmetric random variable $w$. If $w$ does not have a
subexponential tail decay, then for every $m\geq 20$ there is $d\in\mathbb{N}$
and a set $A\subset S^{d-1}$ satisfying $\gamma_{1}(A)\leq 10$ and

$\mathbb{P}\left(\sup_{x\in
A}\|F_{m,x}-F_{x}\|_{L_{\infty}}\geq\frac{1}{10}\right)\geq 0.9.$

The proofs of Lemma 1.7 and Lemma 1.9 are presented in Section 4.

With these obstructions in mind, let us explore Question 1.2 for random
vectors that satisfy the minimal conditions that are a ‘must’:

######  Assumption 1.10.

Let $X$ be an isotropic random vector in $\mathbb{R}^{d}$. There are constants
$L,D\geq 1$ for which:

  1. (a)

For every $x\in S^{d-1}$ and $t\geq 0$, $\mathbb{P}(|\left\langle
X,x\right\rangle|\geq Lt)\leq 2\exp(-t).$

  2. (b)

For every $x\in S^{d-1}$, $\left\langle X,x\right\rangle$ has a density
$f_{x}$ satisfying that $\|f_{x}\|_{L_{\infty}}\leq D$.

The main result of this article (formulated in the context of a class of
linear functionals in $\mathbb{R}^{d}$) is that those necessary conditions are
actually sufficient for a uniform DKW inequality:

######  Theorem 1.11.

For every $L,D\geq 1$ there are constants $c_{1}$ and $c_{2}$ that depend only
on $L$ and $D$ for which the following holds. If $X$ satisfies Assumption
1.10, $A\subset S^{d-1}$ is symmetric, $m\geq\gamma_{1}(A)$, and $\Delta\geq
c_{1}\frac{\gamma_{1}(A)}{m}\log^{3}\left(\frac{em}{\gamma_{1}(A)}\right),$
then with probability at least $1-2\exp(-c_{2}\Delta m)$, $\sup_{x\in
A}\left\|F_{m,x}-F_{x}\right\|_{L_{\infty}}\leq\sqrt{\Delta}.$

Observe that the gaussian random vector is a ‘legal candidate’ in Theorem
1.11: it satisfies Assumption 1.10 for absolute constants $L$ and $D$. As a
result, by the lower bounds in the gaussian case, the probability estimate is
optimal and the restriction on $\Delta$ in Theorem 1.11 cannot be improved
beyond logarithmic factors.

An important example of a family of random vectors that satisfy Assumption
1.10 is the one endowed by _log-concave_ measures. Indeed, it follows from
Borell’s lemma (see, e.g., [5, Lemma 3.5.10]) that if $X$ is isotropic and
log-concave, linear functionals $\left\langle X,x\right\rangle$ exhibit a
subexponential tail decay. Also, the densities of $\left\langle
X,x\right\rangle$ are uniformly bounded by an absolute constant [9,
Proposition 2.1]. Therefore, we have the following.

######  Corollary 1.12.

There are absolute constants $c_{1}$ and $c_{2}$ for which the following
holds. Let $X$ be an isotropic, log-concave random vector in $\mathbb{R}^{d}$.
If $A\subset S^{d-1}$ is a symmetric set, $m\geq\gamma_{1}(A)$ and $\Delta\geq
c_{1}\frac{\gamma_{1}(A)}{m}\log^{3}\left(\frac{em}{\gamma_{1}(A)}\right),$
then with probability at least $1-2\exp(-c_{2}\Delta m)$, $\sup_{x\in
A}\left\|F_{m,x}-F_{x}\right\|_{L_{\infty}}\leq\sqrt{\Delta}.$

The proof of Theorem 1.11 is presented in Section 3, and the proofs of Lemma
1.7 and Lemma 1.9 can be found in Section 4. In Section 5 we present an
application of the uniform DKW inequality to a collection of estimation
problems. These problems have been studied extensively in recent years, and
their objective is estimating $\mathbb{E}\varphi(\left\langle
X,x\right\rangle)$ (for various choices of $\varphi$) uniformly in $x\in A$,
using only the random sample $(X_{i})_{i=1}^{m}$ as data. Finally, Section 6
is devoted to a few concluding remarks.

_Related literature:_ As previously indicated, [7] addresses a similar problem
to the one considered here (albeit just for the gaussian random vector). We
outline some of the differences between the problem studied in [7] and
Question 1.2 in Section 6.2.

Other than [7], the article that seems the most closely related to this one is
[22], where an estimate similar to Theorem 1.11 is proven, but with a
different restriction on $\Delta$. That restriction is given in terms of a
fixed point condition (involving the $L_{2}(\mathbb{P})$-covering numbers and
the Rademacher complexity associated with the underlying class) and it is far
from optimal; for example, one can easily construct sets $A$ for which the
restriction on $\Delta$ in [22] requires that
$\Delta\gtrsim(\frac{\gamma_{1}(A)}{m})^{2/5}$. Other known estimates, such as
the ones from [3, 4, 15, 16, 19, 20], where formulated either in terms of
conditions on the random metric structure of the function class (respectively
of their sub-level sets), or in terms of the VC-dimension. All these results
are too weak to be applicable in the general case we focus on here.

_Notation:_ Throughout, $c,c_{0},c_{1},\ldots$ are absolute constants. Their
value may change from line to line. If a constant $c$ depends on a parameter
$B$ we write $c=c(B)$. If $x\leq cy$ for an absolute constant $c$, that is
denoted by $x\lesssim y$, and $x\sim y$ means that $x\lesssim y$ and $x\gtrsim
y$. Finally, the cardinality of a finite set $B$ is denoted by $|B|$.

##  2\. Preliminary estimates

In this section we prove several basic estimates that play a crucial role in
the proof of Theorem 3.2.

The first observation is that if $X$ and $Y$ are random variables,
$t\in\mathbb{R}$ and $r>0$, then

$\displaystyle\left\\{X\leq t\right\\}$ $\displaystyle=\left\\{X\leq t\
\wedge\ |X-Y|<r\right\\}\cup\left\\{X\leq t\ \wedge\ |X-Y|\geq r\right\\}$
(2.1) $\displaystyle\subset\left\\{Y\leq t+r\right\\}\cup\left\\{|X-Y|\geq
r\right\\}.$

In particular, using (2) for $\mathbb{P}$ and $\mathbb{P}_{m}$ respectively,

(2.2) $\displaystyle\mathbb{P}(X\leq t)$ $\displaystyle\leq\mathbb{P}(Y\leq
t+r)+\mathbb{P}(|X-Y|\geq r)\text{ and}$ (2.3)
$\displaystyle\mathbb{P}_{m}(X\leq t)$ $\displaystyle\leq\mathbb{P}_{m}(Y\leq
t+r)+\mathbb{P}_{m}(|X-Y|\geq r).$

In fact, (2.2) is two-sided. Indeed,

$\displaystyle\left\\{Y\leq t+r\right\\}=$ $\displaystyle\left\\{Y\leq
t-r\right\\}\cup\left\\{Y\in(t-r,t+r]\right\\}$ $\displaystyle\subset$
$\displaystyle\left\\{X\leq t\right\\}\cup\left\\{|X-Y|\geq
r\right\\}\cup\left\\{Y\in(t-r,t+r]\right\\}$

and therefore

(2.4) $\mathbb{P}(Y\leq t+r)\leq\mathbb{P}(X\leq t)+\mathbb{P}(|X-Y|\geq
r)+\mathbb{P}(Y\in(t-r,t+r]).$

######  Corollary 2.1.

Let $X$ and $Y$ be random variables. For any $t\in\mathbb{R}$ and $r>0$, we
have that

$\left|F_{X}(t)-F_{Y}(t)\right|\leq\mathbb{P}(|X-Y|\geq
r)+\mathbb{P}(Y\in(t-r,t+r]).$

In particular, it follows from Corollary 2.1 that if $Y$ has a density $f_{Y}$
that satisfies $\|f_{Y}\|_{L_{\infty}}\leq D$, then

$\left|F_{X}(t)-F_{Y}(t)\right|\leq\mathbb{P}(|X-Y|\geq r)+2Dr.$

Next, let us turn to a simple ‘stability’ estimate: if $Y$ is a random
variable and $\|F_{m,Y}-F_{Y}\|_{L_{\infty}}$ is small on some event, then for
a random variable $X$ that is ‘close to $Y$’ in an appropriate sense,
$\|F_{m,X}-F_{X}\|_{L_{\infty}}$ is also small on the same event. More
accurately:

######  Lemma 2.2.

Let $X$ and $Y$ be random variables. For any $t\in\mathbb{R}$ and $r>0$, we
have that

(2.5)
$\displaystyle\begin{split}\|F_{m,X}-F_{X}\|_{L_{\infty}}&\leq\|F_{m,Y}-F_{Y}\|_{L_{\infty}}+[\mathbb{P}+\mathbb{P}_{m}](|X-Y|\geq
r)\\\ &\qquad+\mathbb{P}(Y\in(t+r,t+r]).\end{split}$

###### Proof.

Fix $t\in\mathbb{R}$ and $r>0$. By (2.3),

$\displaystyle F_{m,X}(t)$ $\displaystyle\leq
F_{m,Y}(t+r)+\mathbb{P}_{m}(|X-Y|\geq r)$ $\displaystyle\leq
F_{Y}(t+r)+\|F_{m,Y}-F_{Y}\|_{L_{\infty}}+\mathbb{P}_{m}(|X-Y|\geq r),$

and by (2.4),

$F_{Y}(t+r)\leq F_{X}(t)+\mathbb{P}(|X-Y|\geq r)+\mathbb{P}(Y\in(t-r,t+r]).$

In a similar manner, by (2.2),

$\displaystyle F_{X}(t)$ $\displaystyle\leq F_{Y}(t+r)+\mathbb{P}(|X-Y|\geq
r)$ $\displaystyle\leq
F_{Y}(t-r)+\mathbb{P}(Y\in(t-r,t+r])+\mathbb{P}(|X-Y|\geq r),$

and by (2.3) (with the roles of $X$ and $Y$ reversed),

$\displaystyle F_{Y}(t-r)$ $\displaystyle\leq
F_{m,Y}(t-r)+\|F_{m,Y}-F_{Y}\|_{L_{\infty}}$ $\displaystyle\leq
F_{m,X}(t)+\mathbb{P}_{m}(|X-Y|\geq r)+\|F_{m,Y}-F_{Y}\|_{L_{\infty}}.\qed$

For the rest of this section, we assume that the random variables $X$ and $Y$
are absolutely continuous. For simplicity, we also assume that their
distribution functions are invertible; the necessary modifications when that
is not the case are minimal. In particular, setting $u=F_{X}(t)$,

$\|F_{m,X}-F_{X}\|_{L_{\infty}}=\sup_{u\in(0,1)}\left|F_{m,X}(F^{-1}_{X}(u))-u\right|.$

Next, let us turn to a continuity argument of a different flavour: that if
$|F_{m,X}(F^{-1}_{X}(u))-u|$ is small on a ‘grid’ of $(0,1)$, then
$\|F_{m,X}-F_{X}\|_{\infty}$ is small as well. To that end, for
$\delta\in(0,1/4)$, set

$U_{\delta}=\left\\{\delta\ell:1\leq\ell\leq\frac{1-\delta}{\delta}\right\\}.$

######  Lemma 2.3.

For every $\delta\in(0,1/4)$,

(2.6) $\|F_{m,X}-F_{X}\|_{L_{\infty}}\leq\delta+\max_{u\in
U_{\delta}}\left|F_{m,X}(F^{-1}_{X}(u))-u\right|.$

###### Proof.

Let $t\in\mathbb{R}$, consider $u=F_{X}(t)$, and set

$\beta=\max_{w\in U_{\delta}}\left|F_{m,X}(F^{-1}_{X}(w))-w\right|.$

We will only prove one direction of (2.6), namely that
$F_{m,X}(t)-F_{X}(t)\leq\delta+\beta$. The other direction follows the same
path and is omitted.

_Case 1:_ $u\in[0,\delta)$. It follows from the monotonicity of $F_{X}$ that
$t\leq F_{X}^{-1}(\delta)$, and by the monotonicity of $F_{m,X}$ and the
definition of $\beta$,

$F_{m,X}(t)\leq F_{m,X}(F^{-1}_{X}(\delta))\leq\delta+\beta\leq
F_{X}(t)+\delta+\beta.$

_Case 2:_ $u\in[\delta,1/2]$. Denote by $w$ the smallest element in
$U_{\delta}$ that satisfies $w\geq u$; in particular $|u-w|\leq\delta$. By the
monotonicity of $F_{X}$, $F_{X}^{-1}(u)\leq F_{X}^{-1}(w)$, and by the
monotonicity of $F_{m,X}$,

$F_{m,X}(t)=F_{m,X}(F^{-1}_{X}(u))\leq F_{m,X}(F^{-1}_{X}(w)).$

Moreover,

$F_{m,X}(F^{-1}_{X}(w))\leq w+\beta\leq u+\delta+\beta=F_{X}(t)+\delta+\beta,$

and therefore $F_{m,X}(t)-F_{X}(t)\leq\delta+\beta$, as claimed.

_Case 3:_ $u\in(1/2,1]$. The proof follows an identical path to the case
$u\in[0,1/2]$, and is omitted. ∎

The final ingredients we need are estimates on the symmetric differences of
‘level sets’ of functions that have the same measure.

######  Lemma 2.4.

Let $X$ and $Y$ be absolutely continuous random variables and assume that
their densities satisfy that
$\|f_{X}\|_{L_{\infty}},\|f_{Y}\|_{L_{\infty}}\leq D$. Then for every
$u\in(0,1)$ and $r>0$,

$\mathbb{P}\left(\left\\{X\leq F^{-1}_{X}(u)\right\\}\ \bigtriangleup\
\left\\{Y\leq F_{Y}^{-1}(u)\right\\}\right)\leq 4\bigl{(}\mathbb{P}(|X-Y|\geq
r)+rD\bigr{)}.$

The proof of Lemma 2.4 requires some preparations. Observe that by the union
bound,

$\mathbb{P}\left(\left\\{X\leq F^{-1}_{X}(u)\right\\}\ \bigtriangleup\
\left\\{Y\leq F_{Y}^{-1}(u)\right\\}\right)\leq 2\min\\{u,1-u\\};$

hence, we may assume that $\delta=\mathbb{P}(|X-Y|\geq
r)<\min\\{u,1-u\\}$—otherwise the lemma is trivially true.

The key to the proof of Lemma 2.4 is the fact that if $\delta<\min\\{u,1-u\\}$
then

(2.7) $F_{X}^{-1}(u)\leq F_{Y}^{-1}\left(u+\delta\right)+r.$

Indeed, following (2.2) once again, we have that $F_{Y}(t)\leq
F_{X}(t+r)+\delta$ for any $t\in\mathbb{R}$ and $r>0$. Setting
$t=F^{-1}_{X}(u)-r$,

$F_{Y}(F_{X}^{-1}(u)-r)\leq u+\delta,$

and (2.7) follows.

###### Proof of Lemma 2.4.

We only consider the case $u\leq 1/2$. If $\delta=\mathbb{P}(|X-Y|\geq r)\geq
u$ then the claim is trivially true; thus, assume that $\delta<u$.

Clearly,

$\displaystyle\mathbb{P}\left(X\leq F^{-1}_{X}(u)\,,\,Y>F_{Y}^{-1}(u)\right)$
$\displaystyle=\mathbb{P}\left(X\leq F^{-1}_{X}(u)\,,\,Y\geq
F_{Y}^{-1}(u+\delta)\right)$ $\displaystyle\qquad+\mathbb{P}\left(X\leq
F^{-1}_{X}(u)\,,\,Y\in(F^{-1}_{Y}(u),F^{-1}_{Y}(u+\delta))\right)$
$\displaystyle=(1)+(2).$

Firstly, note that

$(2)\leq\mathbb{P}\left(Y\in(F^{-1}_{Y}(u)\,,\,F^{-1}_{Y}(u+\delta))\right)=(u+\delta)-u=\delta.$

Secondly, by (2.7), $F_{X}^{-1}(u)\leq F_{Y}^{-1}(u+\delta)+r$. Therefore, if
$t=F_{X}^{-1}(u)$,

$(1)\leq\mathbb{P}\left(X\leq t\,,\,Y\geq t-r\right).$

Also,

$\displaystyle\left\\{X\leq t\,,\,Y\geq t-r\right\\}$
$\displaystyle=\left\\{X\leq t\,,\,Y\geq t-r\,,\,|X-Y|<r\right\\}$
$\displaystyle\qquad\cup\left\\{X\leq t\,,\,Y\geq t-r\,,\,|X-Y|\geq
r\right\\}$
$\displaystyle\subset\left\\{X\in[t-2r,t]\right\\}\cup\left\\{|X-Y|\geq
r\right\\},$

and therefore

$\displaystyle(1)\leq\mathbb{P}\left(X\leq t\,,\,Y\geq t-r\right)$
$\displaystyle\leq\mathbb{P}\left(X\in[t-2r,t]\right)+\mathbb{P}(|X-Y|\geq r)$
$\displaystyle\leq 2rD+\delta.$

An identical argument can be used to estimate
$\mathbb{P}(X>F^{-1}_{X}(u)\,,\,Y\leq F_{Y}^{-1}(u))$, completing the proof. ∎

##  3\. Proofs of the main results

The main results of this article are actually true in a more general setting
then merely for a class of linear functionals. In what follows, $X$ is a
random variable taking values in a measurable space $\mathcal{X}$ and
$X_{1},\dots,X_{m}$ are independent copies of $X$. Let

$\mathcal{H}\subset S(L_{2}(X))=\left\\{h\colon\mathcal{X}\to\mathbb{R}\text{
measurable and }\mathbb{E}h^{2}(X)=1\right\\},$

and set $\|h\|_{L_{2}}=\sqrt{\mathbb{E}h^{2}(X)}$. We ignore (well understood)
measurability issues that may be easily dealt with by assuming that
$\mathcal{H}$ is regular in an appropriate sense.

For $h\in\mathcal{H}$, let

$F_{h}(t)=\mathbb{P}(h(X)\leq t)\quad\text{and}\quad
F_{m,h}(t)=\frac{1}{m}\sum_{i=1}^{m}1_{(-\infty,t]}(h(X_{i}))$

be the real and empirical distribution function of $h$.

An _admissible sequence_ of $\mathcal{H}$ is a collection of subsets
$(\mathcal{H}_{s})_{s\geq 0}$ that satisfy $|\mathcal{H}_{0}|=1$ and
$|\mathcal{H}_{s}|\leq 2^{2^{s}}$ for $s\geq 1$. For $h\in\mathcal{H}$ let
$\pi_{s}h\in\mathcal{H}_{s}$ be the nearest element to $h$ with respect to the
$L_{2}$ distance. Talagrand’s $\gamma_{1}$-functional is defined by

$\gamma_{1}(\mathcal{H})=\inf\sup_{h\in\mathcal{H}}\sum_{s\geq
0}2^{s}\|h-\pi_{s}h\|_{L_{2}},$

with the infimum taken over all admissible sequences of $\mathcal{H}$. We
assume that $\mathcal{H}$ is symmetric class of functions, that is,
$\mathcal{H}=-\mathcal{H}$; in particular, $\gamma_{1}(\mathcal{H})\geq 1$.

Just as in the linear case, the ‘trivial obstacles’—namely, the existence of
atoms and a relatively slow tail decay—are removed by assuming the following:

######  Assumption 3.1.

There are constants $L$ and $D$ for which the following holds:

  1. (a)

For every $h,h^{\prime}\in\mathcal{H}\cup\\{0\\}$ and $t>0$,

(3.1) $\displaystyle\mathbb{P}\left(|h(X)-h^{\prime}(X)|\geq
tL\|h-h^{\prime}\|_{L_{2}}\right)\leq 2\exp(-t).$

  2. (b)

For every $h\in\mathcal{H}$, the density $f_{h}$ of $h(X)$ exists and
satisfies $\|f_{h}\|_{L_{\infty}}\leq D$.

The rest of this section is devoted to the proof of the following
generalization of Theorem 1.11.

######  Theorem 3.2.

For every $L,D\geq 1$ there are constants $c_{1},c_{2},c_{3}$ that depend only
on $L$ and $D$, and for which the following holds. If Assumption 3.1 is
satisfied, $m\geq\gamma_{1}(\mathcal{H})$ and

$\Delta\geq
c_{1}\frac{\gamma_{1}(\mathcal{H})}{m}\log^{3}\left(\frac{em}{\gamma_{1}(\mathcal{H})}\right),$

then with probability at least $1-2\exp(-c_{2}\Delta m)$,

$\displaystyle\sup_{h\in\mathcal{H}}\|F_{m,h}-F_{h}\|_{L_{\infty}}\leq
c_{3}\sqrt{\Delta}.$

######  Remark 3.3.

Note that Theorem 3.2 immediately implies Theorem 1.11.

The proof of Theorem 3.2 relies on a chaining argument. For a comprehensive
study of chaining methods and their applications, we refer to Talagrand’s
treasured book [29].

We may and do assume that $\Delta\leq\frac{1}{10}$ and $m\geq 10$. To ease
notation, we also assume that for every $h\in\mathcal{H}$ the distribution
function $F_{h}$ is invertible; the modifications needed in the general case
are straightforward.

Let $c_{0}=c_{0}(L,D)$ be a (small) constant that is specified in what
follows, and set $\Delta$ to satisfy that

(3.2) $\displaystyle c_{0}\frac{\Delta
m}{\log^{3}(e/\Delta)}\geq\gamma_{1}(\mathcal{H}).$

Consider $(\mathcal{H}_{s})_{s\geq 0}$ for which

(3.3) $\displaystyle\sup_{h\in\mathcal{H}}\sum_{s\geq
0}2^{s}\|h-\pi_{s}h\|_{L_{2}}\leq 2\gamma_{1}(\mathcal{H}),$

and set $s_{0}$ and $s_{1}$ to be the smallest integers that satisfy

$2^{s_{0}}\geq\Delta m\quad\text{and}\quad 2^{s_{1}}\geq\sqrt{\Delta}m;$

in particular $2^{s_{0}}\leq 2\Delta m$ and $2^{s_{1}}\leq 2\sqrt{\Delta}m$.

The proof of Theorem 3.2 consists of three steps that are outlined here. The
complete arguments are presented in Sections 3.1–3.3.

Invoking Lemma 2.2 (with $r=\sqrt{\Delta}$),

$\displaystyle\left\|F_{m,h}-F_{h}\right\|_{L_{\infty}}$
$\displaystyle\leq\|F_{m,\pi_{s_{1}}h}-F_{\pi_{s_{1}}h}\|_{L_{\infty}}+2D\sqrt{\Delta}$
$\displaystyle\qquad+[\mathbb{P}+\mathbb{P}_{m}]\left(|h(X)-\pi_{s_{1}}h(X)|\geq\sqrt{\Delta}\right)$
$\displaystyle=(1)+(2)+(3)$

and one has to show that on a high probability event and uniformly in
$h\in\mathcal{H}$, $(1)$ and $(3)$ are at most of order $\sqrt{\Delta}$.

To that end, by the choice of $s_{1}$ and the restriction on $\Delta$ in
(3.2),

$\|h-\pi_{s_{1}}h\|_{L_{2}}\leq\frac{2\gamma_{1}(\mathcal{H})}{2^{s_{1}}}\leq\frac{\sqrt{\Delta}}{L\log(e/\Delta)};$

therefore, by the subexponential tail decay,

(3.4)
$\displaystyle\mathbb{P}\left(|h(X)-\pi_{s_{1}}h(X)|\geq\sqrt{\Delta}\right)\leq\sqrt{\Delta}.$

An ‘empirical version’ of (3.4) is also true, and its proof is presented in
Section 3.2.

The combination of these two facts implies that $(3)\lesssim\sqrt{\Delta}$.

At the heart of the proof for Theorem 3.2 is the estimate on $(1)$: that with
high probability,

(3.5)
$\displaystyle\sup_{h\in\mathcal{H}}\|F_{m,\pi_{s_{1}}h}-F_{\pi_{s_{1}}h}\|_{L_{\infty}}\leq
c(L,D)\sqrt{\Delta}.$

The proof of (3.5) is based on an unorthodox chaining argument, though its
starting point is rather obvious: seeing ‘how far’ the DKW inequality for a
single random variable takes us.

######  Lemma 3.4.

There is an absolute constant $c_{1}$ such that with probability at least
$1-2\exp(-\Delta m)$, for every $h\in\mathcal{H}$

(3.6) $\displaystyle\|F_{m,\pi_{s_{0}}h}-F_{\pi_{s_{0}}h}\|_{L_{\infty}}\leq
c_{1}\sqrt{\Delta}.$

The proof of Lemma 3.4 is obvious: by Theorem 1.1, (3.6) holds for every fixed
$h\in\mathcal{H}$ with probability at least $1-2\exp(-3\Delta m)$. Since

$|\\{\pi_{s_{0}}h:h\in\mathcal{H}\\}|\leq 2^{2^{s_{0}}}\leq\exp(2\Delta m),$

the claim follows from the union bound.

###  3.1. Going further down the chain

With $\\{\pi_{s_{0}}h:h\in\mathcal{H}\\}$ being the starting points of each
chain, the next step is to go further down the chains — up to $\pi_{s_{1}}h$.

######  Lemma 3.5.

There is an absolute constant $c_{1}$ and a constant $c_{2}$ depending only on
$L$ and $D$ such that with probability at least $1-2\exp(-c_{1}\Delta m)$, for
every $h\in\mathcal{H}$,

(3.7) $\displaystyle\|F_{m,\pi_{s_{1}}h}-F_{\pi_{s_{1}}h}\|_{L_{\infty}}\leq
c_{2}\sqrt{\Delta}.$

Rather than controlling the $L_{\infty}$-norm directly, it follows from Lemma
2.3 that it is enough to bound the difference on a grid. Indeed, setting

$U_{\Delta}=\left\\{\ell\Delta:1\leq\ell\leq\frac{1}{\Delta}-1\right\\},$

the wanted estimate follows once we show that with probability at least
$1-2\exp(-c_{1}\Delta m)$, for every $h\in\mathcal{H}$ and $u\in U_{\Delta}$,

(3.8)
$\displaystyle\left|F_{m,\pi_{s_{1}}h}(F_{\pi_{s_{1}}h}^{-1}(u))-u\right|\leq
c_{2}(L,D)\sqrt{\Delta}.$

To establish (3.8), note that

$\displaystyle\left|F_{m,\pi_{s_{1}}h}(F_{\pi_{s_{1}}h}^{-1}(u))-u\right|$
$\displaystyle\leq\left|F_{m,\pi_{s_{1}}h}(F_{\pi_{s_{1}}h}^{-1}(u))-F_{m,\pi_{s_{0}}h}(F_{\pi_{s_{0}}h}^{-1}(u))\right|$
$\displaystyle\qquad+\left|F_{m,\pi_{s_{0}}h}(F_{\pi_{s_{0}}h}^{-1}(u))-u\right|$
$\displaystyle=(1)+(2).$

By Lemma 3.4, with high probability and uniformly in $h\in\mathcal{H}$,

$(2)\leq\sup_{u\in(0,1)}\left|F_{m,\pi_{s_{0}}h}(F_{\pi_{s_{0}}h}^{-1}(u))-u\right|=\|F_{m,\pi_{s_{0}}h}-F_{\pi_{s_{0}}h}\|_{L_{\infty}}\leq
c_{2}\sqrt{\Delta}.$

To control $(1)$, we first show that a well-chosen auxiliary functional
dominates that term, and then show that this functional can be controlled
using $\gamma_{1}(\mathcal{H})$.

From here on, denote the _symmetric difference_ between level sets of
$h,h^{\prime}\in\mathcal{H}$ at probability value $u\in(0,1)$ by

$\displaystyle{\rm S}^{u}[h,h^{\prime}]=\mathbb{P}\left(\left\\{h(X)\leq
F^{-1}_{h}(u)\right\\}\ \bigtriangleup\ \left\\{h^{\prime}(X)\leq
F_{h^{\prime}}^{-1}(u)\right\\}\right).$

######  Remark 3.6.

In the setup explored in [7] we only consider classes of linear functionals,
i.e., with each $h$ of the form $h=\left\langle\cdot,x\right\rangle$.
Moreover, $X=G$ is the standard gaussian vector in $\mathbb{R}^{d}$, and the
analogue of ${\rm S}^{u}[h,h^{\prime}]$ is

${\rm S}_{t}[h,h^{\prime}]=\mathbb{P}(\\{h(X)\leq t\\}\ \bigtriangleup\
\\{h^{\prime}(X)\leq t\\}),\quad t\in\mathbb{R}.$

It follows from the rotation invariance of the standard gaussian random vector
that $\mathbb{P}(\\{h(X)\leq t\\})=\mathbb{P}(\\{h^{\prime}(X)\leq t\\})$.
That feature is crucial for the argument used in [7] but is not true
here—which is the reason for using ${\rm S}^{u}[h,h^{\prime}]$ instead of
${\rm S}_{t}[h,h^{\prime}]$.

######  Lemma 3.7.

There are absolute constants $c_{1}$ and $c_{2}$ for which, with probability
at least $1-2\exp(-c_{1}\Delta m)$, for every $h\in\mathcal{H}$ and $u\in
U_{\Delta}$,

$\displaystyle\left|F_{m,\pi_{s_{1}}h}(F_{\pi_{s_{1}}h}^{-1}(u))-F_{m,\pi_{s_{0}}h}(F_{\pi_{s_{0}}h}^{-1}(u))\right|\leq
c_{2}\sup_{h\in\mathcal{H}}\sum_{s=s_{0}}^{s_{1}-1}\left(\frac{2^{s}}{m}+\sqrt{\frac{2^{s}}{m}\mathbb{P}\left({\rm
S}^{u}[\pi_{s+1}h,\pi_{s}h]\right)}\right).$

The following (simple) observation is at the heart of the proof of Lemma 3.7.

######  Lemma 3.8.

There is an absolute constant $c$ such that for every
$h,h^{\prime}\in\mathcal{H}$, $u\in(0,1)$, and $t\geq 0$, with probability at
least $1-2\exp(-t)$,

$\displaystyle\left|F_{m,h}\left(F_{h}^{-1}(u)\right)-F_{m,h^{\prime}}\left(F_{h^{\prime}}^{-1}(u)\right)\right|\leq
c\left(\frac{t}{m}+\sqrt{\frac{t}{m}\mathbb{P}\left({\rm
S}^{u}[h,h^{\prime}]\right)}\right).$

###### Proof.

For $1\leq i\leq m$, set

$Z_{i}=1_{(-\infty,F_{h}^{-1}(u)]}(h(X_{i}))-1_{(-\infty,F_{h^{\prime}}^{-1}(u)]}(h^{\prime}(X_{i}))$

and let $Z$ be distributed as $Z_{1}$. Using this notation,

$\displaystyle
F_{m,h}\left(F_{h}^{-1}(u)\right)-F_{m,h^{\prime}}\left(F_{h^{\prime}}^{-1}(u)\right)$
$\displaystyle=\frac{1}{m}\sum_{i=1}^{m}Z_{i},$

and clearly $\|Z\|_{L_{\infty}}\leq 2$, $\mathbb{E}Z=u-u=0$, and
$\mathbb{E}Z^{2}=\mathbb{P}({\rm S}^{u}[h,h^{\prime}])$. The claim follows
immediately from Bernstein’s inequality (see, e.g., [10, Theorem 2.10]). ∎

###### Proof of Lemma 3.7.

Let us show that for every _fixed_ $u\in U_{\Delta}$, with probability at
least $1-2\exp(-c_{1}\Delta m)$,

(3.9)
$\displaystyle\sup_{h\in\mathcal{H}}\left|F_{m,\pi_{s_{1}}h}(F_{\pi_{s_{1}}h}^{-1}(u))-F_{m,\pi_{s_{0}}h}(F_{\pi_{s_{0}}h}^{-1}(u))\right|\leq
c_{2}\sqrt{\Delta}.$

Clearly, once (3.9) is established, the wanted estimate follows from the union
bound: $|U_{\Delta}|\leq\frac{1}{\Delta}$ and by the restriction on $\Delta$
in (3.2) we may assume that $c_{1}\Delta m\geq 2\log(\frac{e}{\Delta})$.

To prove (3.9), fix $u\in U_{\Delta}$ and observe that for every
$h\in\mathcal{H}$,

$\displaystyle
F_{m,\pi_{s_{1}}h}(F_{\pi_{s_{1}}h}^{-1}(u))-F_{m,\pi_{s_{0}}h}(F_{\pi_{s_{0}}h}^{-1}(u))$
$\displaystyle=\sum_{s=s_{0}}^{s_{1}-1}\left(F_{m,\pi_{s+1}h}(F_{\pi_{s+1}h}^{-1}(u))-F_{m,\pi_{s}h}(F_{\pi_{s}h}^{-1}(u))\right).$

Lemma 3.8 implies that with probability at least $1-2\exp(-2^{s+3})$,

(3.10) $\displaystyle
F_{m,\pi_{s+1}h}(F_{\pi_{s+1}h}^{-1}(u))-F_{m,\pi_{s}h}(F_{\pi_{s}h}^{-1}(u))\leq
c_{2}\left(\frac{2^{s}}{m}+\sqrt{\frac{2^{s}}{m}\mathbb{P}({\rm
S}^{u}[\pi_{s+1}h,\pi_{s}h])}\right).$

And since

$|\\{(\pi_{s}h,\pi_{s+1}h):h\in\mathcal{H}\\}|\leq 2^{2^{s}}\cdot
2^{2^{s+1}}\leq\exp\left(2^{s+2}\right),$

it follows from the union bound over pairs $(\pi_{s+1}h,\pi_{s}h)$ that with
probability at least $1-2\exp(-2^{s+2})$, (3.10) holds uniformly for
$h\in\mathcal{H}$. Moreover, by the union bound over
$s\in\\{s_{0},\dots,s_{1}-1\\}$, it is evident that with probability at least

$1-\sum_{s=s_{0}}^{s_{1}-1}2\exp(-2^{s+2})\geq 1-2\exp(-2^{s_{0}})\geq
1-2\exp(-\Delta m),$

for every $h\in\mathcal{H}$,

$\displaystyle\left|F_{m,\pi_{s_{1}}h}(F_{\pi_{s_{1}}h}^{-1}(u))-F_{m,\pi_{s_{0}}h}(F_{\pi_{s_{0}}h}^{-1}(u))\right|\leq
c_{2}\sup_{h\in\mathcal{H}}\sum_{s=s_{0}}^{s_{1}-1}\left(\frac{2^{s}}{m}+\sqrt{\frac{2^{s}}{m}\mathbb{P}({\rm
S}^{u}[\pi_{s+1}h,\pi_{s}h])}\right).\quad\qed$

###### Proof of Lemma 3.5.

Invoking Lemma 2.3 and Lemma 3.7, it suffices to show that for every $u\in
U_{\Delta}$,

(3.11)
$\displaystyle\begin{split}(\ast)_{u}&=\sup_{h\in\mathcal{H}}\sum_{s=s_{0}}^{s_{1}-1}\left(\frac{2^{s}}{m}+\sqrt{\frac{2^{s}}{m}\mathbb{P}({\rm
S}^{u}[\pi_{s+1}h,\pi_{s}h])}\right)\\\ &\leq
c\left(\sqrt{\Delta}+\log^{3/2}\left(\frac{e}{\Delta}\right)\sqrt{\frac{\gamma_{1}(\mathcal{H})}{m}}\right),\end{split}$

where $c$ is a constant that depends only on $L$ and $D$. Indeed, if (3.11) is
true, then the claim follows from the restriction on $\Delta$ in (3.2).

To estimate $(\ast)_{u}$, observe that

$\sum_{s=s_{0}}^{s_{1}-1}\frac{2^{s}}{m}\leq\frac{2^{s_{1}}}{m}\leq
2\sqrt{\Delta},$

and all that is left is to control the second term in the definition of
$(\ast)_{u}$.

To that end, set

$\delta_{s}(h)=\|\pi_{s+1}h(X)-\pi_{s}h(X)\|_{L_{2}}\quad\text{and}\quad
r_{s}(h)=L\delta_{s}(h)\log\left(\frac{e}{\delta_{s}(h)}\right).$

By the subexponential tail decay,

$\mathbb{P}(|\pi_{s+1}h(X)-\pi_{s}h(X)|\geq r_{s}(h))\leq
2\exp\left(-\log\left(\frac{e}{\delta_{s}(h)}\right)\right)\leq\delta_{s}(h)$

and therefore, by Lemma 2.4,

$\displaystyle\mathbb{P}({\rm S}_{u}[\pi_{s+1}h,\pi_{s}h])$ $\displaystyle\leq
4\big{(}\mathbb{P}(|\pi_{s+1}h(X)-\pi_{s}h(X)|\geq r_{s}(h))+r_{s}(h)D\big{)}$
$\displaystyle\leq(4+DL)\delta_{s}(h)\log\left(\frac{e}{\delta_{s}(h)}\right).$

Next, since $2^{s_{0}}\geq\Delta m$ and $2^{s_{1}}\leq 2\sqrt{\Delta}m$, it
follows that

$s_{1}-s_{0}\leq\log_{2}(2\sqrt{\Delta}m)-\log_{2}(\Delta
m)\leq\log\left(\frac{4}{\Delta}\right);$

hence,

$\displaystyle(\ast)_{u}$ $\displaystyle\leq
c_{1}(L,D)\left(\sqrt{\Delta}+\log\left(\frac{4}{\Delta}\right)\sup_{h\in\mathcal{H}}\max_{s_{0}\leq
s<s_{1}}\sqrt{\frac{2^{s}}{m}\delta_{s}(h)\log\left(\frac{e}{\delta_{s}(h)}\right)}\right).$

A straightforward computation (distinguishing between the cases
$\delta_{s}(h)\leq\Delta$ and $\delta_{s}(h)>\Delta$) shows that for a
constant $c_{2}$ that depends only on $L$ and $D$,

$\displaystyle(\ast)_{u}$ $\displaystyle\leq
c_{2}\left(\sqrt{\Delta}+\log^{3/2}\left(\frac{e}{\Delta}\right)\sup_{h\in\mathcal{H}}\max_{s_{0}\leq
s<s_{1}}\sqrt{\frac{2^{s}}{m}\delta_{s}(h)}\right)$ $\displaystyle\leq
c_{2}\left(\sqrt{\Delta}+\log^{3/2}\left(\frac{e}{\Delta}\right)\sqrt{\frac{2\gamma_{1}(\mathcal{H})}{m}}\right),$

where the second inequality holds because $(\mathcal{H}_{s})_{s\geq 0}$ is an
almost optimal admissible sequence for $\gamma_{1}(\mathcal{H})$. ∎

###  3.2. Controlling
$[\mathbb{P}+\mathbb{P}_{m}](|\pi_{s_{1}}h(X)-h(X)|\geq\sqrt{\Delta})$

With Lemma 2.2 in mind, the next component in the proof of Theorem 3.2 is that
with high probability,

$\sup_{h\in\mathcal{H}}[\mathbb{P}+\mathbb{P}_{m}]\left(|h(X)-\pi_{s_{1}}h(X)|\geq\sqrt{\Delta}\right)\leq
c\sqrt{\Delta}.$

The estimate on the $\mathbb{P}$-probability is straightforward: Because
$(\mathcal{H}_{s})_{s\geq 0}$ is an almost optimal admissible sequence for
$\gamma_{1}(\mathcal{H})$ and by the restriction on $\Delta$,

(3.12) $\displaystyle\|h-\pi_{s_{1}}h\|_{L_{2}}\leq
2\frac{\gamma_{1}(\mathcal{H})}{2^{s_{1}}}\leq
2c_{0}\frac{\sqrt{\Delta}}{\log^{3}(e/\Delta)}$

where $c_{0}=c_{0}(L,D)$ is a constant that may be chosen as small as needed.
Thus, invoking the subexponential tail decay,

(3.13)
$\displaystyle\mathbb{P}\left(|h(X)-\pi_{s_{1}}h(X)|\geq\sqrt{\Delta}\right)\leq
2\exp\left(-\log^{3}\left(\frac{e}{\Delta}\right)\right)\leq 2\sqrt{\Delta},$

as required.

Obtaining a similar estimate for the empirical measure $\mathbb{P}_{m}$ is
more subtle.

######  Lemma 3.9.

There is an absolute constant $c_{1}$ satisfying that with probability at
least $1-2\exp(-c_{1}\Delta m)$, for every $h\in\mathcal{H}$,

(3.14)
$\displaystyle\mathbb{P}_{m}\left(|h(X)-\pi_{s_{1}}h(X)|\geq\sqrt{\Delta}\right)\leq
2\sqrt{\Delta}.$

Note that (3.14) is equivalent to

(3.15)
$\displaystyle\left|\left\\{i:|h(X_{i})-\pi_{s_{1}}h(X_{i})|\geq\sqrt{\Delta}\right\\}\right|\leq
2\sqrt{\Delta}m,$

a fact that will be used in the proof of Lemma 3.9: Denote by
$(a^{\ast}_{i})_{i=1}^{m}$ the monotone non-increasing rearrangement of
$(|a_{i}|)_{i=1}^{m}$. Setting $a=(h(X_{i})-\pi_{s_{1}}h(X_{i}))_{i=1}^{m}$,
(3.15) holds if $a^{\ast}_{2\sqrt{\Delta}m}<\sqrt{\Delta}$; in particular it
suffices that $a^{\ast}_{2^{s_{1}}}<\sqrt{\Delta}$. Clearly

$a_{k}^{\ast}\leq\frac{1}{k}\sum_{i=1}^{k}a_{i}^{\ast}$

for every $1\leq k\leq m$, and Lemma 3.9 follows once we show that with
probability at least $1-2\exp(-c_{1}\Delta m)$,

(3.16)
$\displaystyle\sup_{h\in\mathcal{H}}\frac{1}{2^{s_{1}}}\sum_{i=1}^{2^{s_{1}}}\left(h(X_{i})-\pi_{s_{1}}h(X_{i})\right)^{\ast}<\sqrt{\Delta}.$

The proof of (3.16) is based on a (rather standard) chaining argument. For
$1\leq k\leq m$, set

$\mathcal{S}_{k}=\\{b\in\\{-1,0,1\\}^{m}:|\\{i:b_{i}\neq 0\\}|=k\\}$

and note that
$\sum_{i=1}^{k}a_{i}^{\ast}=\max_{b\in\mathcal{S}_{k}}\sum_{i=1}^{m}b_{i}a_{i}$.
The next observation is an immediate consequence of the $\psi_{1}$-version of
Bernstein’s inequality and its proof is presented for the sake of
completeness.

######  Lemma 3.10.

There exists a constant $c_{1}$ that depends only on $L$ such that the
following holds. For every $1\leq k\leq m$, $b\in\mathcal{S}_{k}$,
$h,h^{\prime}\in\mathcal{H}$ and $t\geq 0$, with probability at least
$1-2\exp(-t)$,

$\left|\sum_{i=1}^{m}b_{i}\left(h(X_{i})-h^{\prime}(X_{i})\right)\right|\leq
c_{1}\left(\sqrt{tk}+t\right)\|h-h^{\prime}\|_{L_{2}}.$

###### Proof.

Let $a\in\mathbb{R}^{m}$ be a rearrangement of $b$ that is supported on the
first $k$ coordinates. Set $Z_{i}=h(X_{i})-h^{\prime}(X_{i})$, and clearly
$\sum_{i=1}^{m}b_{i}Z_{i}$ and $\sum_{i=1}^{k}a_{i}Z_{i}$ have the same
distribution. The proof follows from a version of Bernstein’s inequality, see,
e.g. [2, Lemma 3.6]. ∎

###### Proof of Lemma 3.9.

Recall that $2^{s_{1}}\sim\sqrt{\Delta}m$. Therefore,

$|\mathcal{S}_{2^{s_{1}}}|=2^{2^{s_{1}}}\binom{m}{2^{s_{1}}}\leq\exp\left(c_{1}\sqrt{\Delta}m\log\left(\frac{e}{\Delta}\right)\right),$

and by the union bound it suffices to show that for every _fixed_
$b\in\mathcal{S}_{2^{s_{1}}}$, with probability at least
$1-2\exp(-2c_{1}\sqrt{\Delta}m\log(\frac{e}{\Delta}))$,

$\sup_{h\in\mathcal{H}}\frac{1}{2^{s_{1}}}\sum_{i=1}^{m}b_{i}\left(h(X_{i})-\pi_{s_{1}}h(X_{i})\right)<\sqrt{\Delta}.$

To that end, fix $b\in\mathcal{S}_{2^{s_{1}}}$ and let $\eta=\eta(c_{1})\geq
1$ be an absolute constant to be specified in what follows. For $s\geq s_{1}$,
Lemma 3.10 (with the choices of $k=2^{s}$ and $t=\eta
2^{s}\log(\frac{e}{\Delta})$) shows that for every $h\in\mathcal{H}$, with
probability at least $1-2\exp(-\eta 2^{s}\log(\frac{e}{\Delta}))$,

(3.17)
$\displaystyle\left|\sum_{i=1}^{m}b_{i}(\pi_{s+1}h(X_{i})-\pi_{s}h(X_{i}))\right|\leq
c_{2}(L)\eta
2^{s}\log\left(\frac{e}{\Delta}\right)\|\pi_{s+1}h-\pi_{s}h\|_{L_{2}}.$

Recalling that
$|\\{(\pi_{s+1}h,\pi_{s}h):h\in\mathcal{H}\\}|\leq\exp\left(2^{s+2}\right)$,
it follows from the union bound over $s\geq r$ and pairs
$(\pi_{s+1}h,\pi_{s}h)$ that (3.17) holds uniformly with probability at least

$1-\sum_{s\geq s_{1}}2\exp\left(-\eta
2^{s}\log\left(\frac{e}{\Delta}\right)\right)\geq
1-2\exp\left(-2c_{1}\sqrt{\Delta}m\log\left(\frac{e}{\Delta}\right)\right);$

the last inequality holds for a suitable choice of $\eta=\eta(c_{1})$. On that
event,

$\displaystyle\sup_{h\in\mathcal{H}}\frac{1}{2^{s_{1}}}\sum_{i=1}^{m}b_{i}\left(h(X_{i})-\pi_{s_{1}}h(X_{i})\right)$
$\displaystyle=\sup_{h\in\mathcal{H}}\frac{1}{2^{s_{1}}}\sum_{s\geq
s_{1}}\sum_{i=1}^{m}b_{i}(\pi_{s+1}h(X_{i})-\pi_{s}h(X_{i}))$
$\displaystyle\leq
c_{2}(L)\eta\log\left(\frac{e}{\Delta}\right)\sup_{h\in\mathcal{H}}\frac{1}{2^{s_{1}}}\sum_{s\geq
s_{1}}2^{s}\|\pi_{s+1}h-\pi_{s}h\|_{L_{2}}=(\ast).$

Finally, $(\mathcal{H}_{s})_{s\geq 0}$ is an almost optimal admissible
sequence, and by the restriction on $\Delta$ in (3.2), we have that
$(\ast)<\sqrt{\Delta}$. ∎

###  3.3. Putting everything together—proof of Theorem 3.2

Let $\Omega(\mathbb{X})$ be the event in which the assertions of Lemma 3.5 and
Lemma 3.9 hold; in particular $\mathbb{P}(\Omega(\mathbb{X}))\geq
1-2\exp(-c_{1}\Delta m)$. By the estimate in (3.13), it follows that for every
realization $(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$ and $h\in\mathcal{H}$,

$\|F_{m,\pi_{s_{1}}h}-F_{\pi_{s_{1}}h}\|_{L_{\infty}}\leq
c_{2}(L,D)\sqrt{\Delta},$

and

$[\mathbb{P}+\mathbb{P}_{m}]\left(|\pi_{s_{1}}h(X)-h(X)|\geq\sqrt{\Delta}\right)\leq
4\sqrt{\Delta}.$

Therefore, an application of Lemma 2.2 (with $r=\sqrt{\Delta}$) shows that

$\displaystyle\|F_{m,h}-F_{h}\|_{L_{\infty}}$
$\displaystyle\leq\|F_{m,\pi_{s_{1}}h}-F_{\pi_{s_{1}}h}\|_{L_{\infty}}+[\mathbb{P}+\mathbb{P}_{m}]\left(|h(X)-\pi_{s_{1}}h(X)|\geq\sqrt{\Delta}\right)+2D\sqrt{\Delta}$
$\displaystyle\leq(c_{2}(L,D)+4+2D)\sqrt{\Delta},$

as claimed. ∎

##  4\. Proof of Lemma 1.7 and Lemma 1.9

Recall that $w$ is a symmetric random variable with variance 1 and that $X$
has independent coordinates distributed according to $w$. We begin with the
proof of Lemma 1.9, which is the simpler of the two.

###  4.1. Proof of Lemma 1.9

Let $\delta\in(0,\frac{1}{10})$, set $d\in\mathbb{N}$ to be specified in what
follows, and put

(4.1) $\displaystyle A=\left\\{\sqrt{1-\delta^{2}}\cdot e_{1}+\delta\cdot
e_{k}:2\leq k\leq d\right\\}\subset S^{d-1}.$

Note that $\gamma_{1}(A)\leq c_{1}\delta\log(d)$. Indeed, this follows by
considering the admissible sequence $(A_{s})_{s\geq 0}$ defined by
$A_{s}=\\{\sqrt{1-\delta^{2}}e_{1}+\delta e_{2}\\}$ when $2^{2^{s}}<d$ and
$A_{s}=A$ otherwise, and noting that ${\rm diam}(A,\|\cdot\|_{2})\leq
2\delta$.

Clearly, $\left\langle X,x\right\rangle$ is a symmetric random variable with
variance 1, and by Markov’s inequality,

$\sup_{x\in A}F_{x}(-2)\leq\frac{1}{8}.$

Next, let us show that with probability at least $0.9$, there exists $x\in A$
which satisfies that $F_{m,x}(-2)\geq\frac{4}{10}$; in particular

$\mathbb{P}\left(\sup_{x\in
A}|F_{m,x}(-2)-F_{x}(-2)|\geq\frac{1}{10}\right)\geq 0.9,$

as claimed.

To that end, set

$I=\\{i\in\\{1,\dots,m\\}:\left\langle X_{i},e_{1}\right\rangle\leq 0\\}$

and denote by $\Omega_{1}(\mathbb{X})$ the event in which
$|I|\geq\frac{4}{10}m$. Since $\mathbb{P}(\left\langle
X,e_{1}\right\rangle\leq 0)=\frac{1}{2}$, by Markov’s inequality
$\mathbb{P}(\Omega_{1}(\mathbb{X}))\geq 0.99$ when $m\geq 20$. Consider

$\Omega_{2}(\mathbb{X})=\left\\{\text{there is }2\leq k\leq d\text{ such
that}\left\langle X_{i},e_{k}\right\rangle\leq-\frac{2}{\delta}\text{ for
every }1\leq i\leq m\right\\}$

and set

$\beta=\mathbb{P}\left(w\leq-\frac{2}{\delta}\right).$

Therefore,

$\displaystyle\mathbb{P}(\Omega_{2}(\mathbb{X}))=1-(1-\beta^{m})^{d-1}$
$\displaystyle=1-\exp\big{(}(d-1)\log(1-\beta^{m})\big{)}$ $\displaystyle\geq
1-\exp\left(-(d-1)\beta^{m})\right),$

where we used that $\log(1-\lambda)\leq-\lambda$ for $\lambda\in(0,1)$.
Setting $d=c_{2}\beta^{-m}$, it follows that
$\mathbb{P}(\Omega_{2}(\mathbb{X}))\geq 0.99$.

Clearly, for every realization
$(X_{i})_{i=1}^{m}\in\Omega_{1}(\mathbb{X})\cap\Omega_{2}(\mathbb{X})$ there
exists $x\in A$ for which

$\left\langle X_{i},x\right\rangle=\sqrt{1-\delta^{2}}\left\langle
X_{i},e_{1}\right\rangle+\delta\left\langle
X_{i},e_{k}\right\rangle\leq-2\quad\text{for every }i\in I,$

and thus $F_{m,x}(-2)\geq\frac{|I|}{m}\geq\frac{4}{10}$.

It remains to show that there is some $\delta<\frac{1}{10}$ for which
$\gamma_{1}(A)\leq 10$. Since $d=c_{2}\beta^{-m}$, we have that
$\gamma_{1}(A)\leq c_{3}\delta m\log(\frac{1}{\beta})$; therefore
$\gamma_{1}(A)\leq 10$ if

$\displaystyle\beta=\mathbb{P}\left(w\leq-\frac{2}{\delta}\right)\geq\exp\left(-\frac{10}{c_{3}\delta
m}\right).$

Finally, $w$ does not have a subexponential tail decay, and in particular, for
every $L\geq 1$ there exists $t>20$ that satisfies
$\mathbb{P}(w\leq-t)\geq\exp(-t/L)$. The claim follows by setting
$\delta=\frac{2}{t}$ for $t$ corresponding to $L=\frac{c_{3}m}{5}$. ∎

###  4.2. Proof of Lemma 1.7

The proof is based on a similar construction to the one used in the proof of
Lemma 1.9.

Consider $t_{0}$ that satisfies $\mathbb{P}(w=t_{0})=\eta$ and set
$H(\cdot)=\mathbb{P}(w\leq\cdot)$. Since $w$ is symmetric, we may assume
without loss of generality that $t_{0}\geq 0$.

Let $\delta\in(0,\frac{1}{10})$ and $d\in\mathbb{N}$ to be specified in what
follows and again set

$A=\left\\{\sqrt{1-\delta^{2}}\cdot e_{1}+\delta\cdot e_{k}:2\leq k\leq
d\right\\}.$

Moreover, put $\alpha=\frac{1}{10}$ and let $\beta=\mathbb{P}(w\geq\alpha)$.
Recalling that $w$ is ‘nontrivial’ we have that $\beta\geq\frac{1}{20}$.

Let us show that there is some $\delta_{0}>0$ (that may depend on $H$)
satisfying that for every $\delta\leq\delta_{0}$,

(4.2) $\displaystyle\sup_{x\in A}F_{x}(t_{0})\leq
H(t_{0})-\frac{\beta}{2}\eta.$

Indeed, set $x(\delta)=\sqrt{1-\delta^{2}}e_{1}+\delta e_{2}\in A$, and since
$X$ has iid coordinates, $F_{y}=F_{x(\delta)}$ for every $y\in A$. Moreover,
if $w^{\prime}$ is an independent copy of $w$, then

$\displaystyle F_{x(\delta)}(t_{0})$
$\displaystyle=\mathbb{P}\left(\sqrt{1-\delta^{2}}w^{\prime}+\delta w\leq
t_{0}\right)=\mathbb{E}H\left(\frac{t_{0}-\delta
w}{\sqrt{1-\delta^{2}}}\right)$ $\displaystyle=\mathbb{E}(1_{w\leq
0}+1_{w>0})H\left(\frac{t_{0}-\delta w}{\sqrt{1-\delta^{2}}}\right).$

Observe that if $w\leq 0$ then $\frac{t_{0}-\delta w}{\sqrt{1-\delta^{2}}}$
decreases to $t_{0}$ as $\delta\to 0^{+}$, and if $w>0$ then
$\frac{t_{0}-\delta w}{\sqrt{1-\delta^{2}}}$ increases to $t_{0}$ as
$\delta\to 0^{+}$. By the right-continuity of $H$ and the dominated
convergence theorem,

$\displaystyle\lim_{\delta\to 0^{+}}F_{x(\delta)}(t_{0})$
$\displaystyle=\mathbb{P}(w\leq 0)H(t_{0})+\mathbb{P}(w>0)H(t_{0}-)$

where $H(t_{0}-)=\lim_{s\uparrow t_{0}}H(s)=H(t_{0})-\eta$. Clearly
$\mathbb{P}(w>0)\geq\mathbb{P}(w\geq\alpha)\geq\beta$ and (4.2) follows.

Next, set

$I=\\{i\in\\{1,\dots,m\\}:\left\langle X_{i},e_{1}\right\rangle\leq t_{0}\\},$

put $\varepsilon=\frac{\beta\eta}{4H(t_{0})}$, and let
$\Omega_{1}(\mathbb{X})$ be the event in which
$|I|\geq(1-\varepsilon)H(t_{0})m$. By Markov’s inequality,

$\mathbb{P}(\Omega_{1}(\mathbb{X})^{c})\leq\mathbb{P}\big{(}||I|-mH(t_{0})|\geq\varepsilon
H(t_{0})m\big{)}\leq\frac{mH(t_{0})(1-H(t_{0}))}{\varepsilon^{2}H(t_{0})^{2}m^{2}}\leq
0.01,$

where the last inequality holds if $m\geq\frac{c_{1}(\beta)}{\eta^{2}}$.
Setting

$\Omega_{2}(\mathbb{X})=\\{\text{there is }2\leq k\leq d\text{ such that
}\left\langle X_{i},e_{k}\right\rangle\leq-\alpha\text{ for every }1\leq i\leq
m\\},$

the same arguments used in the proof of Lemma 1.9 show that if
$d=c_{2}\beta^{-m}$ then

$\mathbb{P}(\Omega_{2}(\mathbb{X}))=1-(1-\beta^{m})^{d-1}\geq 0.99.$

For a realization
$(X_{i})_{i=1}^{m}\in\Omega_{1}(\mathbb{X})\cap\Omega_{2}(\mathbb{X})$ there
is $x\in A$ satisfying that for every $i\in I$,

$\displaystyle\left\langle X_{i},x\right\rangle$
$\displaystyle=\sqrt{1-\delta^{2}}\left\langle
X_{i},e_{1}\right\rangle+\delta\left\langle X_{i},e_{k}\right\rangle$
$\displaystyle\leq\sqrt{1-\delta^{2}}t_{0}-\alpha\delta=\sqrt{1-\delta^{2}}t_{0}-\frac{\delta}{10}\leq
t_{0},$

where the last inequality holds whenever $\delta\leq c_{3}(t_{0})$ if
$t_{0}>0$, and for any $\delta>0$ if $t_{0}=0$. In particular,
$F_{m,x}(t_{0})\geq\frac{|I|}{m}$, and by the choice of $\varepsilon$ and
(4.2),

$F_{m,x}(t_{0})-F_{x}(t_{0})\geq\left(1-\frac{\beta\eta}{4H(t_{0})}\right)H(t_{0})-\left(H(t_{0})-\frac{\beta}{2}\eta\right)\geq\frac{\beta}{4}\eta.$

To complete the proof, recall that $\gamma_{1}(A)\leq c_{4}\delta\log(d)$ and
that $d=c_{2}\beta^{-m}$. Therefore, $\gamma_{1}(A)\leq c_{5}\delta
m\log(\frac{1}{\beta})$, and for $\delta\leq\min\\{\delta_{0},c_{3}(t_{0})\\}$
small enough we have that $\gamma_{1}(A)\leq 10$. ∎

##  5\. Application: Uniform estimation of monotone functions

A problem one encounters frequently in high dimensional statistics is
estimating the means $\mathbb{E}\varphi(\left\langle X,x\right\rangle)$ for a
given function $\varphi\colon\mathbb{R}\to\mathbb{R}$, and uniformly for every
$x\in A$ — using only a sample $X_{1},\dots,X_{m}$ consisting of independent
copies of $X$.

For example, $\varphi(t)=t^{2}$ corresponds to _covariance estimation_ , where
an intuitive (yet ultimately suboptimal) approach is to use the empirical mean
$\frac{1}{m}\sum_{i=1}^{m}\left\langle X_{i},x\right\rangle^{2}$ as an
estimator. With that choice the resulting error is

$\sup_{x\in S^{d-1}}\left|\frac{1}{m}\sum_{i=1}^{m}\left\langle
X_{i},x\right\rangle^{2}-\mathbb{E}\left\langle
X,x\right\rangle^{2}\right|=\sup_{x\in
S^{d-1}}\left|\int_{\mathbb{R}}t^{2}\,dF_{m,x}(t)-\int_{\mathbb{R}}t^{2}\,dF(t)\right|.$

Another example is estimating $\mathbb{E}|\left\langle X,x\right\rangle|^{p}$
for every $x\in A$ and $p>2$ (see, e.g., [18]) which naturally leads to the
choice $\varphi(t)=|t|^{p}$. Just as in the case $p=2$, the empirical $p$-mean
happens to be a suboptimal procedure. In both cases, the suboptimality is
caused by _outliers_ : atypically large values of $|\left\langle
X_{i},x\right\rangle|$ that occur with nontrivial probability for some $x\in
S^{d-1}$ and some $1\leq i\leq m$.

As it happens, a _trimmed $p$-mean_ estimator can be shown to overcome the
effect of outliers [25], and exhibits optimal statistical performance. To
formulate that result, for $w\in\mathbb{R}^{m}$ denote by $w^{\sharp}$ its
monotone non-decreasing rearrangement and for $\delta\in(0,\frac{1}{10})$ set

$\mathcal{E}_{\delta}(w)=\frac{1}{m}\sum_{i=\delta
m}^{(1-\delta)m}w^{\sharp}_{i}.$

Let $L,p\geq 2$, and $q>2p$. Set $\varphi(t)=|t|^{p}$, let $X$ be an isotropic
random vector in $\mathbb{R}^{d}$, and assume that $\sup_{x\in
S^{d-1}}\mathbb{E}|\left\langle X,x\right\rangle|^{q}\leq L^{q}$.

######  Theorem 5.1.

There are constants $c_{1},\ldots,c_{4}$ that depend only on $L,p,q$ for which
the following holds. If $m\geq d$ and

$\Delta\in\left[c_{1}\frac{d}{m}\log\left(\frac{em}{d}\right)\,,\,1\right],$

then with probability at least $1-2\exp(-c_{2}\Delta m)$,

(5.1) $\displaystyle\sup_{x\in
S^{d-1}}\left|\mathcal{E}_{c_{3}\Delta}\Big{(}\big{(}\varphi(\left\langle
X_{i},x\right\rangle)\big{)}_{i=1}^{m}\Big{)}-\mathbb{E}\varphi(\left\langle
X,x\right\rangle)\right|\leq c_{4}\sqrt{\Delta}.$

Theorem 5.1 was extended in [6]: (5.1) actually holds for any $\varphi$ in the
class

$\mathcal{M}_{p,\beta}=\left\\{\varphi\colon\mathbb{R}\to\mathbb{R}:\varphi\text{
is monotone and
}\sup_{t\in\mathbb{R}}\frac{|\varphi(t)|}{1+|t|^{p}}\leq\beta\right\\}.$

There are two issues with the estimator from Theorem 5.1. Firstly, it deals
with $S^{d-1}$ and not with arbitrary subsets of the sphere (thus forcing that
$m\geq d$ and $\Delta\gtrsim\frac{d}{m}$). Secondly, the trimmed mean
estimator is highly nonlinear.

Here, we resolve both issues by constructing a linear estimator that is
(almost) optimal for an arbitrary set $A\subset S^{d-1}$. More accurately, an
_estimator_ here is a measurable function
$\widehat{\nu}\colon(\mathbb{R}^{d})^{m}\to\mathcal{P}(\mathbb{R}^{d})$ that
assigns to a sample $(X_{i})_{i=1}^{m}$ a probability measure on
$\mathbb{R}^{d}$. Denote by $\mathbb{E}_{\widehat{\nu}}$ the expectation with
respect to the measure $\widehat{\nu}$, and in particular

$\mathbb{E}_{\widehat{\nu}}\,\varphi(\left\langle
X,x\right\rangle)=\int_{\mathbb{R}^{d}}\varphi(\left\langle
w,x\right\rangle)\,\widehat{\nu}(dw).$

######  Theorem 5.2.

For every $L,D,p,\beta\geq 1$ there are constants $c_{1},c_{2},c_{3}$ that
depend only on $L,D,p,\beta$ for which the following holds. If $X$ satisfies
Assumption 1.10, $A\subset S^{d-1}$ is a symmetric set, $m\geq\gamma_{1}(A)$
and

$\Delta\in\left[c_{1}\frac{\gamma_{1}(A)}{m}\log^{3}\left(\frac{em}{\gamma_{1}(A)}\right)\,,\,1\right],$

then there exists an estimator $\widehat{\nu}$, for which with probability at
least $1-2\exp(-c_{2}\Delta m)$,

(5.2) $\displaystyle\sup_{x\in
A}\sup_{\varphi\in\mathcal{M}_{p,\beta}}\big{|}\mathbb{E}_{\widehat{\nu}}\,\varphi(\left\langle
X,x\right\rangle)-\mathbb{E}\varphi(\left\langle X,x\right\rangle)\big{|}\leq
c_{3}\sqrt{\Delta}\log^{p}\left(\frac{e}{\Delta}\right).$

Note that the estimator $\widehat{\nu}$ depends on the parameters
$L,D,p,\beta$ and the wanted accuracy level $\Delta$, but not on any other
feature of $X$ or of $A$.

The proof of Theorem 5.2 requires some preparations. We may assume that
$\sqrt{\Delta}\leq\frac{1}{10}$, and let $\Omega(\mathbb{X})$ be the event in
which the assertion of Theorem 1.11 holds, that is,

(5.3) $\displaystyle\sup_{x\in
A}\|F_{m,x}-F_{x}\|_{L_{\infty}}\leq\sqrt{\Delta}.$

Hence, $\mathbb{P}(\Omega(\mathbb{X}))\geq 1-2\exp(-c_{0}\Delta m)$ for a
constant $c_{0}=c_{0}(L,D)$.

Fix a realization $(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$. Clearly, (5.3)
implies that for every $x\in A$ and $u\in(\sqrt{\Delta},1-\sqrt{\Delta})$,

(5.4) $\displaystyle
F_{m,x}^{-1}(u)\in\left[F_{x}^{-1}(u-\sqrt{\Delta}),F_{x}^{-1}(u+\sqrt{\Delta})\right].$

Moreover, by the subexponential tail decay of $\left\langle X,x\right\rangle$,
it follows that for every $u\in(0,1)$,

(5.5) $\displaystyle|F_{x}^{-1}(u)|\leq
L\log\left(\frac{e}{\min\\{u,1-u\\}}\right).$

######  Lemma 5.3.

For every $L,p,\beta\geq 1$ there is a constant $c$ that depends only on
$L,p,\beta$ for which the following holds. For every
$\varphi\in\mathcal{M}_{p,\beta}$, $x\in A$, and
$(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$,

$\left|\int_{\sqrt{\Delta}}^{1-\sqrt{\Delta}}\varphi(F_{m,x}^{-1}(u))\,du-\mathbb{E}\varphi(\left\langle
X,x\right\rangle)\right|\leq
c\sqrt{\Delta}\log^{p}\left(\frac{e}{\Delta}\right).$

###### Proof.

Fix $\varphi\in\mathcal{M}_{p,\beta}$ and assume without loss of generality
that $\varphi$ is non-decreasing. Define $I^{+}_{x}$ and $I_{x}^{-}$ by

$I^{\pm}_{x}=\int_{\sqrt{\Delta}}^{1-\sqrt{\Delta}}\varphi\left(F_{x}^{-1}(u\pm\sqrt{\Delta})\right)\,du.$

Invoking (5.4) and since $\varphi$ is non-decreasing,

$\int_{\sqrt{\Delta}}^{1-\sqrt{\Delta}}\varphi(F_{m,x}^{-1}(u))\,du\in\left[I_{x}^{-}\,,\,I_{x}^{+}\right].$

A change of variables $u\mapsto u\pm\sqrt{\Delta}$ shows that

$\displaystyle\left|I^{\pm}_{x}-\int_{0}^{1}\varphi(F_{x}^{-1}(u))\,du\right|$
$\displaystyle\leq
2\int_{[0,1]\setminus[2\sqrt{\Delta},1-2\sqrt{\Delta}]}|\varphi(F_{x}^{-1}(u))|\,du$
$\displaystyle\leq
c(L,p,\beta)\sqrt{\Delta}\log^{p}\left(\frac{e}{\Delta}\right),$

where the last inequality follows from the tail behaviour (5.5) and the growth
assumption that $|\varphi(\cdot)|\leq\beta(1+|\cdot|^{p})$. Finally, by tail-
integration, $\mathbb{E}\varphi(\left\langle
X,x\right\rangle)=\int_{0}^{1}\varphi(F_{x}^{-1}(u))\,du$, from which the
claim follows. ∎

The proof of Theorem 5.2 uses a simple (and clever) idea from [1].

###### Proof of Theorem 5.2.

Let $c=c(L,p,\beta)$ be the constant appearing in Lemma 5.3 and set
$\delta=c\sqrt{\Delta}\log^{p}\left(\frac{e}{\Delta}\right)$. For every
$\varphi\in\mathcal{M}_{p,\beta}$ and $x\in A$, put

$\mathcal{P}_{\varphi,x}=\left\\{\nu\in\mathcal{P}(\mathbb{R}^{d}):\left|\mathbb{E}_{\nu}\,\varphi(\left\langle
X,x\right\rangle)-\int_{\sqrt{\Delta}}^{1-\sqrt{\Delta}}\varphi(F_{m,x}^{-1}(u))\,du\right|\leq\delta\right\\}$

(where, if $\varphi(\left\langle X,x\right\rangle)$ is not integrable with
respect to $\nu$ we set $\mathbb{E}_{\nu}\varphi(\left\langle
X,x\right\rangle)=\infty$).

By Lemma 5.3, for every realization $(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$,
the set $\mathcal{P}_{\varphi,x}$ contains $\mu$. In particular, on that event

$\bigcap\left\\{\mathcal{P}_{\varphi,x}:\varphi\in\mathcal{M}_{p,\beta},\,x\in
A\right\\}\neq\emptyset,$

and set $\widehat{\nu}$ to be any element in that intersection. Hence, for any
$\varphi\in\mathcal{M}_{p,\beta}$ and $x\in A$, it follows from the definition
of $\mathcal{P}_{\varphi,x}$ and Lemma 5.3 that on $\Omega(\mathbb{X})$,

$\displaystyle\left|\mathbb{E}_{\widehat{\nu}}\,\varphi(\left\langle
X,x\right\rangle)-\mathbb{E}\varphi(\left\langle X,x\right\rangle)\right|$
$\displaystyle\leq\left|\mathbb{E}_{\widehat{\nu}}\,\varphi(\left\langle
X,x\right\rangle)-\int_{\sqrt{\Delta}}^{1-\sqrt{\Delta}}\varphi(F_{m,x}^{-1}(u))\,du\right|$
$\displaystyle\qquad\qquad+\left|\int_{\sqrt{\Delta}}^{1-\sqrt{\Delta}}\varphi(F_{m,x}^{-1}(u))\,du-\mathbb{E}\varphi(\left\langle
X,x\right\rangle)\right|\leq 2\delta,$

as claimed. ∎

##  6\. Concluding remarks

We end this article with a few remarks that may help putting our main results
in some context.

###  6.1. A Sudakov-type bound

Theorem 1.6 and Theorem 1.11 have a restriction on the choice of $\Delta$:
that

$\Delta\gtrsim\frac{\gamma_{1}(A)}{m}\log^{3}\left(\frac{em}{\gamma_{1}(A)}\right).$

At a first glance this restriction appears strange. As we explain here, it is
(essentially) optimal and the argument is based on a Sudakov-type lower bound.
Before formulating that lower bound, let us outline the standard relations
between the $\gamma_{1}$-functional and _covering numbers_.

Let $\mathcal{N}(A,\delta B_{2}^{d})$ be the smallest number of (open)
Euclidean balls of radius $\delta$ needed to cover $A\subset\mathbb{R}^{d}$.
It is standard to verify that for any $A\subset\mathbb{R}^{d}$,

(6.1) $\displaystyle c_{1}\sup_{\delta\geq
0}\left(\delta\cdot\log\mathcal{N}\left(A,\delta
B_{2}^{d}\right)\right)\leq\gamma_{1}(A)\leq
c_{2}\int_{0}^{\infty}\log\mathcal{N}\left(A,\delta B_{2}^{d}\right)\,d\delta$

for absolute constants $c_{1}$ and $c_{2}$. Indeed, the lower bound holds
because for an (almost) optimal admissible sequence and every $s$,

$\sup_{x\in A}2^{s}\|x-\pi_{s}x\|_{2}\leq 2\gamma_{1}(A);$

the upper bound follows by using suitable $\delta$-covers of $A$ as the sets
$A_{s}$.

When $A\subset S^{d-1}$, the inequalities in (6.1) are sharp up to a
logarithmic factor in the dimension $d$; in particular

(6.2) $\displaystyle\gamma_{1}(A)\leq c\log(ed)\cdot\sup_{\delta\geq
0}\left(\delta\cdot\log\mathcal{N}\left(A,\delta B_{2}^{d}\right)\right),$

see e.g., [29, Section 2.5].

######  Proposition 6.1 ([7, Proposition 1.9]).

There are absolute constants $c_{1}$ and $c_{2}$ such that the following
holds. Let $X=G$ be the standard gaussian random vector, let $A\subset
S^{d-1}$ be symmetric and put $\delta>0$. If

$m\geq c_{1}\max\left\\{\frac{1}{\delta^{2}},\frac{\log\mathcal{N}(A,\delta
B_{2}^{d})}{\delta}\right\\},$

then with probability at least $0.9$

(6.3) $\displaystyle\sup_{x\in A}\|F_{m,x}-F_{x}\|_{L_{\infty}}\geq
c_{2}\sqrt{\frac{\delta\cdot\log\mathcal{N}\left(A,\delta
B_{2}^{d}\right)}{m}}.$

Following (6.1) and (6.2), the right hand side in (6.3) almost coincides with
$\sqrt{\gamma_{1}(A)/m}$. In particular, a straightforward consequence of
Proposition 6.1 is that asymptotically, $\gamma_{1}$ is the correct notion of
complexity (up to logarithmic factors):

$\displaystyle\liminf_{m\to\infty}\sqrt{m}\mathbb{E}\left(\sup_{x\in
A}\|F_{m,x}-F_{x}\|_{L_{\infty}}\right)\geq c_{1}\sup_{\delta\geq
0}\sqrt{\delta\log\mathcal{N}(A,\delta B_{2}^{d})}\geq
c_{2}\sqrt{\frac{\gamma_{1}(A)}{\log(d)}}.$

######  Remark 6.2.

  1. (a)

The proof of Proposition 6.1 extends (without any modifications) to the more
general setting considered in Section 3. Indeed, the key feature of the
gaussian random vector used in the proof is a certain small ball assumption.
In the general case, if $\mathcal{H}$ is an arbitrary class of functions, that
assumption corresponds to

(6.4) $\displaystyle\mathbb{P}\left(\\{h(X)\leq
0\\}\,\bigtriangleup\,\\{h^{\prime}(X)\leq
0\\}\right)\geq\kappa\|h-h^{\prime}\|_{L_{2}},$

and in that case the proof is identical to that of Proposition 6.1, with the
constants $c_{1}$ and $c_{2}$ depending on the small ball constant $\kappa$.

  2. (b)

Note that if $\mathcal{H}=\\{\left\langle\cdot,x\right\rangle:x\in A\\}$ for
$A\subset S^{d-1}$ and $X$ is rotation invariant, then (6.4) holds for an
absolute constant $\kappa$.

###  6.2. A variance dependent DKW inequality

One may rightly ask if choosing the $L_{\infty}$-norm to measure the distance
between $F_{m,x}$ and $F_{x}$ is the best option. On the one hand, both the
estimate

$\mathbb{P}\left(\sup_{x\in
A}\|F_{m,x}-F_{x}\|_{L_{\infty}}\geq\sqrt{\Delta}\right)\leq 2\exp(-c\Delta
m)$

and the restriction
$\Delta\gtrsim\frac{\gamma_{1}(A)}{m}\log^{3}(\frac{em}{\gamma_{1}(A)})$ are
optimal (at least up to logarithmic factors). On the other hand, setting
$\sigma_{x}^{2}(t)=F_{x}(t)(1-F_{x}(t))$ one has that
$\mathrm{\mathbb{V}ar}(F_{m,x}(t))=\frac{1}{m}\sigma_{x}^{2}(t)$; therefore it
is reasonable to expect that the error $|F_{m,x}(t)-F_{x}(t)|$ can be
significantly smaller than $\sqrt{\Delta}$ when $F_{x}(t)$ is far from $1/2$.
And indeed, as was shown in [7, Theorem 1.7], a variant of the uniform DKW
inequality with an improved _variance dependent_ error is true when $X$ is the
standard gaussian random vector:

######  Theorem 6.3.

There are absolute constants $c_{1}$ and $c_{2}$ for which the following
holds. Let $X=G$, the standard gaussian vector in $\mathbb{R}^{d}$. If
$A\subset S^{d-1}$ is a symmetric set, $m\geq\gamma_{1}(A)$ and

$\Delta\geq
c_{1}\frac{\gamma_{1}(A)}{m}\log^{3}\left(\frac{em}{\gamma_{1}(A)}\right),$

then with probability at least $1-2\exp(-c_{2}\Delta m)$, for every $x\in A$
and $t\in\mathbb{R}$,

(6.5)
$\displaystyle|F_{m,x}(t)-F_{x}(t)|\leq\Delta+\sigma_{x}(t)\sqrt{\Delta}.$

The estimate in Theorem 6.3 is optimal, and we refer to [7, 8] for more
information on the problem and the proof.

It is natural to ask whether Theorem 6.3 extends beyond the gaussian
framework. The proof from [7] is ‘very gaussian’: it relies heavily on several
special features of the gaussian density $f_{x}$, in particular that in
addition to being bounded, each $f_{x}$ satisfies that

$\displaystyle
f_{x}(t)\sim\sigma_{x}^{2}(t)\log\left(\frac{e}{\sigma_{x}^{2}(t)}\right).$

As it happens, an upper bound on the density that ‘scales well’ with the
variance is _crucial_ to a variance dependent version of the DKW inequality.
As the next example shows, without that feature even ‘nice’ random vectors
(subgaussian, log-concave, with a density that is bounded by 1) do not satisfy
(6.5).

######  Lemma 6.4.

There are constants $c_{1},\dots,c_{5}$ and for every $m\geq c_{1}$ there is
$d\in\mathbb{N}$ and $A\subset S^{d-1}$ with $\gamma_{1}(A)\leq c_{2}$ for
which the following holds. Let $X$ be uniformly distributed in
$[-\sqrt{3},\sqrt{3}]^{d}$. Then there is $t_{0}\in\mathbb{R}$ that satisfies
$\sigma_{x}^{2}(t_{0})\in[\frac{c_{3}}{\sqrt{m}},\frac{c_{4}}{\sqrt{m}}]$ for
every $x\in A$ and, with probability at least $0.9$,

$\sup_{x\in
A}\left|F_{m,x}(t_{0})-F_{x}(t_{0})\right|\geq\frac{c_{5}}{\sqrt{m}}.$

If the assertion of Theorem 6.3 for the random vector in Lemma 6.4 were true,
then with high probability (and ignoring logarithmic factors)

$\sup_{x\in
A}|F_{m,x}(t_{0})-F_{x}(t_{0})|\lesssim\frac{\sigma_{x}(t_{0})}{\sqrt{m}}\sim\frac{1}{m^{3/4}};$

that is far from the true behaviour for $X$.

The proof of Lemma 6.4 follows the arguments used in the proofs of Lemmas 1.7
and 1.9 but requires certain modifications.

###### Proof of Lemma 6.4.

Let $Y=X/\sqrt{3}$ and note that $Y$ is uniformly distributed in $[-1,1]^{d}$.
Set $\delta=\frac{1}{\sqrt{m}}$ and $d=\exp(c_{0}\sqrt{m})$ for a suitable
constant $c_{0}$ that is specified in what follows, and put

$A=\left\\{\sqrt{1-\delta^{2}}\cdot e_{1}+\delta\cdot
e_{k}:k=2,\dots,d\right\\}\subset S^{d-1};$

thus $\gamma_{1}(A)\leq c_{1}\delta\log(d)\leq c_{1}c_{0}$.

Denote by $I$ the set of indices corresponding to the smallest
$\frac{1}{3}\delta m$ coordinates of $(\left\langle
Y_{i},e_{1}\right\rangle)_{i=1}^{m}$ and let

$\Omega_{1}(\mathbb{Y})=\left\\{\left\langle
Y_{i},e_{1}\right\rangle\leq-1+\frac{7}{10}\delta\text{ for every }i\in
I\right\\}.$

Since

$\mathbb{P}\left(\left\langle
Y,e_{1}\right\rangle\leq-1+\frac{7}{10}\delta\right)=\frac{7}{20}\delta>\frac{1}{3}\delta,$

it follows from Markov’s inequality that
$\mathbb{P}(\Omega_{1}(\mathbb{Y}))\geq 0.99$ when
$m\geq\frac{c_{1}}{\delta}=c_{1}\sqrt{m}$.

Set

$\Omega_{2}(\mathbb{Y})=\left\\{\text{there is }2\leq k\leq d\text{ such that
}\left\langle Y_{i},e_{k}\right\rangle\leq-\frac{8}{10}\text{ for every }i\in
I\right\\}.$

Clearly $\mathbb{P}(\left\langle
Y,e_{k}\right\rangle\leq-\frac{8}{10})=\frac{1}{10}$, and using the
independence of the coordinates of $Y$,

$\mathbb{P}\big{(}\Omega_{2}(\mathbb{Y})\,\big{|}\,\Omega_{1}(\mathbb{Y})\big{)}=1-\left(1-10^{-|I|}\right)^{d-1}\geq
1-\exp\left(-(d-1)10^{-|I|}\right)\geq 0.99.$

Indeed, the first inequality holds because $\log(1-\lambda)\geq-\lambda$ for
$\lambda\in(0,1)$, and the second one follows if $d\geq c_{2}10^{|I|}$. Since
$|I|=\frac{1}{3}\sqrt{m}$ and $d=\exp(c_{0}\sqrt{m})$ for a constant $c_{0}$
that we are free to choose, the latter is satisfied.

Fix a realization
$(Y_{i})_{i=1}^{m}\in\Omega_{1}(\mathbb{Y})\cap\Omega_{2}(\mathbb{Y})$. Then
there exists $x=\sqrt{1-\delta^{2}}e_{1}+\delta e_{k}\in A$ and at least
$\frac{1}{3}\delta m$ indices $i$ for which

$\displaystyle\left\langle Y_{i},x\right\rangle$
$\displaystyle=\sqrt{1-\delta^{2}}\left\langle
Y_{i},e_{1}\right\rangle+\delta\left\langle Y_{i},e_{k}\right\rangle$
$\displaystyle\leq\sqrt{1-\delta^{2}}\cdot\left(-1+\frac{7}{10}\delta\right)-\frac{8}{10}\delta=(\ast).$

Moreover, if $\delta=\frac{1}{\sqrt{m}}\leq c_{3}$ then $(\ast)\leq-1$ and in
particular

$\mathbb{P}_{m}(\left\langle Y,x\right\rangle\leq-1)\geq\frac{1}{3}\delta.$

On the other hand, it is straightforward to show that for every $x\in A$,

$\mathbb{P}(\left\langle
Y,x\right\rangle\leq-1)\in\left[c_{4}\delta,\frac{1}{4}\delta\right].$

Setting $t_{0}=-\sqrt{3}$ it follows that
$F_{m,x}(t_{0})-F_{x}(t_{0})\geq\frac{1}{12}\delta$ and that
$F_{z}(t_{0})\in[c_{4}\delta,\frac{\delta}{4}]$ for every $z\in A$, as
claimed. ∎

###  6.3. Uniform estimates on Wasserstein distances

As was shown in Theorem 5.2, the uniform DKW inequality can be used to
construct an estimator $\widehat{\nu}$ of the underlying distribution $\mu$ of
$X$ that is ‘close’ in the sense of integration relative to a (large) family
of test functions. An alternative and more standard approach of comparing
similarity of measures is via the Wasserstein distance.

######  Definition 6.5.

For two probability measures $\alpha$ and $\beta$ on $\mathbb{R}$ and $p\geq
1$, the $p$-order _Wasserstein distance_ is

$\mathcal{W}_{p}(\alpha,\beta)=\left(\inf\int_{\mathbb{R}\times\mathbb{R}}|s-t|^{p}\,\pi(ds,dt)\right)^{1/p},$

with the infimum taken over all couplings $\pi$, i.e. over all probability
measures whose first marginal is $\alpha$ and the second marginal is $\beta$.

We refer to [14, 32] for more information on the $\mathcal{W}_{p}$ distance
and optimal transport.

An estimate on $\sup_{x\in A}\mathcal{W}_{2}(F_{m,x},F_{x})$ for general
$A\subset S^{d-1}$ was recently established in [7] for the standard gaussian
vector. There are other estimates on $\sup_{x\in
A}\mathcal{W}_{p}(F_{m,x},F_{x})$ for more general random vectors but only for
$A=S^{d-1}$ — in which case the distance is the so-called _max-sliced
Wasserstein distance_ [12, 21], see [6, 23, 26, 27] and the references
therein.

The methods developed in the previous sections can be used for estimating
$\sup_{x\in A}\mathcal{W}_{1}(F_{m,x},F_{x})$ for an arbitrary $A\subset
S^{d-1}$ and relatively general random vectors:

######  Theorem 6.6.

For every $L,D\geq 1$ there are constants $c_{1},c_{2},c_{3}$ that depend only
on $L$ and $D$ for which the following holds. If $X$ satisfies Assumption
1.10, $A\subset S^{d-1}$ is a symmetric set, $m\geq\gamma_{1}(A)$ and

$\Delta\in\left[c_{1}\frac{\gamma_{1}(A)}{m}\log^{3}\left(\frac{em}{\gamma_{1}(A)}\right)\,,\,1\right],$

then with probability at least $1-2\exp(-c_{2}\Delta m)$,

$\sup_{x\in A}\mathcal{W}_{1}\left(F_{m,x},F_{x}\right)\leq
c_{3}\sqrt{\Delta}\log\left(\frac{e}{\Delta}\right).$

###### Sketch of proof.

Let $\mathcal{L}_{1}$ be the set of all real $1$-Lipschitz functions $\varphi$
that satisfy $\varphi(0)=0$. By the Kantorovich-Rubinstein duality (see, e.g.,
[14, Proposition 2.6.6]),

(6.6) $\displaystyle\mathcal{W}_{1}\left(F_{m,x},F_{x}\right)$
$\displaystyle=\sup_{\varphi\in\mathcal{L}_{1}}\left(\int_{\mathbb{R}}\varphi(t)\,dF_{m,x}(t)-\int_{\mathbb{R}}\varphi(t)\,dF_{x}(t)\right)$
$\displaystyle=\sup_{\varphi\in\mathcal{L}_{1}}\left(\int_{0}^{1}\varphi(F_{m,x}^{-1}(u))\,du-\int_{0}^{1}\varphi(F_{x}^{-1}(u))\,du\right).$

Every $\varphi\in\mathcal{L}_{1}$ can be written as the difference of two
increasing functions with sublinear growth, and it follows from Lemma 5.3 that
with probability at least $1-2\exp(c_{1}\Delta m)$, for every
$\varphi\in\mathcal{L}_{1}$,

$\left|\int_{\sqrt{\Delta}}^{1-\sqrt{\Delta}}\varphi(F_{m,x}^{-1}(u))\,du-\int_{\sqrt{\Delta}}^{1-\sqrt{\Delta}}\varphi(F_{x}^{-1}(u))\right|\leq
c_{2}(L,D)\sqrt{\Delta}\log\left(\frac{e}{\Delta}\right).$

All that remains is to control the ‘tails’, that is, estimate the integrals in
the intervals $[0,\sqrt{\Delta}]$ and $[1-\sqrt{\Delta},1]$.

Set $U=[0,1]\setminus[\sqrt{\Delta},1-\sqrt{\Delta}]$ and recall that by the
tail behaviour of $F_{x}$ (see (5.5)),

$\sup_{\varphi\in\mathcal{L}_{1}}\int_{U}\varphi(F_{x}^{-1}(u))\,du\leq\int_{U}|F_{x}^{-1}(u)|\,du\leq
c_{3}(L)\sqrt{\Delta}\log\left(\frac{e}{\Delta}\right).$

Moreover, using the notation of Section 3.2,

$\sup_{\varphi\in\mathcal{L}_{1}}\int_{U}\varphi(F_{m,x}^{-1}(u))\,du\leq\int_{U}|F_{m,x}^{-1}(u)|\,du\sim\frac{1}{m}\sum_{i=1}^{2\sqrt{\Delta}m}\left\langle
X_{i},x\right\rangle^{\ast}=\Psi(x).$

A standard chaining argument similar to the one used in Section 3.2 shows that
with probability at least $1-2\exp(-c_{4}\Delta m)$,

$\sup_{x\in A}\Psi(x)\leq
c_{5}(L)\sqrt{\Delta}\log\left(\frac{e}{\Delta}\right),$

and the proof is completed by combining these observations. ∎

######  Remark 6.7.

By applying the uniform DKW inequality it is possible to extend the scope of
Theorem 6.6 and analyse higher order Wasserstein distances $\mathcal{W}_{p}$
as well (rather than just $\mathcal{W}_{1}$). However, the proof is more
involved because a representation as in (6.6) is no longer true when $p>1$. We
defer those results to future work.

Acknowledgements: Daniel Bartl is grateful for financial support through the
Austrian Science Fund (grant DOI: 10.55776/ESP31 and 10.55776/P34743).

## References

  * [1] P. Abdalla and N. Zhivotovskiy.  Covariance estimation: Optimal dimension-free guarantees for adversarial corruption and heavy tails.  Journal of the European Mathematical Society, to appear, 2022.
  * [2] R. Adamczak, A. E. Litvak, A. Pajor, and N. Tomczak-Jaegermann.  Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling.  Constructive Approximation, 34:61–88, 2011.
  * [3] K. S. Alexander.  The central limit theorem for weighted empirical processes indexed by sets.  Journal of multivariate analysis, 22(2):313–339, 1987.
  * [4] K. S. Alexander.  Rates of growth and sample moduli for weighted empirical processes indexed by sets.  Probability Theory and Related Fields, 75(3):379–423, 1987.
  * [5] S. Artstein-Avidan, A. Giannopoulos, and V. D. Milman.  Asymptotic Geometric Analysis, Part I, volume 202.  American Mathematical Society, 2015.
  * [6] D. Bartl and S. Mendelson.  Structure preservation via the Wasserstein distance.  arXiv preprint arXiv:2209.07058, 2022.
  * [7] D. Bartl and S. Mendelson.  Empirical approximation of the gaussian distribution in $\mathbb{R}^{d}$.  arXiv preprint arXiv:2309.02013, 2023.
  * [8] D. Bartl and S. Mendelson.  On a variance dependent Dvoretzky-Kiefer-Wolfowitz inequality.  arXiv preprint arXiv:2308.04757, 2023.
  * [9] S. G. Bobkov and G. P. Chistyakov.  On concentration functions of random variables.  Journal of Theoretical Probability, 28(3):976–988, 2015.
  * [10] S. Boucheron, G. Lugosi, and P. Massart.  Concentration inequalities: A nonasymptotic theory of independence.  Oxford university press, 2013.
  * [11] F. P. Cantelli.  Sulla determinazione empirica delle leggi di probabilita.  Giorn. Ist. Ital. Attuari, 4(421-424), 1933.
  * [12] I. Deshpande, Y.-T. Hu, R. Sun, A. Pyrros, N. Siddiqui, S. Koyejo, Z. Zhao, D. Forsyth, and A. G. Schwing.  Max-sliced Wasserstein distance and its use for gans.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10648–10656, 2019.
  * [13] A. Dvoretzky, J. Kiefer, and J. Wolfowitz.  Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator.  The Annals of Mathematical Statistics, pages 642–669, 1956.
  * [14] A. Figalli and F. Glaudo.  An Invitation to Optimal Transport, Wasserstein Distances, and Gradient Flows.  EMS Textbooks in Mathematics, 2021.
  * [15] E. Giné and V. Koltchinskii.  Concentration inequalities and asymptotic results for ratio type empirical processes.  The Annals of Probability, 34:1143–1216, 2006.
  * [16] E. Giné, V. Koltchinskii, and J. A. Wellner.  Ratio limit theorems for empirical processes.  In Stochastic inequalities and applications, pages 249–278. Springer, 2003.
  * [17] V. Glivenko.  Sulla determinazione empirica delle leggi di probabilita.  Gion. Ist. Ital. Attauri., 4:92–99, 1933.
  * [18] O. Guédon and M. Rudelson.  Lp-moments of random vectors via majorizing measures.  Advances in Mathematics, 208(2):798–823, 2007.
  * [19] V. Koltchinskii.  Bounds on margin distributions in learning problems.  Annales de l’IHP Probabilités et statistiques, 39(6):943–978, 2003.
  * [20] V. Koltchinskii and D. Panchenko.  Empirical margin distributions and bounding the generalization error of combined classifiers.  The Annals of Statistics, 30(1):1–50, 2002.
  * [21] T. Lin, Z. Zheng, E. Chen, M. Cuturi, and M. I. Jordan.  On projection robust optimal transport: Sample complexity and model misspecification.  In International Conference on Artificial Intelligence and Statistics, pages 262–270. PMLR, 2021.
  * [22] G. Lugosi and S. Mendelson.  Multivariate mean estimation with direction-dependent accuracy.  Journal of the European Mathematical Society, to appear, 2020.
  * [23] T. Manole, S. Balakrishnan, and L. Wasserman.  Minimax confidence intervals for the sliced wasserstein distance.  Electronic Journal of Statistics, 16(1):2252–2345, 2022.
  * [24] P. Massart.  The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality.  The Annals of Probability, pages 1269–1283, 1990.
  * [25] S. Mendelson.  Approximating Lp unit balls via random sampling.  Advances in Mathematics, 386:107829, 2021.
  * [26] S. Nietert, Z. Goldfeld, R. Sadhu, and K. Kato.  Statistical, robustness, and computational guarantees for sliced wasserstein distances.  Advances in Neural Information Processing Systems, 35:28179–28193, 2022.
  * [27] J. Olea, C. Rush, A. Velez, and J. Wiesel.  On the generalization error of norm penalty linear regression models.  arXiv preprint arXiv:2211.07608, 2022.
  * [28] M. Talagrand.  Majorizing measures: the generic chaining.  The Annals of Probability, 24(3):1049–1103, 1996.
  * [29] M. Talagrand.  Upper and lower bounds for stochastic processes: decomposition theorems, volume 60.  Springer Nature, 2022.
  * [30] A. W. Vaart and J. A. Wellner.  Weak convergence.  In Weak convergence and empirical processes, pages 16–28. Springer, 1996.
  * [31] R. Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press, 2018.
  * [32] C. Villani.  Topics in optimal transportation, volume 58.  American Mathematical Soc., 2021.