# Optimal non-gaussian Dvoretzky-Milman embeddings

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

We 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 Dvoretzky-Milman Theorem is one of most remarkable results in Asymptotic
Geometric Analysis. Dvoretzky proved in [8] that $\ell_{2}$ is _finitely
represented_ in any infinite dimensional normed space: that any infinite
dimensional normed space has subspaces of arbitrarily high (finite) dimension
that are almost Euclidean in the _Banach-Mazur sense_ (for the definition of
that distance see, e.g., [2]). Dvoretzky’s proof was finite dimensional: he
showed that there is $d=d(n,\varepsilon)$ that tends to infinity with $n$ for
any fixed $\varepsilon>0$, such that every $n$-dimensional normed space has a
subspace of dimension $d$ that is $1+\varepsilon$ close to Euclidean. As it
happens, his estimate on $d(n,\varepsilon)$ was suboptimal, and was
dramatically improved by Milman in his seminal work [19].

Milman showed that any finite dimensional normed space
$(\mathbb{R}^{n},\|\cdot\|)$ has a _critical dimension_ $d^{\ast}$, and a
typical subspace of dimension $c(\varepsilon)d^{\ast}$—with respect to the
Haar measure on the Grassmann manifold of that dimension—is almost Euclidean.
Moreover, every normed space is isometric to a space for which $d^{\ast}\geq
c_{1}\log n$.

The idea behind Milman’s proof is based on the fact that Lipschitz functions
are almost constant on the sphere. More accurately and in the gaussian version
of the theorem, set $d\leq d^{\ast}$ and let $G_{1},\dots,G_{d}$ be
independent copies of the standard gaussian random vector $G$ in
$\mathbb{R}^{n}$. One can show that a typical realization of the function
$x\mapsto\|\sum_{i=1}^{d}x_{i}G_{i}\|$ is almost constant on $S^{d-1}$. As a
result, there is $\Lambda>0$ such that for every $x\in\mathbb{R}^{d}$,

$(1-\varepsilon)\|x\|_{2}\leq\Lambda^{-1}\left\|\sum_{i=1}^{d}x_{i}G_{i}\right\|\leq(1+\varepsilon)\|x\|_{2}.$
(1.1)

Equation 1.1 follows from two features of the gaussian vector: firstly,
_rotation invariance_ , in particular that for any $x\in\mathbb{R}^{d}$,
$\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 a
$d$-dimensional subspace selected according to the Haar measure on the right
Grassmann manifold. Those were the only examples of random ensembles that
satisfied both rotation invariance and suitable concentration. Our goal in
what follows is to construct more general ensembles (in fact, ensembles that
can be heavy-tailed) that exhibit Euclidean subspaces of the optimal dimension
in arbitrary normed spaces.

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, compact, centrally-symmetric subset of
$\mathbb{R}^{n}$ with a nonempty interior. Denote by
$\left\langle\cdot,\cdot\right\rangle$ 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$. Consider the standard gaussian random vector $G$
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) is the following.

######  Theorem 1.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$.

######  Remark 1.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$.

The proof of Theorem 1.1 with the optimal
$c_{1}(\varepsilon)\sim\varepsilon^{2}$ is due to Gordon [9] (see also
Schechtman’s proof [23]). A simpler argument that follows Milman’s original
proof can be found in [21], leading to the slightly suboptimal estimate of
$c_{1}(\varepsilon)\sim\frac{\varepsilon^{2}}{\log(1/\varepsilon)}$. A
detailed survey on the Dvoretzky-Milman Theorem can be found in [2].

The key features of the gaussian ensemble $A$ that lead to the proof of
Theorem 1.1, namely, “gaussian concentration” and rotation invariance are
rather special. At least one of the two fails when it comes to other natural
choices of random vectors. For example, if $A$ is generated by the Bernoulli
random vector $(\varepsilon_{i})_{i=1}^{n}$—uniformly distributed in
$\\{-1,1\\}^{n}$—, and $\|\cdot\|=\|\cdot\|_{\infty}$, then
$x\mapsto\mathbb{E}\|Ax\|$ is not even equivalent to a constant on $S^{d-1}$.
The reason for the gap between $\inf_{x\in S^{d-1}}\|Ax\|_{\infty}$ and
$\sup_{x\in S^{d-1}}\|Ax\|_{\infty}$ is straightforward: if $x=e_{i}$,
$\|Ax\|_{\infty}=\|(\varepsilon_{1},...,\varepsilon_{n})\|_{\infty}=1$, but if
$x$ is in a ‘diagonal direction’, $\|Ax\|_{\infty}$ is close to
$\|G\|_{\infty}$, and for a typical realization the latter behaves like
$\sqrt{\log n}$ (see, e.g., [15] 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 [12]).

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 [18]), but none of them preforms well in an _arbitrary_ normed space.

The _key_ to our construction of general Dvoretzky-Milman ensembles 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 iid rows $(X_{i})_{i=1}^{m}$ generated by a random vector $X$,

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

and 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 independent copies of a random vector $Z$ in
$\mathbb{R}^{n}$ that has iid coordinates; in particular, $D$ has iid entries.
We will always assume that $(X_{i})_{i=1}^{m}$ and $(Z_{i})_{i=1}^{m}$ are
independent.

As a preliminary test case to this idea’s validity, let $Z$ be the standard
gaussian random vector in $\mathbb{R}^{n}$. Clearly $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 subgaussian333A random
vector $Z$ is called $(L-)$subgaussian if $\|\left\langle
Z,x\right\rangle\|_{L_{p}}\leq L\sqrt{p}\|\left\langle
Z,x\right\rangle\|_{L_{2}}$ for every $x\in\mathbb{R}^{n}$ and $p\geq 2$.,
isotropic random vector $Z$: as noted previously, if $\Gamma=\mathrm{Id}$, $Z$
is the Bernoulli vector and $\|\cdot\|=\|\cdot\|_{\infty}$, there is a
logarithmic gap between $\inf_{x\in S^{m-1}}\|D\Gamma x\|$ and $\sup_{x\in
S^{m-1}}\|D\Gamma x\|$, and 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 rotation invariant, and is an almost isometric embedding of
$\ell_{2}^{d}$ in $\ell_{2}^{m}$, and $D\colon\mathbb{R}^{m}\to\mathbb{R}^{n}$
has iid entries and isotropic subgaussian columns, then with high probability,
$(D\Gamma\mathbb{R}^{d})\cap K$ is almost Euclidean.

Before we list the assumptions that we require and specify the choices of $d$
and $m$, let us recall some well-known definitions and facts.

######  Definition 1.3.

A centred random vector $X$ in $\mathbb{R}^{d}$ satisfies $L_{p}-L_{2}$ norm
equivalence with constant constant $L$ if for any $u\in\mathbb{R}^{d}$,

$\displaystyle\|\left\langle X,u\right\rangle\|_{L_{p}}\leq L\|\left\langle
X,u\right\rangle\|_{L_{2}}.$ (1.2)

Note that if, in addition, $X$ is isotropic (that is, $X$ is centred and its
covariance is the identity), then (1.2) is equivalent to $\sup_{u\in
S^{d-1}}\|\left\langle X,u\right\rangle\|_{L_{p}}\leq L$.

Next, given $X_{1},...,X_{m}$ that are independent, selected according to the
isotropic random vector $X$, set

$\rho_{d,m}=\sup_{u\in S^{d-1}}\left|\frac{1}{m}\sum_{i=1}^{m}\left\langle
X_{i},u\right\rangle^{2}-1\right|.$

Observe that the singular values of the random matrix
$\Gamma=m^{-1/2}\sum_{i=1}^{m}\left\langle X_{i},\cdot\right\rangle e_{i}$
satisfy that

$1-\rho_{d,m}\leq\lambda_{\rm{min}}^{2}(\Gamma)\leq\lambda_{\rm{max}}^{2}(\Gamma)\leq
1+\rho_{d,m}.$

The behaviour of $\rho_{d,m}$ is well-understood in rather general situations
(see, e.g., [1, 11, 17, 25]). It turns out that under minimal assumptions on
$X$ and with high probability, the random matrix $\Gamma$ satisfies the
_quantitative Bai-Yin asymptotics_ (see [4]), namely that $\rho_{d,m}\leq
c(d/m)^{1/2}$ for an absolute constant $c$.

The assumptions we require on the random vectors $X$ and $Z$ are as follows:
(A1) $X$ is an isotropic, rotation invariant random vector in $\mathbb{R}^{d}$
that satisfies $L_{4}-L_{2}$ norm equivalence with constant $L\geq 1$.
Moreover, with probability at least $1-\eta$, $\rho_{d,m}\leq
B(d/m)^{2/\alpha}$ for some constants $B\geq 1$ and $\alpha\geq 4$. (A2) $Z$
is an isotropic, symmetric, $L$-subgaussian random vector in $\mathbb{R}^{n}$
that has iid coordinates.

A key component in our construction relies on the recent results of [5]. In a
nutshell, the random set $\Gamma S^{d-1}$ has a rather specific structure: the
coordinates of each vector $(\left\langle X_{i},u\right\rangle)_{i=1}^{m}$
concentrate around a well-determined set of values, endowed by the probability
distribution of $X$. More accurately, denote by $a^{\sharp}$ the monotone non-
decreasing rearrangement of a vector $a\in\mathbb{R}^{m}$ and set, for $1\leq
s\leq m$,

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

Let $F_{\left\langle X,u\right\rangle}^{-1}$ be the (right-)inverse
distribution function of $\left\langle X,u\right\rangle$ and put, for
$i=1,\dots,m$,

$\lambda_{i}^{u}=m\int_{(\frac{i-1}{m},\frac{i}{m}]}F_{\left\langle
X,u\right\rangle}^{-1}(p)\,dp.$

######  Proposition 1.4 ([5]).

Then there are constants $c_{1},c_{2},c_{3}$ that depend on $L,B,\alpha$ such
that the following holds. Suppose that Assumption (A1) is satisfied with the
values $L,B,\alpha$. Then, for every $d\geq 1$ and $m\geq c_{1}d$, with
probability at least $1-\eta-\exp(-d)$,

$\sup_{u\in S^{d-1}}\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
X_{i},u\right\rangle^{\sharp}-\lambda_{i}^{u}\right|^{2}\right)^{1/2}\leq
c_{2}\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_{3}\left(\left(\frac{s}{m}\right)^{1/4}+\left(\frac{d}{m}\right)^{1/\alpha}\log\left(\frac{m}{d}\right)\right).$

Denote by $\Omega(\mathbb{X})$ the event in which both the assertion of
Proposition 1.4 holds and $\rho_{d,m}\leq B(d/m)^{2/\alpha}$.

Note that if $X$ is rotation invariant then $\lambda^{u}=\lambda^{v}$ for
every $u,v\in S^{d-1}$. Thus, Proposition 1.4 implies that after replacing the
vectors in $\Gamma S^{d-1}$ by their monotone non-decreasing ordering, the
resulting set has a small Euclidean diameter. This is the key feature that
‘generates’ sufficient invariance. As a result there is no need to assume that
the random vector $Z$ is rotation invariant.

We are now ready to formulate our main result. Recall that
$\Gamma\colon\mathbb{R}^{d}\to\mathbb{R}^{m}$ is the random operator whose
rows are $(X_{i})_{i=1}^{m}$ and $D\colon\mathbb{R}^{m}\to\mathbb{R}^{n}$ is
the random operator whose columns are $(Z_{i})_{i=1}^{m}$. And, assume (as we
may—see Remark 1.2) that $d^{\ast}(K)\geq C_{0}\log n$ for an absolute
constant $C_{0}$.

######  Theorem 1.5.

There are constants $c_{1}\leq\frac{1}{2}$, $c_{2},\dots,c_{8}$ that depend on
$L,B,\alpha,C_{0}$ such that the following holds. Suppose that Assumptions
(A1) and (A2) are satisfied with the values $L,B,\alpha$. Let $\varepsilon\leq
c_{1}$, $n\geq c_{2}$, $m=c_{3}(d^{\ast}(K))^{\alpha}\quad\text{and}\quad
d\leq c_{4}\frac{\varepsilon^{2}}{\log(1/\varepsilon)}d^{\ast}(K).$ Then there
is some $\Lambda\in[c_{5}\mathbb{E}\|G\|,c_{6}\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_{7}\varepsilon^{2}d^{\ast}(K))$, $\sup_{u\in
S^{d-1}}\left|\frac{\|D\Gamma u\|}{\Lambda}-1\right|\leq c_{8}\varepsilon.$

######  Remark 1.6.

The assumption that $X$ satisfies $L_{4}-L_{2}$ norm equivalence is necessary:
by [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 $\rho_{d,m}$ is
not well-behaved and $\Gamma$ cannot even be an isomorphic embedding of
$\ell_{2}^{d}$ in $\ell_{2}^{m}$. At the same time, 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$.

######  Remark 1.7.

The idea of factoring through a higher dimensional space was used in [15] to
prove the 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 1.5. Before we dive
into technical details, let us give an example of such an ensemble, for a
heavy-tailed choice of $X$ and $Z=(\varepsilon_{1},...,\varepsilon_{n})$ — the
Bernoulli vector.

######  Example 1.8.

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)$. Let $W$ be
distributed uniformly in $S^{d-1}$ and consider a symmetric random variable
$v$ for which $\mathbb{E}v^{2}=1$ and $\|v\|_{L_{7}}\leq L$ (but potentially
$v\notin L_{q}$ for $q>7$).

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_{7}-L_{2}$
norm equivalence with a constant $L^{\prime}\sim L$. By [25], with probability
at least $1-\frac{1}{d}$,

$\rho_{d,m}\leq c_{2}(L)\left(\max_{1\leq i\leq
m}\frac{\|X_{i}\|_{2}^{2}}{m}+\sqrt{\frac{d}{m}}\right).$

Moreover, for $m\geq d^{4}$, by Markov’s inequality,

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

where we used that $q\geq 7$ in the last inequality. Hence, with probability
at least $1-\frac{2}{d}$, $\rho_{d,m}\leq c_{3}(L)\sqrt{d/m}$, and Assumption
(A1) is satisfied with $\eta=\frac{2}{d}$, $\alpha=4$ and a constant $B$
depending only on $L$.

Now put $m\sim(d^{*}(K))^{4}$ and consider a realization of $\Gamma$ for which
the assertion of Proposition 1.4 holds and $\rho_{d,m}\leq c_{3}\sqrt{d/m}$,
i.e. $(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$. By Theorem 1.5, 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.

######  Remark 1.9.

Let us note that the set of Euclidean subspaces generated by our operator
$D\Gamma$ significantly differs from those generated by the standard approach.
Have, for example, the setting in Example 1.8. We claim that the Haar measure
of all $d$-dimensional subspaces generated by $D\Gamma$ is zero.

Indeed, each subspace we generate is $d$-dimensional and contained in the span
of $m$ vertices of the combinatorial cube in $\mathbb{R}^{n}$. Since there are
$\binom{2^{n}}{m}$ such $m$-dimensional subspaces, it is enough to show that
the probability (with respect to the Haar measure on the Grassmann manifold
$G_{d,m}$) that a $d$-dimensional subspace of $\mathbb{R}^{n}$ is contained in
a _fixed_ $m$-dimensional subspace of $\mathbb{R}^{n}$ is 0. By rotation
invariance, we may assume that the $m$-dimensional subspace is ${\rm
span}(e_{1},...e_{m})$. Moreover,

$\mathbb{P}_{G_{d,m}}\left(E\in{\rm
span}(e_{1},...e_{m})\right)=\mathbb{P}_{O_{n}}\left(Oe_{i}\in{\rm
span}(e_{1},...e_{m})\text{ for }1\leq i\leq d\right)$

where $\mathbb{P}_{O_{n}}$ is the Haar measure on the orthonormal group
$O_{n}$. But $Oe_{i}$ is distributed as $G/\|G\|_{2}$, and almost surely all
coordinate of the standard gaussian are nonzero.

Recall that the operator $D$ in Example 1.8, generated by the Bernoulli
vector, does not ‘act well’ on the entire sphere $S^{m-1}$: 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 of $S^{m-1}$ 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\|)$, with
high probability 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 Proposition 1.4. Obviously, the random operator
$D\Gamma$ is far from being gaussian, but we shall show that thanks to
Proposition 1.4, $D\Gamma$ still exhibits some key gaussian features.
Specifically, because vectors in $\Gamma S^{d-1}$ inherit $X$’s rotation
invariance in the sense described in Proposition 1.4, the function
$x\mapsto\mathbb{E}_{Z}\|Dx\|$ is almost constant on $\Gamma S^{d-1}$. And, in
addition, Proposition 1.4 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 (a behaviour that does not hold for an arbitrary
$y\in S^{m-1}$).

##  2 Preliminaries and a reduction step

We start 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$. The cardinality of finite
sets is denoted by $|\cdot|$. 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.1 Preliminaries

Let us consider some implications of the assumptions made in Theorem 1.5. We
can and do assume that $\varepsilon^{2}d^{\ast}(K)\geq 1$—otherwise, the claim
is trivially true.

Let $\varepsilon\leq c_{0}$ for a constant $c_{0}=c_{0}(L)\leq 1/2$. The
choice of $c_{0}$ is specified in Lemma 5.3. 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).$ (2.1)

The choice of $c_{1}$ and $c_{2}$ is specified in Theorem 4.1.

Recall that $\Omega(\mathbb{X})$ is the event in which the assertion of
Proposition 1.4 holds and $\rho_{d,m}\leq B(d/m)^{2/\alpha}$. Consider
$(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$. Since $X$ is rotation invariant it
follows that for every $u,v\in S^{d-1}$, $\lambda^{u}=\lambda^{v}=\lambda$;
hence

$\displaystyle\sup_{u\in
S^{d-1}}\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
X_{i},u\right\rangle^{\sharp}-\lambda_{i}\right|^{2}\right)^{1/2}$
$\displaystyle\leq
c(L,B)\left(\frac{d}{m}\right)^{1/\alpha}\log\left(\frac{m}{d}\right)$

and

$\displaystyle H_{s,m}$ $\displaystyle\leq
c^{\prime}(L,B)\left(\left(\frac{s}{m}\right)^{1/4}+\left(\frac{d}{m}\right)^{1/\alpha}\log\left(\frac{m}{d}\right)\right).$

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

$m=c_{3}(c_{1},c_{2},L,B,\alpha,\beta)\cdot(d^{\ast}(K))^{\alpha},$ (2.2)

then

$\frac{H_{s,m}}{\sqrt{s}}\leq\frac{\beta}{d^{\ast}(K)},\qquad\sup_{u\in
S^{d-1}}\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
X_{i},u\right\rangle^{\sharp}-\lambda_{i}\right|^{2}\right)^{1/2}\leq\frac{1}{\sqrt{d^{\ast}}}\leq\varepsilon,$
(2.3)

and

$\sup_{u\in S^{d-1}}\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
X_{i},u\right\rangle^{\sharp}-\left\langle
X_{i},v\right\rangle^{\sharp}\right|^{2}\right)^{1/2}\leq 2\varepsilon.$ (2.4)

The choice of $\beta$ is specified in Theorem 4.1. Moreover, since
$\rho_{d,m}\leq B(d/m)^{2/\alpha}$, we may also assume that $\rho_{d,m}\leq
1$. Thus,

$\displaystyle\sup_{u\in S^{d-1}}\frac{1}{m}\sum_{i=1}^{m}\left\langle
X_{i},u\right\rangle^{2}\leq 2.$ (2.5)

Finally, $d^{\ast}(K)\geq C_{0}\log n$ for an absolute constant $C_{0}$. We
only consider $n$ sufficiently large, specifically, $n\geq c_{4}(L,\alpha)$
for a suitable constant $c_{4}$ that is specified in Theorem 5.1.

###  2.2 A reduction step

Let $W\subset S^{d-1}$ be a maximal $\varepsilon$-separated subset with
respect to the Euclidean norm. Recall that $Z$ is an isotropic, symmetric,
$L$-subgaussian random vector taking values in $\mathbb{R}^{n}$ and has iid
entries444The fact that $Z$ has iid coordinates is used only in Section 5
where we prove condition (2.7) below., let $(Z_{i})_{i=1}^{m}$ be independent
copies of $Z$ and define $\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\|.$

######  Lemma 2.1.

Let $\varepsilon\leq 1/2$ and assume that there are $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. (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\|.$ (2.6)

  2. (2)

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

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

  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\|.$ (2.8)

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.$

We show that (1)-(3) are satisfied with $\mathcal{A}=\Omega(\mathbb{X})$.
Specifically, (3) is established in Theorem 3.3; (1) is verified in Theorem
4.1; and (2) is proved in Theorem 5.1.

###### Proof of Lemma 2.1.

Since $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}\gamma_{j}w_{j}^{u},$ (2.9)

where $\gamma_{0}=1$ and $|\gamma_{j}|\leq\varepsilon^{j}$ for $j\geq 1$.
Using the 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.$ (2.10)

To that end, for $w\in W$

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

By combining (2.6) and (2.7),
$(\ast)\leq\frac{c_{1}}{c_{2}}\varepsilon\Lambda$; and by invoking (2.7) and
(2.8), $(\ast\ast)\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 (2.9).
Using the estimates on $(\ast)$ and $(\ast\ast)$ 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$

##  3 The conditional expectation is almost constant—proof of (2.8)

Let us show that for every realization $(X_{i})_{i=1}^{m}$ that satisfies
(2.4), the oscillation of $u\mapsto\mathbb{E}_{Z}\Psi(u)$ is at most of order
$\varepsilon\mathbb{E}\|G\|$. To that end, define the distance $w_{2}$ on
$\mathbb{R}^{m}$ by

$\displaystyle
w_{2}(x,y)=\min_{\sigma}\left(\sum_{i=1}^{m}\left(x_{i}-y_{\sigma(i)}\right)^{2}\right)^{1/2},$
(3.1)

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

######  Remark 3.1.

The reason for the name $w_{2}$ is the obvious connection (3.1) has with
$\mathcal{W}_{2}$—the second order Wasserstein distance (see Remark 3.4),
namely

$w_{2}(x,y)=\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 3.2.

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 w_{2}(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}$, and by gaussian domination
(which is an immediate consequence of Talagrand’s majorizing measure theorem,
see, e.g., [24, Theorem 2.10.11]), 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 3.2, 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(\Gamma S^{d-1}\right)=\left\\{\left(\frac{\left\langle
X_{i},u\right\rangle}{\sqrt{m}}\right)_{i=1}^{m}:u\in S^{d-1}\right\\}$

has a small diameter with respect to the distance $w_{2}$. That follows
immediately from (2.4): indeed, for every $x,y\in\Gamma S^{d}$,
$w_{2}(x,y)\leq 2\varepsilon$.

In particular, we have the following.

######  Theorem 3.3.

There is a constant $c$ that depends on $L$ such that for every
$(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$,

$\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\|.$

######  Remark 3.4.

The condition in Theorem 1.5 that $X$ is rotation invariant can be relaxed in
the following sense: For $u\in S^{d-1}$, let $\mu^{u}$ be the law of
$\left\langle X,u\right\rangle$. The (second order) Wasserstein distance
between two probability measures $\alpha,\beta$ on $\mathbb{R}$ with finite
second moment is

$\mathcal{W}_{2}(\alpha,\beta)=\inf_{\pi}\left(\int_{\mathbb{R}\times\mathbb{R}}(x-y)^{2}\,\pi(dx,dy)\right)^{1/2},$

where the infimum is taken over all probability measures $\pi$ on
$\mathbb{R}\times\mathbb{R}$ with first marginal $\alpha$ and second marginal
$\beta$. Using this notation, the assertion of Theorem 1.5 remains valid under
the assumption that $\sup_{u,v\in
S^{d-1}}\mathcal{W}_{2}(\mu^{u},\mu^{v})\leq\varepsilon$ (clearly, if $X$ is
rotation invariant then for any $u,v\in S^{d-1}$,
$\mathcal{W}_{2}(\mu^{u},\mu^{v})=0$). However, as optimising the choice of
$X$ in this sense is not the focus of the article, we shall not pursue this
point further.

##  4 Uniform concentration on the net—proof of (2.6)

The second component needed in the proof of Theorem 1.5 is concentration on
the net. Recall that $W\subset S^{d-1}$ is a maximal $\varepsilon$-separated
subset with respect to the Euclidean norm, and we need to show that there is a
number $\Lambda$ (that happens to be proportional to $\mathbb{E}\|G\|$), such
that for every realization $(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$, with high
probability with respect $(Z_{i})_{i=1}^{m}$,

$\sup_{u\in W}\left|\Psi(u)-\Lambda\right|\leq c(L)\varepsilon\Lambda.$ (4.1)

######  Theorem 4.1.

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

$\displaystyle 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))].$ (4.2)

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\begin{split}\sup_{u\in
B_{2}^{d}}\frac{1}{m}\sum_{i=1}^{m}\left\langle X_{i},u\right\rangle^{2}&\leq
2\quad\text{and}\\\ 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}&\leq\beta\frac{\sqrt{s}}{d^{\ast}(K)}.\end{split}$
(4.3)

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

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

On the assumptions in Theorem 4.1: Observe that all of its assumptions are
satisfied by the choices made in Theorem 1.5 and for
$(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$. Indeed,

  1. 1.

(4.3) follows from (2.3) and (2.5).

  2. 2.

The condition on $m$ holds because $d^{\ast}(K)\geq C(L)$ for a large constant
$C$ that we are free to choose. And since $m$ is proportional to
$(d^{\ast}(K))^{\alpha}$ for $\alpha\geq 4$ (see (2.2)), it follows that (4.2)
is satisfied as well.

The proof of Theorem 4.1 is somewhat involved. We first present its ‘road map’
and only then turn to the technical details.

###  4.1 Highlights of the proof of Theorem 4.1

It is worth stressing once again that the proof of Theorem 4.1 does not simply
follow from gaussian concentration even though $Z$ is subgaussian. In fact, it
was recently shown that gaussian-like concentration in a subgaussian setup is
false in general, see [12]. 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}$, and $\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}$._

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 $i$
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 sets $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}$.

It turns out 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}\|:$

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 $i\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)$.

###  4.2 Preliminary structural estimates for Theorem 4.1

The following lemma contains well-known facts on subgaussian processes.

######  Lemma 4.2.

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. Let $Z$ be an isotropic,
$L$-subgaussian random variable in $\mathbb{R}^{n}$, let $Z_{1},\dots,Z_{m}$
be independent copies of $Z$ and set ${\cal R}(K^{\circ})=\sup_{t\in
K^{\circ}}\|t\|_{2}$. Then:

  1. (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).$ (4.4)

  2. (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).$ (4.5)

  3. (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.$ (4.6)

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

###### Sketch of the proof of Lemma 4.2.

Let $\Sigma_{r}\subset S^{m-1}$ be the set of $r$-sparse unit vectors, that
is, $\Sigma_{r}=\\{x\in S^{m-1}:|\\{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 $\binom{m}{r}$ 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}$ (see, e.g., [2, Corollary 4.1.15]). A convexity
argument (just as in the proof of Lemma 2.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 straightforward 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\left(\mathbb{E}\left\|\sum_{j=1}^{m}x_{j}Z_{j}\right\|^{p}\right)^{1/p}$
$\displaystyle\leq c_{1}L(\mathbb{E}\|G\|^{p})^{1/p}.$ (4.7)

Moreover, by the strong-weak inequality for the gaussian measure (which
follows directly from the gaussian concentration inequality, see, e.g., [14,
Lemma 3.1]),

$(\mathbb{E}\|G\|^{p})^{1/p}\leq c_{2}(\mathbb{E}\|G\|+\sqrt{p}{\cal
R}(K^{\circ})).$

When applied to $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
(see, e.g., [6, Theorem 2.9]), with probability at least
$1-2\exp(-c_{6}r\log(em/r))$, we have that $|\\{i:\delta_{i}=1\\}|\leq r$, as
claimed. ∎

Let $Z$ be the random variable as in Theorem 1.5. For $1\leq r\leq m$, denote
by $\Omega_{r}(\mathbb{Z})$ the set of all $(Z_{i})_{i=1}^{m}$ such that both
(4.4) and (4.6) hold.

###  4.3 Proof of Theorem 4.1—part 1

Throughout this section, denote by $C_{0},C_{1}$ the absolute constants from
Lemma 4.2. The constants $c,c_{0},c_{1},c_{2}$ etc. depend on $L$, $C_{0}$ and
$C_{1}$. 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),$ (4.8)

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

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 4.4 that the
conditions are satisfied under the assumptions of Theorem 4.1.

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
2$.

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 choice of $s$ and the definitions of
$H_{s,m}$ and $\Omega_{s}(\mathbb{Z})$ 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}$ the
following holds:

If $H_{s,m}\leq c_{1}\varepsilon\qquad{\rm and}\qquad s\log(em/s)\leq
c_{1}^{\prime}d^{*}(K),$ (4.9) 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 (4.5) and an identical argument, the conditions in (4.9) also imply that

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

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 (4.8) and set

$J_{u,r}=\left\\{j\in\\{1,\dots,m\\}:\left\|\tfrac{1}{\sqrt{m}}\left\langle
X_{j},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}$; hence,

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

Moreover, by the definition of $\Omega_{r}(\mathbb{Z})$,
$|\\{j:\|Z_{j}\|\geq\phi(r)\\}|\leq r$. Therefore,

$\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})$,

$\|\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}$, we
have the following:

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),$ (4.12) then $\sup_{u\in
B_{2}^{d}}\|\diamondsuit_{u}\|\leq\varepsilon\mathbb{E}\|G\|.$

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

######  Lemma 4.3.

If (4.12) 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}$ and set $Q=|\\{i\in
I_{u,s}^{c}:\|Z_{i}\|\geq\phi(r)\\}|$. 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, by (4.11),

$\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}_{Z}\sqrt{Q}S(Q)\leq c\sqrt{r}\mathbb{E}\|G\|$ for a
suitable constant $c$. And indeed, 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=(\ast)+(\ast\ast).$

By (4.5), 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 (4.12) and the choice of $d^{\ast}(K)$,
$\mathbb{E}_{Z}(\ast)\leq c_{1}\sqrt{r}\mathbb{E}\|G\|$.

To estimate $\mathbb{E}_{Z}(\ast\ast)$, apply the Cauchy-Schwartz inequality
to each term $\mathbb{E}_{Z}\mathbbm{1}_{(2^{s},2^{s+1}]}(Q)S(2^{s+1})$:

$\mathbb{E}_{Z}(\ast\ast)\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 4.2,
$\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}(\ast\ast)\leq
c_{3}\sqrt{r}\mathbb{E}\|G\|$, as claimed. ∎

Step 3 — $\heartsuit_{u}$: 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}).$
(4.13)

######  Remark 4.4.

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 (4.13) 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 [13].

######  Theorem 4.5.

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).$ (4.14)

In the case that interests us, $k=|I_{u,s}^{c}|=m-s$ and
$\mathcal{F}=\mathcal{F}_{u}$. We start by verifying the assumptions of
Theorem 4.5 for the empirical process from (4.13).

######  Lemma 4.6.

The set $\mathcal{F}_{u}$ satisfies the assumptions in Theorem 4.5 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 $1\leq i\leq k$. Indeed, since $\|t\|=\|-t\|$ and $Y_{i}$ is symmetric,

$\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 2$ 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 2\sup_{t\in K^{\circ}}\|t\|_{2}^{2}=2{\cal
R}^{2}(K^{\circ}).$

Finally, since $(Z_{i})_{i=1}^{m}$ and $(\varepsilon_{i}Z_{i})_{i=1}^{m}$ have
the same distribution by the symmetry of $Z$, a standard Bernoulli contraction
argument (see, e.g., [14, Theorem 4.4]) applied conditionally on
$(X_{i})_{i=1}^{m}$ and $(Z_{i})_{i=1}^{m}$ shows that

$\displaystyle\mathbb{E}U$
$\displaystyle=\mathbb{E}_{Z}\mathbb{E}_{\varepsilon}\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)\\}}\varepsilon_{i}\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\|=(\ast).$

Since $(Z_{i})_{i=1}^{m}$ are independent and $L$-subgaussian, gaussian
domination and the assumption that $\frac{1}{m}\sum_{i=1}^{m}\left\langle
X_{i},u\right\rangle^{2}\leq 2$ imply that $(\ast)\leq cL\mathbb{E}\|G\|$ for
an absolute constant $c$. ∎

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

$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).$

It follows from the definition of $\phi$ that if

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

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

$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
(4.13)), it follows from Theorem 4.5 that for suitable constants $c_{7}$,
$c_{7}^{\prime}$ and $c_{7}^{\prime\prime}$ we have that:

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)),$ (4.15) 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 4.7.

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$.

###  4.4 Proof of Theorem 4.1

First, let us show that for well-chosen $s,r,m$, and $d$, all the requirements
collected in (4.9), (4.12), and (4.15) 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 (4.9) and (4.12)
are satisfied for suitable choices of $c_{1},c_{2}$. Moreover, as noted
previously, one may assume without loss of generality that
$\varepsilon^{2}d^{\ast}(K)\geq 1$—otherwise the claim in Theorem 4.1 is
trivially true; thus, $m$ satisfies (4.15) for suitable choice of $c_{4}$.

Next, collecting the requirements on $H_{s,m}$ from (4.9), (4.12), and (4.15),
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\\}.$
(4.16)

To that end, recall that $r\leq c_{2}s$ and that $\varepsilon\geq
1/\sqrt{d^{\ast}(K)}$; in particular, the third term in (4.16) is the dominant
one, and (4.16) 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$, we have that $s\log(em/s)\geq
c_{7}\varepsilon^{2}d^{\ast}(K)$. Repeating the argument for $r$, it is
evident from Lemma 4.2 that

$\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 4.2.

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$, with $\mathbb{P}_{Z}$-probability at least
$1-2\exp(-c_{8}\varepsilon^{2}d^{*}(K))$

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

and $\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\|.$ (4.17)

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

##  5 A lower bound on the conditional expectation—proof of (2.7)

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

######  Theorem 5.1.

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.1)

then

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

######  Remark 5.2.

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

$\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 the proof relied on the construction of an
approximation of $K^{\circ}\subset\mathbb{R}^{n}$ consisting of $\exp(cm)$
points. 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.

Note that the condition $m\geq c_{1}\log n$ in Theorem 5.1 is satisfied in the
setting of Theorem 1.5. Indeed, $m$ is proportional to
$(d^{\ast}(K))^{\alpha}$ for $\alpha\geq 4$ (see (2.2)), $d^{\ast}(K)\geq
C_{0}\log n$ for an absolute constant $C_{0}$, and $n\geq C(L,\alpha)$ for a
constant $C$ that we are free to choose as large as needed.

We will verify in Lemma 5.3 that there are constants $\delta,\eta>0$ depending
only on $L$ such that (5.1) is satisfied.

Finally, by gaussian domination, if $\frac{1}{m}\sum_{i=1}^{m}\left\langle
X_{i},v\right\rangle^{2}\leq 2$ then $\mathbb{E}_{Z}\Psi(v)\leq
C_{2}L\mathbb{E}\|G\|$ for an absolute constant $C_{2}$. Thus, in the setting
of Theorem 1.5,

$\mathbb{E}_{Z}\Psi(v)\in[C_{3}\mathbb{E}\|G\|,C_{4}\mathbb{E}\|G\|]$

for constants $C_{3}$ and $C_{4}$ that depend only on $L$.

Recall that for $1\leq i\leq m$,
$\lambda_{i}^{v}=m\int_{(\frac{i-1}{m},\frac{i}{m}]}F_{\left\langle
X,v\right\rangle}^{-1}(p)\,dp$.

######  Lemma 5.3.

Let $X$ satisfy $L_{4}-L_{2}$ norm equivalence with constant $L$. There are
constants $\delta,\eta>0$ that depend only on $L$ such that the following
holds. If $m\geq 2/\delta$ and

$\displaystyle\left(\frac{1}{m}\sum_{i=1}^{m}\left|\left\langle
X_{i},v\right\rangle^{\sharp}-\lambda_{i}^{v}\right|^{2}\right)^{1/2}\leq\eta\sqrt{\delta},$
(5.2)

then

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

Note that (5.2) holds for $(X_{i})_{i=1}^{m}\in\Omega(\mathbb{X})$. Indeed, by
(2.3), the left hand side in (5.2) is smaller than $2\varepsilon$, and we may
assume that $\varepsilon\leq C$ for an arbitrarily small constant $C=C(L)$,
e.g., for $C=\eta\sqrt{\delta}$.

###### Proof.

By the $L_{4}-L_{2}$ norm equivalence and the Paley-Zygmund inequality (see,
e.g., [7, Corollary 3.3.2]), 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.$

In particular $\mathbb{P}(\left\langle X,v\right\rangle\geq 2\eta)\geq
2\delta$ or $\mathbb{P}(\left\langle X,v\right\rangle\leq-2\eta)\geq 2\delta$,
and we focus without loss of generality on the latter case. Then clearly

$\lambda^{v}_{i}\leq-2\eta\quad\text{for }i=1,\dots,2\delta m.$

It is straightforward to verify that if $\left\langle X_{\delta
m},v\right\rangle^{\sharp}>-\eta$, then (5.2) cannot be true. In particular,
(5.2) implies that $|\\{i:\left\langle
X_{i},v\right\rangle\leq-\eta\\}|\geq\delta m$ and (5.1) holds. ∎

###  5.1 Proof of Theorem 5.1

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

######  Lemma 5.4.

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.5.

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.3)

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.4)

The proof of Lemma 5.5 relies on the an estimate due to Montgomery-Smith [20].
To formulate it, denote by $\lfloor u\rfloor$ the largest integer that is
smaller than $u$.

######  Lemma 5.6.

There are absolute constants $c_{1},c_{2}$ and $c_{3}$ such that the following
holds. Let $\varepsilon=(\varepsilon_{i})_{i=1}^{m}$ be the Bernoulli vector
and set $0<u\leq m-2$. Then, for every $x\in\mathbb{R}^{m}$, 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).$ (5.5)

###### Proof of Lemma 5.5.

We only present a proof of (5.4). 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, by the Paley–Zygmund inequality,
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}$. Let
$\varepsilon=(\varepsilon_{i})_{i=1}^{m}$ be the Bernoulli vector, independent
of $(Z_{i})_{i=1}^{m}$. Setting

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

then clearly $\mathbb{P}\left(|I^{\prime}|\geq c_{3}|I|\right)\geq 1/2$. 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|$.
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.6)

for a suitable constant $c_{4}$. To that end, by Lemma 5.6 there are absolute
constants $c_{5},c_{6},c_{7}$ such that for $0\leq u^{2}\leq|I^{\prime}|-2$,
with probability at least $c_{5}\exp(-c_{6}u^{2})$,

$\displaystyle\left|\sum_{i\in
I^{\prime}}\frac{c_{2}}{\sqrt{m}}\varepsilon_{i}\right|\geq
c_{7}\left(\sum_{i=1}^{\lfloor
u^{2}\rfloor}\frac{c_{2}}{\sqrt{m}}+u\left(\sum_{i=\lfloor
u^{2}\rfloor+1}^{|I^{\prime}|}\frac{c_{2}^{2}}{m}\right)^{1/2}\right)=A(u).$

Let $u=c_{8}\sqrt{\log\frac{n}{k}}$ for a (small) constant
$c_{8}=c_{8}(\delta)$ and observe that for that choice of $u$, $A(u)\geq
c_{9}(\delta)u$. Indeed, as was assumed,

$|I^{\prime}|\geq c_{3}|I|\geq c_{3}\delta m\geq c_{3}\delta\log n;$

in particular $|I^{\prime}|-(\lfloor u^{2}\rfloor+1)\geq\frac{c_{3}\delta
m}{2}$ and thus $A(u)\geq c_{7}u(\sum_{i=\lfloor
u^{2}\rfloor+1}^{|I^{\prime}|}\frac{c_{2}^{2}}{m})^{1/2}\geq c_{9}(\delta)u$.
Therefore

$\displaystyle\mathbb{P}_{\varepsilon}\left(\left|\frac{1}{\sqrt{m}}\sum_{i\in
I^{\prime}}c_{2}\varepsilon_{i}\right|\geq c_{9}\cdot u\right)$
$\displaystyle\geq
c_{5}\exp\left(-c_{6}c_{8}^{2}\log\left(\frac{n}{k}\right)\right),$ (5.7)

and if $c_{8}$ is sufficiently small and $k\leq c_{10}n$, then the right hand
side in (5.7) is at least $c_{1}\frac{k}{n}$. This completes the proof. ∎

###### Proof of Theorem 5.1.

Set

$I=\\{i\in\\{1,\dots,m\\}:|\left\langle X_{i},v\right\rangle|\geq\eta\\}$

and thus $|I|\geq\delta m$. Let $\varepsilon=(\varepsilon_{i})_{i=1}^{m}$ be
the Bernoulli vector, independent of $(Z_{i})_{i=1}^{m}$. By the symmetry of
$Z$ and the contraction principle for Bernoulli processes,

$\displaystyle\begin{split}\mathbb{E}_{Z}\sup_{t\in
K^{\circ}}\sum_{i=1}^{m}\frac{1}{\sqrt{m}}\left\langle
X_{i},v\right\rangle\left\langle
Z_{i},t\right\rangle&=\mathbb{E}_{Z}\mathbb{E}_{\varepsilon}\sup_{t\in
K^{\circ}}\sum_{i=1}^{m}\varepsilon_{i}\frac{1}{\sqrt{m}}\left\langle
X_{i},v\right\rangle\left\langle Z_{i},t\right\rangle\\\
&\geq\mathbb{E}_{Z}\mathbb{E}_{\varepsilon}\sup_{t\in K^{\circ}}\sum_{i\in
I}\varepsilon_{i}\frac{1}{\sqrt{m}}\eta\left\langle
Z_{i},t\right\rangle.\end{split}$ (5.8)

Also, for every $t\in K^{\circ}$, using the symmetry of $Z$ once again,

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

In particular, it follows from (5.8) that

$\displaystyle\mathbb{E}_{Z}\sup_{t\in K^{\circ}}\sum_{i=1}^{m}\left\langle
X_{i},v\right\rangle\left\langle
Z_{i},t\right\rangle\geq\eta\mathbb{E}_{Z}\sup_{t\in
K^{\circ}}\sum_{j=1}^{n}Y_{j}t_{j}.$ (5.9)

To complete the proof one has to “replace” $(Y_{j})_{j=1}^{m}$ by independent
gaussian random variables $(g_{j})_{j=1}^{m}$. To that end, observe that by
Lemma 5.5 there is a constant $c_{1}=c_{1}(L,\delta)$ such that for every
$1\leq k\leq n$, $\mathbb{E}|Y_{k}|\geq c_{1}$. And, by Lemma 5.4,

$\displaystyle\mathbb{E}_{G}\sup_{t\in
K^{\circ}}\sum_{j=1}^{m}g_{j}t_{j}=\mathbb{E}_{G,\pi,\varepsilon}\sup_{t\in
K^{\circ}}\sum_{j=1}^{n}g_{j}^{\ast}\varepsilon_{\pi(j)}t_{\pi(j)}$
$\displaystyle=\mathbb{E}_{G}\mathbb{E}_{\varepsilon,\pi}\sup_{t\in
K^{\circ}}\sum_{j=1}^{n}\left(\frac{g_{j}^{\ast}}{\mathbb{E}_{Y}Y^{\ast}_{j}+c_{1}}\right)(\mathbb{E}_{Y}Y^{\ast}_{j}+c_{1})\varepsilon_{\pi(j)}t_{\pi(j)}$
$\displaystyle\leq\left(\mathbb{E}_{G}\max_{1\leq j\leq
n}\frac{g_{j}^{\ast}}{\mathbb{E}_{Y}Y^{\ast}_{j}+c_{1}}\right)\cdot\left(\mathbb{E}_{\varepsilon,\pi}\sup_{t\in
K^{\circ}}\sum_{j=1}^{n}(\mathbb{E}_{Y}Y^{\ast}_{j}+c_{1})\varepsilon_{\pi(j)}t_{\pi(j)}\right)=(\ast)\cdot(\ast\ast),$

where the last inequality follows from the contraction principle for Bernoulli
processes (applied conditionally with respect to $G$).

All that remains is to show that $(\ast)\leq c(c_{1},L,\delta)$ and that
$(\ast\ast)\leq 2\mathbb{E}_{Y}\sup_{t\in K^{\circ}}\sum_{j=1}^{n}Y_{j}t_{j}$.

To estimate the first term in $(\ast\ast)$, note that by Jensen’s inequality
followed by Lemma 5.4,

$\displaystyle\mathbb{E}_{\varepsilon,\pi}\sup_{t\in
K^{\circ}}\sum_{j=1}^{n}(\mathbb{E}_{Y}Y^{\ast}_{j})\varepsilon_{\pi(j)}t_{\pi(j)}$
$\displaystyle\leq\mathbb{E}_{\varepsilon,\pi,Y}\sup_{t\in
K^{\circ}}\sum_{j=1}^{n}Y^{\ast}_{j}\varepsilon_{\pi(j)}t_{\pi(j)}$
$\displaystyle=\mathbb{E}_{Y}\sup_{t\in K^{\circ}}\sum_{j=1}^{n}Y_{j}t_{j}.$

As for the second term in $(\ast\ast)$, invoking Lemma 5.5,
$\mathbb{E}_{Y}|Y_{j}|\geq c_{1}$ for $1\leq j\leq n$. Hence, by contraction

$\displaystyle\mathbb{E}_{\varepsilon,\pi}\sup_{t\in
K^{\circ}}\sum_{j=1}^{n}c_{1}\varepsilon_{\pi(j)}t_{\pi(j)}$
$\displaystyle\leq\mathbb{E}_{\varepsilon,\pi}\sup_{t\in
K^{\circ}}\sum_{j=1}^{n}\mathbb{E}_{Y}|Y_{\pi(j)}|\varepsilon_{\pi(j)}t_{\pi(j)}$
$\displaystyle\leq\mathbb{E}_{Y}\sup_{t\in
K^{\circ}}\sum_{j=1}^{n}Y_{j}t_{j},$

as required.

To control $(\ast)$, a standard binomial estimate shows that there are
absolute constants $c_{2}$ and $c_{3}$ such that for $u\geq c_{3}$,

$\displaystyle\mathbb{P}\left(g^{\ast}_{j}\geq u\sqrt{\log(en/j)}\right)\leq
2\exp\left(-c_{4}u^{2}j\log(en/j)\right).$ (5.10)

By Lemma 5.5 there is $c_{5}=c_{5}(L,\delta)$ such that
$\mathbb{E}_{Y}Y^{\ast}_{j}+c_{1}\geq c_{5}\sqrt{\log(en/j)}$ for every $1\leq
j\leq n$. Thus, (5.10) and the union bound imply that

$\displaystyle\mathbb{P}_{G}\left(\max_{1\leq j\leq
n}\frac{g_{j}^{\ast}}{\mathbb{E}_{Y}Y^{\ast}_{j}+c_{1}}\geq\frac{u}{c_{5}}\right)$
$\displaystyle\leq\sum_{j=1}^{n}2\exp\left(-c_{4}u^{2}j\log\left(\frac{en}{j}\right)\right)$
$\displaystyle\leq 2\exp\left(-c_{6}u^{2}\right),$

and the claim follows from tail-integration. ∎

Acknowledgements: The first author is grateful for financial support through
the Austrian Science Fund (FWF) projects ESP-31N and P34743N.

## References

  * [1] R. Adamczak, A. Litvak, A. Pajor, and N. Tomczak-Jaegermann.  Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles.  Journal of the American Mathematical Society, 23(2):535–561, 2010\.
  * [2] S. Artstein-Avidan, A. Giannopoulos, and V. D. Milman.  Asymptotic Geometric Analysis, Part I, volume 202.  American Mathematical Society, 2015.
  * [3] Z.-D. Bai, J.-W. Silverstein,and Y.-Q. Yin.  A note on the largest eigenvalue of a large dimensional sample covariance matrix.  Journal of Multivariate Analysis, 26(2):166–168, 1988.
  * [4] Z.-D. Bai and Y.-Q. Yin.  Limit of the smallest eigenvalue of a large dimensional sample covariance matrix.  The Annals of Probability, 21(3):1275–1294, 1993.
  * [5] D. Bartl and S. Mendelson.  Structure preservation via the Wasserstein distance.  arXiv preprint arXiv:2209.07058, 2022.
  * [6] S. Boucheron, G. Lugosi, and P. Massart.  Concentration inequalities: A nonasymptotic theory of independence.  Oxford university press, 2013.
  * [7] V. De la Pena and E. Giné.  Decoupling: from dependence to independence.  Springer Science & Business Media, 2012.
  * [8] A. Dvoretzky.  Some results on convex bodies and Banach spaces.  Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960).
  * [9] Y. Gordon.  Some inequalities for Gaussian processes and applications.  Israel Journal of Mathematics, 50(4):265–289, 1985.
  * [10] Y. Gordon, M. Meyer, and A. Pajor.  Ratios of volumes and factorization through $l_{\infty}$.  Illinois Journal of Mathematics, 40(1):91–107, 1996.
  * [11] O. Guédon, A. Litvak, A. Pajor, and N. Tomczak-Jaegermann.  On the interval of fluctuation of the singular values of random matrices.  Journal of the European Mathematical Society,19(5), 2017.
  * [12] H. Huang and K. Tikhomirov.  On dimension-dependent concentration for convex lipschitz functions in product spaces.  Electronic Journal of Probability, 28:1–23, 2023.
  * [13] T. Klein and E. Rio.  Concentration around the mean for maxima of empirical processes.  The Annals of Probability, 33(3):1060–1077, 2005.
  * [14] M. Ledoux and M. Talagrand.  Probability in Banach Spaces: isoperimetry and processes, volume 23.  Springer Science & Business Media, 1991.
  * [15] S. Mendelson.  An isomorphic Dvoretzky-Milman theorem using general random ensembles.  Journal of Functional Analysis, 283(2):109473, 2022.
  * [16] S. Mendelson and G. Paouris.  On generic chaining and the smallest singular value of random matrices with heavy tails.  Journal of Functional Analysis, 262(9):3775–3811, 2012.
  * [17] S. Mendelson and G. Paouris.  On the singular values of random matrices.  Journal of the European Mathematical Society, 16(4):823–834, 2014\.
  * [18] S. Mendelson and N. Tomczak-Jaegermann.  A subgaussian embedding theorem.  Israel Journal of Mathematics, 164(1):349–364, 2008.
  * [19] V. D. Milman.  A new proof of A. Dvoretzky’s theorem on cross-sections of convex bodies.  Funkcional. Anal. i Prilozen, 5:28–37, 1971.
  * [20] S. J. Montgomery-Smith.  The distribution of Rademacher sums.  Proceedings of the American Mathematical Society, 109(2):517–522, 1990.
  * [21] G. Pisier.  Probabilistic methods in the geometry of Banach spaces.  In Probability and analysis, pages 167–241. Springer, 1986.
  * [22] G. Pisier.  The volume of convex bodies and Banach space geometry, volume 94.  Cambridge University Press, 1999.
  * [23] G. Schechtman.  A remark concerning the dependence on $\varepsilon$ in Dvoretzky’s theorem.  Geometric aspects of functional analysis, 1376:274–277, 1989.
  * [24] M. Talagrand  Upper and lower bounds for stochastic processes: decomposition theorems Springer Nature, Vol. 60, 2022.
  * [25] K. Tikhomirov.  Sample covariance matrices of heavy-tailed distributions.  International Mathematics Research Notices, 2018(20):6254–6289, 2018.