# Structure preservation via the Wasserstein distance

Daniel Bartl111 University of Vienna, Faculty of Mathematics
<EMAIL_ADDRESS>Shahar Mendelson222University of Warwick,
Department of Statistics and The Australian National University, Centre for
Mathematics and its Applications<EMAIL_ADDRESS>
###### Abstract

We show that under minimal assumptions on a random vector
$X\in\mathbb{R}^{d}$, and with high probability, given $m$ independent copies
of $X$, the coordinate distribution of each vector $(\langle
X_{i},\theta\rangle)_{i=1}^{m}$ is dictated by the distribution of the true
marginal $\langle X,\theta\rangle$. Formally, we show that with high
probability,

$\sup_{\theta\in S^{d-1}}\left(\frac{1}{m}\sum_{i=1}^{m}\left|\langle
X_{i},\theta\rangle^{\sharp}-\lambda^{\theta}_{i}\right|^{2}\right)^{1/2}\leq
c\left(\frac{d}{m}\right)^{1/4},$

where $\lambda^{\theta}_{i}=m\int_{(\frac{i-1}{m},\frac{i}{m}]}F_{\langle
X,\theta\rangle}^{-1}(u)^{2}\,du$ and $a^{\sharp}$ denotes the monotone non-
decreasing rearrangement of $a$.

The proof follows from the optimal estimate on the worst Wasserstein distance
between a marginal of $X$ and its empirical counterpart,
$\frac{1}{m}\sum_{i=1}^{m}\delta_{\langle X_{i},\theta\rangle}$.

We then use the accurate information on the structures of the vectors
$(\langle X_{i},\theta\rangle)_{i=1}^{m}$ to construct the first non-gaussian
ensemble that yields the optimal estimate in the Dvoretzky-Milman Theorem: the
ensemble exhibits almost Euclidean sections in arbitrary normed spaces of the
same dimension as the gaussian embedding—despite being very far from gaussian
(in fact, it happens to be heavy-tailed).

##  1 Introduction

The study of the way in which structure can be preserved using random sampling
is of central importance in modern mathematics. Various notions of structure
have been considered over the years, resulting in numerous applications in
pure mathematics, statistics and data science.

Here, we focus on the way in which a typical sample, consisting of $m$
independent copies of a random vector distributed according to a centred
probability measure $\mu$ on $\mathbb{R}^{d}$, inherits features of that
measure. Informally put, we explore the following:

######  Question 1.1.

Given $X_{1},\dots,X_{m}$ selected independently according to $\mu$, how much
“information” on $\mu$ can be extracted (with high probability) from the set
$\\{X_{1},\dots,X_{m}\\}$?

Since the empirical measure $s=\frac{1}{m}\sum_{i=1}^{m}\delta_{X_{i}}$
converges weakly to $\mu$ almost surely, the main interest in Question 1.1 is
of a quantitative nature.

To put this (still rather vague) question in some perspective, let us start
with a natural notion that will prove to be instructive, but at the same time
rather useless. Consider two independent samples $(X_{i})_{i=1}^{m}$ and
$(X_{i}^{\prime})_{i=1}^{m}$, both selected according to $\mu^{\otimes m}$.
Intuitively, if for a typical sample $(X_{i})_{i=1}^{m}$, the set
$\\{X_{i}:1\leq i\leq m\\}$ inherits much of $\mu$’s structure, then
$\\{X_{i}:1\leq i\leq m\\}$ and $\\{X_{i}^{\prime}:1\leq i\leq m\\}$ should be
“close” to each other. And, because the way the points are ordered is
irrelevant, a natural notion of similarity between the two “clouds” of points
is

$\displaystyle\inf_{\pi}\left(\frac{1}{m}\sum_{i=1}^{m}\left\|X_{\pi(i)}-X_{i}^{\prime}\right\|_{2}^{2}\right)^{1/2},$
(1.1)

with the infimum taken over all permutations $\pi$ of $\\{1,\dots,m\\}$.

As it happens, (1.1) is simply the $\mathcal{W}_{2}$ _Wasserstein distance_
between the two empirical measures $\frac{1}{m}\sum_{i=1}^{m}\delta_{X_{i}}$
and $\frac{1}{m}\sum_{i=1}^{m}\delta_{X_{i}^{\prime}}$. The $\mathcal{W}_{2}$
distance is defined on $\mathcal{P}_{2}(\mathbb{R}^{d})$—the set of Borel
probability measures on $\mathbb{R}^{d}$ with finite second moment—by

$\mathcal{W}_{2}(\tau,\nu)=\inf_{\Pi}\left(\int_{\mathbb{R}^{d}\times\mathbb{R}^{d}}\|x-y\|_{2}^{2}\,\Pi(dx,dy)\right)^{1/2}.$

Here the infimum taken over all _couplings_ $\Pi$, that is, probability
measures whose first marginal is $\tau$ and their second marginal is $\nu$.
For detailed surveys on the Wasserstein distance, see, e.g., [13, 41].

Setting $\mu_{m}=\frac{1}{m}\sum_{i=1}^{m}\delta_{X_{i}}$ and
$\mu_{m}^{\prime}=\frac{1}{m}\sum_{i=1}^{m}\delta_{X_{i}^{\prime}}$, it is
straightforward to verify that (1.1) is simply
$\mathcal{W}_{2}(\mu_{m},\mu_{m}^{\prime})$. Moreover, a standard convexity
argument shows that obtaining high probability estimates on
$\mathcal{W}_{2}(\mu_{m},\mu_{m}^{\prime})$ and on
$\mathcal{W}_{2}(\mu_{m},\mu)$ are equivalent questions, and in what follows
we focus on the latter.

While $\mathcal{W}_{2}(\mu_{m},\mu)$ is a natural way of comparing $\mu_{m}$
and $\mu$, using the Wasserstein distance has a significant drawback. In the
high-dimensional setup, $\mathcal{W}_{2}$ is just _too sensitive_ : the
typical distance between $\mu_{m}$ and $\mu$ is almost diametric unless $m$ is
exponential in the dimension $d$. Indeed, although
$\mathcal{W}_{2}(\mu_{m},\mu)\to 0$ almost surely as $m\to\infty$, the
pointwise best approximation of $\mu$ by $m$ points, i.e.,
$\inf_{x_{1},\dots,x_{m}\in\mathbb{R}^{d}}\mathcal{W}_{2}(\frac{1}{m}\sum_{i=1}^{m}\delta_{x_{i}},\mu)$,
typically scales like $m^{-1/d}$ even for well-behaved measures—like the
gaussian measure or the uniform measure on the unit cube, see [11].

The slow decay of $\mathcal{W}_{2}(\mu_{m},\mu)$ is a manifestation of the
_curse of dimensionality_ phenomenon, rendering that notion of similarity
useless for our purposes. It also hints that if one is to overcome the curse
of dimensionality, a useful notion of structure preservation should depend
only on low-dimensional marginals of $\mu$.

One such notion is based on the behaviour of the _extremal singular values_ of
the random matrix whose rows are $X_{1},...,X_{m}$. Assume for the sake of
simplicity that the centred measure $\mu$ is also isotropic (that is, its
covariance is the identity) and consider $S^{d-1}$, the Euclidean unit sphere
in $\mathbb{R}^{d}$, viewed as a class of linear functionals
$\\{\left\langle\theta,\cdot\right\rangle:\theta\in S^{d-1}\\}\subset
L_{2}(\mu)$. Let $X$ be distributed according to $\mu$, set
$X_{1},\dots,X_{m}$ to be independent copies of $X$ and put

$\Gamma=\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\left\langle X_{i},\cdot\right\rangle
e_{i}.$

The random operator $\Gamma$ is an embedding of
$(\mathbb{R}^{d},\|\cdot\|_{L_{2}(\mu)})$ into
$\ell_{2}^{m}=(\mathbb{R}^{m},\|\cdot\|_{2})$, and it is natural to identify
conditions on $X$ and $m$ under which $\Gamma$ is a $1\pm\varepsilon$
isomorphism, i.e., that

$\displaystyle\sup_{\theta\in
S^{d-1}}\left|\|\Gamma\theta\|_{2}^{2}-1\right|\leq\varepsilon.$ (1.2)

Clearly, (1.2) means that the extremal singular values of $\Gamma$ are close
to $1$, and the extent to which the random sample $X_{1},\dots,X_{m}$ inherits
the $L_{2}$ structure endowed by $\mu$ is measured by (1.2).

While (1.2) captures significant information on structure preservation, it is
still rather crude: it yields very little on the measure $\mu$—other than
exhibiting that it is isotropic. And, if $\mu$ is not isotropic, analogs of
(1.2) allow one to recover $\mu$’s covariance structure (see, for example,
[21, 23, 28] for results of that flavour), but nothing beyond that. In
comparison, far more accurate information is ‘coded’ in estimates on the
‘worst’ Wasserstein distance of a one-dimensional marginal of $\mu$ from its
empirical counterpart. To see why, consider a direction $\theta\in S^{d-1}$,
let $\mu^{\theta}(A)=\mu(\\{x\in\mathbb{R}^{d}:\left\langle
x,\theta\right\rangle\in A\\})$ be the marginal of $\mu$ in direction $\theta$
and set

$F_{\mu^{\theta}}(t)=\mu^{\theta}((-\infty,t])\quad\text{and}\quad
F_{\mu^{\theta}}^{-1}(u)=\inf\left\\{t\in\mathbb{R}:F_{\mu^{\theta}}(t)\geq
u\right\\}$

to be the _distribution function_ of $\mu^{\theta}$ and its _(right-)inverse_.

######  Definition 1.2 (Max-sliced Wasserstein distance).

For every $\mu,\nu\in\mathcal{P}_{2}(\mathbb{R}^{d})$, the _max-sliced
Wasserstein distance_ is defined by

$\mathcal{SW}_{2}(\mu,\nu)=\sup_{\theta\in
S^{d-1}}\mathcal{W}_{2}\left(\mu^{\theta},\nu^{\theta}\right).$

One can show that $\mathcal{SW}_{2}$ is a metric on
$\mathcal{P}_{2}(\mathbb{R}^{d})$ that endows the same topology as
$\mathcal{W}_{2}$. For the proof of this fact and more information on notions
of a similar flavour, see, e.g., [10, 20, 22, 32].

A fact that is used frequently in what follows is a closed-form of the
Wasserstein distance between one-dimensional measures, implying that

$\mathcal{SW}_{2}(\mu_{m},\mu)=\sup_{\theta\in
S^{d-1}}\left(\int_{0}^{1}\left(F_{\mu^{\theta}_{m}}^{-1}(u)-F_{\mu^{\theta}}^{-1}(u)\right)^{2}\,du\right)^{1/2},$
(1.3)

see [35] and Lemma 2.1.

Using the representation (1.3), the following observation is of central
importance:

An upper bound on $\mathcal{SW}_{2}(\mu_{m},\mu)$ implies uniform
concentration of the coordinate distribution of the vectors $(\left\langle
X_{i},\theta\right\rangle)_{i=1}^{m}$ around a well-determined set of values,
endowed by $\mu$.

To be more precise, let $\theta\in S^{d-1}$ and for $1\leq i\leq m$ set

$\lambda^{\theta}_{i}=m\int_{(i-1)/m}^{i/m}F_{\mu^{\theta}}^{-1}(u)\,du.$

One may show (see Section 2 for the proof) that

$\displaystyle\sup_{\theta\in
S^{d-1}}\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
X_{i},\theta\right\rangle^{\sharp}-\lambda^{\theta}_{i}\right|^{2}\right)^{1/2}\leq\mathcal{SW}_{2}(\mu_{m},\mu),$
(1.4)

where here and throughout this article, $(a_{i}^{\sharp})_{i=1}^{m}$ is non-
decreasing rearrangement of $(a_{i})_{i=1}^{m}$. Equation (1.4) means that the
random vectors $(\left\langle X_{i},\theta\right\rangle)_{i=1}^{m}$ all
inherit—on the same event—the distribution of the corresponding one-
dimensional marginals of $\mu$.

One scenario of particular interest is when the random vector $X$ is rotation
invariant. In such a situation, an upper estimate on $\mathcal{SW}_{2}$
combined with (1.4) implies that $\Gamma S^{d-1}$ inherits $\mu$’s invariance,
in the sense that

$\sup_{\theta,\theta^{\prime}\in
S^{d-1}}\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
X_{i},\theta\right\rangle^{\sharp}-\left\langle
X_{i},\theta^{\prime}\right\rangle^{\sharp}\right|^{2}\right)^{1/2}\leq
2\mathcal{SW}_{2}(\mu_{m},\mu).$

In other words, after replacing vectors in $\Gamma S^{d-1}$ by their monotone
rearrangement, the Euclidean diameter of the resulting set is bounded by
$2\mathcal{SW}_{2}(\mu_{m},\mu)$. Hence, if $\mathcal{SW}_{2}(\mu_{m},\mu)$ is
‘small’ then the vectors $(\left\langle X_{i},\theta\right\rangle)_{i=1}^{m}$
are ‘close’ to one another.

Roughly put, our main result is that under minimal assumptions on $X$ and with
high probability, $\mathcal{SW}_{2}(\mu_{m},\mu)$ is indeed small:
$\mathcal{SW}_{2}(\mu_{m},\mu)\leq c\left(\frac{d}{m}\right)^{1/4},$ (1.5)
where $c$ is a suitable constant—and this estimate is optimal. In particular,
using the above notation, we have that $\sup_{\theta\in
S^{d-1}}\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
X_{i},\theta\right\rangle^{\sharp}-\lambda^{\theta}_{i}\right|^{2}\right)^{1/2}\leq
c\left(\frac{d}{m}\right)^{1/4},$ (1.6) and if $X$ is rotation invariant then
$\sup_{\theta,\theta^{\prime}\in
S^{d-1}}\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
X_{i},\theta\right\rangle^{\sharp}-\left\langle
X_{i},\theta^{\prime}\right\rangle^{\sharp}\right|^{2}\right)^{1/2}\leq
2c\left(\frac{d}{m}\right)^{1/4}.$ (1.7)

To explain what is meant by “minimal assumptions on $X$”, let us compare (1.5)
with (1.2). Both estimates are some form of uniform control on the one-
dimensional marginals of $X$, with one (trivially) stronger than the other.
Indeed, setting

$\displaystyle\rho_{d,m}=\sup_{\theta\in
S^{d-1}}\left|\frac{1}{m}\sum_{i=1}^{m}\left\langle
X_{i},\theta\right\rangle^{2}-1\right|=\sup_{\theta\in
S^{d-1}}\left|\|\Gamma\theta\|_{2}^{2}-1\right|,$ (1.8)

it is straightforward to verify that if $\mathcal{SW}_{2}(\mu_{m},\mu)\leq 1$
then

$\displaystyle\rho_{d,m}\leq 3\cdot\mathcal{SW}_{2}(\mu_{m},\mu).$ (1.9)

(see Lemma 2.2 for the proof).

The proof of our main result is based on that, to some extent, (1.9) can be
reversed, and $\mathcal{SW}_{2}(\mu_{m},\mu)$ can be controlled in terms of
$\rho_{d,m}$:

######  Theorem 1.3.

Let $X$ be centred and isotropic, and assume that $\sup_{\theta\in
S^{d-1}}\|\left\langle X,\theta\right\rangle\|_{L_{q}}\leq L$ for some $q\geq
4$. Then there are absolute constants $c_{0},c_{1},c_{2}$ and a constant
$c_{3}$ that depends only on $q$ and $L$ such that the following holds. Let
$0<\Delta\leq c_{0}$ and set $m\geq c_{1}\frac{d}{\Delta}$. With probability
at least $1-\exp(-c_{2}\Delta m)$, $\mathcal{SW}_{2}(\mu_{m},\mu)\leq
c_{3}\begin{cases}\rho_{d,m}^{1/2}+\Delta^{1/4}&\text{if }q>4,\\\ \\\
\rho_{d,m}^{1/2}+\Delta^{1/4}\log\left(\frac{1}{\Delta}\right)&\text{if
}q=4.\end{cases}$

######  Remark 1.4.

In a one dimensional framework, Bobkov-Ledoux [6] study in great detail the
behaviour of $\mathbb{E}\mathcal{W}_{2}(\mu_{m},\mu)$. In particular they
explore conditions under which the error estimate is $m^{-1/2}$ (up to
logarithmic factors) and show that this can only happen under strong
regularity assumptions—e.g., that the support of $\mu$ is connected. Since the
focus of this article is on the effect of high dimensions in the context of
_general_ random vectors, we chose not pursue a similar path here. In addition
to the general case we only consider one family of regular random
vectors—isotropic, log-concave random vectors—see Theorem 1.6.

As we explain in what follows, Theorem 1.3 is optimal. At the same time, it is
rather surprising, as it implies a significant improvement on the state-of-
the-art geometric estimates related to the study of the extremal singular
values of the random matrix $\Gamma$. Sharp upper bounds on $\rho_{d,m}$
follow from (crude) structural information on the vectors
$\\{\Gamma\theta:\theta\in S^{d-1}\\}$ (see, e.g., [26, 39]), and are based on
(necessary) assumptions on the isotropic random vector $X$—namely that
$\|X\|_{2}^{2}/d$ has a well-behaved tail-decay and $\sup_{\theta\in
S^{d-1}}\|\left\langle X,\theta\right\rangle\|_{L_{q}}\leq L$ for some $q\geq
4$. At the heart of the arguments in [26, 39] is that under those assumptions
the following holds on a high probability event:

$\bullet$ For each vector $w=\sqrt{m}\Gamma\theta=(\left\langle
X_{i},\theta\right\rangle)_{i=1}^{m}$, the contribution of its largest $\Delta
m$ coordinates to $\|w\|_{2}$ norm is not “too big”.

$\bullet$ The remaining coordinates “live” within a multiplicative envelope,
dictated by the assumed tail-decay. For example, under an $L_{q}-L_{2}$ norm
equivalence assumption one has that for every such vector $w$ and $k=\Delta
m,\dots,m$

$w^{\ast}_{k}\leq c(L)(m/k)^{1/q},$ (1.10)

where $w^{\ast}$ denotes the monotone non-increasing rearrangement of
$(|w_{i}|)_{i=1}^{m}$.

When $q>4$, this type of structural information suffices for establishing the
optimal estimate—that $\rho_{d,m}\leq c\sqrt{d/m}$ with high probability.

######  Remark 1.5.

When $q=4$, the state-of-the-art estimate on $\rho_{d,m}$ due to Tikhomirov
[39], has an additional multiplicative logarithmic factor in $m/d$. And in a
similar manner, the estimate in Theorem 1.3 when $q=4$ also has an additional
factor of $\log\frac{1}{\Delta}$ when $\Delta\geq d/m$. The Bai-Yin
asymptotics [3] imply that when $q=4$ the logarithmic factor in $\rho_{d,m}$
should disappear when $d,m\to\infty$ while keeping the ratio $d/m$ fixed. It
is reasonable to expect that the same is true in regard to Theorem 1.3 and
that the $\log\frac{1}{\Delta}$ factor is superfluous.

Although the structural information in (1.10) plays an instrumental role in
obtaining sharp estimates on $\rho_{d,m}$, it is still significantly weaker
than the outcome of Theorem 1.3. Indeed, if $X$ satisfies a non-asymptotic
‘Bai-Yin’ estimate, i.e., $\rho_{d,m}\leq c\sqrt{\Delta}$ with probability at
least $1-\eta$, then it follows from Theorem 1.3 that with probability at
least $1-\exp(-c_{2}\Delta m)-\eta$,

$\mathcal{SW}_{2}(\mu_{m},\mu)\leq\begin{cases}c_{4}\Delta^{1/4}&\text{if
}q>4,\\\ \\\ c_{4}\Delta^{1/4}\log\left(\frac{1}{\Delta}\right)&\text{if
}q=4.\end{cases}$

Thus, the monotone non-decreasing rearrangement of each $(\left\langle
X_{i},\theta\right\rangle)_{i=1}^{m}$ satisfies that

$\sup_{\theta\in S^{d-1}}\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
X_{i},\theta\right\rangle^{\sharp}-\lambda^{\theta}_{i}\right|^{2}\right)^{1/2}\leq\begin{cases}c_{5}\Delta^{1/4}&\text{if
}q>4,\\\ \\\ c_{5}\Delta^{1/4}\log\left(\frac{1}{\Delta}\right)&\text{if
}q=4,\end{cases}$

which is far more accurate than the existence of a one-sided multiplicative
envelope function for the non-increasing rearrangement of vectors
$(|\left\langle X_{i},\theta\right\rangle|)_{i=1}^{m}$ as in (1.10).

The question of the optimality of Theorem 1.3 is explored in Section 2. For
example, we show that the estimate of $(d/m)^{1/4}$ is sharp in general—even
if one allows for a significantly weaker probability estimate—of constant
probability rather than of $1-\exp(-cd)$—, or even if the random vector $X$ is
well-behaved, e.g., isotropic and $L$-subgaussian333Recall that if a random
vector $X$ is isotropic and $L$-subgaussian then $\|\left\langle
X,\theta\right\rangle\|_{L_{p}}\leq L\sqrt{p}$ for every $p\geq 2$ and
$\theta\in S^{d-1}$.. The latter stems from a simple one-dimensional
phenomenon: if $\mu^{\theta}$ is symmetric and $\\{-1,1\\}$-valued, it is
straightforward to verify that for $\Delta\leq 1/4$ and $m\geq 4$,

$\displaystyle\int_{1/4}^{3/4}\left(F_{\mu^{\theta}_{m}}^{-1}(u)-F_{\mu^{\theta}}^{-1}(u)\right)^{2}\,du\geq
c_{1}\sqrt{\Delta}$ (1.11)

with probability at least $c_{2}\exp(-c_{3}\Delta m)$ (see Lemma 2.7 for the
proof). Thus, invoking the representation (1.3) it is evident that if $X$ is
uniformly distributed in $\\{-1,1\\}^{d}$, then with probability at least
$c_{2}\exp(-c_{3}\Delta m)$,

$\displaystyle\mathcal{SW}_{2}(\mu_{m},\mu)\geq\sqrt{c_{1}}\Delta^{1/4}.$
(1.12)

In particular, the fact that $X$ is subgaussian does not mean that the error
estimate in Theorem 1.3 can be better than $\sim\Delta^{1/4}$.

At the same time, once the random vector is ‘regular’ in a certain sense, the
estimate in Theorem 1.3 can be improved to $\sqrt{\Delta}$ (up to logarithmic
factors)—in which case (1.9) truly can be reversed—see Theorem 1.6.

One outcome of Theorem 1.3—specifically, of the fact that $\Gamma S^{d-1}$
inherits $\mu$’s rotation invariance, is our second main result: the first
non-gaussian version of the celebrated Dvoretzky-Milman Theorem.

Informally put, the Dvoretzky-Milman Theorem establishes the existence of high
dimensional, almost Euclidean subspaces in arbitrary normed spaces. For more
details on the Dvoretzky-Milman theorem see [2] and Section 4.

The idea behind Milman’s seminal proof is that certain well-chosen random
functions are almost constant on the Euclidean unit sphere of the right
dimension. Indeed, one can show that for any norm $\|\cdot\|$ on
$\mathbb{R}^{n}$ there is a critical dimension $d^{\ast}$ such that if $d\leq
d^{\ast}$ and $G_{1},\dots,G_{d}$ are independent copies of the standard
gaussian random vector $G$ in $\mathbb{R}^{n}$, a typical realization of the
function $x\mapsto\|\sum_{i=1}^{d}x_{i}G_{i}\|$ is almost constant on
$S^{d-1}$. That follows from two features of the gaussian vector: firstly,
that for any $x\in\mathbb{R}^{d}$ and any norm $\|\cdot\|$,
$\mathbb{E}\|\sum_{i=1}^{d}x_{i}G_{i}\|=\|x\|_{2}\cdot\mathbb{E}\|G\|$; and
secondly, that each random variable $\|\sum_{i=1}^{d}x_{i}G_{i}\|$
concentrates sharply around its mean.

Since Milman’s proof—some 50 years ago—the only random ensembles known to
exhibit Euclidean subspaces of the optimal (critical) dimension in arbitrary
normed spaces were the gaussian ensemble $x\to\sum_{i=1}^{d}x_{i}G_{i}$; and
the projection onto a random $d$-dimensional subspace, selected according to
the uniform measure on the Grassmann manifold. Those were the only examples of
random ensembles that satisfied the two features simultaneously.

Our construction of a non-gaussian (in fact, a heavy-tailed) optimal
Dvoretzky-Milman ensemble relies heavily on the structural information on
$\Gamma S^{d-1}$ that follows from Theorem 1.3. The accurate statement is
presented in Section 4.

###  1.1 A Warm up exercise: Theorem 1.3 in the log-concave case

The proof of Theorem 1.3 is rather involved, and it is useful to present some
of the ideas used in the argument in a simpler context—when $X$ is a centred,
isotropic, log-concave random vector444Recall that a random vector is log-
concave if it has a density that is a log-concave function.. As it happens,
for such random vectors the estimate in Theorem 1.3 can be improved from
$\Delta^{1/4}$ to $\sqrt{\Delta}$ (up to logarithmic factors). At the same
time, it is important to keep in mind that $\Delta^{1/4}$ is the best one can
hope for unless $X$ is regular in a strong sense—see Section 2.1.

######  Theorem 1.6.

There are absolute constants $c_{0},c_{1},c_{2}$ and $c_{3}$ for which the
following holds. Let $X$ be a centred, isotropic and log-concave random vector
in $\mathbb{R}^{d}$. Let $0<\Delta\leq c_{0}$ and set $m\geq
c_{1}\frac{d}{\Delta}$. Then with probability at least
$1-\exp(-c_{2}\sqrt{\Delta m}\log^{2}(\frac{1}{\Delta}))$,

$\mathcal{SW}_{2}(\mu_{m},\mu)\leq
c_{3}\sqrt{\Delta}\log^{2}\left(\frac{1}{\Delta}\right).$

In particular, setting $\Delta=c_{1}d/m$, then with probability at least
$1-\exp(-c^{\prime}_{2}\sqrt{d}\log^{2}(\frac{m}{d}))$,

$\mathcal{SW}_{2}(\mu_{m},\mu)\leq
c^{\prime}_{3}\sqrt{\frac{d}{m}}\log^{2}\left(\frac{m}{d}\right).$ (1.13)

If $X$ is, in addition, $L$-subgaussian, then the constants $c_{2},c_{3}$
depend on $L$, and with probability at least $1-\exp(-c_{2}\Delta m)$,

$\mathcal{SW}_{2}(\mu_{m},\mu)\leq
c_{3}\sqrt{\Delta}\log^{3/2}\left(\frac{1}{\Delta}\right).$

We show in Section 2.1 that if $X$ is isotropic and not degenerate in the
sense that $\mathbb{E}\|X\|_{2}\geq\beta\sqrt{d}$, then with probability at
least $c_{1}(\beta)$, $\mathcal{SW}_{2}(\mu_{m},\mu)\geq
c_{2}(\beta)\sqrt{d/m}$. It is well-known that an isotropic, log-concave
random vector satisfies that $\mathbb{E}\|X\|_{2}\geq c\sqrt{d}$ for an
absolute constant $c$, and thus (1.13) is sharp up to the logarithmic factor.

######  Remark 1.7.

It is relatively simple to construct measures that are close to a log-concave
measure in some natural sense (e.g., in the $\mathcal{W}_{1}$ distance), but
the behaviour of $\mathcal{SW}_{2}(\mu_{m},\mu)$ is far worse than
$\sim\Delta^{1/2}$. We will not pursue this direction here.

Below we sketch the main ideas used in the proof of Theorem 1.6. The complete
proof can be found in Section 3.

###  1.2 Theorem 1.6—highlights of the argument

As was noted previously,

$\mathcal{SW}_{2}(\mu_{m},\mu)=\sup_{\theta\in
S^{d-1}}\left(\int_{0}^{1}\left(F_{\mu^{\theta}_{m}}^{-1}(u)-F_{\mu^{\theta}}^{-1}(u)\right)^{2}\,du\right)^{1/2}.$

Set $\delta=\kappa\Delta\log^{2}(\frac{e}{\Delta})$ for a well-chosen constant
$\kappa\geq 1$ to be specified in what follows, let
$U=[0,\delta)\cup(1-\delta,1]$, and observe that

$\displaystyle\begin{split}&\int_{0}^{1}\left(F_{\mu^{\theta}_{m}}^{-1}(u)-F_{\mu^{\theta}}^{-1}(u)\right)^{2}\,du\\\
&\leq\int_{\delta}^{1-\delta}\left(F_{\mu^{\theta}_{m}}^{-1}(u)-F_{\mu^{\theta}}^{-1}(u)\right)^{2}\,du+2\int_{U}\left(F_{\mu^{\theta}_{m}}^{-1}(u)\right)^{2}\,du+2\int_{U}\left(F_{\mu^{\theta}}^{-1}(u)\right)^{2}\,du\\\
&=(1)+(2)+(3).\end{split}$ (1.14)

Intuitively, (1.14) is sharp when $\Delta$ is small, as it is unrealistic to
expect cancellations between $F_{\mu^{\theta}_{m}}^{-1}(u)$ and
$F_{\mu^{\theta}}^{-1}(u)$ when $u\in U$: that range corresponds to the
“$\delta$-outliers” of $\mu^{\theta}$ and the $\delta m$ extremal values of
its empirical counterpart, respectively.

From here on the argument relies heavily on $\mu$’s log-concavity—and hence on
the log-concavity of each $\mu^{\theta}$.

Consider first the effect of the outliers, i.e., $(2)$ and $(3)$ in Equation
(1.14). Clearly,

$(3)\leq c_{0}(\kappa)\Delta\log^{4}\left(\frac{1}{\Delta}\right)$ (1.15)

because marginals of a log-concave measure exhibit a sub-exponential tail-
decay: setting $\gamma(u)=\min\\{u,1-u\\}$ for $u\in[0,1]$, it follows from
Borell’s Lemma (see, e.g., [2]) that for $u\in(0,1)$,

$\left|F_{\mu^{\theta}}^{-1}(u)\right|\leq
c_{1}\log\left(\frac{1}{\gamma(u)}\right).$

Next, it is standard to show that $(2)$ is equivalent to
$\frac{1}{m}\sum_{i=1}^{\delta m}(\left\langle
X_{i},\theta\right\rangle^{\ast})^{2}$, assuming without loss of generality
that $\delta m$ is an integer. Moreover, the behaviour of

$\displaystyle H_{s,m}=\sup_{\theta\in
S^{d-1}}\max_{|I|=s}\left(\frac{1}{m}\sum_{i\in I}\left\langle
X_{i},\theta\right\rangle^{2}\right)^{1/2}=\sup_{\theta\in
S^{d-1}}\left(\frac{1}{m}\sum_{i=1}^{s}(\left\langle
X_{i},\theta\right\rangle^{\ast})^{2}\right)^{1/2}$ (1.16)

has been studied extensively over the years in rather general situations (see,
e.g., [1, 26, 39]). In particular, when $X$ is isotropic and log-concave, the
estimate on (1.16) was established in [1] and also in [38].

######  Theorem 1.8.

There are constants $c_{1}$ and $c_{2}$ depending only on $\kappa$ such that
the following holds. Let $m\geq 2d$ and set $\Delta\geq d/m$. Then, with
probability at least $1-2\exp(-c_{2}\sqrt{\Delta
m}\log^{2}(\frac{1}{\Delta}))$,

$H_{\delta m,m}\leq c_{1}\sqrt{\Delta}\log^{2}\left(\frac{1}{\Delta}\right).$

While the estimates on $(2)$ and $(3)$ are either well-understood or trivial,
the key ingredient in the proof of Theorem 1.6 is the estimate on $(1)$:
_cancellations_ that occur in the interval $[0,1]\backslash U$. Those
cancellations are due to a significant generalization of the Dvoretzky-Kiefer-
Wolfowitz (DKW) inequality that is _scale sensitive_ and _holds uniformly in
$\theta$_. More accurately, we show that with high probability, uniformly in
$\theta\in S^{d-1}$ and for any $t\in\mathbb{R}$ satisfying that
$F_{\mu^{\theta}}(t)\in[\Delta,1-\Delta]$,

$\displaystyle\left|F_{\mu^{\theta}_{m}}(t)-F_{\mu^{\theta}}(t)\right|\leq\sqrt{\Delta\gamma(F_{\mu^{\theta}}(t))}\cdot\log\left(\frac{e}{\gamma(F_{\mu^{\theta}}(t))}\right),$
(1.17)

where once again, $\gamma(u)=\min\\{u,1-u\\}$. In particular, for
$u\in[\delta,1-\delta]$,

$\displaystyle
F_{\mu^{\theta}_{m}}^{-1}(u)\in\left[F_{\mu^{\theta}}^{-1}\left(u-2\sqrt{\Delta\gamma(u)}\log\left(\tfrac{e}{\gamma(u)}\right)\right),F_{\mu^{\theta}}^{-1}\left(u+2\sqrt{\Delta\gamma(u)}\log\left(\tfrac{e}{\gamma(u)}\right)\right)\right].$
(1.18)

The proofs of (1.17) and (1.18) can be found in Section 3.1.

Once (1.18) is established, one may invoke the fact that a log-concave measure
with variance 1 satisfies Cheeger’s isoperimetric inequality with an absolute
constant: there is an absolute constant $h>0$ such that for any $u\in(0,1)$
and any $\theta\in S^{d-1}$,

$\displaystyle\frac{d}{du}F_{\mu^{\theta}}^{-1}(u)\leq\frac{1}{h\gamma(u)};$

see [5, 16], and for the formulation used here, see [7]. By a first order
Taylor expansion and in the high probability event on which (1.18) holds,

$\displaystyle\int_{\delta}^{1-\delta}\left(F_{\mu^{\theta}_{m}}^{-1}(u)-F_{\mu^{\theta}}^{-1}(u)\right)^{2}\,du$
$\displaystyle\leq
c_{2}\int_{\delta}^{1-\delta}\left(\frac{\sqrt{\Delta\gamma(u)}\log(\frac{e}{\gamma(u)})}{h\gamma(u)}\right)^{2}\,du\sim\Delta\log^{3}\left(\frac{1}{\Delta}\right).$

Combining all these estimates it follows that

$\mathcal{SW}_{2}(\mu_{m},\mu)\leq
C\sqrt{\Delta}\log^{2}\left(\frac{1}{\Delta}\right),$

as claimed. ∎

Let us stress that this argument relies on log-concavity in a crucial way and
that the answer in the general case has to follow a completely different path.
Most notably, in the log-concave case $F_{\mu^{\theta}}^{-1}$ is
differentiable with a well-behaved derivative, but for a general measure
$F_{\mu^{\theta}}^{-1}$ need not even be continuous. In particular, the
pointwise control on $|F_{\mu^{\theta}_{m}}^{-1}-F_{\mu^{\theta}}^{-1}|$ that
can be established when $X$ is log-concave is simply false when it comes to an
arbitrary measure. Cancellations in the integral on $[\delta,1-\delta]$ happen
to be of a “global” nature, leading to a weaker bound, that nevertheless is
optimal in the context of Theorem 1.3.

We end this introduction with a word about _notation_. $\|\cdot\|_{2}$ is the
Euclidean norm and $\left\langle\cdot,\cdot\right\rangle$ is the standard
inner product—though in what follows we do not specify the (finite) dimension
of the underlying space. Throughout, $c,c_{0},c_{1},C,C_{0},C_{1},\dots$ are
absolute constants whose values may change from line to line. If a constant
$c$ depends on a parameter $a$, we write $c=c(a)$, and if $cA\leq B\leq CA$
for absolute constants $c$ and $C$, that is denoted by $A\sim B$. Finally, for
two independent random vectors $X$ and $Y$, $\mathbb{E}_{X}$ is the
expectation with respect to $X$; i.e., if $X$ is distributed according to
$\mu$ then $\mathbb{E}_{X}f(X,Y)=\int f(x,Y)\,\mu(dx)$.

##  2 Preliminary estimates and lower bounds

In what follows, $X$ is a centred, isotropic random vector in $\mathbb{R}^{d}$
that satisfies $L_{q}-L_{2}$ _norm equivalence_ with constant $L$ for some
$q\geq 4$. Hence,

$\displaystyle\|\left\langle X,\theta\right\rangle\|_{L_{q}}\leq
L\|\left\langle X,\theta\right\rangle\|_{L_{2}}=L\quad\text{ for every
}\theta\in S^{d-1}.$ (2.1)

Let $\mu$ be the probability measure endowed by $X$, and for $\theta\in
S^{d-1}$, $\mu^{\theta}$ is the marginal endowed by $\left\langle
X,\theta\right\rangle$. Thus, for $t>0$

$\mu^{\theta}((-t,t)^{c})=\mathbb{P}(|\left\langle X,\theta\right\rangle|\geq
t)\leq\frac{\mathbb{E}|\left\langle
X,\theta\right\rangle|^{q}}{t^{q}}\leq\frac{L^{q}}{t^{q}},$

and recalling that $\gamma(u)=\min\\{u,1-u\\}$, it follows that for every
$u\in(0,1)$

$\left|F_{\mu^{\theta}}^{-1}(u)\right|\leq\frac{L}{\gamma(u)^{1/q}}.$ (2.2)

Let us turn to several simple observations that play an instrumental role in
the proof of Theorem 1.3. We begin with the useful characterization of the
Wasserstein distance between measures on the real line mentioned previously.

######  Lemma 2.1.

For $\nu,\tau\in\mathcal{P}_{2}(\mathbb{R})$,

$\mathcal{W}_{2}(\nu,\tau)=\left(\int_{0}^{1}\left(F_{\nu}^{-1}(u)-F_{\tau}^{-1}(u)\right)^{2}\,du\right)^{1/2}.$
(2.3)

The proof of Lemma 2.1 can be found, for example, in [35, Theorem 2]. Let us
sketch the simple argument for the upper estimate. If $|\cdot|$ is the uniform
probability measure on $(0,1)$ and

$\Pi(A)=|\\{u\in(0,1):(F_{\nu}^{-1}(u),F_{\tau}^{-1}(u))\in A\\}|,$

then $\Pi$ is a coupling between $\nu$ and $\tau$. The $\mathcal{W}_{2}$
distance is the infimum over all such couplings and therefore,

$\mathcal{W}_{2}^{2}(\nu,\tau)\leq\int_{\mathbb{R}\times\mathbb{R}}(x-y)^{2}\,\Pi(dx,dy)=\int_{0}^{1}\left(F_{\nu}^{-1}(u)-F_{\tau}^{-1}(u)\right)^{2}\,du.$
∎

The next observation is equally straightforward: the (trivial) connection
between $\mathcal{SW}_{2}$ and $\rho_{d,m}=\sup_{\theta\in
S^{d-1}}|\|\Gamma\theta\|_{2}^{2}-1|$.

######  Lemma 2.2.

If $\mathcal{SW}_{2}\left(\mu_{m},\mu\right)\leq 1$ then $\rho_{d,m}\leq
3\mathcal{SW}_{2}\left(\mu_{m},\mu\right)$.

###### Proof.

By the isotropicity of $X$, for $\theta\in S^{d-1}$ it is evident that

$\displaystyle\|\Gamma\theta\|_{2}^{2}-1$
$\displaystyle=\int_{0}^{1}F^{-1}_{\mu^{\theta}_{m}}(u)^{2}\,du-\int_{0}^{1}F^{-1}_{\mu^{\theta}}(u)^{2}\,du$
$\displaystyle=\int_{0}^{1}\left(F^{-1}_{\mu^{\theta}_{m}}(u)-F^{-1}_{\mu^{\theta}}(u)\right)\left(F^{-1}_{\mu^{\theta}_{m}}(u)+F^{-1}_{\mu^{\theta}}(u)\right)\,du.$

The claim follows from the Cauchy-Schwartz inequality, (2.3) and the triangle
inequality. ∎

The final two observations focus on connections between the Wasserstein
distance and monotone ordering. Let $a^{\sharp}$ be the monotone non-
decreasing rearrangement of a vector $a\in\mathbb{R}^{m}$, and for $\theta\in
S^{d-1}$ and $1\leq i\leq m$, set
$\lambda^{\theta}_{i}=m\int_{(i-1)/m}^{i/m}F_{\mu^{\theta}}^{-1}(u)\,du$.

######  Lemma 2.3.

We have that

$\sup_{\theta\in S^{d-1}}\left(\frac{1}{m}\sum_{i=1}^{m}\left(\left\langle
X_{i},\theta\right\rangle^{\sharp}-\lambda^{\theta}_{i}\right)^{2}\right)^{1/2}\leq\mathcal{SW}_{2}(\mu_{m},\mu).$

###### Proof.

Note that for every $1\leq i\leq m$ and $u\in(\frac{i-1}{m},\frac{i}{m}]$,
$F_{\mu^{\theta}_{m}}^{-1}(u)=\left\langle
X_{i},\theta\right\rangle^{\sharp}$. Thus, by Jensen’s inequality and invoking
Lemma 2.1,

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}\left(\left\langle
X_{i},\theta\right\rangle^{\sharp}-\lambda^{\theta}_{i}\right)^{2}$
$\displaystyle\leq\sum_{i=1}^{m}\int_{(i-1)/m}^{i/m}\left(F_{\mu^{\theta}_{m}}^{-1}(u)-F_{\mu^{\theta}}^{-1}(u)\right)^{2}\,du=\mathcal{W}_{2}^{2}\left(\mu^{\theta}_{m},\mu^{\theta}\right).\qed$

###  2.1 Lower bounds on the Wasserstein distance

This section is devoted to showing that Theorem 1.3 and Theorem 1.6 are
optimal in a strong sense.

#### Estimates with constant probability

We begin with lower bounds on $\mathcal{SW}_{2}(\mu_{m},\mu)$ that hold with
constant probability, exhibiting that the dependence on $\Delta$ in Theorem
1.3 and Theorem 1.6 cannot be improved even if one is willing to accept much
weaker probability estimates.

######  Lemma 2.4.

Let $X$ be centred and isotropic, and set $0<\beta<1$ such that
$\mathbb{E}\|X\|_{2}\geq\beta\sqrt{d}$. Then with probability at least
$c_{0}(\beta)$,

$\mathcal{SW}_{2}(\mu_{m},\mu)\geq c_{1}(\beta)\sqrt{\frac{d}{m}}.$ (2.4)

Note that if $X$ is isotropic and log-concave then $\mathbb{E}\|X\|_{2}\geq
c\sqrt{d}$ for an absolute constant $c$. In particular, the dependence on
$\Delta$ in Theorem 1.6 cannot be improved (up to the logarithmic factor) even
in the constant probability regime.

The proof of Lemma 2.4 requires a standard observation that will be used again
in what follows.

Let $\tau$ be a centred probability measure on $\mathbb{R}$ and set $Y$ to be
distributed according to $\tau$. Let $(Y_{i})_{i=1}^{m}$ be independent copies
of $Y$ and put $\tau_{m}$ to be the corresponding empirical measure. Consider
an optimal coupling $\Pi$ of $\tau_{m}$ and $\tau$ in the $\mathcal{W}_{2}$
sense. Since $\tau$ is centred, it follows from the Cauchy-Schwarz inequality
that

$\left|\frac{1}{m}\sum_{i=1}^{m}Y_{i}\right|=\left|\int_{\mathbb{R}}x\,\tau_{m}(dx)\right|=\left|\int_{\mathbb{R}\times\mathbb{R}}(x-y)\,\Pi(dx,dy)\right|\leq\mathcal{W}_{2}(\tau_{m},\tau).$
(2.5)

###### Proof of Lemma 2.4.

By (2.5) applied to all the one-dimensional marginals of $X$,

$\left\|\frac{1}{m}\sum_{i=1}^{m}X_{i}\right\|_{2}\leq\mathcal{SW}_{2}(\mu_{m},\mu).$
(2.6)

In particular, to establish (2.4) it suffices to show that if
$\mathbb{E}\|X\|_{2}\geq\beta\sqrt{d}$, then with probability at least
$c_{0}(\beta)$

$\left\|\frac{1}{m}\sum_{i=1}^{m}X_{i}\right\|_{2}\geq
c_{1}(\beta)\sqrt{\frac{d}{m}}.$

To that end, note that by isotropicity, $\mathbb{E}\|X\|_{2}^{2}=d$. Invoking
the Paley-Zygmund inequality (see, e.g., [9]), there are constants $c_{2}$ and
$c_{3}$ that depend on $\beta$ for which

$\mathbb{P}\left(\|X\|_{2}\geq c_{2}\sqrt{d}\right)\geq c_{3}.$

A standard binomial estimate shows that there is a constant $c_{4}(\beta)$
such that with probability at least $1-2\exp(-c_{4}m)$,

$\left|\left\\{i:\|X_{i}\|_{2}\geq
c_{2}\sqrt{d}\right\\}\right|\geq\frac{c_{3}}{2}m,$

and by symmetrization and the Kahane-Khintchine inequality (see, e.g., [19]),

$\mathbb{E}\left\|\frac{1}{m}\sum_{i=1}^{m}X_{i}\right\|_{2}\geq
c_{5}\mathbb{E}_{X}\left(\frac{1}{m^{2}}\sum_{i=1}^{m}\|X_{i}\|_{2}^{2}\right)^{1/2}\geq
c_{6}(\beta)\sqrt{\frac{d}{m}}.\qed$

Next, let us establish the optimality of Theorem 1.3 by constructing an
isotropic random vector $X$ that satisfies $L_{4}-L_{2}$ norm equivalence and
with constant probability

$\mathcal{SW}_{2}(\mu_{m},\mu)\geq c\left(\frac{d}{m}\right)^{1/4}.$ (2.7)

In particular, setting $\Delta\sim d/m$, (2.7) implies that the term
$\Delta^{1/4}$ in Theorem 1.3 is the best one can hope for, even if one allows
a probability estimate of a constant rather than of $1-\exp(-c_{1}\Delta m)$.

######  Remark 2.5.

As it happens, the random vector $X$ we construct satisfies that with constant
probability,

$\sup_{\theta\in S^{d-1}}\left|\frac{1}{m}\sum_{i=1}^{m}\left\langle
X_{i},\theta\right\rangle^{2}-1\right|\leq
c_{2}\sqrt{\frac{d}{m}\log\left(\frac{em}{d}\right)},$ (2.8)

showing that there can be a substantial gap between
$\mathcal{SW}_{2}(\mu_{m},\mu)$ and $\rho_{d,m}$.

######  Example 2.6.

Let $\beta>0$ to be named in what follows. Set $W$ to be a random vector
distributed uniformly in $S^{d-1}$ and let $v$ be a real-valued random
variable that is independent of $W$ and takes the values $\beta\sqrt{d}$ with
probability $1-\frac{1}{2m}$ and $(md)^{1/4}$ with probability $\frac{1}{2m}$.

The wanted random vector is $X=vW$; it is rotation invariant, and for a well-
chosen $\beta\sim 1$ it is also isotropic. Moreover, it is straightforward to
verify that with that choice of $\beta$, $\sup_{\theta\in
S^{d-1}}\|\left\langle X,\theta\right\rangle\|_{L_{4}}\leq C$ for an absolute
constant $C$, implying that $X$ satisfies $L_{4}-L_{2}$ norm equivalence.

Let $\theta\in S^{d-1}$ and observe that with probability at least
$1-\frac{1}{2m}$, $\left\langle X,\theta\right\rangle\leq\beta\sqrt{d}$. Thus
$F^{-1}_{\mu^{\theta}}(u)\leq\beta\sqrt{d}$ for $u<1-\frac{1}{2m}$. On the
other hand, with constant probability,

$\sup_{\theta\in S^{d-1}}\max_{1\leq i\leq m}|\left\langle
X_{i},\theta\right\rangle|=\max_{1\leq i\leq m}\|X_{i}\|_{2}=(md)^{1/4},$

and on that event there is some $\theta$ such that
$F^{-1}_{\mu_{m}^{\theta}}(u)=(md)^{1/4}$ for $u>1-\frac{1}{m}$. Therefore, by
Lemma 2.1,

$\displaystyle\mathcal{W}_{2}^{2}\left(\mu_{m}^{\theta},\mu^{\theta}\right)\geq$
$\displaystyle\int_{1-1/m}^{1-1/2m}\left(F^{-1}_{\mu_{m}^{\theta}}(u)-F^{-1}_{\mu^{\theta}}(u)\right)^{2}\,du$
$\displaystyle\geq$
$\displaystyle\int_{1-1/m}^{1-1/2m}\left((md)^{1/4}-\beta\sqrt{d}\right)^{2}\,du\geq\left(\frac{d}{2m}\right)^{1/4},$

provided that $m\geq c(\beta)d$. Thus, $X$ satisfies (2.7) with constant
probability, as claimed.

Regarding (2.8), that follows immediately from Tikhomirov’s estimate from [39]
on the extremal singular values of random matrices with independent rows.
Indeed, $X$ satisfies $L_{4}-L_{2}$ norm equivalence and
$\|X\|_{2}\leq(md)^{1/4}$ almost surely. ∎

The random vector $X$ constructed in Example 2.6 might be considered
‘a-typical’. Next we turn to an example which shows that even for “nice”
random vectors, the best that one can hope for in Theorem 1.3 is an upper
bound of order $\Delta^{1/4}$ that holds with probability at least
$1-\exp(-c\Delta m)$.

#### The Bernoulli vector

Let $X$ be distributed uniformly in $\\{-1,1\\}^{d}$. In particular, $X$ is
isotropic and $L$-subgaussian for an absolute constant $L$. It is standard to
verify that for subgaussian random vectors, $\rho_{d,m}\leq c_{0}\sqrt{d/m}$
with probability at least $1-2\exp(-c_{1}m)$, and hence, Theorem 1.3 implies
that for such a random vector, with probability at least $1-\exp(-c_{2}\Delta
m)$,

$\mathcal{SW}_{2}(\mu_{m},\mu)\leq c_{3}\Delta^{1/4}.$

Here, we show that for the uniform distribution in $\\{-1,1\\}^{d}$,

$\mathcal{SW}_{2}(\mu_{m},\mu)\geq c_{4}\Delta^{1/4}$

with probability at least $c_{5}\exp(-c_{6}\Delta m)$.

As it happens, the reason for this lower bound is actually one dimensional. It
is caused by the behaviour of

$\nu=\frac{1}{2}(\delta_{-1}+\delta_{1}),$

corresponding to a marginal of $X$ in a coordinate direction.

######  Lemma 2.7.

There are absolute constants $c_{1},c_{2}$ and $c_{3}$ such that, for
$\Delta<1/4$ and $m\geq 4$, with probability $c_{1}\exp(-c_{2}\Delta m)$,

$\mathcal{W}_{2}(\nu_{m},\nu)\geq c_{3}\Delta^{1/4}.$

Lemma 2.7 can be established via a standard lower bound on the binomial
distribution and Lemma 2.1. For the sake of simplicity the argument we present
is based on an estimate due to Montgomery-Smith [30]. To formulate that fact,
denote by $x^{\ast}$ the monotone non-increasing rearrangement of
$(|x_{i}|)_{i=1}^{m}$.

######  Lemma 2.8.

There are absolute constants $c_{1},c_{2}$ and $c_{3}$ such that the following
holds. Let $(\varepsilon_{i})_{i=1}^{m}$ be distributed as $\nu^{\otimes m}$,
consider $x\in\mathbb{R}^{m}$ and set $0<u\leq m-2$. Then, with probability at
least $c_{1}\exp(-c_{2}u)$,

$\displaystyle\sum_{i=1}^{m}x_{i}\varepsilon_{i}\geq
c_{3}\left(\sum_{i=1}^{\lfloor
u\rfloor}x^{\ast}_{i}+\sqrt{u}\left(\sum_{i=\lfloor
u\rfloor+1}^{m}(x^{\ast}_{i})^{2}\right)^{1/2}\right).$ (2.9)

###### Proof of Lemma 2.7.

Let $\nu_{m}=\frac{1}{m}\sum_{i=1}^{m}\delta_{\varepsilon_{i}}$ and note that
for $x=(\frac{1}{m},...,\frac{1}{m})$ and $u=c_{0}\Delta m$ for an absolute
constant $c_{0}$, the RHS in (2.9) is at least $c_{1}\sqrt{\Delta}$. Moreover,
when (2.9) holds,

$F_{\nu_{m}}(-1)\leq\tfrac{1}{2}-c_{2}\sqrt{\Delta}.$

Hence, $F_{\nu_{m}}^{-1}(u)=1$ for $u\in(\frac{1}{2}-c_{2}\sqrt{\Delta},1]$,
but $F_{\nu}^{-1}(u)=-1$ for $u\in[0,\frac{1}{2}]$. Therefore,

$\int_{1/2-c_{2}\sqrt{\Delta}}^{1/2}\left(F_{\nu_{m}}^{-1}(u)-F_{\nu}^{-1}(u)\right)^{2}\,du=c_{2}\sqrt{\Delta}$

and the claim follows from Lemma 2.1. ∎

######  Remark 2.9.

By combining (2.5) and Lemma 2.8, it is straightforward to show that even
‘regular’ random vectors satisfy $\mathcal{SW}_{2}(\mu_{m},\mu)\geq
c_{1}\sqrt{\Delta}$ with probability at least $c_{2}\exp(-c_{3}\Delta m)$. In
particular, the estimate of $\sim\Delta^{1/2}$ is the best one can hope for
even when $m\gg d$.

##  3 Theorem 1.3 and Theorem 1.6 — Proofs

Recall that $q\geq 4$ and $X$ is a centred isotropic random vector in
$\mathbb{R}^{d}$ distributed according to $\mu$ that satisfies $L_{q}-L_{2}$
norm equivalence with a constant $L$. $\kappa\geq 1$ is a (large) absolute
constant that will be specified in what follows: assume that
$\Delta\leq(10\kappa)^{-2}$, set

$\displaystyle\delta$
$\displaystyle=\kappa\Delta\log^{2}\left(\frac{e}{\Delta}\right),$
$\displaystyle U$ $\displaystyle=[0,\delta)\cup(1-\delta,1],$
$\displaystyle\gamma(u)$ $\displaystyle=\min\\{u,1-u\\}\quad\text{for
}u\in[0,1];$

and observe that $\delta\leq\frac{1}{4}$.

Invoking (2.3) and the triangle inequality,

$\displaystyle\begin{split}\mathcal{W}_{2}\left(\mu^{\theta}_{m},\mu^{\theta}\right)&\leq\left(\int_{\delta}^{1-\delta}\left(F_{\mu^{\theta}_{m}}^{-1}(u)-F_{\mu^{\theta}}^{-1}(u)\right)^{2}\,du\right)^{1/2}+\left(\int_{U}F_{\mu^{\theta}_{m}}^{-1}(u)^{2}\,du\right)^{1/2}\\\
&\qquad+\left(\int_{U}F_{\mu^{\theta}}^{-1}(u)^{2}\,du\right)^{1/2}=(1)+(2)+(3).\end{split}$

The term $(3)$ can be bounded trivially using the tail-estimate (2.2). In
contrast, estimating $(2)$ is more subtle, and we defer that to Section 3.4.
The key estimate is on $(1)$. It is based on our multi-dimensional, scale
sensitive generalization of the Dvoretzky-Kiefer-Wolfowitz inequality: we show
in Section 3.1 that on a high probability event,

$F_{\mu^{\theta}_{m}}^{-1}(u)-F_{\mu^{\theta}}^{-1}(u)$

can be bounded (pointwise) using the (deterministic) difference

$\displaystyle
F_{\mu^{\theta}}^{-1}(\psi_{-}(u))-F_{\mu^{\theta}}^{-1}(\psi_{+}(u)),$ (3.1)

where $\psi_{\pm}$ are suitable perturbations of the identity. In particular,
the heart of the matter is to control the “stability” of
$F^{-1}_{\mu^{\theta}}$—showing that (3.1) has a small $L_{2}$ norm. It is
important to note that this small $L_{2}$ norm _does not_ follow from an
$L_{\infty}$ estimate on (3.1); the latter is true only under strong
regularity assumptions on $\mu$.

###  3.1 A generalization of the DKW inequality for linear functions

A key component in the proof of Theorem 1.3 is the following uniform estimate
on the deviation between the empirical and the true distribution functions for
each marginal $\mu^{\theta}$. Let

$\mathcal{U}=\left\\{\\{\left\langle\theta,\cdot\right\rangle\in
I\\}:\theta\in\mathbb{R}^{d},\ I\subset\mathbb{R}\ \text{is a generalized
interval}\right\\},$

where by “generalized interval” we mean an open/closed, half-open/closed
interval in $\mathbb{R}$, including rays.

######  Theorem 3.1.

There are absolute constants $c_{0},c_{1}$ such that the following holds. Let
$\Delta\leq 1$ and $m\geq c_{0}\frac{d}{\Delta}$. Then, with probability at
least $1-\exp(-c_{1}\Delta m)$, for every $A\in\mathcal{U}$ satisfying
$\mu(A)\geq\Delta$, we have that

$\left|\mu_{m}(A)-\mu(A)\right|\leq\sqrt{\Delta\mu(A)}\log\left(\frac{e}{\mu(A)}\right).$

######  Remark 3.2.

A version of Theorem 3.1 was proved in [24], with an error estimate of the
order $\sqrt{\Delta\mu(A)}$ (without a logarithmic factor) but with the
restriction that $\Delta\geq c\frac{d}{m}\log(\frac{em}{d})$. That restriction
results in a suboptimal estimate in Theorem 1.3, while the optimal one, at
least for $q>4$, can be derived from Theorem 3.1. We conjecture that the
logarithmic factor in Theorem 3.1 can be removed, but its removal does not
affect the estimate in Theorem 1.3 for $q>4$, nor will it eliminate the
logarithmic factor when $q=4$.

The proof of Theorem 3.1 is a simple outcome of Talagrand’s concentration
inequality for classes of uniformly bounded functions [37], applied to a class
of binary valued functions that has a finite $\mathrm{VC}$ dimension. For more
information on Talagrand’s inequality see [8], and detailed surveys on
$\mathrm{VC}$-classes can be found in [40].

######  Definition 3.3.

Let $\mathcal{H}$ be a class of subsets of $\Omega$. A set
$\\{x_{1},\dots,x_{\ell}\\}$ is _shattered_ by $\mathcal{H}$ if for every
$I\subset\\{1,\dots,\ell\\}$ there exists $A\in\mathcal{H}$ such that
$x_{i}\in A$ for $i\in I$ and $x_{i}\notin A$ for $i\notin I$. The _${\rm VC}$
-dimension_ of $\mathcal{H}$ is

${\rm
VC}(\mathcal{H})=\sup\left\\{\ell\in\mathbb{N}:\\{x_{1},\dots,x_{\ell}\\}\subset\Omega\text{
is shattered by }\mathcal{H}\right\\}.$

The following is an immediate corollary of Talagrand’s concentration
inequality, see, e.g., [8, 18].

######  Theorem 3.4.

There is an absolute constant $c$ such that the following holds. Let
$\mathcal{H}$ be a class of subsets of $\Omega$, put
$k=\mathrm{VC}(\mathcal{H})$ and set
$\sigma^{2}=\sigma^{2}(\mathcal{H})=\sup_{A\in\mathcal{H}}\mu(A)$. Then, for
every $t\geq 0$, with probability at least $1-\exp(-t)$,

$\sup_{A\in\mathcal{H}}|\mu_{m}(A)-\mu(A)|\leq
c\left(\sigma\sqrt{\frac{k}{m}\log\left(\frac{e}{\sigma}\right)}+\frac{k}{m}\log\left(\frac{e}{\sigma}\right)+\sigma\sqrt{\frac{t}{m}}+\frac{t}{m}\right).$

###### Proof of Theorem 3.1.

Let $\mu$ be a probability measure on $\mathbb{R}^{d}$. Using the notation
introduced previously, set $j\geq 0$ such that $2^{j}\Delta\leq 1$, and let

$\mathcal{U}_{j}=\left\\{A\in\mathcal{U}:\mu(A)\in[2^{j}\Delta,2^{j+1}\Delta)\right\\}.$

It is well-known that as a class of ‘slabs’ in $\mathbb{R}^{d}$, ${\rm
VC}(\mathcal{U})\leq c_{0}d$ for an absolute constant $c_{0}$ (see, e.g.,
[40]) and in particular $\mathrm{VC}(\mathcal{U}_{j})\leq c_{0}d$. Moreover,
$\sigma^{2}(\mathcal{U}_{j})\in[2^{j}\Delta,2^{j+1}\Delta]$, and by Theorem
3.4, for every $t\geq 0$, with probability at least $1-2\exp(-t)$,

$\displaystyle\sup_{A\in\mathcal{U}_{j}}|\mu_{m}(A)-\mu(A)|$
$\displaystyle\leq
c_{1}\left(\sqrt{2^{j+1}\Delta\frac{d}{m}\log\left(\frac{e}{2^{j}\Delta}\right)}+\frac{d}{m}\log\left(\frac{e}{2^{j}\Delta}\right)+\sqrt{2^{j+1}\Delta}\sqrt{\frac{t}{m}}+\frac{t}{m}\right).$

Set $t=c_{2}\Delta m\log(\frac{e}{2^{j}\Delta})$ and let $m\geq
c_{3}\frac{d}{\Delta}$. It is straightforward to verify that with probability
at least $1-2\exp(-c_{2}\Delta m\log(\frac{e}{2^{j}\Delta}))$,

$\displaystyle\sup_{A\in\mathcal{U}_{j}}|\mu_{m}(A)-\mu(A)|\leq\sqrt{\Delta
2^{j}\Delta}\log\left(\frac{e}{2^{j+1}\Delta}\right),$ (3.2)

which is the required estimate for sets in $\mathcal{U}_{j}$. In particular,
if $j_{\Delta}$ is the first integer such that $2^{j_{\Delta}}\Delta>1$, then
by the union bound with probability at least

$\displaystyle 1-\sum_{j=0}^{j_{\Delta}-1}2\exp\left(-c_{2}\Delta
m\log\left(\frac{e}{2^{j}\Delta}\right)\right)\geq 1-2\exp(-c_{4}\Delta m),$

(3.2) holds for each $0\leq j\leq j_{\Delta}-1$. ∎

An immediate outcome of Theorem 3.1 (applied to sets of the form
$\\{\left\langle\theta,\cdot\right\rangle\leq t\\}$ and
$\\{\left\langle\theta,\cdot\right\rangle>t\\}$) is the following.

######  Corollary 3.5.

There are absolute constants $c_{0},c_{1}$ such that the following holds. Let
$\Delta\leq 1$ and $m\geq c_{0}\frac{d}{\Delta}$. Then, with probability at
least $1-\exp(-c_{1}\Delta m)$, for every $\theta\in S^{d-1}$ and
$t\in\mathbb{R}$ satisfying that $F_{\mu^{\theta}}(t)\in[\Delta,1-\Delta]$, we
have that

$\displaystyle\left|F_{\mu^{\theta}_{m}}(t)-F_{\mu^{\theta}}(t)\right|\leq\sqrt{\Delta\gamma(F_{\mu^{\theta}}(t))}\cdot\log\left(\frac{e}{\gamma(F_{\mu^{\theta}}(t))}\right).$
(3.3)

For the remainder of the proof of Theorem 1.3, we shall assume that
$F_{\mu^{\theta}}$ is invertible. This assumption is only made to simplify
notation and holds without loss of generality. Indeed, one may always consider
$\nu$ distributed as $\sqrt{1-\beta^{2}}X+\beta G$ where $G$ is the standard
gaussian vector in $\mathbb{R}^{d}$ (independent of $X$) and $\beta$ is
arbitrarily small. In particular, $\nu$ is centred, isotropic, satisfies
$L_{q}-L_{2}$ norm equivalence with a constant $L+1$, and $F_{\nu^{\theta}}$
is invertible for every $\theta\in S^{d-1}$. Thus, one may replace the RHS in
(3.3) by
$\sqrt{2\Delta\gamma(F_{\nu^{\theta}}(t))}\log(\frac{e}{\gamma(F_{\nu^{\theta}}(t))})$,
and $F_{\mu^{\theta}}$ by $F_{\nu^{\theta}}$ in all of the following
arguments, finally taking $\beta$ to 0.

By Lemma 2.1, the key is to control the difference between empirical and true
_inverse_ distribution functions. To that end, consider the two functions
$\psi_{+},\psi_{-}\colon[0,1]\to\mathbb{R}$ defined by

$\psi_{\pm}(u)=u\pm
2\sqrt{\Delta\gamma(u)}\log\left(\frac{e}{\gamma(u)}\right).$

$\psi_{\pm}$ are perturbations of the identity, in a sense described in the
next lemma.

######  Lemma 3.6.

There is an absolute constant $\kappa$ such that the following hold. Let
$\delta=\kappa\Delta\log^{2}(\frac{e}{\Delta})$. Then for
$u\in[\delta,1-\delta]$ we have

$(1)$ $\psi_{\pm}(u)\in[\Delta,1-\Delta]$,

$(2)$ $|\psi_{\pm}(u)-u|\leq\frac{1}{10}\cdot\gamma(u)$,

$(3)$ $\psi_{\pm}$ are absolutely continuous, strictly increasing on
$[\delta,1-\delta]$, and their derivatives satisfy

$\left|\psi_{\pm}^{\prime}(u)-1\right|\leq
3\sqrt{\frac{\Delta}{\gamma(u)}}\log\left(\frac{e}{\gamma(u)}\right).$

###### Proof.

We only consider the case $u\in[\delta,\frac{1}{2}]$ and thus $\gamma(u)=u$;
the argument in the case $u\in[\frac{1}{2},1-\delta]$ is identical and is
omitted.

Note that if $\kappa\geq 1$ then $u\geq\Delta$ and in particular
$\log\frac{e}{u}\leq\log\frac{e}{\Delta}$. Moreover, for
$u\geq\delta=\kappa\Delta\log^{2}(\frac{e}{\Delta})$ we have that $\Delta\leq
u/\kappa\log^{2}(\frac{e}{\Delta})$. Hence,

$\displaystyle|\psi_{\pm}(u)-u|$ $\displaystyle=2\sqrt{\Delta
u}\log\left(\frac{e}{u}\right)$ $\displaystyle\leq
2\frac{u}{\sqrt{\kappa}\log(\frac{e}{\Delta})}\log\left(\frac{e}{\Delta}\right)\leq\frac{2u}{\sqrt{\kappa}},$

and (2) follows if $\kappa\geq 400$, while (1) is an immediate consequence of
(2) and the fact that $\delta\geq 2\Delta$ if $\kappa\geq 2$.

Turning to (3), it is evident that $\psi_{\pm}$ are absolutely continuous and
satisfy the claimed bound on their derivative. The fact that $\psi_{\pm}$ are
strictly increasing on $[\delta,\frac{1}{2}]$ follows because $\Delta\leq
u/\kappa\log^{2}(\frac{e}{\Delta})$, and if $\kappa\geq 36$ then

$\left|\psi_{\pm}^{\prime}(u)-1\right|\leq
3\sqrt{\frac{\Delta}{u}}\log\left(\frac{e}{u}\right)\leq\frac{3}{\sqrt{\kappa}}\leq\frac{1}{2}.\qed$

From now on, fix $\kappa$ as in Lemma 3.6. By combining Corollary 3.5 and
Lemma 3.6, the following holds.

######  Lemma 3.7.

Fix a realization $(X_{i})_{i=1}^{m}$ for which (3.3) holds. Then, for every
$\theta\in S^{d-1}$ and every $u\in[\delta,1-\delta]$,

$F_{\mu^{\theta}_{m}}^{-1}(u)\in\left[F_{\mu^{\theta}}^{-1}\left(\psi_{-}(u)\right),F_{\mu^{\theta}}^{-1}\left(\psi_{+}(u)\right)\right].$

###### Proof.

We only consider the case $u\in[\delta,\frac{1}{2}]$, and in particular
$\gamma(u)=u$. The analysis when $u\in(\frac{1}{2},1-\delta]$ is identical and
is omitted.

First, let us show that $t_{u}=F_{\mu^{\theta}}^{-1}(\psi_{+}(u))$ satisfies
that

$\displaystyle F_{\mu^{\theta}_{m}}(t_{u})\geq u.$ (3.4)

Note that if (3.4) holds, then by the definition of the (right-)inverse,
$F_{\mu^{\theta}_{m}}^{-1}(u)\leq F_{\mu^{\theta}}^{-1}(\psi_{+}(u))$.

To prove (3.4), consider $u\in[\delta,\frac{1}{2}]$. Thus,
$F_{\mu^{\theta}}(t_{u})=\psi_{+}(u)$, and by Lemma 3.6
$F_{\mu_{\theta}}(t_{u})\in[\Delta,1-\Delta]$. In particular, by Corollary 3.5

$F_{\mu^{\theta}_{m}}(t_{u})\geq
F_{\mu^{\theta}}(t_{u})-\sqrt{\Delta\gamma(F_{\mu^{\theta}}(t_{u}))}\log\left(\frac{e}{\gamma(F_{\mu^{\theta}}(t_{u}))}\right).$

Applying Lemma 3.6 once again,
$\frac{3}{4}u\leq\gamma(F_{\mu^{\theta}}(t_{u}))\leq\frac{5}{4}u$ and
therefore

$\displaystyle F_{\mu^{\theta}_{m}}(t_{u})$ $\displaystyle\geq u+2\sqrt{\Delta
u}\log\left(\frac{e}{u}\right)-\sqrt{\Delta\tfrac{5}{4}u}\log\left(\frac{4e}{3u}\right)$
$\displaystyle=u+\sqrt{\Delta
u}\left(2\log\left(\frac{e}{u}\right)-\sqrt{\tfrac{5}{4}}\log\left(\frac{4e}{3u}\right)\right).$

Now it is straightforward to verify that $F_{\mu^{\theta}}(t_{u})\geq u$, as
claimed.

Finally, using the same argument, if
$t_{u}=F_{\mu^{\theta}}^{-1}(\psi_{-}(u))$, then

$F_{\mu^{\theta}_{m}}(t_{u})<u$

and therefore $F_{\mu^{\theta}_{m}}^{-1}(u)\geq
F_{\mu^{\theta}}^{-1}(\psi_{-}(u))$. ∎

By Lemma 3.7 and the monotonicity of $F_{\mu^{\theta}}^{-1}$, we immediately
have the following.

######  Corollary 3.8.

Fix a realization $(X_{i})_{i=1}^{m}$ that satisfies (3.3). Then, for every
$\theta\in S^{d-1}$,

$\displaystyle\int_{\delta}^{1-\delta}\left(F_{\mu^{\theta}_{m}}^{-1}(u)-F_{\mu^{\theta}}^{-1}(u)\right)^{2}\,du$
$\displaystyle\leq\int_{\delta}^{1-\delta}\left(F_{\mu^{\theta}}^{-1}\left(\psi_{+}(u)\right)-F_{\mu^{\theta}}^{-1}\left(\psi_{-}(u)\right)\right)^{2}\,du.$

######  Remark 3.9.

It is worthwhile to note once again that the RHS in Corollary 3.8 depends only
on $F_{\mu^{\theta}}$ and not on $F_{\mu^{\theta}_{m}}$.

The analysis of

$\int_{\delta}^{1-\delta}\left(F_{\mu^{\theta}}^{-1}\left(\psi_{+}(u)\right)-F_{\mu^{\theta}}^{-1}\left(\psi_{-}(u)\right)\right)^{2}\,du$

is the focus of the next section.

###  3.2 A global modulus of continuity of $F_{\mu^{\theta}}^{-1}$

Throughout this section we consider a distribution function $F$ of a symmetric
random variable, and in particular $F(0)=\frac{1}{2}$. The formulations and
proofs for general random variables require only trivial changes and are
omitted for the sake of a simpler presentation.

Once again, we may and do assume without loss of generality that $F$ is
invertible, and that for some $q\geq 4$ and every $t\geq 1$,

$\displaystyle F(-t)\leq\frac{L^{q}}{2t^{q}}.$ (3.5)

Before formulating the main estimate of this section, let us introduce some
notation. Set $\mathrm{id}\colon\mathbb{R}\to\mathbb{R}$ to be the identity
function, and denote the derivative of an absolutely continuous function
$\psi\colon\mathbb{R}\to\mathbb{R}$ by $\psi^{\prime}$. For $q\geq 4$, let

$r=1+\frac{q}{2q-4},$

and recall that $\delta=\kappa\Delta\log^{2}(\frac{e}{\Delta})$ and
$\gamma(u)=\min\\{u,1-u\\}$. Since $\Delta\leq(10\kappa)^{-2}$ we have that
$\delta\leq\frac{1}{4}$.

######  Proposition 3.10.

Let

$\psi\colon[\delta,1-\delta]\to[0,1]$

be an absolutely continuous, strictly increasing function that satisfies
$|\psi-\mathrm{id}|\leq\frac{1}{2}\gamma(\cdot)$, and for which either
$\psi\geq\mathrm{id}$ or $\psi\leq\mathrm{id}$. Then there is a constant
$c=c(\kappa,q)$ such that

$\displaystyle\int_{\delta}^{1-\delta}\left(F^{-1}(u)-F^{-1}(\psi(u))\right)^{2}\,du$
$\displaystyle\leq
c\begin{cases}\sqrt{\Delta}+\left|\psi^{-1}\left(\tfrac{1}{2}\right)-\tfrac{1}{2}\right|+\left(\int_{\delta}^{1-\delta}|\psi^{\prime}(u)-1|^{r}\,du\right)^{1/r}&\text{if
}q>4,\\\ \\\
\sqrt{\Delta}\log\frac{1}{\Delta}+\left|\psi^{-1}\left(\tfrac{1}{2}\right)-\tfrac{1}{2}\right|+\sqrt{\log\frac{1}{\Delta}}\left(\int_{\delta}^{1-\delta}|\psi^{\prime}(u)-1|^{2}\,du\right)^{1/2}&\text{if
}q=4.\end{cases}$

Proposition 3.10 replaces the key part of the argument that was presented in
Section 1.2 and which was based on the assumption that $F^{-1}$ has a well
behaved modulus of continuity. That assumption allowed one to control
$|F^{-1}(u)-F^{-1}(\psi(u))|$ in terms of $|u-\psi(u)|$, but unfortunately, it
is useless in the general case. Instead, one may write

$\displaystyle\int_{\delta}^{1-\delta}\left(F^{-1}(u)-F^{-1}(\psi(u))\right)^{2}\,du$
$\displaystyle=\int_{\delta}^{1-\delta}F^{-1}(u)^{2}\,du+\int_{\delta}^{1-\delta}F^{-1}(\psi(u))^{2}\,du-2\int_{\delta}^{1-\delta}F^{-1}(u)F^{-1}(\psi(u))\,du,$

and show that all three integrals are close to each other. The details of the
proof are presented in Lemma 3.11 and Lemma 3.12, but intuitively the reason
that the three integrals are close is that $\psi$ is a perturbation of the
identity. As a result, the second integral should be close to the first one.
Moreover, if $u$ is sufficiently far away from the point of symmetry
($F(0)=\frac{1}{2}$), the terms $F^{-1}(u)$ and $F^{-1}(\psi(u))$ have the
same sign; thus, by monotonicity, their product is sandwiched between
$F^{-1}(u)^{2}$ and $F^{-1}(\psi(u))^{2}$.

The formal proof is also based on the tail-estimate of $F$, namely that

$\displaystyle\left|F^{-1}(u)\right|\leq\frac{L}{\gamma(u)^{1/q}}\quad\text{for
}u\in(0,1),$ (3.6)

which is an immediate consequence of (3.5).

######  Lemma 3.11.

There is a constant $c=c(\kappa,q,L)$ such that

$\displaystyle\left|\int_{\delta}^{1-\delta}F^{-1}(\psi(u))^{2}\,du-\int_{\delta}^{1-\delta}F^{-1}(u)^{2}\,du\right|$
$\displaystyle\leq
c\begin{cases}\sqrt{\Delta}+\left(\int_{\delta}^{1-\delta}|\psi^{\prime}(u)-1|^{r}\,du\right)^{1/r}&\text{if
}q>4,\\\ \\\
\sqrt{\Delta}\log\frac{1}{\Delta}+\sqrt{\log\frac{1}{\Delta}}\left(\int_{\delta}^{1-\delta}|\psi^{\prime}(u)-1|^{2}\,du\right)^{1/2}&\text{if
}q=4,\end{cases}$

where, as always, $r=1+\frac{q}{2q-4}$.

###### Proof.

We only present the case $\psi\geq\mathrm{id}$ and $q>4$. The case
$\psi\leq\mathrm{id}$ follows from an identical argument to the one presented
here, while the case $q=4$ requires only simple modifications.

By a change of variables $u\leftrightarrow\psi(u)$,

$\displaystyle\int_{\delta}^{1-\delta}F^{-1}(\psi(u))^{2}\,du$
$\displaystyle=\int_{\delta}^{1-\delta}F^{-1}(\psi(u))^{2}\psi^{\prime}(u)\,du-\int_{\delta}^{1-\delta}F^{-1}(\psi(u))^{2}(\psi^{\prime}(u)-1)\,du$
$\displaystyle=\int_{\psi(\delta)}^{\psi(1-\delta)}F^{-1}(v)^{2}\,dv-\int_{\delta}^{1-\delta}F^{-1}(\psi(u))^{2}(\psi^{\prime}(u)-1)\,du=A+B.$

First, observe that $A$ is close to
$\int_{\delta}^{1-\delta}F^{-1}(u)^{2}\,du$. Indeed, since
$|\psi-\mathrm{id}|\leq\frac{1}{2}\gamma$ we have that

$\psi(\delta)\in\left[\delta,2\delta\right]\quad\text{and}\quad\psi(1-\delta)\in\left[1-\delta,1-\tfrac{1}{2}\delta\right].$

Hence, there is a constant $c_{1}=c_{1}(\kappa,q,L)$ such that

$\displaystyle\left|A-\int_{\delta}^{1-\delta}F^{-1}(v)^{2}\,dv\right|$
$\displaystyle\leq\left(\int_{\delta}^{2\delta}+\int_{1-\delta}^{1-\delta/2}\right)F^{-1}(v)^{2}\,dv\leq
c_{1}\sqrt{\Delta}$

where the last inequality follows from the tail-estimate (3.6), using that
$q>4$.

Second, to estimate $B$, apply Hölder’s inequality (with exponent $r$)

$\displaystyle B$
$\displaystyle\leq\left(\int_{\delta}^{1-\delta}|F^{-1}(\psi(u))|^{2r^{\prime}}\,du\right)^{1/r^{\prime}}\left(\int_{\delta}^{1-\delta}|\psi^{\prime}(u)-1|^{r}\,du\right)^{1/r}=B_{1}\cdot
B_{2}.$

To complete the proof it suffices to show that $B_{1}\leq c_{1}(q,L)$. To that
end, note that $|\psi-\rm id|\leq\frac{1}{2}\gamma$. Thus, by the tail-
estimate (3.6) there is an absolute constant $c_{2}$ such that and any
$u\in[\delta,1-\delta]$,

$\left|F^{-1}(\psi(u))\right|\leq\frac{c_{2}L}{\gamma(u)^{1/q}}.$

Finally, with the choice of $r$ we have that $2r^{\prime}/q<1$; hence
$\gamma(\cdot)^{-2r^{\prime}/q}$ is integrable in $(0,1)$ and $B\leq
c_{1}(q,L)$. ∎

######  Lemma 3.12.

There is a constant $c=c(\kappa,q,L)$ such that

$\displaystyle\left|\int_{\delta}^{1-\delta}F^{-1}(u)F^{-1}(\psi(u))\,du-\int_{\delta}^{1-\delta}F^{-1}(u)^{2}\,du\right|$
$\displaystyle\leq
c\begin{cases}\sqrt{\Delta}+\left|\psi^{-1}(\tfrac{1}{2})-\tfrac{1}{2}\right|+\left(\int_{\delta}^{1-\delta}|\psi^{\prime}(u)-1|^{r}\,du\right)^{1/r}&\text{if
}q>4,\\\ \\\
\sqrt{\Delta}\log\frac{1}{\Delta}+\left|\psi^{-1}(\tfrac{1}{2})-\tfrac{1}{2}\right|+\sqrt{\log\frac{1}{\Delta}}\left(\int_{\delta}^{1-\delta}|\psi^{\prime}(u)-1|^{2}\,du\right)^{1/2}&\text{if
}q=4.\end{cases}$

###### Proof.

Once again, we only present the proof in the case $\psi\geq\rm id$ and $q>4$.
The other cases follow a similar path and are omitted.

If $\psi\geq\rm id$ then $\psi^{-1}(\frac{1}{2})\leq\frac{1}{2}$, and since
$|\psi-\mathrm{id}|\leq\frac{1}{2}\rm{id}$ then
$\psi^{-1}(\frac{1}{2})\geq\frac{1}{4}\geq\delta$. Now set

$\displaystyle\int_{\delta}^{1-\delta}F^{-1}(u)F^{-1}(\psi(u))\,du$
$\displaystyle=\left(\int_{\delta}^{\psi^{-1}(1/2)}+\int_{\psi^{-1}(1/2)}^{1/2}+\int_{1/2}^{1-\delta}\right)F^{-1}(u)F^{-1}(\psi(u))\,du$
$\displaystyle=A+B+C.$

The range of integration of $B$ is contained in $[\frac{1}{4},\frac{1}{2}]$.
By the tail-estimate (3.6), there is an absolute constant $c_{1}$ such that
for $u\in[\frac{1}{4},\frac{1}{2}]$, $|F^{-1}(u)|\leq c_{1}L$; thus
$B\leq(c_{1}L)^{2}|\psi^{-1}(\tfrac{1}{2})-\tfrac{1}{2}|$.

Turning to $A$, let us show that

$\displaystyle\begin{split}\left|A-\int_{\delta}^{1/2}F^{-1}(u)^{2}\,du\right|&\leq
c_{2}\left(\sqrt{\Delta}+\left|\psi^{-1}\left(\tfrac{1}{2}\right)-\tfrac{1}{2}\right|+\left(\int_{\delta}^{1-\delta}|\psi^{\prime}(u)-1|^{r}\,du\right)^{1/r}\right)\end{split}$
(3.7)

for a constant $c_{2}=c_{2}(\kappa,q,L)$.

Note that $F(\frac{1}{2})=0$ since the underlying random variable is
symmetric. Thus, by the monotonicity of $F^{-1}$ and recalling that
$\psi\geq\mathrm{id}$,

$F^{-1}(u)\leq F^{-1}(\psi(u))\leq 0\quad\text{for
}u\in\left[\delta,\psi^{-1}(\tfrac{1}{2})\right].$

Setting

$\displaystyle A_{-}$
$\displaystyle=\int_{\delta}^{\psi^{-1}(1/2)}F^{-1}(\psi(u))^{2}\,du\quad\text{and}$
$\displaystyle A_{+}$
$\displaystyle=\int_{\delta}^{\psi^{-1}(1/2)}F^{-1}(u)^{2}\,du,$

it is evident that $A\in[A_{-},A_{+}]$. Therefore, it suffices to show that
$A_{-}$ and $A_{+}$ are both sufficiently close to
$\int_{\delta}^{1/2}F^{-1}(u)^{2}\,du$.

Using once again that $|F^{-1}(u)|\leq c_{1}L$ for
$u\in[\psi^{-1}(\frac{1}{2}),\frac{1}{2}]$, it is evident that

$\left|A_{+}-\int_{\delta}^{1/2}F^{-1}(u)^{2}\,du\right|\leq(c_{1}L)^{2}\left|\psi^{-1}\left(\tfrac{1}{2}\right)-\tfrac{1}{2}\right|.$

As for $A_{-}$, one may follow the same argument as used in the proof of Lemma
3.11—a change of variables, Hölder’s inequality, and invoking (3.6)—to show
that

$\displaystyle\left|A_{-}-\int_{\delta}^{1/2}F^{-1}(u)^{2}\,du\right|\leq
c_{4}\left(\sqrt{\Delta}+\left(\int_{\delta}^{1-\delta}|\psi^{\prime}(u)-1|^{r}\,du\right)^{1/r}\right)$

for a constant $c_{4}=c_{4}(\kappa,q,L)$. This proves (3.7)

Finally, an identical argument can be used to show that

$\displaystyle\left|C-\int_{1/2}^{1-\delta}F^{-1}(u)^{2}\,du\right|$
$\displaystyle\leq
c_{5}\left(\sqrt{\Delta}+\left|\psi^{-1}\left(\tfrac{1}{2}\right)-\tfrac{1}{2}\right|+\left(\int_{\delta}^{1-\delta}|\psi^{\prime}(u)-1|^{r}\,du\right)^{1/r}\right)$

for a constant $c_{5}=c_{5}(\kappa,q,L)$, completing the proof. ∎

###  3.3 The deterministic estimate

Recall that

$\psi_{\pm}(u)=u\pm
2\sqrt{\Delta\gamma(u)}\log\left(\frac{e}{\gamma(u)}\right).$

Thanks to Corollary 3.8, it suffices to prove the following:

######  Lemma 3.13.

There exists an absolute constant $\kappa$ and a constant $c(\kappa,q,L)$ such
that

$\int_{\delta}^{1-\delta}\left(F_{\mu^{\theta}}^{-1}\left(\psi_{-}(u)\right)-F_{\mu^{\theta}}^{-1}\left(\psi_{+}(u)\right)\right)^{2}\,du\leq
c\begin{cases}\sqrt{\Delta}&\text{if }q>4,\\\ \\\
\sqrt{\Delta}\log^{2}\frac{1}{\Delta}&\text{if }q=4.\end{cases}$

Again, we shall assume for the sake of simplicity that each $F_{\mu^{\theta}}$
is symmetric and without loss of generality that it is invertible. The
argument is based on applying Proposition 3.10 to $F=F_{\mu^{\theta}}$ and the
monotone functions $\psi_{+}$ and $\psi_{-}$.

###### Proof.

Clearly, $F$ falls within the scope of Proposition 3.10. Moreover
$\psi_{+}\geq\rm id$ and $\psi_{-}\leq\rm id$, and if $\kappa$ is as in Lemma
3.6, then by that lemma $\psi_{\pm}$ satisfy the remaining conditions in
Proposition 3.10. Hence, for the choice $r=1+\frac{q}{2q-4}$, there is a
constant $c_{1}=c_{1}(\kappa,q,L)$ such that

$\displaystyle\int_{\delta}^{1-\delta}\left(F_{\mu^{\theta}}^{-1}\left(\psi_{\pm}(u)\right)-F_{\mu^{\theta}}^{-1}\left(u\right)\right)^{2}\,du$
$\displaystyle\leq
c_{1}\begin{cases}\sqrt{\Delta}+\left|\psi^{-1}_{\pm}\left(\tfrac{1}{2}\right)-\tfrac{1}{2}\right|+\left(\int_{\delta}^{1-\delta}|\psi_{\pm}^{\prime}(u)-1|^{r}\,du\right)^{1/r}&\text{if
}q>4,\\\ \\\
\sqrt{\Delta}\log\frac{1}{\Delta}+\left|\psi_{\pm}^{-1}\left(\tfrac{1}{2}\right)-\tfrac{1}{2}\right|+\sqrt{\log\frac{1}{\Delta}}\left(\int_{\delta}^{1-\delta}|\psi_{\pm}^{\prime}(u)-1|^{2}\,du\right)^{1/2}&\text{if
}q=4.\end{cases}$

Clearly $|\psi_{\pm}^{-1}(\frac{1}{2})-\frac{1}{2}|\leq 10\sqrt{\Delta}$, and
by Lemma 3.6

$\left|\psi^{\prime}_{\pm}(u)-1\right|\leq
3\sqrt{\frac{\Delta}{\gamma(u)}}\log\left(\frac{e}{\gamma(u)}\right).$

Thus

$\left(\int_{\delta}^{1-\delta}\left|\psi^{\prime}_{\pm}(u)-1\right|^{r}\,du\right)^{1/r}\leq
c_{2}\begin{cases}\sqrt{\Delta}&\text{if }q>4,\\\
\sqrt{\Delta}\log^{3/2}\frac{1}{\Delta}&\text{if }q=4,\end{cases}$

for a suitable constant $c_{2}=c_{2}(\kappa,q)$. The proof is completed by an
application of the $L_{2}$ triangle inequality. ∎

###  3.4 The empirical tail integrals

The last component needed in the proofs of Theorem 1.3 and 1.6 is an estimate
on

$\displaystyle\sup_{\theta\in
S^{d-1}}\left(\int_{U}\left(F_{\mu^{\theta}_{m}}^{-1}(u)\right)^{2}\,du\right)^{1/2}$
(3.8)

where $U=[0,\delta)\cup(1-\delta,1]$.

We begin with a general estimate in terms of $\rho_{d,m}=\sup_{\theta\in
S^{d-1}}|\|\Gamma\theta\|_{2}^{2}-1|$ that suffices for the proof of Theorem
1.3.

######  Lemma 3.14.

There are absolute constants $\kappa,c_{0},c_{1}$ and a constant
$c_{2}=c_{2}(\kappa,q,L)$ such that the following holds. If $m\geq
c_{0}\frac{d}{\Delta}$, then with probability at least $1-\exp(-c_{1}\Delta
m)$,

$\displaystyle\sup_{\theta\in
S^{d-1}}\left(\int_{U}\left(F_{\mu^{\theta}_{m}}^{-1}(u)\right)^{2}\,du\right)^{1/2}$
$\displaystyle\leq c_{2}\begin{cases}\rho_{d,m}^{1/2}+\Delta^{1/4}&\text{if
}q>4,\\\ \\\ \rho_{d,m}^{1/2}+\Delta^{1/4}\log\frac{1}{\Delta}&\text{if
}q=4.\end{cases}$

###### Proof.

Fix $\theta\in S^{d-1}$ and set

$\displaystyle A_{\theta}$
$\displaystyle=\int_{0}^{1}F_{\mu^{\theta}_{m}}^{-1}(u)^{2}\,du-\int_{0}^{1}F_{\mu^{\theta}}^{-1}(u)^{2}\,du,$
$\displaystyle B_{\theta}$
$\displaystyle=\int_{\delta}^{1-\delta}F_{\mu^{\theta}}^{-1}(u)^{2}\,du-\int_{\delta}^{1-\delta}F_{\mu^{\theta}_{m}}^{-1}(u)^{2}\,du.$

Thus

$\displaystyle\int_{U}F_{\mu^{\theta}_{m}}^{-1}(u)^{2}\,du$
$\displaystyle=\int_{U}F_{\mu^{\theta}}^{-1}(u)^{2}\,du+A_{\theta}+B_{\theta}.$

By isotropicity, $A_{\theta}=\|\Gamma\theta\|_{2}^{2}-1$, and in particular
$\sup_{\theta\in S^{d-1}}|A_{\theta}|\leq\rho_{d,m}$. Moreover, by (3.6),

$\int_{U}F_{\mu^{\theta}}^{-1}(u)^{2}\,du\leq
2\int_{0}^{\delta}\frac{L^{2}}{u^{2/q}}\,du\leq
c_{1}\begin{cases}\sqrt{\Delta}&\text{if }q>4,\\\
\sqrt{\Delta}\log\frac{1}{\Delta}&\text{if }q=4,\end{cases}$

for a constant $c_{1}=c_{1}(\kappa,q,L)$.

As for $B_{\theta}$, using the estimates from Section 3.2 and Section 3.3 one
may verify that with probability at least $1-\exp(-c_{2}\Delta m)$,

$\displaystyle\sup_{\theta\in S^{d-1}}|B_{\theta}|\leq
c_{3}\begin{cases}\sqrt{\Delta}&\text{if }q>4,\\\
\sqrt{\Delta}\log^{2}\frac{1}{\Delta}&\text{if }q=4,\end{cases}$ (3.9)

for a constant $c_{3}=c_{3}(\kappa,q,L)$. ∎

Lemma 3.14 implies that if $\rho_{d,m}\leq\sqrt{\Delta}$ then (3.8) is (at
most) of order $\Delta^{1/4}$—up to a logarithmic factor. While this estimate
is sufficient for the proof of Theorem 1.3, it is not enough when the goal is
to obtain an upper bound of $\Delta^{1/2}$— when such an estimate is possible
as in Theorem 1.6.

That calls for a more careful analysis of (3.8), and to that end, let us re-
write (3.8) in a more standard form.

######  Definition 3.15.

For $1\leq s\leq m$, let

$H_{s,m}=\sup_{\theta\in S^{d-1}}\max_{|I|=s}\left(\frac{1}{m}\sum_{i\in
I}\left\langle X_{i},\theta\right\rangle^{2}\right)^{1/2}.$

Thus, $\sqrt{m}H_{s,m}$ is the Euclidean norm of the largest $s$ coordinates
of $(|\left\langle X_{i},\theta\right\rangle|)_{i=1}^{m}$ taken in the ‘worst’
direction $\theta$.

It is straightforward to verify that (3.8) is equivalent to $H_{\delta m,m}$.
Also, sharp estimates on $H_{s,m}$ have been established as part of the study
of $\rho_{d,m}$, (see, e.g., [1, 4, 26, 39]). Let us outline two such cases:

######  Example 3.16.

If $X$ is $L$-subgaussian, then there are constants $c_{1},c_{2}$ depending
only on $L$ such that, with probability at least $1-2\exp(-c_{1}s\log(em/s))$,

$\displaystyle H_{s,m}\leq
c_{2}\left(\sqrt{\frac{d}{m}}+\sqrt{\frac{s}{m}\log\left(\frac{em}{s}\right)}\right).$

The proof of Example 3.16 is standard and follows from a net argument and
individual subgaussian tail-decay.

######  Example 3.17.

If $X$ is a $\psi_{1}$ random vector (that is, it satisfies $L_{q}-L_{2}$ norm
equivalence with constant $qL$ for every $q\geq 2$), then there are constants
$c_{1},c_{2}$ depending on $L$, such that with probability at least
$1-2\exp(-c_{1}\sqrt{s}\log(em/s))$,

$H_{s,m}\leq c_{2}\left(\max_{1\leq i\leq
m}\frac{\|X_{i}\|_{2}}{\sqrt{m}}+\sqrt{\frac{s}{m}}\log\left(\frac{em}{s}\right)\right).$

Example 3.17 was shown established [1], with a minor (but from our perspective
important) restriction: an upper bound on $m$ has a function of $d$. This
restriction was later removed in [38], see Theorem 11.4.1 and Proposition
11.4.4 therein.

Theorem 1.8 follows by combining Example 3.17 and a well-known result on the
tail-decay of the Euclidean norm of an isotropic log-concave random vector,
due to Paouris [31].

######  Theorem 3.18.

There is an absolute constant $c$ such that if $X$ is an isotropic log-concave
random vector in $\mathbb{R}^{d}$ and $u\geq 1$, then

$\mathbb{P}\left(\|X\|_{2}\geq cu\sqrt{d}\right)\leq
2\exp\left(-u\sqrt{d}\right).$

###### Proof of Theorem 1.8.

By Borell’s lemma, an isotropic log-concave random vector is $\psi_{1}$ with
an absolute constant $L$. Thus, following Example 3.17, it remains show that
there are absolute constants $c_{1},c_{2}$ such that with probability at least
$1-2\exp(-c_{1}\sqrt{\Delta m}\log^{2}(\frac{1}{\Delta}))$,

$\max_{1\leq i\leq m}\frac{\|X_{i}\|_{2}}{\sqrt{m}}\leq
c_{2}\sqrt{\Delta}\log^{2}\left(\frac{1}{\Delta}\right).$

Let $u=\beta\sqrt{\frac{\Delta m}{d}}\log^{2}(\frac{1}{\Delta})$ and by
Theorem 3.18 and the union bound,

$\mathbb{P}\left(\max_{1\leq i\leq m}\frac{\|X_{i}\|_{2}}{\sqrt{m}}\geq
c_{3}\beta\sqrt{\Delta}\log^{2}\left(\frac{1}{\Delta}\right)\right)\leq
2m\exp\left(-\beta\sqrt{\Delta
m}\log^{2}\left(\frac{1}{\Delta}\right)\right).$

Hence, recalling that $\Delta\geq d/m$ and $m\geq 2d$, the claim follows if
$\beta$ is a sufficiently large absolute constant. ∎

###  3.5 Proofs of Theorems 1.3 and 1.6

Let us connect all the steps we have made, leading to the proofs of Theorems
1.3 and 1.6.

Set $\kappa$ as in Lemma 3.6. Note that for an absolute constant $c_{1}$ and a
constant $c_{2}=c_{2}(L)$,

$A=\sup_{\theta\in
S^{d-1}}\int_{U}\left(F_{\mu^{\theta}}^{-1}(u)\right)^{2}\,du\leq\begin{cases}c_{1}\Delta\log^{4}\frac{1}{\Delta}&\text{
if $X$ is log-concave,}\\\ c_{2}\Delta\log^{3}\frac{1}{\Delta}&\text{ if $X$
is $L$-subgaussian.}\end{cases}$

And in the general case, when $X$ only satisfies $L_{q}-L_{2}$ norm
equivalence with a constant $L$, there is a constant $c_{3}=c_{3}(q,L)$ such
that $A\leq c_{3}\sqrt{\Delta}$ if $q>4$ and $A\leq
c_{3}\sqrt{\Delta}\log(\frac{1}{\Delta})$ if $q=4$.

The empirical tail integral $\sup_{\theta\in
S^{d-1}}\int_{U}(F_{\mu^{\theta}}^{-1}(u))^{2}\,du$ is controlled by Theorem
1.8 (applied to $s=\delta m$) in the log-concave case; by Example 3.16 (again
applied to $s=\delta m$) in the subgaussian case; and by Lemma 3.14 in the
general case.

As for $\sup_{\theta\in
S^{d-1}}\int_{\delta}^{1-\delta}(F_{\mu^{\theta}_{m}}^{-1}(u)-F_{\mu^{\theta}}^{-1}(u))^{2}\,du$,
fix a realization $(X_{i})_{i=1}^{m}$ for which (3.3) holds. The log-concave
case follows from the arguments presented in Section 1.2, and the general case
follows from Corollary 3.8 and Lemma 3.13. ∎

Finally, let us record the following (trivial) bound and its highly useful
consequence—obtained by invoking Theorem 1.3. Observe that if $X$ is isotropic
and satisfies $L_{4}-L_{2}$ norm equivalence with a constant $L$, then by the
triangle inequality and the tail-estimate (3.6) we have that for every $1\leq
s\leq m$,

$H_{s,m}\leq\mathcal{SW}_{2}(\mu_{m},\mu)+c(L)\left(\frac{s}{m}\right)^{1/4}.$

Setting $\Delta=cd/m$ in Theorem 1.3 leads to the following:

######  Corollary 3.19.

Assume that $(1)$ $X$ is isotropic and satisfies $L_{4}-L_{2}$ norm
equivalence with constant $L$; and $(2)$ there is some $\alpha\geq 4$ such
that with probability $1-\eta$, $\rho_{d,m}\leq\tilde{c}(d/m)^{2/\alpha}$.
Then there are constants $c_{1},\dots,c_{4}$ that depend on $L$ and
$\tilde{c}$ such that, if $m\geq c_{1}d$, then with probability at least
$1-\eta-\exp(-c_{2}d)$ both $\mathcal{SW}_{2}(\mu_{m},\mu)\leq
c_{3}\left(\frac{d}{m}\right)^{1/\alpha}\log\left(\frac{m}{d}\right),$ and for
every $1\leq s\leq m$, $H_{s,m}\leq
c_{4}\left(\left(\frac{s}{m}\right)^{1/4}+\left(\frac{d}{m}\right)^{1/\alpha}\log\left(\frac{m}{d}\right)\right).$

Note that the case $\alpha=4$ corresponds to the quantitative Bai-Yin
estimate, namely that with high probability,
$\rho_{d,m}\leq\tilde{c}\sqrt{d/m}$.

Corollary 3.19 will play an instrumental role in the proof of our second main
result—a non-gaussian Dvoretzky-Milman theorem.

##  4 Towards a non-gaussian Dvoretzky-Milman ensemble

The Dvoretzky-Milman Theorem is one of most remarkable results in Asymptotic
Geometric Analysis. Dvoretzky proved in [12] that $\ell_{2}$ is _finitely
represented_ in any infinite dimensional normed space; i.e., that any infinite
dimensional normed space has subspaces of arbitrarily high (finite) dimension
that are almost Euclidean in the _Banach-Mazur sense_.

The quantitative estimate in Dvoretzky’s proof was suboptimal, and the right
one was discovered by Milman, in his seminal work [29]. Milman showed that any
finite dimensional normed space has a _critical dimension_ , and a typical
subspace—with respect to the Haar measure on the Grassmann manifold—of that
dimension, is almost Euclidean. Moreover, any normed space of dimension $n$ is
isometric to a space whose critical dimension is at least $c\log n$.

To formulate Milman’s result, consider a normed space
$F=(\mathbb{R}^{n},\|\cdot\|)$ and denote its unit ball by $K$. Thus, $K$ is a
_convex body_ : it is a convex, bounded, centrally-symmetric subset of
$\mathbb{R}^{n}$ with a nonempty interior. Recall that
$\left\langle\cdot,\cdot\right\rangle$ is the standard Euclidean inner
product, and set

$K^{\circ}=\\{y\in\mathbb{R}^{n}:\left\langle x,y\right\rangle\leq 1\ {\rm
for\ every\ }x\in K\\}$

to be the polar body of $K$. Let $G$ be the standard gaussian random vector in
$\mathbb{R}^{n}$ and define the critical dimension of $K$ by

$d^{\ast}(K)=\left(\frac{\mathbb{E}\|G\|}{\sup_{t\in
K^{\circ}}\|t\|_{2}}\right)^{2}.$

Milman’s result (in its gaussian version, due to Pisier—see, e.g., [33]) is
the following.

######  Theorem 4.1.

For every $\varepsilon>0$ there is a constant $c_{1}$ depending on
$\varepsilon$ and absolute constants $c_{2},c_{3}$ such that the following
holds. Let $d\leq c_{1}(\varepsilon)d^{\ast}(K)$ and set $G_{1},\dots,G_{d}$
to be independent copies of $G$. If $A=\sum_{i=1}^{d}\left\langle
e_{i},\cdot\right\rangle G_{i}\colon\mathbb{R}^{d}\to\mathbb{R}^{n}$ then with
probability at least $1-2\exp(-c_{2}\varepsilon^{2}d^{\ast}(K))$,

$\displaystyle(1-\varepsilon)\mathbb{E}\|G\|\cdot\left(K\cap
A\mathbb{R}^{d}\right)\subset
AB_{2}^{d}\subset(1+\varepsilon)\mathbb{E}\|G\|\cdot\left(K\cap
A\mathbb{R}^{d}\right).$

Moreover, for any convex body $K$ there is $T\in GL_{n}$ such that
$d^{\ast}(TK)\geq c_{3}\log n$.

The standard argument shows that one may set
$c_{1}(\varepsilon)\sim\frac{\varepsilon^{2}}{\log(1/\varepsilon)}$, while a
more careful analysis due to Gordon [14] (see also Schechtman’s proof [36])
leads to a better estimate of $c_{1}(\varepsilon)\sim\varepsilon^{2}$. A
detailed survey on the Dvoretzky-Milman Theorem can be found in [2].

######  Remark 4.2.

Clearly, for any $T\in GL_{n}$ the normed spaces whose unit balls are $K$ and
$TK$ are isometric. Hence, for the purpose of finding almost Euclidean
sections of $K$ we may and do assume without loss of generality that
$d^{\ast}(K)\geq c\log n$.

An equivalent formulation of the fact that $A$ is an almost isometric
embedding of $\ell_{2}^{d}$ in $(\mathbb{R}^{n},\|\cdot\|)$ is that the
function $x\mapsto\|Ax\|$ is _almost constant_ on the sphere $S^{d-1}$: there
is a number $\Lambda$ such that

$\displaystyle 1-\varepsilon\leq\frac{\|Ax\|}{\Lambda}\leq
1+\varepsilon\qquad\text{for all }x\in S^{d-1}.$ (4.1)

As noted previously, the proof that (4.1) holds with high probability relies
heavily on the fact that $A$ is a gaussian random operator and follows from a
combination of _gaussian concentration_ and _rotation invariance_.
Specifically, that for every $x\in S^{d-1}$, $\|Ax\|$ concentrates sharply
around its mean $\mathbb{E}\|Ax\|$, and that $x\mapsto\mathbb{E}\|Ax\|$ is the
constant function on $S^{d-1}$. Both these features are rather special and at
least one of the two is fails when it comes to other natural choices of random
vectors. For example, if $A$ is generated by the Bernoulli vector and
$\|\cdot\|=\|\cdot\|_{\infty}$, then $x\mapsto\mathbb{E}\|Ax\|$ is not even
equivalent to a constant on $S^{d-1}$. Intuitively, the reason for the gap
between $\inf_{x\in S^{d-1}}\|Ax\|_{\infty}$ and $\sup_{x\in
S^{d-1}}\|Ax\|_{\infty}$ in that case is that if $x=e_{i}$,
$\|Ax\|_{\infty}=\|(\varepsilon_{1},...,\varepsilon_{n})\|_{\infty}=1$. At the
same time, if $x$ is in a ‘diagonal direction’, $\|Ax\|_{\infty}$ is close to
$\|G\|_{\infty}$, and the latter behaves like $\sqrt{\log n}$ (see, e.g., [25]
for a detailed proof). Also, it is standard to verify that $\|Ax\|$ does not
exhibit gaussian concentration around its mean for every fixed $x\in S^{d-1}$
(see the recent results from [15]).

Given the difficulty in finding ensembles that satisfy the two features, it is
natural to ask whether the gaussian ensemble is really the only _optimal
Dvoretzky-Milman ensemble_. That is, are there other families of random
operators that exhibit, _for an arbitrary normed space_ and with nontrivial
probability, the same behaviour as the gaussian operator: exposing Euclidean
sections of the space’s critical dimension. There are examples of optimal
ensembles for restricted classes of normed spaces (e.g. spaces with cotype 2,
see [27]), but non of them exhibit Euclidean sections of the critical
dimension in an _arbitrary_ space. Our goal is to construct such ensembles
that are far from being gaussian; in fact, they can be heavy-tailed.

The key to the construction is factoring through an intermediate space: first
use the random operator $\Gamma\colon\mathbb{R}^{d}\to\mathbb{R}^{m}$ (with
$m=\mathrm{poly}(d)$) that has independent rows generated by a random vector
$X$, i.e.,

$\Gamma=\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\left\langle X_{i},\cdot\right\rangle
e_{i};$

then apply the random operator $D=\sum_{i=1}^{m}\left\langle
e_{i},\cdot\right\rangle Z_{i}\colon\mathbb{R}^{m}\to\mathbb{R}^{n}$, where
$(Z_{i})_{i=1}^{m}$ are iid copies of a random vector in $\mathbb{R}^{n}$ — in
particular, $D$ has iid columns.

As a preliminary test case to this idea’s validity, let $Z$ be the standard
gaussian random vector in $\mathbb{R}^{n}$. Then $D\Gamma$ has a chance of
being an optimal Dvoretzky-Milman ensemble only if $\Gamma$ is an almost
isometric Euclidean embedding of $\mathbb{R}^{d}$ in $\mathbb{R}^{m}$;
otherwise, the embedding would fail even if $\|\cdot\|$ were the Euclidean
norm. At the same time, even if $\Gamma$ is an isometry, $D\Gamma$ need not be
an optimal Dvoretzky-Milman ensemble for an arbitrary subgaussian, isotropic
random vector $Z$. Indeed, as noted previously, if $\Gamma=\mathrm{Id}$, $Z$
is the Bernoulli vector and $\|\cdot\|=\|\cdot\|_{\infty}$ the resulting
embedding is not even isomorphic with an absolute constant.

In a nutshell, we show that these are the only two restrictions. Essentially,
if the matrix $\Gamma$ has iid rows distributed according to a random vector
that is (almost) rotation invariant, and is an almost isometric embedding of
$\ell_{2}^{d}$ in $\ell_{2}^{m}$; and $D:\mathbb{R}^{m}\to\mathbb{R}^{n}$ has
iid isotropic subgaussian columns, then with high probability,
$(D\Gamma\mathbb{R}^{d})\cap K$ is almost Euclidean.

To be more precise, assume without loss of generality that $d^{\ast}(K)\geq
c_{0}\log n$. Fix a parameter $L$ and let $c_{1}$ and $c_{2}$ be well-chosen
constants that depend only on $L$. Let $0<\varepsilon<c_{1}$, set

$d\leq c_{2}\frac{\varepsilon^{2}}{\log(1/\varepsilon)}d^{\ast}(K)$

and let $m$ be specified in what follows. Also, assume that

(A1) $X$ is an isotropic random vector in $\mathbb{R}^{d}$ that satisfies
$L_{4}-L_{2}$ norm equivalence with constant $L$, and with probability at
least $1-\eta$, $\rho_{d,m}\leq\tilde{c}(d/m)^{2/\alpha}$ for some $\alpha\geq
4$.

(A2) $X$ is almost rotation invariant in the sense that

$\sup_{u,v\in S^{d-1}}{\mathcal{W}}_{2}(\mu^{u},\mu^{v})\leq\varepsilon,$
(4.2)

where for every $v\in S^{d-1}$, $\mu^{v}$ is the marginal of $X$ in direction
$v$.

(A3) $Z$ is an isotropic, $L$-subgaussian random vector in $\mathbb{R}^{n}$
that has iid coordinates.

(A4) $m=c_{4}(L,\tilde{c},\alpha)\cdot(d^{\ast}(K))^{\alpha}$.

Denote by $\Omega(\mathbb{X})$ the event on which the assertion of Corollary
3.19 holds (and recall that $\Omega(\mathbb{X})$ has probability at least
$1-\eta-\exp(-c_{3}(L)d)$).

######  Theorem 4.3.

There are constants $c_{0},\dots,c_{4}$ that depend on $L,\alpha,\tilde{c}$
such that the following holds. If $n\geq c_{0}$, then there is some
$\Lambda\in[c_{1}\mathbb{E}\|G\|,c_{2}\mathbb{E}\|G\|]$ such that for any
realization $(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$, with
$\mathbb{P}_{Z}$-probability at least
$1-2\exp(-c_{3}\varepsilon^{2}d^{\ast}(K))$,

$\sup_{u\in S^{d-1}}\left|\frac{\|D\Gamma u\|}{\Lambda}-1\right|\leq
c_{4}\varepsilon.$

######  Remark 4.4.

The assumption that $X$ satisfies $L_{4}-L_{2}$ norm equivalence is necessary:
by the Bai-Yin Theorem [3], if $X$ has iid coordinates distributed according
to a mean zero, variance $1$ random variable that is not bounded in $L_{4}$,
then $\rho_{d,m}\to\infty$ as $d$ and $m$ tend to infinity while keeping their
ratio constant. Hence, without the norm equivalence assumption, it is
impossible to expect that $\rho_{d,m}$ is well-behaved and that $\Gamma$ is
even an isomorphic embedding of $\ell_{2}^{d}$ in $\ell_{2}^{m}$. Also, if
$\Gamma$ satisfies the quantitative Bai-Yin asymptotics (and as noted
previously, that is the case under minimal assumptions on $X$) then (A1) holds
for $\alpha=4$. Finally, if $X$ is rotation invariant then (A2) is trivially
satisfied for any $\varepsilon\geq 0$.

######  Remark 4.5.

The idea of factoring through a higher dimensional space was used in [25] to
prove existence of _isomorphic_ non-gaussian Dvoretzky-Milman ensembles. The
argument was based on establishing lower bounds on the expected suprema of
certain Bernoulli processes. Such bounds are possible only up to a
multiplicative constant, and thus cannot be used to prove that an ensemble
yields an almost isometric embedding regardless of the choice of $X$.

The rest of the article is devoted to the proof of Theorem 4.3, but before we
dive into technical details, let us give an example of such an ensemble, for a
heavy-tailed choice of $X$ and for $Z=(\varepsilon_{1},...,\varepsilon_{n})$
that is the Bernoulli vector.

######  Example 4.6.

Let $K$ be the unit ball of $(\mathbb{R}^{n},\|\cdot\|)$ and set $d\leq
c_{0}\frac{\varepsilon^{2}}{\log(1/\varepsilon)}d^{\ast}(K)$ as above. Let $W$
be distributed uniformly in $S^{d-1}$ and set $v$ to be a symmetric random
variable for which $\mathbb{E}v^{2}=1$ and for $t\geq 100$,

$\frac{1}{100t^{11}}\leq\mathbb{P}(v\geq t)\leq\frac{100}{t^{11}}.$

Setting $X=\sqrt{d}Wv$, it is straightforward to verify that $X$ is a centred,
isotropic random vector that is rotation invariant and satisfies $L_{9}-L_{2}$
norm equivalence with an absolute constant $L$. Moreover, if $m\geq
c_{1}d^{4}$ then

$\displaystyle\mathbb{P}\left(\max_{1\leq i\leq
m}\|X_{i}\|_{2}\leq(dm)^{1/4}\right)\geq
1-m\mathbb{P}\left(|v|\geq\left(\frac{m}{d}\right)^{1/4}\right)\geq
1-\frac{1}{m}.$ (4.3)

Therefore, by [26], with probability at least $1-c_{2}m^{-1}-2\exp(-c_{3}d)$,
$\rho_{d,m}\leq c_{4}\sqrt{d/m}$ (in fact, in [26] it is assumed that
$\max_{1\leq i\leq m}\|X_{i}\|_{2}\leq(dm)^{1/4}$, but as was noted there, a
standard argument may be used to show that the $L_{\infty}$-bound can be
replaced by (4.3)). In particular, (A1) is satisfied with nontrivial
probability for $\alpha=4$ and an absolute constant $\tilde{c}$.

Now put $m\sim(d^{*}(K))^{4}$ and consider a realization of $\Gamma$ for which
the assertion of Corollary 3.19 holds. By Theorem 4.3, for every such
realization of $\Gamma$ and with high $\mathbb{P}_{Z}$-probability, the
section $D\Gamma\mathbb{R}^{d}\cap K$ is $(1\pm c\varepsilon)$-Euclidean. In
particular, $D\Gamma$ is an optimal Dvoretzky-Milman ensemble despite being
‘very far’ from gaussian.

It should be noted that the operator $D$ in Example 4.6, generated by the
Bernoulli vector, does not ‘act well’ on the entire sphere $S^{m-1}$. Indeed,
as noted in [25], if $\|\cdot\|=\|\cdot\|_{\infty}$, there is a logarithmic
gap between $\inf_{x\in S^{m-1}}\|Dx\|$ and $\sup_{x\in S^{m-1}}\|Dx\|$.
However, $D$ acts well on the $d$-dimensional section endowed by $\Gamma
S^{d-1}$. Thus, the meaning of $\Gamma S^{d-1}$ being in a _good position_ is
that, regardless of the choice of $Z$ or of the normed space
$(\mathbb{R}^{n},\|\cdot\|)$, the oscillation of $x\to\|Dx\|$ on $\Gamma
S^{d-1}$ is minimal.

The proof that a typical realization of $\Gamma S^{d-1}$ is indeed in a good
position relies heavily on Theorem 1.3. Obviously, the random operator
$D\Gamma$ is far from being gaussian, but thanks to Theorem 1.3 and its
consequences, $D\Gamma$ still exhibits some key gaussian features.
Specifically, because vectors in $\Gamma S^{d-1}$ inherit $X$’s (almost)
rotation invariance in the sense described in Theorem 1.3, one can show that
the function $x\mapsto\mathbb{E}_{Z}\|Dx\|$ is almost constant on $\Gamma
S^{d-1}$. And, Corollary 3.19 is the crucial ingredient in establishing that
for each $x\in\Gamma S^{d-1}$ the random variable $\|Dx\|$ exhibits ‘gaussian’
concentration around its mean.

###  4.1 Preliminary observations

As part of the proof of Theorem 4.3 we can and do assume without loss of
generality that $\varepsilon^{2}d^{\ast}(K)\geq 1$—otherwise, the claim in is
trivially true. Let $c_{1}$ and $c_{2}$ be well-chosen constants that depend
only on $L$, and set

$s=c_{1}\frac{d^{\ast}(K)}{\log(em/d^{\ast}(K))},\qquad d\leq
c_{2}\frac{\varepsilon^{2}}{\log(1/\varepsilon)}d^{\ast}(K).$ (4.4)

Let $\Omega(\mathbb{X})$ be the event on which the assertion of Corollary 3.19
holds and consider $(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$. In particular,
there are constants $C_{1}$ and $C_{2}$ that depend only on $L$ and
$\tilde{c}$ such that

$\displaystyle\mathcal{SW}_{2}(\mu_{m},\mu)$ $\displaystyle\leq
C_{1}\left(\frac{d}{m}\right)^{1/\alpha}\log\left(\frac{m}{d}\right)\quad\text{and}$
$\displaystyle H_{s,m}$ $\displaystyle\leq
C_{2}\left(\left(\frac{s}{m}\right)^{1/4}+\left(\frac{d}{m}\right)^{1/\alpha}\log\left(\frac{m}{d}\right)\right).$

Hence, for any given constant $\beta>0$, if

$m\geq c_{3}(C_{1},C_{2},\alpha,\beta)(d^{\ast}(K))^{\alpha},$ (4.5)

then

$\mathcal{SW}_{2}(\mu_{m},\mu)\leq\frac{1}{\sqrt{d^{\ast}}}\leq\varepsilon\quad\text{and}\quad\frac{H_{s,m}}{\sqrt{s}}\leq\frac{\beta}{d^{\ast}(K)}.$
(4.6)

In particular, since $\varepsilon\leq 1$, it follows from Lemma 2.2 that
$\rho_{d,m}\leq 2$.

Equation (4.6) will be used frequently in the proof of Theorem 4.3 (for a
well-chosen constant $\beta$), and thus we will consider values of $m$ that
satisfy (4.5) and $(X_{i})_{i=1}^{m}$ for which (4.6) holds.

###  4.2 The behaviour of $u\mapsto\mathbb{E}_{Z}\|D\Gamma u\|$

The first component in the proof of Theorem 4.3 is establishing that
$u\mapsto\mathbb{E}_{Z}\|D\Gamma u\|$ is almost constant on $S^{d-1}$. To that
end, consider an isotropic, symmetric, $L$-subgaussian random vector $Z$
taking values in $\mathbb{R}^{n}$ and let $Z_{1},\dots,Z_{m}$ be independent
copies of $Z$. Set $\Psi\colon\mathbb{R}^{d}\to\mathbb{R}$ by

$\Psi(u)=\left\|\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\left\langle
X_{i},u\right\rangle Z_{i}\right\|,$

and let us show that the oscillation of $u\mapsto\mathbb{E}_{Z}\Psi(u)$ is
governed by $\mathcal{SW}_{2}(\mu_{m},\mu)$.

Consider

$d(x,y)=\min_{\sigma}\left(\sum_{i=1}^{m}\left(x_{i}-y_{\sigma(i)}\right)^{2}\right)^{1/2}\quad\text{for
}x,y\in\mathbb{R}^{m},$

where the minimum is taken over all permutations $\sigma$ of
$\\{1,\dots,m\\}$.

######  Lemma 4.7.

There is an absolute constant $c$ such that for every $x,y\in\mathbb{R}^{m}$,

$\left|\mathbb{E}\left\|\sum_{i=1}^{m}x_{i}Z_{i}\right\|-\mathbb{E}\left\|\sum_{i=1}^{m}y_{i}Z_{i}\right\|\right|\leq
cL\mathbb{E}\|G\|\cdot d(x,y).$

###### Proof.

Fix $x,y\in\mathbb{R}^{m}$ and let $\sigma$ be a permutation of
$\\{1,\dots,m\\}$. Note that $\sum_{i=1}^{m}y_{i}Z_{i}$ has the same
distribution as $\sum_{i=1}^{m}y_{\sigma(i)}Z_{i}$, By gaussian domination, if
$G_{1},\dots,G_{m}$ are independent copies of $G$ then for any
$(w_{i})_{i=1}^{m}\in\mathbb{R}^{m}$,

$\mathbb{E}\left\|\sum_{i=1}^{m}w_{i}Z_{i}\right\|\leq
cL\mathbb{E}\left\|\sum_{i=1}^{m}w_{i}G_{i}\right\|=cL\|w\|_{2}\mathbb{E}\left\|G\right\|.$

Therefore,

$\displaystyle\mathbb{E}\left\|\sum_{i=1}^{m}x_{i}Z_{i}\right\|$
$\displaystyle\leq\mathbb{E}\left\|\sum_{i=1}^{m}(x_{i}-y_{\sigma(i)})Z_{i}\right\|+\mathbb{E}\left\|\sum_{i=1}^{m}y_{\sigma(i)}Z_{i}\right\|$
$\displaystyle\leq
cL\left(\sum_{i=1}^{m}\left(x_{i}-y_{\sigma(i)}\right)^{2}\right)^{1/2}\mathbb{E}\|G\|+\mathbb{E}\left\|\sum_{i=1}^{m}y_{i}Z_{i}\right\|,$

and the claim follows. ∎

In view of Lemma 4.7, to ensure that $u\mapsto\mathbb{E}_{Z}\|D\Gamma u\|$ is
almost constant on $S^{d-1}$ it suffices to show that the set

$\left\\{\left(\left\langle X_{i},u\right\rangle\right)_{i=1}^{m}:u\in
S^{d-1}\right\\}$

has a small diameter with respect to $d$. That follows because, as noted
previously, $d(x,y)$ is proportional to the Wasserstein distance between the
corresponding empirical measures. Formally, we have that

######  Lemma 4.8.

For every $x,y\in\mathbb{R}^{m}$, we have that

$d(x,y)=\sqrt{m}\mathcal{W}_{2}\left(\frac{1}{m}\sum_{i=1}^{m}\delta_{x_{i}},\frac{1}{m}\sum_{i=1}^{m}\delta_{y_{i}}\right).$

Lemma 4.8 is well-known, for example, see Lemma 4.1 and Lemma 4.2 in [6].

Next, set $\mu^{u}$ to be the law of the marginal $\left\langle
X,u\right\rangle$. Set $x=(\left\langle X_{i},u\right\rangle)_{i=1}^{m}$ and
$y=(\left\langle X_{i},v\right\rangle)_{i=1}^{m}$, and by Lemma 4.8 and the
triangle inequality for $\mathcal{W}_{2}$,

$\displaystyle\begin{split}\frac{d(x,y)}{\sqrt{m}}&=\mathcal{W}_{2}(\mu^{u}_{m},\mu^{v}_{m})\\\
&\leq\mathcal{W}_{2}(\mu^{u}_{m},\mu^{u})+\mathcal{W}_{2}(\mu^{u},\mu^{v})+\mathcal{W}_{2}(\mu^{v},\mu_{m}^{v}).\end{split}$
(4.7)

If $X$ is rotation invariant then $\mu^{u}=\mu^{v}$ and the second term is
zero. In general, following (4.2), it is bounded by $\varepsilon$.

Since $X$ is almost rotation-invariant in the sense of (A2) and
$(X_{i})_{i=1}^{m}$ satisfies (4.6), the proof follows by combining Lemma 4.7,
Lemma 4.8 and (4.7):

######  Theorem 4.9.

There is a constant $c$ that depends on $L$ such that

$\sup_{u,v\in
S^{d-1}}\left|\mathbb{E}_{Z}\Psi(u)-\mathbb{E}_{Z}\Psi(v)\right|\leq
c\varepsilon\mathbb{E}\|G\|.$

##  5 Concentration around the conditional expectation

The second component needed in the proof of Theorem 4.3 is concentration:
showing that there is a number $\Lambda$ (that happens to be proportional to
$\mathbb{E}\|G\|$), such that with high probability with respect to
$(X_{i})_{i=1}^{m}$ and $(Z_{i})_{i=1}^{m}$,

$\sup_{u\in S^{d-1}}\left|\Psi(u)-\Lambda\right|\leq c\varepsilon\Lambda.$
(5.1)

Here, the constant $c$ does not depend on the norm, the realization of
$(X_{i})_{i=1}^{m}$ and $(Z_{i})_{i=1}^{m}$, nor on the choices of $d$ or $m$.

###  5.1 A reduction step

For the rest of this section, $W\subset S^{d-1}$ is a maximal
$\varepsilon$-separated subset with respect to the Euclidean norm.

######  Lemma 5.1.

Let $\varepsilon\leq 1/2$ and assume that there is $v\in S^{d-1}$,
$\eta\in[0,1]$, constants $c_{1},c_{2},c_{3}$, and an event ${\cal A}$ such
that for $(X_{i})_{i=1}^{m}\in\mathcal{A}$ the following holds.

$(1)$ Uniform concentration on the net: with $\mathbb{P}_{Z}$-probability at
least $1-\eta$,

$\max_{w\in W}\left|\Psi(w)-\mathbb{E}_{Z}\Psi(w)\right|\leq
c_{1}\varepsilon\mathbb{E}\|G\|.$ (5.2)

$(2)$ A lower bound on the conditional expectation: setting
$\Lambda=\mathbb{E}_{Z}\Psi(v)$,

$\Lambda\geq c_{2}\mathbb{E}\|G\|.$ (5.3)

$(3)$ Almost constant conditional expectation on the net:

$\max_{w\in W}\left|\mathbb{E}_{Z}\Psi(w)-\Lambda\right|\leq
c_{3}\varepsilon\mathbb{E}\|G\|.$ (5.4)

Then, there is a constant $c=c(c_{1},c_{2},c_{3})$ such that for
$(X_{i})_{i=1}^{m}\in\mathcal{A}$, with $\mathbb{P}_{Z}$-probability at least
$1-\eta$,

$\sup_{u\in S^{d-1}}\left|\Psi(u)-\Lambda\right|\leq c\varepsilon\Lambda.$

The previous section was devoted to the proof that (5.4) holds with high
probability for the entire sphere. Thus, once Lemma 5.1 is established, it
suffices to show that (5.2) and (5.3) hold. Those are treated in Theorem 5.2
and Theorem 5.9, respectively.

###### Proof.

Recall that $W$ is an $\varepsilon$-net in $S^{d-1}$. By a standard successive
approximation argument, for every $u\in S^{d-1}$ there is a sequence
$(w_{j}^{u})_{j\geq 0}$ in $W$ such that

$\displaystyle u=\sum_{j=0}^{\infty}\beta_{j}w_{j}^{u},$ (5.5)

where $\beta_{0}=1$ and $|\beta_{j}|\leq\varepsilon^{j}$ for $j\geq 1$. Using
linearity of
$\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\left\langle\cdot,X_{i}\right\rangle Z_{i}$
it follows that

$\displaystyle|\Psi(u)-\Psi(w_{0}^{u})|\leq 2\varepsilon\sup_{w\in W}\Psi(w).$

Let us show that $\sup_{w\in W}\Psi(w)\leq c\Lambda$ for a constant
$c=c(c_{1},c_{2},c_{3})$, and in particular

$\displaystyle\sup_{u\in S^{d-1}}|\Psi(u)-\Psi(w_{0}^{u})|\leq
2c\varepsilon\Lambda.$ (5.6)

To that end, for $w\in W$

$\Psi(w)\leq|\Psi(w)-\mathbb{E}_{Z}\Psi(w)|+|\mathbb{E}_{Z}\Psi(w)-\Lambda|+\Lambda=A+B+\Lambda.$

By combining (5.2) and (5.3), $A\leq\frac{c_{1}}{c_{2}}\varepsilon\Lambda$;
and by combining (5.3) and (5.4),
$B\leq\frac{c_{3}}{c_{2}}\varepsilon\Lambda$.

Finally, set $u\in S^{d-1}$ and consider $(w_{j}^{u})_{j\geq 0}$ as in (5.5).
Using the estimates on $A$ and $B$ again,

$\displaystyle|\Psi(u)-\Lambda|$
$\displaystyle\leq|\Psi(u)-\Psi(w_{0}^{u})|+|\Psi(w_{0}^{u})-\mathbb{E}_{Z}\Psi(w_{0}^{u})|+|\mathbb{E}_{Z}\Psi(w_{0}^{u})-\Lambda|$
$\displaystyle\leq c^{\prime}(c_{1},c_{2},c_{3})\varepsilon\Lambda.\qed$

###  5.2 Uniform concentration on the net—proof of (5.2)

Following Definition 3.15, let $1\leq s\leq m$ and set

$H_{s,m}=\sup_{u\in B_{2}^{d}}\max_{|I|=s}\left(\frac{1}{m}\sum_{i\in
I}\left\langle X_{i},u\right\rangle^{2}\right)^{1/2}.$

######  Theorem 5.2.

There are constants $c_{1},\dots,c_{7}$ depending only on $L$ such that the
following holds. Let $\varepsilon\leq 1/2$. Set

$d\leq c_{1}\frac{\varepsilon^{2}}{\log(1/\varepsilon)}d^{\ast}(K)\ \ \ {\rm
and}\ \ \ m\in[c_{2}d^{\ast}(K),c_{3}\exp(d^{\ast}(K))].$

Consider $s=c_{4}\frac{d^{\ast}(K)}{\log(em/d^{\ast}(K))}$ and with that
choice of $s$, fix a realization $(X_{i})_{i=1}^{m}$ satisfying that

$\displaystyle\sup_{u\in B_{2}^{d}}\frac{1}{m}\sum_{i=1}^{m}\left\langle
X_{i},u\right\rangle^{2}\leq 4\quad\text{and}\quad H_{s,m}\leq
c_{5}\frac{\sqrt{s}}{d^{\ast}(K)}.$ (5.7)

Then with $\mathbb{P}_{Z}$-probability at least
$1-2\exp(-c_{6}\varepsilon^{2}d^{\ast}(K))$,

$\max_{u\in W}\left|\Psi(u)-\mathbb{E}_{Z}\Psi(u)\right|\leq
c_{7}\varepsilon\mathbb{E}\|G\|.$

Before proceeding with the proof of Theorem 5.2, observe that all of its
assumptions are satisfied by the choices specified in Theorem 4.3 and for
$(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$ as in Corollary 3.19. That follows
from the estimates on $H_{s,m}$ and on $\rho_{d,m}$ established in Section 4.1
and since $d^{\ast}(K)\geq c_{0}\log n$ and $n\geq c_{1}(\alpha,\tilde{c},L)$.
Thus, once the proofs of Theorem 5.2 and of (5.3) from Lemma 5.1 are
established, that would also conclude the proof of Theorem 4.3.

Because the proof of Theorem 5.2 is somewhat involved, we first present its
‘road map’ before turning to the technical details.

###  5.3 Highlights of the proof of Theorem 5.2

It is worth stressing once again that the proof of Theorem 5.2 does not simply
follow from gaussian concentration, despite the assumption that $Z$ is
subgaussian. In fact, it was recently shown that gaussian-like concentration
in a subgaussian setup is false in general, see [15]. As we explain in what
follows, what saves the day is the particular structure of the vectors
$(\left\langle X_{i},u\right\rangle)_{i=1}^{m}$.

The idea is to write for $u\in W$,

$\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\left\langle X_{i},u\right\rangle
Z_{i}=\clubsuit_{u}+\diamondsuit_{u}+\heartsuit_{u},$

where $\|\clubsuit_{u}\|$ and $\|\diamondsuit_{u}\|$ are “small”, while
$\|\heartsuit_{u}\|$ concentrates sharply around its mean. The vectors
$\clubsuit_{u}$ are obtained by truncating the vectors $(\left\langle
X_{i},u\right\rangle)_{i=1}^{m}$, while $\diamondsuit_{u}$ is obtained from a
truncation of $(\|Z\|_{i})_{i=1}^{m}$.

The wanted decomposition is achieved in three steps. Recall that $K$ is the
unit ball of the norm $\|\cdot\|$ and $K^{\circ}$ its polar body; in
particular $\|\cdot\|=\sup_{t\in K^{\circ}}\langle\cdot,t\rangle$, and, for
every $I\subset\\{1,\dots,m\\}$,

$\left\|\frac{1}{\sqrt{m}}\sum_{i\in I}\left\langle X_{i},u\right\rangle
Z_{i}\right\|=\sup_{t\in K^{\circ}}\frac{1}{\sqrt{m}}\sum_{i\in I}\left\langle
X_{i},u\right\rangle\left\langle Z_{i},t\right\rangle.$

Step 1 — $\clubsuit_{u}$: _Removing the large coordinates of $(\left\langle
X_{i},u\right\rangle)_{i=1}^{m}$._

Fix $s$ to be named in what follows. Let $I_{u,s}\subset\\{1,\dots,m\\}$ be
the set of indices corresponding to the $s$ largest coordinates of
$(|\left\langle X_{i},u\right\rangle|)_{i=1}^{m}$, and put

$\clubsuit_{u}=\frac{1}{\sqrt{m}}\sum_{i\in I_{u,s}}\left\langle
X_{i},u\right\rangle Z_{i}.$

By the assumption on $(X_{i})_{i=1}^{m}$, the term
$\|(\frac{1}{\sqrt{m}}\left\langle X_{i},u\right\rangle)_{i\in
I_{u,s}}\|_{2}\leq H_{s,m}$ is small. We will show that as a result
$\|\clubsuit_{u}\|$ must be small as well.

Following Step 1, one is left with $\frac{1}{\sqrt{m}}\sum_{i\in
I_{u,s}^{c}}\left\langle X_{i},u\right\rangle Z_{i}$ to deal with. Set

$\xi_{u}=\frac{1}{\sqrt{m}}\max_{i\in I_{u,s}^{c}}|\left\langle
X_{i},u\right\rangle|$

and note that

$\xi_{u}\leq\frac{H_{s,m}}{\sqrt{s}}.$

Thus, a bound on $H_{s,m}$ leads to a uniform bound on $\xi_{u}$, a fact that
will prove to be useful in Step 2 and Step 3.

Step 2 — $\diamondsuit_{u}$: _Truncation of $\|Z_{i}\|$._

Fix $r$ to be named in what follows. For a well-chosen function $\phi(r)$,
denote by $J_{u,r}\subset\\{1,\dots,m\\}$ the (random!) set of indices such
that $\|\frac{1}{\sqrt{m}}\left\langle X_{i},u\right\rangle
Z_{i}\|\geq\xi_{u}\phi(r)$. We will show that with high probability with
respect to $Z$, the set $I_{u,s}^{c}\cap J_{u,r}$ consist of at most $r$
elements.

Put

$\diamondsuit_{u}=\frac{1}{\sqrt{m}}\sum_{i\in I_{u,s}^{c}\cap
J_{u,r}}\left\langle X_{i},u\right\rangle Z_{i}.$

The choice of $\diamondsuit_{u}$ is useful in two important aspects:

$(1)$ Control in $\ell_{\infty}$: For every $i\in I_{u,s}^{c}\cap J_{u,r}$, we
have $\frac{1}{\sqrt{m}}|\left\langle X_{i},u\right\rangle|\leq\xi_{u}$. $(2)$
“Short support”: since $|I_{u,s}^{c}\cap J_{u,r}|\leq r$, $\diamondsuit_{u}$
is the sum of a few terms of the form $\frac{1}{\sqrt{m}}\left\langle
X_{i},u\right\rangle Z_{i}$.

We will show that $(1)$ and $(2)$ are enough to ensure that
$\|\diamondsuit_{u}\|$ is sufficiently small.

Step 3 — $\heartsuit_{u}$: _Concentration._

Finally, one has to show that the norm of

$\heartsuit_{u}=\frac{1}{\sqrt{m}}\sum_{i\in I_{u,s}^{c}\cap
J_{u,r}^{c}}\left\langle X_{i},u\right\rangle Z_{i},$

concentrates sharply around its mean. Note that here there is sufficient
control on

$\max_{i\in I_{u,s}^{c}\cap J_{u,r}^{c}}\|\left\langle X_{i},u\right\rangle
Z_{i}\|.$

Indeed, thanks to the choice of $I_{u,s}$ and $J_{u,r}$, both $|\left\langle
X_{i},u\right\rangle|$ and $\|Z_{i}\|$ are well bounded for indices in
$I_{u,s}^{c}\cap J_{u,r}^{c}$.

That will be enough to show that $\|\heartsuit_{u}\|$ (as a function of
$(Z_{i})_{i=1}^{m}$) concentrates around $\mathbb{E}_{Z}\|\heartsuit_{u}\|$.
Moreover, thanks to the estimates in Step 1 and Step 2,
$\mathbb{E}_{Z}\|\heartsuit_{u}\|$ is close to
$\Lambda=\mathbb{E}_{Z}\Psi(u)$.

###  5.4 Preliminary structural estimates for Theorem 5.2

The following lemma contains well-known facts on subgaussian processes. Recall
that $Z$ is an isotropic and $L$-subgaussian random vector in $\mathbb{R}^{n}$
and set ${\cal R}(K^{\circ})=\sup_{t\in K^{\circ}}\|t\|_{2}$.

######  Lemma 5.3.

There are absolute constants $C_{0},C_{0}^{\prime},C_{1},C_{1}^{\prime}$ such
that for every $1\leq r\leq m$ the following hold:

$(1)$ With probability at least $1-2\exp(-C_{0}^{\prime}r\log(em/r))$,

$\sup_{t\in K^{\circ}}\max_{|J|=r}\left(\sum_{j\in J}\left\langle
Z_{j},t\right\rangle^{2}\right)^{1/2}\leq C_{0}L\left(\mathbb{E}\|G\|+{\cal
R}(K^{\circ})\sqrt{r\log(em/r)}\right).$ (5.8)

$(2)$ We have that

$\left(\mathbb{E}\sup_{t\in K^{\circ}}\max_{|J|=r}\sum_{j\in J}\left\langle
Z_{j},t\right\rangle^{2}\right)^{1/2}\leq C_{0}L\left(\mathbb{E}\|G\|+{\cal
R}(K^{\circ})\sqrt{r\log(em/r)}\right).$ (5.9)

$(3)$ With probability at least $1-2\exp(-C_{1}^{\prime}r\log(em/r))$,

$\left|\left\\{i\in\\{1,\dots,m\\}:\|Z_{i}\|\geq
C_{1}L\left(\mathbb{E}\|G\|+{\cal
R}(K^{\circ})\sqrt{\log\left(em/r\right)}\right)\right\\}\right|\leq r.$
(5.10)

The proof of Lemma 5.3 is standard, and it is outlined for the sake of
completeness.

###### Sketch of the Proof of Lemma 5.3.

Let $\Sigma_{r}\subset S^{m-1}$ be the set of $r$-sparse unit vectors. In
particular, for $x\in\Sigma_{r}$, $|\\{i:x_{i}\neq 0\\}|\leq r$. Set
$\Sigma_{r}^{\prime}\subset\Sigma_{r}$ to be a minimal $1/10$-cover of
$\Sigma_{r}$ with respect to the Euclidean norm. Because $\Sigma_{r}$ is the
union of Euclidean spheres, a standard volumetric estimate shows that
$|\Sigma_{r}^{\prime}|\leq\exp(c_{0}r\log\frac{em}{r})$ for an absolute
constant $c_{0}$. And a convexity argument (just as in the proof of Lemma 5.1)
implies that

$\displaystyle\sup_{t\in K^{\circ}}\max_{|J|=r}\left(\sum_{j\in J}\left\langle
Z_{j},t\right\rangle^{2}\right)^{1/2}$
$\displaystyle=\sup_{x\in\Sigma_{r}}\left\|\sum_{j=1}^{m}x_{j}Z_{j}\right\|\leq
2\max_{x\in\Sigma_{r}^{\prime}}\left\|\sum_{j=1}^{m}x_{j}Z_{j}\right\|.$

It is standard to verify that each random vector $\sum_{j=1}^{m}x_{j}Z_{j}$ is
$cL\|x\|_{2}$-subgaussian and isotropic; thus, by gaussian domination, there
is an absolute constant $c_{1}$ such that for every $x\in\Sigma_{r}^{\prime}$
and $p\geq 1$,

$\displaystyle\begin{split}\left(\mathbb{E}\left\|\sum_{j=1}^{m}x_{j}Z_{j}\right\|^{p}\right)^{1/p}&\leq
c_{1}L(\mathbb{E}\|G\|^{p})^{1/p}\\\ &\leq
c_{2}L\left(\mathbb{E}\|G\|+\sqrt{p}{\cal R}(K^{\circ})\right),\end{split}$
(5.11)

where the second inequality follows from the strong-weak moment inequality for
the gaussian random vector (see, e.g., [34]). Applying (5.11) for
$p=2c_{0}r\log\frac{em}{r}$, it follows from Chebyshev’s inequality that for
every $x\in\Sigma_{r}^{\prime}$, with probability at least
$1-\exp(-2c_{0}r\log\frac{em}{r})$,

$\left\|\sum_{j=1}^{m}x_{j}Z_{j}\right\|\leq c_{3}L\left(\mathbb{E}\|G\|+{\cal
R}(K^{\circ})\sqrt{r\log(em/r)}\right),$

and (1) is evident by the union bound.

The proof of (2) follows a similar path to (1), combined with tail-
integration.

As for (3), by an identical argument to the one used previously, there are
absolute constants $c_{4}$ and $c_{5}\geq 2$, such that

$\displaystyle\mathbb{P}\left(\|Z\|\geq
c_{4}L\left(\mathbb{E}\|G\|+\sqrt{\log\left(em/r\right)}{\cal
R}(K^{\circ})\right)\right)$
$\displaystyle\leq\exp\left(-c_{5}\log\left(em/r\right)\right)\leq\left(\frac{r}{em}\right)^{2}.$

Consider $m$ independent selectors (that is, $\\{0,1\\}$-valued random
variables), defined by

$\delta_{i}=1\ \ {\rm if}\ \ \|Z_{i}\|\geq
c_{4}L\left(\mathbb{E}\|G\|+\sqrt{\log\left(em/r\right)}{\cal
R}(K^{\circ})\right).$

Then $\mathbb{P}(\delta_{i}=1)\leq(r/em)^{2}$, and by Bennett’s inequality,
with probability at least $1-2\exp(-c_{6}r\log(em/r))$, we have that
$|\\{i:\delta_{i}=1\\}|\leq r$, as claimed. ∎

For $1\leq r\leq m$, denote by $\Omega_{r}(\mathbb{Z})$ the set of all
$(Z_{i})_{i=1}^{m}$ such that both (5.8) and (5.10) hold.

###  5.5 Proof of Theorem 5.2—part 1

Throughout this section, denote by $C_{0},C_{1}$ the absolute constants from
Lemma 5.3. For $1\leq r\leq m$ set

$\displaystyle\phi(r)=C_{1}L\left(\mathbb{E}\|G\|+{\cal
R}(K^{\circ})\sqrt{\log(em/r)}\right),$ (5.12)

i.e., $\phi$ is the function appearing in (5.10).

The values of $C_{0}$ and $C_{1}$ will remain unchanged throughout this
section, and in what follows, the constants $c,c_{0},c_{1},c_{2}$ etc. depend
on $L$, $C_{0}$ and $C_{1}$.

Rather than specifying the required values of $r,s,m,d$ and $H_{s,m}$, we
shall collect conditions on those values, and show in Section 5.6 that those
are satisfied under the assumptions of Theorem 5.2.

Finally, fix a realization $(X_{i})_{i=1}^{m}$ for which $\sup_{u\in
B_{2}^{d}}\frac{1}{m}\sum_{i=1}^{m}\left\langle X_{i},u\right\rangle^{2}\leq
4$.

Step 1 — $\clubsuit_{u}$: Let $s$ be specified in what follows, set
$(Z_{i})_{i=1}^{m}\in\Omega_{s}(\mathbb{Z})$ and recall that $I_{u,s}$ is the
set of indices corresponding to the $s$ largest coordinates of $(|\left\langle
X_{i},u\right\rangle|)_{i=1}^{m}$. By the Cauchy-Schwartz inequality,

$\displaystyle\|\clubsuit_{u}\|=$ $\displaystyle\sup_{t\in
K^{\circ}}\frac{1}{\sqrt{m}}\sum_{i\in I_{u,s}}\left\langle
X_{i},u\right\rangle\left\langle Z_{i},t\right\rangle$ $\displaystyle\leq$
$\displaystyle\left(\frac{1}{m}\sum_{i\in I_{u,s}}\left\langle
X_{i},u\right\rangle^{2}\right)^{1/2}\cdot\sup_{t\in
K^{\circ}}\left(\sum_{i\in I_{u,s}}\left\langle
Z_{i},t\right\rangle^{2}\right)^{1/2}$

Since $|I_{u,s}|=s$, it follows from the definitions of $H_{s,m}$ and
$\Omega_{s}(\mathbb{Z})$ and by the choice of $s$ that

$\|\clubsuit_{u}\|\leq H_{s,m}\cdot C_{0}L\left(\mathbb{E}\|G\|+{\cal
R}(K^{\circ})\sqrt{s\log(em/s)}\right).$

Moreover, since

$d^{*}(K)=\left(\frac{\mathbb{E}\|G\|}{{\cal R}(K^{\circ})}\right)^{2},$

it is evident that for suitable constants $c_{1}$ and $c_{1}^{\prime}$, if

$H_{s,m}\leq c_{1}\varepsilon\qquad{\rm and}\qquad s\log(em/s)\leq
c_{1}^{\prime}d^{*}(K),$ (5.13) then for
$(Z_{i})_{i=1}^{m}\in\Omega_{s}(\mathbb{Z})$, $\sup_{u\in
B_{2}^{d}}\|\clubsuit_{u}\|\leq\varepsilon\mathbb{E}\|G\|.$

Using (5.9) and an identical argument, the conditions in (5.13) also imply
that

$\sup_{u\in
B_{2}^{d}}\mathbb{E}_{Z}\|\clubsuit_{u}\|\leq\varepsilon\mathbb{E}\|G\|.$
(5.14)

Step 2 — $\diamondsuit_{u}$: Let $r$ be named in what follows and set
$(Z_{i})_{i=1}^{m}\in\Omega_{r}(\mathbb{Z})$. Recall that

$\xi_{u}=\frac{1}{\sqrt{m}}\max_{i\in I_{u,s}^{c}}|\left\langle
X_{i},u\right\rangle|$

and thus $\xi_{u}\leq H_{s,m}/\sqrt{s}$. Consider the function $\phi$ defined
in (5.12) and set

$J_{u,r}=\left\\{j\in\\{1,\dots,m\\}:\left\|\tfrac{1}{\sqrt{m}}\left\langle
X_{i},u\right\rangle Z_{j}\right\|\geq\xi_{u}\phi(r)\right\\}.$

Clearly $|\frac{1}{\sqrt{m}}\left\langle X_{i},u\right\rangle|\leq\xi_{u}$ for
every $i\in I_{u,s}^{c}$; thus,

$I_{u,s}^{c}\cap
J_{u,r}\subset\left\\{j\in\\{1,\dots,m\\}:\|Z_{j}\|\geq\phi(r)\right\\}.$

Moreover, by the definition of $\Omega_{r}(\mathbb{Z})$, the set
$\\{j:\|Z_{j}\|\geq\phi(r)\\}$ has cardinality at most $r$. Hence,

$\displaystyle\|\diamondsuit_{u}\|$ $\displaystyle=\sup_{t\in
K^{\circ}}\frac{1}{\sqrt{m}}\sum_{i\in I_{u,s}^{c}\cap J_{u,r}}\left\langle
X_{i},u\right\rangle\left\langle Z_{i},t\right\rangle$
$\displaystyle\leq\xi_{u}\cdot\sup_{t\in K^{\circ}}\max_{|J|=r}\sum_{j\in
J}|\left\langle Z_{j},t\right\rangle|$
$\displaystyle\leq\frac{H_{s,m}}{\sqrt{s}}\cdot\sqrt{r}\sup_{t\in
K^{\circ}}\max_{|J|=r}\left(\sum_{j\in J}\left\langle
Z_{j},t\right\rangle^{2}\right)^{1/2},$

where the last inequality is evident by comparing the $\ell_{1}^{r}$ and
$\ell_{2}^{r}$ norms. Since $(Z_{i})_{i=1}^{m}\in\Omega_{r}(\mathbb{Z})$, it
follows that

$\|\diamondsuit_{u}\|\leq
H_{s,m}\cdot\sqrt{\frac{r}{s}}C_{0}L\left(\mathbb{E}\|G\|+{\cal
R}(K^{\circ})\sqrt{r\log\left(em/r\right)}\right),$

and in particular, for suitable constants $c_{2}$ and $c_{2}^{\prime}$, if

$H_{s,m}\sqrt{\frac{r}{s}}\leq c_{2}\varepsilon,\ \ {\rm and}\ \
r\log\left(em/r\right)\leq c_{2}^{\prime}d^{*}(K),$ (5.15) then $\sup_{u\in
B_{2}^{d}}\|\diamondsuit_{u}\|\leq\varepsilon\mathbb{E}\|G\|$

Next, let us estimate $\mathbb{E}_{Z}\|\diamondsuit_{u}\|$.

######  Lemma 5.4.

If (5.15) holds then $\sup_{u\in
B_{2}^{d}}\mathbb{E}_{Z}\|\diamondsuit_{u}\|\leq\varepsilon\mathbb{E}\|G\|$.

###### Proof.

Fix $u\in B_{2}^{d}$, set $Q=|\\{i\in I_{u,s}^{c}:\|Z_{i}\|\geq\phi(r)\\}|$
and for $q\geq 1$, let

$S(q)=\left(\sup_{t\in K^{\circ}}\max_{|J|\leq q}\sum_{j\in J}\left\langle
Z_{j},t\right\rangle^{2}\right)^{1/2},$

with the convention that $\max\emptyset=0$. Therefore

$\displaystyle\|\diamondsuit_{u}\|$ $\displaystyle\leq\max_{i\in
I_{u,s}^{c}}\left|\frac{1}{\sqrt{m}}\left\langle
X_{i},u\right\rangle\right|\cdot\sup_{t\in K^{\circ}}\sum_{j\in
I_{u,s}^{c}\cap J_{u,r}}|\left\langle Z_{j},t\right\rangle|$
$\displaystyle\leq\frac{H_{s,m}}{\sqrt{s}}\cdot\sqrt{Q}S(Q).$

Since $H_{s,m}$ is independent of $(Z_{i})_{i=1}^{m}$, all that is left is to
show that $\mathbb{E}\sqrt{Q}S(Q)\leq c\sqrt{r}\mathbb{E}\|G\|$ for a suitable
constant $c$. To that end, observe that

$\displaystyle\sqrt{Q}S(Q)$
$\displaystyle\leq\mathbbm{1}_{[0,2r]}(Q)\sqrt{2r}S(2r)+\sum_{r<2^{s}<m}\mathbbm{1}_{(2^{s},2^{s+1}]}(Q)\sqrt{2^{s+1}}S(2^{s+1})$
$\displaystyle=A+B.$

By (5.9), for $1\leq q\leq m$,

$\left(\mathbb{E}_{Z}S^{2}(q)\right)^{1/2}\leq
C_{0}L\left(\mathbb{E}\|G\|+{\cal
R}(K^{\circ})\sqrt{q\log\left(em/q\right)}\right),$

and for $r$ as in (5.15), $\mathbb{E}_{Z}A\leq c_{1}\sqrt{r}\mathbb{E}\|G\|$.

In order to estimate $\mathbb{E}_{Z}B$, one applies the Cauchy-Schwartz
inequality to each term
$\mathbb{E}_{Z}\mathbbm{1}_{(2^{s},2^{s+1}]}(Q)S(2^{s+1})$, and thus

$\mathbb{E}_{Z}B\leq\sum_{r<2^{s}<m}\sqrt{\mathbb{P}(Q\geq
2^{s})}\cdot\sqrt{2^{s+1}}C_{0}L\left(\mathbb{E}\|G\|+{\cal
R}(K^{\circ})\sqrt{2^{s+1}\log\left(em/2^{s+1}\right)}\right).$

Finally, just as in the proof of the third part of Lemma 5.3,
$\mathbb{P}(Q\geq 2^{s})\leq 2\exp(-c_{2}2^{s})$ for $2^{s}\geq 2r$; hence, by
comparing the sum to a geometric progression, $\mathbb{E}_{Z}B\leq
c_{3}\sqrt{r}\mathbb{E}\|G\|$, as claimed. ∎

Step 3 — $\heartsuit_{u}$: Observe that by definition of $J_{u,r}$,

$\displaystyle\heartsuit_{u}$ $\displaystyle=\frac{1}{\sqrt{m}}\sum_{i\in
I_{u,s}^{c}\cap J^{c}_{u,r}}\left\langle X_{i},u\right\rangle Z_{i}$
$\displaystyle=\frac{1}{\sqrt{m}}\sum_{i\in I_{u,s}^{c}}\left\langle
X_{i},u\right\rangle\mathbbm{1}_{\left\\{\left\|\frac{1}{\sqrt{m}}\left\langle
X_{i},u\right\rangle Z_{i}\right\|\leq\xi_{u}\phi(r)\right\\}}Z_{i}.$

In particular, if we set

$\displaystyle\mathcal{F}_{u}$
$\displaystyle=\left\\{f_{t}(\cdot)=\left\langle
t,\cdot\right\rangle\mathbbm{1}_{\\{\|\cdot\|\leq\xi_{u}\phi(r)\\}}:t\in
K^{\circ}\right\\}\text{ and}$ $\displaystyle Y_{i}$
$\displaystyle=\frac{1}{\sqrt{m}}\left\langle X_{i},u\right\rangle
Z_{i}\in\mathbb{R}^{n},$

then

$\|\heartsuit_{u}\|=\sup_{t\in K^{\circ}}\sum_{i\in I_{u,s}^{c}}f_{t}(Y_{i}).$
(5.16)

######  Remark 5.5.

Note that the sets $I_{u,s}$ depend on $(X_{i})_{i=1}^{m}$ but not on
$(Z_{i})_{i=1}^{m}$.

Let us show that conditionally on $(X_{i})_{i=1}^{m}$, each random variable
$\|\heartsuit_{u}\|$ concentrates around its mean. Equation (5.16) means that
$\|\heartsuit_{u}\|$ is a supremum of an empirical process and one may invoke
the following version of Talagrand’s concentration inequality for bounded
empirical processes due to Klein and Rio [17].

######  Theorem 5.6.

Let $Y_{1},\dots,Y_{k}$ be independent, set $\mathcal{F}$ to be a class of
functions into $[-a,a]$ such that $\mathbb{E}f(Y_{i})=0$ for every
$i\in\\{1,\dots,k\\}$ and $f\in\mathcal{F}$. Let
$\sigma^{2}=\sup_{f\in\mathcal{F}}\sum_{i=1}^{k}\mathbb{E}f^{2}(Y_{i})$ and
consider

$U=\sup_{f\in\mathcal{F}}\sum_{i=1}^{k}f(Y_{i}).$

Then for $x>0$,

$\displaystyle\mathbb{P}\left(|U-\mathbb{E}U|\leq x\right)\geq
1-2\exp\left(-\frac{-x^{2}}{2(\sigma^{2}+2a\mathbb{E}U)+3ax}\right).$ (5.17)

Here $k=|I_{u,s}^{c}|=m-s$ and $\mathcal{F}=\mathcal{F}_{u}$. We start by
verifying that the assumptions of Theorem 5.6 hold in the context of the
empirical process from (5.16).

######  Lemma 5.7.

The set $\mathcal{F}_{u}$ satisfies the assumptions in Theorem 5.6 with
$a=\frac{H_{s,m}}{\sqrt{s}}\phi(r)$. Moreover, $\sigma^{2}\leq
4\mathcal{R}^{2}(K^{\circ})$ and $\mathbb{E}U\leq cL\mathbb{E}\|G\|$ for an
absolute constant $c$.

###### Proof.

First note that $\mathbb{E}f(Y_{i})=0$ for every $f=f_{t}\in\mathcal{F}_{u}$
and $i$. Indeed, since $\|t\|=\|-t\|$ and $Y_{i}$ is symmetric, then

$\mathbb{E}f_{t}(Y_{i})=\mathbb{E}_{Z}\left\langle
t,Y_{i}\right\rangle\mathbbm{1}_{\\{\|Y_{i}\|\leq\xi_{u}\phi(r)\\}}=0.$

Turning to the estimate on $a$, let $f=f_{t}$ for $t\in K^{\circ}$. Then for
every $y\in\mathbb{R}^{n}$,

$\displaystyle|f_{t}(y)|$ $\displaystyle=|\left\langle t,y\right\rangle|\
\mathbbm{1}_{\\{\|y\|\leq\xi_{u}\phi(r)\\}}$
$\displaystyle\leq\|y\|\mathbbm{1}_{\\{\|y\|\leq\xi_{u}\phi(r)\\}}\leq\xi_{u}\phi(r)\leq\phi(r)\frac{H_{s,m}}{\sqrt{s}}$

by the (uniform) upper estimate on $\xi_{u}$.

As for $\sigma^{2}$, recall that $\frac{1}{m}\sum_{i=1}^{m}\left\langle
X_{i},u\right\rangle^{2}\leq 4$ and that $Z$ is isotropic. Hence

$\displaystyle\sigma^{2}$ $\displaystyle\leq\sup_{t\in K^{\circ}}\sum_{i\in
I_{u,s}^{c}}\frac{1}{m}\left\langle
X_{i},u\right\rangle^{2}\mathbb{E}\left\langle Z_{i},t\right\rangle^{2}$
$\displaystyle\leq 4\sup_{t\in K^{\circ}}\|t\|_{2}^{2}=4{\cal
R}^{2}(K^{\circ}).$

Finally, using a standard contraction argument (see, e.g., [19]),

$\displaystyle\mathbb{E}U$ $\displaystyle=\mathbb{E}_{Z}\sup_{t\in
K^{\circ}}\frac{1}{\sqrt{m}}\sum_{i\in I_{u,s}^{c}}\left\langle
X_{i},u\right\rangle\mathbbm{1}_{\\{\|Y_{i}\|\leq\xi_{u}\phi(r)\\}}\left\langle
Z_{i},t\right\rangle$
$\displaystyle\leq\mathbb{E}_{Z}\left\|\frac{1}{\sqrt{m}}\sum_{i\in
I_{u,s}^{c}}\left\langle X_{i},u\right\rangle Z_{i}\right\|=A.$

Since $(Z_{i})_{i=1}^{m}$ are independent and $L$-subgaussian, it follows from
gaussian domination that $A\leq cL\mathbb{E}\|G\|$ for an absolute constant
$c$. ∎

The next step is to control the denominator in the probability estimate in
(5.17). Consider $0<x<\mathbb{E}\|G\|$, and note that by Lemma 5.7,

$2(\sigma^{2}+2a\mathbb{E}U)+3ax\leq c_{3}\left({\cal
R}^{2}(K^{\circ})+\frac{H_{s,m}}{\sqrt{s}}\phi(r)\mathbb{E}\|G\|\right).$

By definition of $\phi$, if

$m\leq c_{4}r\exp(d^{*}(K))$

then $\phi(r)\leq c_{5}\mathbb{E}\|G\|$, and thus

$2(\sigma^{2}+2a\mathbb{E}U)+3ax\leq c_{6}\left({\cal
R}^{2}(K^{\circ})+\frac{H_{s,m}}{\sqrt{s}}(\mathbb{E}\|G\|)^{2}\right).$

Setting $x=\varepsilon\mathbb{E}\|G\|$ and since $U=\|\heartsuit_{u}\|$ (see
(5.16)), it follows from Theorem 5.6 that for suitable constants $c_{7}$,
$c_{7}^{\prime}$ and $c_{7}^{\prime\prime}$, if

$\frac{H_{s,m}}{\sqrt{s}}\leq\frac{c_{7}}{d^{\ast}(K)}\quad\text{and}\quad
m\leq c_{7}^{\prime}r\exp(d^{*}(K)),$ (5.18) then for every $u\in B_{2}^{d}$,
with $\mathbb{P}_{Z}$-probability at least
$1-2\exp(-c_{7}^{\prime\prime}\varepsilon^{2}d^{*}(K))$,
$\left|\|\heartsuit_{u}\|-\mathbb{E}_{Z}\|\heartsuit_{u}\|\right|\leq\varepsilon\mathbb{E}\|G\|.$

######  Remark 5.8.

It is worth stressing that in contrast to Step 1 and Step 2, the probability
estimate here does not hold uniformly for $u\in B_{2}^{d}$, but only for a
single (arbitrary) $u$.

###  5.6 Proof of Theorem 5.2

First, let us show that for well-chosen $s,r,m$, and $d$, all the requirements
collected in (5.13), (5.15), and (5.18) are indeed satisfied. Let
$c_{1},\dots,c_{4}$ be suitable constants that turn out to depend only on $L$,
$C_{0}$, and $C_{1}$. Set

$s=c_{1}\frac{d^{*}(K)}{\log\left(em/d^{*}(K)\right)}\ \ \ {\rm and}\ \ \
r=c_{2}\min\\{\varepsilon^{2}d^{*}(K),s\\},$

and let $m\in[c_{3}d^{*}(K),c_{4}\exp(d^{\ast}(K))]$. Then (5.13) and (5.15)
are satisfied for suitable choices of $c_{1},c_{2}$. Moreover, one may assume
without loss of generality that $\varepsilon^{2}d^{\ast}(K)\geq 1$—otherwise
the claim in Theorem 5.2 is trivially true; thus, $m$ satisfies (5.18) for
suitable choice of $c_{4}$.

Next, collecting the requirements on $H_{s,m}$ from (5.13), (5.15), and
(5.18), one has to verify that

$\displaystyle H_{s,m}\leq
c_{5}\min\left\\{\varepsilon,\varepsilon\sqrt{\frac{s}{r}},\frac{\sqrt{s}}{d^{\ast}(K)}\right\\}.$
(5.19)

Recall that $r\leq c_{2}s$ and that $\varepsilon\geq 1/\sqrt{d^{\ast}(K)}$; in
particular, the third term in (5.19) is the dominant one, and (5.19) is
equivalent to having $H_{s,m}\leq c_{6}\sqrt{s}/d^{\ast}(K)$, which was
assumed to hold.

Therefore, if

$(Z_{i})_{i=1}^{m}\in\Omega_{s}(\mathbb{Z})\cap\Omega_{r}(\mathbb{Z}),$

then

$\max\left\\{\|\clubsuit_{u}\|,\|\diamondsuit_{u}\|,\mathbb{E}_{Z}\|\clubsuit_{u}\|,\mathbb{E}_{Z}\|\diamondsuit_{u}\|\right\\}\leq\varepsilon\mathbb{E}\|G\|.$

To estimate the probability of the event
$\Omega_{s}(\mathbb{Z})\cap\Omega_{r}(\mathbb{Z})$, note that $s\log(em/s)\geq
c_{7}d^{\ast}(K)$ by the choice of $s$ and since $m\geq c_{3}d^{\ast}(K)$. In
particular, as $\varepsilon\leq 1$, it follows that $s\log(em/s)\geq
c_{7}\varepsilon^{2}d^{\ast}(K)$. Repeating the argument for $r$, by Lemma 5.3

$\displaystyle\mathbb{P}_{Z}\left(\Omega_{r}(\mathbb{Z})\cap\Omega_{s}(\mathbb{Z})\right)$
$\displaystyle\geq
1-2\exp\left(-C_{2}s\log\left(\frac{em}{s}\right)\right)-2\exp\left(-C_{2}r\log\left(\frac{em}{r}\right)\right)$
$\displaystyle\geq 1-2\exp(-C_{3}\varepsilon^{2}d^{\ast}(K))$

for constants $C_{2}$ and $C_{3}$ that depend on $c_{7}$ and on the absolute
constants $C_{0}^{\prime}$ and $C_{1}^{\prime}$ from Lemma 5.3.

Finally, one has to show that $\|\heartsuit_{u}\|$ concentrates around its
mean, and that the required concentration holds uniformly in $u\in W$. As was
noted previously, for any $u\in W$,

$\left|\ \|\heartsuit_{u}\|-\mathbb{E}_{Z}\|\heartsuit_{u}\|\
\right|\leq\varepsilon\mathbb{E}\|G\|$

with $\mathbb{P}_{Z}$-probability at least
$1-2\exp(-c_{8}\varepsilon^{2}d^{*}(K))$. Recall that $W\subset S^{d-1}$ is a
maximal $\varepsilon$-separated subset, and in particular $\log|W|\leq
d\log(5/\varepsilon)$. If

$d\leq c_{9}\frac{\varepsilon^{2}d^{*}(K)}{\log(5/\varepsilon)}$

for a suitable constant $c_{9}$, then by the union bound, with
$\mathbb{P}_{Z}$-probability at least
$1-2\exp(-c_{10}\varepsilon^{2}d^{*}(K))$,

$\max_{u\in W}\left|\ \|\heartsuit_{u}\|-\mathbb{E}_{Z}\|\heartsuit_{u}\|\
\right|\leq\varepsilon\mathbb{E}\|G\|.$ (5.20)

Taking the intersection of $\Omega_{r}(\mathbb{Z})\cap\Omega_{s}(\mathbb{Z})$
and the high-probability event on which (5.20) holds completes the proof. ∎

###  5.7 A lower bound on the conditional expectation—proof of (5.3)

Let us turn to verifying (5.3) from Lemma 5.1. Once again, recall that $Z$ is
a symmetric, isotropic, $L$-subgaussian random vector in $\mathbb{R}^{n}$ that
has iid coordinates.

######  Theorem 5.9.

Let $\delta,\eta>0$. There are constants $c_{1}$ and $c_{2}$ that depend on
$\delta$ and $\eta$ such that the following holds. Let $m\geq c_{1}\log n$ and
fix $v\in S^{d-1}$. If

$\displaystyle|\\{i\in\\{1,\dots,m\\}:|\left\langle
X_{i},v\right\rangle|\geq\eta\\}|\geq\delta m,$ (5.21)

then

$\mathbb{E}_{Z}\Psi(v)\geq c_{2}\mathbb{E}\|G\|.$

Note that under different conditions (most notably that $m\geq cn$ instead of
$m\geq c\log n$), a version of Theorem 5.9 was established in [25] without the
assumption that the coordinates of $Z$ are iid. The idea was to find a lower
bound on

$\mathbb{E}_{\varepsilon}\sup_{t\in
K^{\circ}}\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\varepsilon_{i}\left\langle
X_{i},v\right\rangle\left\langle Z_{i},t\right\rangle,$

conditioned on a typical realization of $(X_{i})_{i=1}^{m}$ and
$(Z_{i})_{i=1}^{m}$, and relied on the construction of an approximation of
$K^{\circ}\subset\mathbb{R}^{n}$ of cardinality $\exp(cm)$. Unfortunately, in
the worst case it forced $m$ to be proportional to $n$. Since the aim here is
for $m$ to be as small as possible—specifically a low-degree polynomial
function of the critical dimension $d^{\ast}(K)$—a different argument is
called for.

######  Lemma 5.10.

Let $X$ satisfy $L_{4}-L_{2}$ norm equivalence with a constant $L$. There are
constants $\eta,\delta,c_{0}$ that depend only on $L$ such that if
$\mathcal{SW}_{2}(\mu_{m},\mu)\leq c_{0}$, then (5.21) holds.

###### Proof.

By the $L_{4}-L_{2}$ norm equivalence and the Paley–Zygmund inequality, there
are constants $\eta$ and $\delta$ that depend only on $L$ such that

$\mu^{v}\left(\left(-2\eta,2\eta\right)^{c}\right)=\mathbb{P}\left(|\left\langle
X,v\right\rangle|\geq 2\eta\right)\geq 4\delta.$

It is straightforward to verify that if
$\mu^{v}_{m}((-\eta,\eta)^{c})\leq\delta$, then
$\mathcal{W}_{2}(\mu^{v}_{m},\mu^{v})\geq\sqrt{\delta}\eta$. Set
$c_{0}=\sqrt{\delta}\eta/2$ and note that
$\mu^{v}_{m}((-\eta,\eta)^{c})\geq\delta$ is equivalent to (5.21). ∎

Lemma 5.10 shows that (5.21) holds in the setting of Theorem 4.3. Moreover,
using gaussian domination, it is standard to verify that if
$\frac{1}{m}\sum_{i=1}^{m}\left\langle X_{i},v\right\rangle^{2}\leq 4$, then
$\mathbb{E}_{Z}\Psi(v)\leq cL\mathbb{E}\|G\|$. Thus, in the setting of Theorem
4.3,

$\mathbb{E}_{Z}\Psi(v)\in[c_{1}\mathbb{E}\|G\|,c_{2}\mathbb{E}\|G\|]$

for $c_{1}$ and $c_{2}$ that depend on $L$.

Thus, the proof of Theorem 5.9 is the final component need for the proof of
Theorem 4.3.

###  5.8 Proof of Theorem 5.9

The proof of Theorem 5.9 is based on two facts. To formulate them, recall that
$x^{\ast}$ is the non-increasing rearrangement of $(|x_{i}|)_{i=1}^{m}$.

######  Lemma 5.11.

Let $w$ be a symmetric random variable, set $(w_{i})_{i=1}^{n}$ to be
independent copies of $w$ and put $W=(w_{i})_{i=1}^{n}$. Let
$\varepsilon=(\varepsilon_{i})_{i=1}^{n}$ be the Bernoulli vector and set
$\pi$ to be the uniform distribution on the permutations of $\\{1,\dots,n\\}$.
If $W$, $\varepsilon$ and $\pi$ are independent then

$\mathbb{E}_{W}\sup_{t\in
K^{\circ}}\sum_{i=1}^{n}w_{i}t_{i}=\mathbb{E}_{W,\pi,\varepsilon}\sup_{t\in
K^{\circ}}\sum_{i=1}^{n}w^{\ast}_{i}\varepsilon_{\pi(i)}t_{\pi(i)}.$

###### Proof.

The key is the (rather obvious) observation that $(w_{1},\dots,w_{n})$ has the
same distribution as
$(\varepsilon_{1}w^{\ast}_{\pi(1)},\dots,\varepsilon_{n}w^{\ast}_{\pi(n)})$.
Therefore,

$\displaystyle\mathbb{E}_{W}\sup_{t\in K^{\circ}}\sum_{i=1}^{n}w_{i}t_{i}$
$\displaystyle=\mathbb{E}_{W,\pi,\varepsilon}\sup_{t\in
K^{\circ}}\sum_{i=1}^{n}\varepsilon_{i}w^{\ast}_{\pi(i)}t_{i}$
$\displaystyle=\mathbb{E}_{W,\pi,\varepsilon}\sup_{t\in
K^{\circ}}\sum_{i=1}^{n}w^{\ast}_{i}\varepsilon_{\pi(i)}t_{\pi(i)}$

where the last equality holds because $\pi^{-1}$ and $\pi$ have the same
distribution. ∎

######  Lemma 5.12.

Let $\delta>0$. There are constants $c_{1},\dots,c_{4}$ that depend only on
$\delta$ and $L$ such that the following holds. Let $m\geq c_{1}\log n$,
consider $I\subset\\{1,\dots,m\\}$, $|I|\geq\delta m$ and set for
$j=1,\dots,n$,

$\displaystyle Y_{j}=\frac{1}{\sqrt{m}}\sum_{i\in I}\left\langle
Z_{i},e_{j}\right\rangle.$ (5.22)

Then for any $1\leq k\leq n$, $\mathbb{E}|Y_{k}|\geq c_{2}$. Also, for any
$1\leq k\leq c_{3}n$,

$\displaystyle\mathbb{E}Y^{\ast}_{k}\geq
c_{4}\sqrt{\log\left(\frac{n}{k}\right)}.$ (5.23)

###### Proof.

We only present a proof of (5.23). The proof that $\min_{1\leq k\leq
n}\mathbb{E}|Y_{k}|\geq c$ follows a similar (but simpler) path.

Since $Z$ has iid coordinates, the random variables $(Y_{j})_{j=1}^{n}$ are
independent and each $Y_{j}$ has the same distribution as $Y=Y_{1}$. It is
straightforward to verify that if $u$ satisfies that $\mathbb{P}(|Y|\geq
u)\geq c_{1}k/n$, then $\mathbb{P}(Y^{\ast}_{k}\geq u)\geq 1/2$ as long as
$c_{1}$ is a well-chosen absolute constant; in particular,
$\mathbb{E}Y^{\ast}_{k}\geq u/2$. The rest of the proof is devoted to
establishing that $u$ of the order $\sqrt{\log\frac{n}{k}}$ is a valid choice.

Since $Z$ is $L$-subgaussian and isotropic, it follows from the Paley–Zygmund
inequality that there are constants $c_{2}$ and $c_{3}$ depending only on $L$
such that $\mathbb{P}(|\left\langle Z,e_{1}\right\rangle|\geq c_{2})\geq
2c_{3}$. Setting

$I^{\prime}=\\{i\in I:|\left\langle Z_{i},e_{1}\right\rangle|\geq c_{2}\\},$

by of Markov’s inequality $\mathbb{P}\left(|I^{\prime}|\geq
c_{3}|I|\right)\geq 1/2$, and by the contraction inequality for Bernoulli
processes and the symmetry of $Z$,

$\displaystyle\mathbb{P}(|Y|\geq u)$
$\displaystyle=\mathbb{E}_{Z}\mathbb{P}_{\varepsilon}\left(\left|\frac{1}{\sqrt{m}}\sum_{i\in
I}\varepsilon_{i}\left\langle Z_{i},e_{1}\right\rangle\right|\geq u\right)$
$\displaystyle\geq\mathbb{E}_{Z}\mathbbm{1}_{\\{|I^{\prime}|\geq
c_{3}|I|\\}}\frac{1}{2}\mathbb{P}_{\varepsilon}\left(\left|\frac{1}{\sqrt{m}}\sum_{i\in
I^{\prime}}c_{2}\varepsilon_{i}\right|\geq u\right).$

Fix a realization $(Z_{i})_{i=1}^{n}$ satisfying $|I^{\prime}|\geq c_{3}|I|$
and it suffices to show that

$\displaystyle\mathbb{P}_{\varepsilon}\left(\left|\frac{1}{\sqrt{m}}\sum_{i\in
I^{\prime}}c_{2}\varepsilon_{i}\right|\geq
c_{4}\sqrt{\log\left(\frac{n}{k}\right)}\right)\geq\frac{4c_{1}k}{n}$ (5.24)