hence given the definition (67) of $f_0$ and since $\|\cdot\|_{a,\star} = \|\cdot\|_{\Sigma^{-1}}$ we have $f_0(\omega) \le \frac{3}{2}(\|\omega\|_{\Sigma^{-1}} + \|\omega\|_{\Sigma^{-1}}^3)$ for every $\omega$, so that

$$ \begin{aligned} |\psi(\omega)f_0(\omega)| \stackrel{(91)}{=} B_{\psi}e^{-\omega^T\Sigma\omega/2}f_0(\omega) &\le \frac{3}{2}B_{\psi}e^{-\|\omega\|_{\Sigma^{-1}}^2/2}(\|\omega\|_{\Sigma^{-1}} + \|\omega\|_{\Sigma^{-1}}^3) \\ &\le \frac{3}{2}B_{\psi}\varphi(\|\omega\|_{\Sigma^{-1}}) \le 4B_{\psi} \end{aligned} $$

since $\varphi(t) := (t+t^3)e^{-t^2/2}$ satisfies $\varphi(t) \le 8/3$ for $t \in \mathbb{R}$. Indeed, we have

$$ \sup_{t \in \mathbb{R}} \varphi(t) \le \sup_{t \in \mathbb{R}} \varphi_1(t) + \sup_{t \in \mathbb{R}} \varphi_2(t), $$

where $\varphi_1(t) := te^{-t^2/2}$, and $\varphi_2(t) := t^3e^{-t^2/2}$, and it is easy to prove that $\sup_{t \in \mathbb{R}} \varphi_1(t) = \varphi_1(1) = e^{-1/2} \le 1$, and $\sup_{t \in \mathbb{R}} \varphi_2(t) = \varphi_2(\sqrt{3}) = 3\sqrt{3}e^{-3/2} \approx 1.16 \le 5/3 \approx 1.66$.

**Identifying M such that Item 2 holds for mixtures of Diracs with $v = v_k(\tau)$**

Since $\psi(\omega) = 1$ (cf (96)) we have $\Psi_0(\Omega) = \frac{1}{m}\sum_{j=1}^m f_0(\omega_j)$, with $f_0(\omega)$ defined in (67).

Since $\|\cdot\|_a = \|\cdot\|_2$ we have $\|\cdot\|_{a,\star} = \|\cdot\|_2$ hence $f_0(\omega) = \sum_{t=1}^3 \|\omega\|_2^t$. As $\omega \sim \mathcal{N}(0, s^{-2}\mathbb{I}_d)$, Proposition 11 yields

$$ \forall t \ge 0, \quad \mathbb{P}(\Psi_0(\Omega) > \tilde{M}(t)) \le \exp\left(-\frac{(mt)^{2/3}}{2}\right), $$

with $\tilde{M}(t) := 1 + \frac{8}{s^3}(\sqrt{\frac{8}{\pi}}d^{3/2} + t)$. We define

$$ C_0 := 7B_{\psi}B \qquad (169) $$

and recall that $C_0 \ge 7$ since $B_{\psi} \ge 1$ and $B \ge 1$. Therefore, for $0 < \tau \le 1$, and $v_k(\tau)$ as defined in (99), we have

$$ \mathbb{P}(\Psi_0(\Omega) > \tilde{M}(\tau^{3/2}m^{1/2})) \le \exp\left(-\frac{m\tau}{2}\right) \le 2\exp(-m/v_k(\tau)), $$

since $2/\tau \le 2/\tau^2 \le 2(C_0/\tau)^2 \le v_k(\tau)$.

In other words, (85) holds with $M = \tilde{M}(\tau^{3/2}m^{1/2})$ and $v = v_k(\tau)$.

**Wrapping up the proof.**

To complete the proof of Corollary 1 and Corollary 2 we use Theorem 5 and the last step is to give explicit upper bounds of the constants $C$ and $v'$ respectively defined in (88) and (89).

We start with $v'$, and we show that it is upper bounded by $v_k(\tau)$ defined in (94) (resp. in (99)). By (167), $\nu = \beta = 4B$ hence, by (86) $\nu' = \sqrt{2}\sqrt{\nu^2 + 8B^2} = \sqrt{48B^2} \le \sqrt{49B^2} = 7B$. Hence, $B_{\psi}^2\nu'^2 \le (7B_{\psi}B)^2 = C_0^2$ and $B_{\psi}\beta = 4B_{\psi}B = \frac{4}{7}C_0$ where $C_0$ is defined in (169). Since the block size is $b=1$, by (89) we obtain

$$ \begin{aligned} v' = \frac{256k^2b(2B_{\psi}^2\nu'^2 + B_{\psi}\beta\tau)}{\tau^2} &\le 512k^2\left((C_0/\tau)^2 + \frac{2}{7}(C_0/\tau)\right) \\ &\le 512k^2\left((C_0/\tau)^2 + \frac{1}{3}(C_0/\tau)\right). \end{aligned} $$
This matches the expressions of $v_k(\tau)$ used in (94) and (99). Soon we will also prove that $C_0$ satisfies the bounds expressed in (94) and (99).

As for $C$, observe that by definition (88), $C = 6144MC_\kappa \cdot k(1 + \text{diam}_a(\Theta))$, so that we only need to give an upper bound of $6144MC_\kappa$ to get the expressions that appear in (95) and (100).

To conclude we bound $C_0$ and $6144MC_\kappa$. First, by (166), we have $C_\kappa \le \max(1, \sqrt{3}\epsilon^2)$, and by (167) $B = \max(1, C_\kappa s^{-2})$. We study separately the two settings:

* For mixtures of Gaussians, by (92) we have $\epsilon \ge \max(s, 1)$ hence $C_\kappa \le \sqrt{3}\epsilon^2$, $B \le \sqrt{3}(\epsilon/s)^2$. Since $B_\psi = (1 + 2s^{-2})^{d/2}$, we get by (169) $C_0 = 7BB_\psi \le 7\sqrt{3}\epsilon^2 s^{-2}(1 + 2s^{-2})^{d/2}$ as claimed in (94). Since $M = 4B_\psi$ by (168), we get $6144MC_\kappa \le (4 \times 6144\sqrt{3})\epsilon^2 B_\psi \le 43000\epsilon^2 B_\psi$ as claimed in (95).

* For mixtures of Diracs, by (97) we have $\epsilon \ge s$ hence $\sqrt{3}\epsilon^2 s^{-2} \ge 1$. As $C_\kappa s^{-2} \le \max(s^{-2}, \sqrt{3}\epsilon^2 s^{-2})$, it follows that $B = \max(1, C_\kappa s^{-2}) \le \max(1, s^{-2}, \sqrt{3}\epsilon^2 s^{-2}) = \max(s^{-2}, \sqrt{3}\epsilon^2 s^{-2}) = s^{-2}\max(1, \sqrt{3}\epsilon^2)$. Since $B_\psi = 1$ it follows by (169) that $C_0 = 7BB_\psi = 7B \le 7s^{-2}\max(1, \sqrt{3}\epsilon^2)$ as claimed in (99). Finally observe that $c := \sqrt{8/\pi} \approx 1.6$ so that $cd^{3/2} + t \ge 1$ for every $t > 0$ hence $\tilde{M}(t) = 1 + \frac{8}{s^3}(cd^{3/2} + t) \le (1 + 8/s^3)(cd^{3/2} + t) \le (1 + 2/s)^3(cd^{3/2} + t) \le (1 + 2/s)^3(2d^{3/2} + t)$. Since $M = \tilde{M}(m^{1/2}\tau^{3/2})$ it follows that $6144MC_\kappa \le 6144(1 + 2/s)^3 \max(1, \sqrt{3}\epsilon^2)(2d^{3/2} + \sqrt{m}\tau^{3/2})$ as claimed in (100).

### A.9.5 Some helpful results

**Lemma 10.** Consider $\sigma > 0$ and for $r \ge 0$ define $\alpha_\sigma(r) := \frac{r}{\sqrt{1-e^{-r^2/\sigma^2}}}$. For each $R > 0$ we have

$$ \sup_{r \in [0, R]} |\alpha_{\sigma}(r)| \le \sqrt[4]{3} \max(\sigma, R), \quad \text{and} \quad \sup_{r \in (0, R]} |\alpha'_{\sigma}(r)| \le 1. \quad (170) $$

*Proof.* First we show that $\alpha_\sigma(r) = \sigma\alpha_1(r/\sigma) \le (1 - e^{-1})^{-1/2} \max(\sigma, r)$ when $r \ge 0$. This implies the first bound as $(1 - e^{-1})^{-1/2} \approx 1.26 \le 1.316 \approx \sqrt[4]{3}$. When $\sigma \le r$ we have

$$ |\alpha_{\sigma}(r)| = \frac{r}{\sqrt{1 - e^{-r^2/\sigma^2}}} \le \frac{r}{\sqrt{1 - e^{-1}}} \le (1 - e^{-1})^{-1/2} r = (1 - e^{-1})^{-1/2} \max(\sigma, r). $$

When $0 \le r \le \sigma$, we prove below that $|\alpha_1(t)| \le (1 - e^{-1})^{-1/2}$ for every $t \in [0, 1]$, so that

$$ |\alpha_{\sigma}(r)| = \sigma|\alpha_{1}(r/\sigma)| \le (1 - e^{-1})^{-1/2}\sigma = (1 - e^{-1})^{-1/2}\max(\sigma, r). $$

To show that $|\alpha_1(t)| \le (1 - e^{-1})^{-1/2}$ on $[0, 1]$ observe that since $u \mapsto e^{-u}$ is convex, it has non-decreasing slopes so that $(e^{-u} - 1)/u \le (e^{-1} - 1)/1, \forall u \in [0, 1]$. This reads $u/(1 - e^{-u}) \le 1/(1 - e^{-1})$ and implies $|\alpha_1(t)|^2 = t^2/(1 - e^{-t^2}) \le 1/(1 - e^{-1})$ for $t \in [0, 1]$, thus $|\alpha_1(t)| \le 1/\sqrt{1 - e^{-1}}$.

We now prove that $|\alpha'_1(t)| \le 1, \forall t > 0$. This implies the second bound since $\alpha'_\sigma(r) = \alpha'_1(r/\sigma)$. Writing $\alpha_1(t) = t[v(t)]^{-1/2}$ with $v(t) := 1 - e^{-t^2}$ we get

$$ \alpha'_{1}(t) = [v(t)]^{-1/2} - \frac{t}{2}v'(t)[v(t)]^{-3/2} = [v(t)]^{-3/2}(v(t) - tv'(t)/2) = [v(t)]^{-3/2}(1 - e^{-t^2}(1 + t^2)) $$

For each $t \ge 0$, since $e^{t^2} \ge 1 + t^2$, it follows that $|\alpha'_1(t)| = \alpha'_1(t)$. When $t \ge 1$, since $0 < x := e^{-t^2} \le 1/e \approx 0.368 < 1/2 < 0.618 \approx (\sqrt{5} - 1)/2$ we have
$(x-1)^3+(1-2x)^2 = x^3+x^2-x = x(x^2+x-1) = x[x+(1+\sqrt{5})/2][x+(1-\sqrt{5})/2] \le 0$ hence $(1-2x)^2 \le (1-x)^3$, and since $1-2x > 0$ it follows that $1-2x \le (1-x)^{3/2}$. Thus, we obtain

$$|\alpha'_1(t)| = \frac{1 - e^{-t^2}(1 + t^2)}{\sqrt{1 - e^{-t^2}}} \le \frac{1 - 2e^{-t^2}}{\sqrt{1 - e^{-t^2}}} = \frac{1 - 2x}{(1 - x)^{3/2}} \le 1,$$

Now, when $0 < t \le 1$, since $[v(t)]^{-3/2} = (\alpha_1(t)/t)^3$, using that $|\alpha_1(t)| \le (1 - e^{-1})^{-1/2} \max(1, t) = (1 - e^{-1})^{-1/2}$ and $(1 - e^{-1})^{-3/2} \approx 1.99 \le 2$ we get

$$|\alpha'_1(t)| \le (1 - e^{-1})^{-3/2} \frac{1 - e^{-t^2}(1 + t^2)}{t^3} \le 2 \frac{1 - e^{-t^2}(1 + t^2)}{t^3}.$$

It is enough to show that $g(t) := (1 - e^{-t^2}(1 + t^2))/t^3 \le 1/2$, $\forall t \in (0, 1]$. We have $g'(t) = t^{-4}(-3 + e^{-t^2}(3 + 3t^2 + 2t^4))$ hence $\text{sign}(g'(t)) = -\text{sign}(e^{t^2} - (1 + t^2 + \frac{2}{3}t^4))$. Thus there is a neighborhood of zero in which $g$ is increasing, since $\text{sign}(g'(t)) = -\text{sign}(1 + t^2 + \frac{1}{2}t^4 + O(t^6) - (1 + t^2 + \frac{2}{3}t^4)) = -\text{sign}(-\frac{1}{6}t^4 + O(t^6)) = +1$ for $t$ small enough. Since $g$ is continuously differentiable, its supremum on $(0, 1]$ is thus either equal to $g(1) = 1 - 2/e \approx 0.264 < 1/2$ or to $g(t_*)$, for some local maximum $0 < t_* \le 1$ which must satisfy $g'(t_*) = 0$. To conclude without further characterizing the existence or value of such a root, we establish that any such root must satisfy $g(t_*) \le 1/2$. Indeed using that $g'(t_*) = 0$ if, and only if $e^{t_*^2} = 1 + t_*^2 + \frac{2}{3}t_*^4$, we obtain

$$g(t_*) = \frac{1 - e^{-t_*^2}(1 + t_*^2)}{t_*^3} = \frac{e^{t_*^2} - (1 + t_*^2)}{e^{t_*^2} t_*^3} = \frac{1 + t_*^2 + \frac{2}{3}t_*^4 - (1 + t_*^2)}{(1 + t_*^2 + \frac{2}{3}t_*^4)t_*^3} = \frac{\frac{2}{3}t_*}{1 + t_*^2 + \frac{2}{3}t_*^4}.$$

We finally distinguish two cases: i) if $t_* < 1/\sqrt{2}$ then $g(t_*) \le \frac{2}{3}t_* \le \frac{\sqrt{2}}{3} \le 1/2$; ii) if $1/\sqrt{2} \le t_* \le 1$ then $g(t_*) \le \frac{2}{3+\frac{2}{3}(1/2)} = 0.4 < 1/2$. $\square$

**Proposition 11.** Consider $s > 0$, and let $\omega_1, \dots, \omega_m$ be i.i.d. samples from $\mathcal{N}(0, \frac{1}{s^2}\mathbb{I}_d)$. Then

$$\forall \tau \ge 0, \quad \mathbb{P}\left(\frac{1}{m} \sum_{j=1}^{m} \|\omega_j\|^3 > \frac{4}{s^3} \left(d^{3/2} \sqrt{8/\pi} + \tau\right)\right) \le \exp\left(-\frac{(m\tau)^{2/3}}{2}\right). \quad (171)$$

Moreover, as a consequence we have for $\tau > 0$

$$\mathbb{P}\left(\frac{1}{m} \sum_{j=1}^{m} \sum_{t=1}^{3} \|\omega_j\|_2^t > 1 + \frac{8}{s^3} \left(d^{3/2} \sqrt{8/\pi} + \tau\right)\right) \le \exp\left(-\frac{(m\tau)^{2/3}}{2}\right). \quad (172)$$

*Proof.* First, to prove (171) when $\omega_1, \dots, \omega_m$ are i.i.d. samples from $\mathcal{N}(0, \frac{1}{s^2}\mathbb{I}_d)$, it is enough to deal with the case $s = 1$. Next, for $s = 1$, denoting $\Omega \in \mathbb{R}^{dm}$ the concatenation of $\omega_1, \dots, \omega_m \in \mathbb{R}^d$, the vector $\Omega$ has independent standard normal random entries when $\omega_1, \dots, \omega_m$ are i.i.d. samples from $\mathcal{N}(0, \mathbb{I}_d)$, and for any $2 \le p < \infty$ the function $f_p: \mathbb{R}^{dm} \to \mathbb{R}$ defined by $f_p(\Omega) := (\sum_{j=1}^m \|\omega_j\|_2^p)^{1/p}$ is (as we will soon show) 1-Lipschitz with respect to the Euclidean norm in $\mathbb{R}^{dm}$. Therefore, we may use the Tsirelson-Ibragimov-Sudakov inequality [TIS76], a.k.a. concentration of a random variable that writes as a Lipschitz function of a Gaussian vector [BLM13a,
Theorem 5.6], to obtain $\mathbb{P}(f_p(\Omega) - \mathbb{E}f_p(\Omega) \ge t) \le \exp(-t^2/2)$, for each $t \ge 0$, or equivalently

$$ \forall t \ge 0, \quad \mathbb{P}([f_p(\Omega)]^p \ge [\mathbb{E}f_p(\Omega) + \tau]^p) \le \exp(-t^2/2). $$

By convexity we have $(a+b)^p = 2^p(a/2 + b/2)^p \le 2^{p-1}(a^p + b^p)$ for every $a, b \in \mathbb{R}_+$, hence

$$ \forall t \ge 0, \quad \mathbb{P}([f_p(\Omega)]^p \ge 2^{p-1} ([\mathbb{E}f_p(\Omega)]^p + t^p)) \le \exp(-t^2/2). $$

We now show that $[\mathbb{E}f_p(\Omega)]^p \le md^{p/2}\mathbb{E}|g|^p$. The convexity of $t \mapsto t^{p/2}$ ($p \ge 2$) on $\mathbb{R}_+$ yields

$$ \mathbb{E}\|\omega\|_2^p = d^{p/2}\mathbb{E}\left(\frac{1}{d}\sum_{i=1}^d \omega_i^2\right)^{p/2} \le d^{p/2}\mathbb{E}\left[\frac{1}{d}\sum_{i=1}^d |\omega_i|^p\right] = d^{p/2}\mathbb{E}|g|^p $$

where $\omega \sim \mathcal{N}(0, I_d)$, $g \sim \mathcal{N}(0, 1)$. B convexity of $t \mapsto t^p$ and Jensen's inequality, it follows that

$$ [\mathbb{E}f_p(\Omega)]^p \le \mathbb{E}[f_p(\Omega)]^p = \sum_{j=1}^m \mathbb{E}\|\omega_j\|_2^p = m\mathbb{E}\|\omega\|_2^p \le md^{p/2}\mathbb{E}|g|^p. $$

As a result

$$ \forall t \ge 0, \quad \mathbb{P}([f_p(\Omega)]^p \ge 2^{p-1}(md^{p/2}\mathbb{E}|g|^p + t^p)) \le \exp(-t^2/2), $$

or equivalently $\mathbb{P}(\frac{1}{m}\sum_{j=1}^m \|\omega_j\|^p \ge 2^{p-1}(d^{p/2}\mathbb{E}|g|^p + \tau)) \le \exp(-(m\tau)^{2/p}/2)$ for each $\tau \ge 0$. Since $\mathbb{E}|g|^3 = \sqrt{8/\pi}$ [FEHP11, Chapter 11], considering $p=3$ yields (171) (for $s=1$) as claimed. Now, observe that for $t \ge 0$ we have $t^3 - t - (t^2 - 1) = (t^2 - 1)(t - 1) = (t - 1)^2(t + 1) \ge 0$ hence $t^3 + 1 \ge t^2 + t$ and $t + t^2 + t^3 \le 1 + 2t^3$. Thus $\sum_{i=1}^3 \|\omega_j\|_2^i \le 1 + 2\|\omega_j\|_2^2$, and we deduce (172) from (171).

To complete the proof, we show that $f_p$ is 1-Lipschitz with respect to $\|\cdot\|_2$. Denoting $v_\Omega := (\|\omega_j\|_2)_{j \in [m]} \in \mathbb{R}^m$, observe that $f_p(\Omega) = \|v_\Omega\|_p$. Thus, for $\Omega, \Omega' \in \mathbb{R}^{dm}$, since $p \ge 2$, we have

$$ |f_p(\Omega) - f_p(\Omega')| = \|v_\Omega\|_p - \|v_{\Omega'}\|_p \le \|v_\Omega - v_{\Omega'}\|_p \le \|v_\Omega - v_{\Omega'}\|_2. $$

Finally,

$$ \|v_\Omega - v_{\Omega'}\|_2^2 = \sum_{j=1}^m (\|\omega_j\|_2 - \|\omega'_j\|_2)^2 \le \sum_{j=1}^m \|\omega_j - \omega'_j\|_2^2 = \|\Omega - \Omega'\|_2^2. \quad \square $$

### A.9.6 Proof of Lemma 7

Denote $c := 2(\alpha + 2)$ and $\varphi(t) := e^{-(c-\alpha)t^2/2+t} - te^{-ct^2/2}$. Since $\varphi(0) = 1$, it is enough to prove that $\varphi$ is non-increasing on $\mathbb{R}_+$. Since $\varphi$ is $C^1$, we study the sign of $\varphi'(t) = -(c-\alpha)t + 1 + (ct^2-1)e^{-\alpha t^2/2-t})e^{-(c-\alpha)t^2/2+t}$ which is the sign of $\psi(t) := 1 - (c-\alpha)t + (ct^2-1)e^{-\alpha t^2/2-t}$. To show that $\psi(t) \le 0$ for each $t \in \mathbb{R}_+$ we study its sign on the intervals $(0, \frac{1}{c-\alpha})$ and $(\frac{1}{c-\alpha}, +\infty)$. As a preliminary we record that since $\alpha > 0$, we have

$$ \sqrt{c/(c-\alpha)} = \sqrt{2(2+\alpha)/(\alpha+4)} \le 1/2. \quad (173) $$
**Case of** $t \in (0, \frac{1}{c-\alpha})$. Since $1 - (c - \alpha)t > 0$, we will get that $\psi(t) \le 0$ if we show that

$$ \frac{1 - ct^2}{1 - (c - \alpha)t} \ge e^{\alpha t^2/2 + t}. \qquad (174) $$

Since $t \in (0, 1/(c - \alpha))$, using (173) we have $\sqrt{ct} < (c - \alpha)t < 1$ hence

$$ \frac{1 - ct^2}{1 - (c - \alpha)t} = \frac{(1 - \sqrt{ct})(1 + \sqrt{ct})}{1 - (c - \alpha)t} \ge 1 + \sqrt{ct}. \qquad (175) $$

Denoting $h(u) := (1 + \sqrt{cu})e^{-\alpha u^2/2-u}$, it is enough to prove that $h(t) \ge 1 = h(1)$, which will follow if we establish that $h'(u) = (\sqrt{c}(1-u-\alpha u^2)-(\alpha u+1))e^{-\alpha u^2/2-u} \ge 0$ on $(0, 1/(c-\alpha))$, or equivalently that the quadratic function $\sqrt{c}(1-u-\alpha u^2)-(\alpha u+1)$ takes non-negative values at $u = 0$ and at $u = 1/(c - \alpha)$. Indeed, its evaluation at $u = 0$ yields $\sqrt{c-1} = \sqrt{2(2+\alpha)-1} > 0$, while its evaluation on $1/(c-\alpha) = 1/(\alpha+4)$ is lower bounded by $8/(\alpha+4)^2 > 0$.

**Case of** $t \in (\frac{1}{c-\alpha}, +\infty)$. Since $1 - (c - \alpha)t < 0$, we get that $\psi(t) \le 0$ as soon as

$$ \frac{ct^2 - 1}{(c - \alpha)t - 1} \le e^{\alpha t^2/2 + t}. \qquad (176) $$

Since $t > 1/(c - \alpha)$, we have $(c - \alpha)t > 1$, and using (173) we get

$$ \frac{\sqrt{ct} - 1}{(c - \alpha)t - 1} \le \frac{\sqrt{ct}}{(c - \alpha)t} \le \frac{1}{2}. $$

Therefore

$$ \frac{ct^2 - 1}{(c - \alpha)t - 1} = \frac{(\sqrt{ct} - 1)(\sqrt{ct} + 1)}{(c - \alpha)t - 1} \le \frac{1}{2} + \frac{1}{2}\sqrt{ct} \le \frac{e^{\alpha t^2/2 + t}}{2} + \frac{\sqrt{ct}}{2}. \qquad (177) $$

Denoting $g(u) := ue^{-\alpha u^2/2-u}$, it is thus enough to show that $\sqrt{cg}(t) \le 1$ to conclude. Since $g'(u) = -(1 + u + \alpha u^2)e^{-\alpha u^2/2-u}$, the unique $u \ge 0$ such that $g'(u) = 0$ is $u_\alpha := 2/(\sqrt{4\alpha+1}+1)$, which satisfies $\alpha u_\alpha^2 + u_\alpha - 1 = 0$, and the maximum of $g(u)$ on $\mathbb{R}_+$ is at $u = u_\alpha$. As a result

$$ \sqrt{cg}(t) \le \sqrt{cg}(u_\alpha) = 2 \frac{\sqrt{2(2+\alpha)}}{\sqrt{4\alpha+1}+1} e^{-1/2 - u_\alpha/2}. \qquad (178) $$

To conclude, we show that the r.h.s. is bounded by one, by distinguishing two cases. On the one hand, if $\alpha \ge 2$, we have $2\sqrt{2(2+\alpha)}/(\sqrt{4\alpha+1}+1) \le \sqrt{2}$, and since $u_\alpha \ge 0$ the r.h.s. of (178) is upper bounded by $e^{-1/2}\sqrt{2} \le 1$. On the other hand, if $\alpha \le 2$, we have $u_\alpha/2 \ge 1/4$ and $2\sqrt{2(2+\alpha)}/(\sqrt{4\alpha+1}+1) \le 2$ (the latter inequality holds for any $\alpha \ge 0$), so that the r.h.s. of (178) is upper bounded by $2e^{-3/4} \le 1$. In both cases, we get as claimed that $\sqrt{cg_\alpha}(t) \le 1$.
References

[AC06] N. Ailon and B. Chazelle. Approximate nearest neighbors and the fast johnson-lindenstrauss transform. In *Proceedings of the thirty-eighth annual ACM symposium on Theory of computing*, pages 557–563, 2006.

[Ach01] D. Achlioptas. Database-friendly random projections. In *Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems*, pages 274–281, 2001.

[AKM+17] H. Avron, M. Kapralov, C. Musco, Ch. Musco, A. Velingker, and A. Zandieh. Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees. In *International conference on machine learning*, pages 253–262. PMLR, 2017.

[Bac17] F. Bach. On the equivalence between kernel quadrature rules and random feature expansions. *The Journal of Machine Learning Research*, 18(1):714–751, 2017.

[BKZ20] O. Bousquet, Y. Klochkov, and N. Zhivotovskiy. sharper bounds for uniformly stable algorithms. In *Conference on Learning Theory*, pages 610–626. PMLR, 2020.

[BLM13a] S. Boucheron, G. Lugosi, and P. Massart. *Concentration Inequalities: A Nonasymptotic Theory of Independence*. OUP Oxford, 2013.

[BLM13b] S. Boucheron, G. Lugosi, and P. Massart. *Concentration Inequalities: A Nonasymptotic Theory of Independence*. OUP Oxford, 2013.

[BM01] E. Bingham and H. Mannila. Random projection in dimensionality reduction: applications to image and text data. In *Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining*, pages 245–250, 2001.

[BTA11] A. Berlinet and Ch. Thomas-Agnan. *Reproducing kernel Hilbert spaces in probability and statistics*. Springer Science & Business Media, 2011.

[Can08] E. J. Candes. The restricted isometry property and its implications for compressed sensing. *Comptes rendus mathematique*, 346(9-10):589–592, 2008.

[CGK18] A. Chatalic, R. Gribonval, and N. Keriven. Large-scale high-dimensional clustering with fast sketching. In *2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)*, pages 4714–4718. IEEE, 2018.

[Cha20] A. Chatalic. *Efficient and privacy-preserving compressive learning*. PhD thesis, Université Rennes 1, 2020.

[CRS+18] K. Choromanski, M. Rowland, T. Sarlós, V. Sindhwani, R. Turner, and A. Weller. The geometry of random features. In *International Conference on Artificial Intelligence and Statistics*, pages 1–9. PMLR, 2018.
[CRW17] K. M. Choromanski, M. Rowland, and A. Weller. The unreasonable effectiveness of structured random orthogonal embeddings. *Advances in neural information processing systems*, 30, 2017.

[CS01] F. Cucker and S. Smale. On the mathematical foundations of learning. *BULLETIN*, 39, 11 2001.

[CS16] K. Choromanski and V. Sindhwani. Recycling randomness with structure for sublinear time kernel expansions. In *International Conference on Machine Learning*, pages 2502–2510. PMLR, 2016.

[DDSR17] T. Dao, Ch. De Sa, and Ch. Ré. Gaussian quadrature for kernel features. *Advances in neural information processing systems*, 30, 2017.

[FEHP11] C. Forbes, M. Evans, N. Hastings, and B. Peacock. *Statistical distributions*. John Wiley & Sons, 2011.

[FR13] S. Foucart and H. Rauhut. An invitation to compressive sensing. In *A mathematical introduction to compressive sensing*, pages 1–39. Springer, 2013.

[GBKT21a] R. Gribonval, G. Blanchard, N. Keriven, and Y. Traonmilin. Compres- sive statistical learning with random feature moments. *Mathematical Statistics and Learning*, 3(2):113–164, 2021.

[GBKT21b] Rémi Gribonval, Gilles Blanchard, Nicolas Keriven, and Yann Traon- milin. Statistical learning guarantees for compressive clustering and compressive mixture modeling. *Mathematical Statistics and Learning*, 3(2):165–257, 2021.

[GBR+12] A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola. A kernel two-sample test. *The Journal of Machine Learning Research*, 13(1):723–773, 2012.

[GCK+20] R. Gribonval, A. Chatalic, N. Keriven, V. Schellekens, L. Jacques, and P. Schniter. Sketching datasets for large-scale learning (long version). *arXiv preprint arXiv:2008.01839*, 2020.

[Hal50] P. R. Halmos. Measure theory. (University Series in Higher Mathemat- ics) New York: D. Van Nostrand Co., Inc.; London: Macmillan & Co., Ltd., XII, 304 p. (1950)., 1950.

[Hoe94] W. Hoeffding. Probability inequalities for sums of bounded random variables. In *The collected works of Wassily Hoeffding*, pages 409–426. Springer, 1994.

[KBGP18] N. Keriven, A. Bourrier, R. Gribonval, and P. Pérez. Sketching for large-scale learning of mixture models. *Information and Inference: A Journal of the IMA*, 7(3):447–508, 2018.

[KTTG17] N. Keriven, N. Tremblay, Y. Traonmilin, and R. Gribonval. Compressive k-means. In *2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)*, pages 6369–6373. IEEE, 2017.
[LHCS21] F. Liu, X. Huang, Y. Chen, and J. A.K. Suykens. Random features for kernel approximation: A survey on algorithms, theory, and beyond. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 44(10):7128-7148, 2021.

[LSS13] Q. Le, T. Sarlós, and A. Smola. Fastfood-approximating kernel expansions in loglinear time. In *Proceedings of the international conference on machine learning*, volume 85, page 8, 2013.

[LTOS19] Z. Li, JF. Ton, D. Oglic, and D. Sejdinovic. Towards a unified analysis of random fourier features. In *International conference on machine learning*, pages 3905-3914. PMLR, 2019.

[MFS$^{+}$17] K. Muandet, K. Fukumizu, B. Sriperumbudur, B. Schölkopf, et al. Kernel mean embedding of distributions: A review and beyond. *Foundations and Trends® in Machine Learning*, 10(1-2):1-141, 2017.

[MKBO18] M. Munkhoeva, Y. Kapushev, E. Burnaev, and I. Oseledets. Quadrature-based features for kernel approximation. *Advances in neural information processing systems*, 31, 2018.

[MM09] O. Maillard and R. Munos. Compressed least-squares regression. *Advances in neural information processing systems*, 22, 2009.

[MM12] O. Maillard and R. Munos. Linear regression with random projections. *Journal of Machine Learning Research*, 13(1):2735-2772, 2012.

[RR07] A. Rahimi and B. Recht. Random features for large-scale kernel machines. *Advances in neural information processing systems*, 20, 2007.

[Rud17] W. Rudin. *Fourier analysis on groups*. Courier Dover Publications, 2017.

[Sar06] T. Sarlos. Improved approximation algorithms for large matrices via random projections. In *2006 47th annual IEEE symposium on foundations of computer science (FOCS'06)*, pages 143-152. IEEE, 2006.

[SGF$^{+}$10] B. K. Sriperumbudur, A. Gretton, K. Fukumizu, B. Schölkopf, and G. R.G. Lanckriet. Hilbert space embeddings and metrics on probability measures. *The Journal of Machine Learning Research*, 11:1517-1561, 2010.

[SS15a] B. Sriperumbudur and Z. Szabó. Optimal rates for random fourier features. *Advances in neural information processing systems*, 28, 2015.

[SS15b] D. J. Sutherland and J. Schneider. On the error of random fourier features. In *Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence*, UAI'15, page 862-871, Arlington, Virginia, USA, 2015. AUAI Press.

[SZ21] I. Steinwart and J. F. Ziegel. Strictly proper kernel scores and characteristic kernels on compact spaces. *Applied and Computational Harmonic Analysis*, 51:510-542, 2021.
[TIS76] B. S. Tsirelson, I. A. Ibragimov, and V. N. Sudakov. Norms of gaussian sample functions. In *Proceedings of the Third Japan—USSR Symposium on Probability Theory*, pages 20–41. Springer, 1976.

[Ver18] R. Vershynin. *High-dimensional probability: An introduction with applications in data science*, volume 47. Cambridge university press, 2018.

[Wai19] M. J. Wainwright. *High-dimensional statistics: A non-asymptotic viewpoint*, volume 48. Cambridge University Press, 2019.

[Wen04] H. Wendland. *Scattered data approximation*, volume 17. Cambridge university press, 2004.

[YSAM14] J. Yang, V. Sindhwani, H. Avron, and M. Mahoney. Quasi-monte carlo feature maps for shift-invariant kernels. In *International Conference on Machine Learning*, pages 485–493. PMLR, 2014.

[ZM15] J. Zhao and D. Meng. Fastmmd: Ensemble of circular discrepancy for efficient two-sample test. *Neural computation*, 27(6):1345–1372, 2015.