Combining (<ref>) and (<ref>), using Lemma <ref> and the penultimate item of Lemma <ref> yields

\begin{equation*}
\inf_{\hat{\sigma}^{2}} \sup_{P \in \mathcal{P}_{\text{Gauss}}(\mu)} R_{n, \delta}(P, \hat{\sigma}^{2}) \geq \sup_{k \in \N} p_{\alpha_k}^{-1}(1-\delta) = p^{-1}_{n/2}(1-\delta)
\end{equation*}

This proves the lower bound. For the upper bound, we have, for any $\sigma^2 \in (0, \infty)$

\begin{equation*}
\frac{n \cdot \sigma^2}{\sum_{i=1}^{n}(X_i - \mu)^{2}} \sim \text{Inv-Gamma}(n/2, n/2)
\end{equation*}

therefore, for $\hat{\sigma}^{2}$ as defined in the theorem, we have

\begin{align*}
&\Prob\paren*{\abs*{\log(\sigma^2/\hat{\sigma}^{2}((X_i)_{i=1}^{n}))} \leq p_{n/2}^{-1}(1-\delta)} \\
&= \Prob\paren*{\exp(-p_{n/2}^{-1}(1-\delta)) \leq \frac{\sigma^2}{\hat{\sigma}^{2}((X_i)_{i=1}^{n})} \leq \exp(p_{n/2}^{-1}(1-\delta))}\\
&= \Prob\paren*{\frac{1-\exp(-2p^{-1}_{n/2}(1-\delta))}{2p^{-1}_{n/2}(1-\delta)} \leq \frac{n \cdot \sigma^{2}}{\sum_{i=1}^{n}(X_i - \mu)^{2}} \leq \frac{\exp(2p^{-1}_{n/2}(1-\delta)) - 1}{2p^{-1}_{n/2}(1-\delta)}} \\
&= p_{n/2}(p_{n/2}^{-1}(1 - \delta))\\
&= 1-\delta
\end{align*}

from which we conclude that for all $\sigma^{2} \in (0, \infty)$

\begin{equation*}
R_{n, \delta}(P, \hat{\sigma}^{2}) \leq p_{n/2}^{-1}(1-\delta)
\end{equation*}

completing the proof of the minimaxity of $\hat{\sigma}^{2}$ and of the upper bound on the minimax risk.

§ PROOFS OF SECTION <REF>

§.§ Proof of Theorem <ref>

Before we proceed with the proof, we start with a simple lemma.

Under the setup of Theorem <ref>, the functions $\widetilde{\mathcal{E}}, \widetilde{E}$ are strictly convex and symmetric with unique minimizer $0$. Furthermore, if $(X, Y) \sim P \in \mathcal{P}_{\text{Gauss}}(P_{X}, \sigma^{2})$ so that $Y = \inp{w^{*}}{X} + \eta$, then $E(v) = \widetilde{E}(v - w^{*})$ for all $v$, and $w^{*}$ is the unique minimizer of $E(w)$.

We prove the convexity and symmetry of $\widetilde{E}$ first. We start with the symmetry.

\begin{equation*}
\widetilde{E}(-\Delta) = \Exp\brack*{e(- \inp{\Delta}{X} + \eta)}
= \Exp\brack*{e(\inp{\Delta}{X} - \eta)}
= \Exp\brack*{e(\inp{\Delta}{X} + \eta)} = \widetilde{E}(\Delta),
\end{equation*}

where the second equality follows from the symmetry of $e$, and the fourth equality follows from $\eta \overset{d}{=} -\eta$.
For the strict convexity, let $t \in (0, 1)$ and $\Delta, \Delta' \in \R^{d}$. Then

\begin{equation*}
\widetilde{E}((1-t) \Delta + t \Delta') = \Exp\brack*{e\paren*{(1-t)\brace*{\inp{\Delta}{X} + \eta} + t\brace*{\inp{\Delta'}{X} + \eta}}} < (1-t) \widetilde{E}(\Delta) + t \widetilde{E}(\Delta'),
\end{equation*}

where the inequality follows from the strict convexity of $e$. Therefore $\widetilde{E}$ is strictly convex and symmetric, and since $\widetilde{\mathcal{E}}$ and $\widetilde{E}$ differ by a constant, the same holds for $\widetilde{\mathcal{E}}$.

For the second statement, notice that, by symmetry of $\eta$,

\begin{equation*}
E(v) = \Exp\brack*{e(\inp{v}{X} - Y)} = \Exp\brack*{e(\inp{v-w^{*}}{X} - \eta)} = \Exp\brack*{e(\inp{v-w^{*}}{X} + \eta)} = \widetilde{E}(v-w^{*}).
\end{equation*}

After routine calculations and an application of the chain rule, this also shows that $E$ is strictly convex, symmetric, and differentiable at $w^{*}$ with $\nabla E(w^{*}) = \nabla \widetilde{E}(0)$. We compute

\begin{equation*}
\nabla E(w^{*}) = \nabla \widetilde{E}(0) =  \Exp\brack*{\nabla e(\eta)} = \Exp\brack*{e'(\eta) X} = \Exp\brack*{e'(\eta)} \Exp\brack*{X},
\end{equation*}

where $\eta \sim \mathcal{N}(0, \sigma^{2})$ and the last equality follows from the independence of $\eta$ and $X$. Now

\begin{equation*}
\Exp\brack*{e'(\eta)} = \frac{1}{\sigma^{2}}\Exp\brack*{e(\eta) \eta} = \frac{1}{\sigma^{2}} \Exp\brack*{e(-\eta) \cdot (-\eta)} = -\frac{1}{\sigma^{2}}\Exp\brack*{e(\eta)\eta} = -\Exp\brack*{e'(\eta)}
\end{equation*}

where the first and last equalities are by Stein's lemma, the second since $\eta \overset{d}{=} -\eta$, and the third by the symmetry of $e$. This proves that $\Exp\brack{e'(\eta)} = 0$, and hence that $w^{*}$ is the unique minimizer of $E$ by strong convexity.

We now present the main proof of the theorem.

Our strategy is to use Theorem <ref> with a properly chosen sequence of distributions $(\pi_k)_{k \in \N}$. Notice that, associated to each $P \in \mathcal{P}_{\text{Gauss}}(P_{X}, \sigma^2)$ is a unique minimizer $w^{*} \in \R^{d}$ of the expected error $E(w)$. So putting a distribution on the set of the latter, $\R^{d}$, induces a distribution on the set of the former, $\mathcal{P}_{\text{Gauss}}(P_{X}, \sigma^2)$. Specifically, let $(\lambda_k)_{k \in \N}$ be a strictly positive sequence converging to $0$, and define $\pi_{k} \defeq \mathcal{N}(0, \lambda_k^{-1} \cdot (\sigma^2/n) \cdot I_{d \times d})$. With the goal of applying Theorem <ref>, we need to compute

\begin{equation*}
p_{k}(t) \defeq \sup_{\hat{w}} \Prob\paren*{\mathcal{E}(\hat{w}((X_i, Y_i)_{i=1}^{n})) \leq t},
\end{equation*}

where $w^{*} \sim \pi_k$, $(X_i)_{i=1}^{n} \sim P_{X}^{n}$, and $Y_{i} \mid (w^{*}, X_i) \sim \mathcal{N}(\inp{w^{*}}{X_i}, \sigma^2)$ for all $i \in [n]$, and independently. A basic calculation shows that $w^{*} \mid (X_i, Y_i)_{i=1}^{n} \sim \mathcal{N}(w_{k}, (\sigma^2/n) \Sigma_{k}^{-1})$, where

\begin{equation*}
w_{k} \defeq \Sigma_{k}^{-1} \paren*{\frac{1}{n}\sum_{i=1}^{n}Y_{i}X_i}, \quad \Sigma_{k} \defeq \widehat{\Sigma}_{n} + \lambda_k I_{d}, \quad \widehat{\Sigma}_{n} \defeq \frac{1}{n}\sum_{i=1}^{n} X_{i}X_{i}^{T}
\end{equation*}

Therefore, using Lemma <ref>,

\begin{align*}
p_{k}(t) &= \sup_{\hat{w}} \Prob\paren*{\mathcal{E}(\hat{w}) \leq t} = \sup_{\hat{w}} \Prob\paren*{\widetilde{\mathcal{E}}(\hat{w} - w^{*}) \leq t} \\
&= \sup_{\hat{w}} \Exp\brack*{\Prob\paren*{\widetilde{\mathcal{E}}(\hat{w} - w^{*}) \leq t \st (X_i, Y_i)_{i=1}^{n}}} \\
&= \Exp\brack*{\sup_{v \in \R^{d}} \Prob\paren*{w^{*} - v \in \widetilde{\mathcal{E}}^{-1}((-\infty,t]) \st (X_i, Y_i)_{i=1}^{n}}} \\
&= \Exp\brack*{\Prob\paren*{w^{*} - w_k \in \widetilde{\mathcal{E}}^{-1}((-\infty,t]) \st (X_i, Y_i)_{i=1}^{n}}} \\
&= \Prob\paren*{\widetilde{\mathcal{E}}(Z_k) \le t} = F_{\widetilde{\mathcal{E}}(Z_k)}(t)
\end{align*}

where $Z_{k} \mid (X_i)_{i=1}^{n} \sim \mathcal{N}(0, (\sigma^{2}/n)\Sigma_{k}^{-1})$. The fifth equality is obtained by combining the first item of Lemma <ref> with the first item of Lemma <ref>, and an application of Lemma <ref>. With the goal of applying Theorem <ref>, we verify the needed properties on the sequence $(p_{k})_{k \in \N}$.

First, since each $p_{k}$ is a CDF, it is right-continuous. To show that $(p_k)_{k \in \N}$ is decreasing, let $k \in \N$. Since $\lambda_{k} \geq \lambda_{k+1}$ by assumption,  $\Sigma_{k} \succeq \Sigma_{k+1}$, and therefore $\Sigma_{k}^{-1} \preceq \Sigma_{k+1}^{-1}$. We conclude that $Z_{k+1} \overset{d}{=} Z_{k} + Y_{k}$ where $Y_{k} \indep Z_{k} \mid (X_i)_{i=1}^{n}$ and $Y_k \mid (X_i)_{i=1}^{n} \sim \mathcal{N}(0, \frac{\sigma^{2}}{n} \brace*{\Sigma_{k+1}^{-1} - \Sigma_{k}^{-1}})$. Now

\begin{align*}
F_{\widetilde{\mathcal{E}}(Z_{k+1}) \mid (X_i)_{i=1}^{n}}(t) &= \Prob\paren*{\widetilde{\mathcal{E}}(Z_{k+1}) \leq t \st (X_i)_{i=1}^{n}} \\
&= \Prob\paren*{Z_{k+1} \in \widetilde{\mathcal{E}}^{-1}((-\infty, t]) \st (X_i)_{i=1}^{n}} \\
&= \Prob\paren*{Z_{k} + Y_{k} \in \widetilde{\mathcal{E}}^{-1}((-\infty, t]) \st (X_i)_{i=1}^{n}} \\
&= \Exp\brack*{\Prob\paren*{Z_k + Y_{k} \in \widetilde{\mathcal{E}}^{-1}((-\infty, t]) \st (X_i)_{i=1}^{n}, Y_k}} \\
&\leq \Exp\brack*{\sup_{a \in \R^{d}}\Prob\paren*{Z_k + a \in \widetilde{\mathcal{E}}^{-1}((-\infty, t]) \st (X_i)_{i=1}^{n}, Y_k}} \\
&= \Exp\brack*{\Prob\paren*{Z_k \in \widetilde{\mathcal{E}}^{-1}((-\infty, t]) \st (X_i)_{i=1}^{n}, Y_k}} \\
&= F_{\widetilde{\mathcal{E}}(Z_{k}) \mid (X_i)_{i=1}^{n}}(t),
\end{align*}

where the penultimate equality follows from Lemma <ref> and the fact that, given $((X_i)_{i=1}^{n}, Y_k)$, $Z_k$ is a centred Gaussian vector. Taking expectation of both sides with respect to $(X_i)_{i=1}^{n}$ proves that the sequence $(p_k)_{k \in \N}$ is decreasing. It remains to compute its limit.

By the monotone convergence theorem, we have

\begin{align}
\lim_{k \to \infty} F_{\widetilde{\mathcal{E}}(Z_k)}(t) &= \lim_{k \to \infty} \Prob\paren*{\widetilde{\mathcal{E}}(Z_k) \leq t} \nonumber \\
&= \lim_{k \to \infty} \Exp\brack*{\Prob\paren*{\widetilde{\mathcal{E}}(Z_k) \leq t \st (X_i)_{i=1}^{n}}} \nonumber \\
&= \Exp\brack*{\lim_{k \to \infty} \Prob\paren*{\widetilde{\mathcal{E}}(Z_k) \leq t \st (X_i)_{i=1}^{n}}}. \label{eq:pf_thm_3_6}
\end{align}

Furthermore, letting $Z \sim \mathcal{N}(0, I_{d \times d})$, we have

\begin{align}
\lim_{k\to \infty} \Prob\paren*{\widetilde{\mathcal{E}}(Z_k) \leq t \st (X_i)_{i=1}^{n}} &= \lim_{k\to \infty} \Prob\paren*{Z_k \in \widetilde{\mathcal{E}}^{-1}((-\infty, t]) \st (X_i)_{i=1}^{n}} \nonumber \\
&= \lim_{k\to \infty} \Prob\paren*{Z \in \frac{\sqrt{n}}{\sigma}\Sigma_k^{1/2} \widetilde{\mathcal{E}}^{-1}((-\infty, t]) \st (X_i)_{i=1}^{n}} \nonumber \\
&= \Prob\paren*{Z \in \bigcap_{k=1}^{\infty} \brace*{\frac{\sqrt{n}}{\sigma}\Sigma_k^{1/2} \widetilde{\mathcal{E}}^{-1}((-\infty, t])} \mid (X_i)_{i=1}^{n}} \nonumber \\
&= \Prob\paren*{Z \in \frac{\sqrt{n}}{\sigma} \widehat{\Sigma}_{n}^{1/2} \widetilde{\mathcal{E}}^{-1}((-\infty, t]) \st (X_i)_{i=1}^{n}}, \label{eq:pf_thm_3_7}
\end{align}

where the second line follows from the fact that $Z_k \overset{d}{=} \frac{\sigma}{\sqrt{n}}\Sigma^{1/2}_{k} Z$ and the third line from the continuity of probability and the fact that for all $k \in \N$,

\begin{equation*}
\frac{\sqrt{n}}{\sigma}\Sigma_{k+1}^{1/2} \widetilde{\mathcal{E}}^{-1}((-\infty, t]) \subset \frac{\sqrt{n}}{\sigma}\Sigma_k^{1/2} \widetilde{\mathcal{E}}^{-1}((-\infty, t]).
\end{equation*}

Indeed, by the spectral theorem, there exists an orthogonal matrix $Q$ and a diagonal matrix $\Lambda$ such that $\widehat{\Sigma}_{n} = Q \Lambda Q^{T}$, so  $\Sigma_{k}^{1/2} = Q (\Lambda^{1/2} + \lambda_k^{1/2} I) Q^{T}$. Now since $\lambda_{k+1} \leq \lambda_{k}$, we have by Lemma <ref>

\begin{equation*}
(\Lambda^{1/2} + \lambda_{k+1}^{1/2}) Q^{T}\widetilde{\mathcal{E}}^{-1}((-\infty, t]) \subset (\Lambda^{1/2} + \lambda_{k}^{1/2}) Q^{T}\widetilde{\mathcal{E}}^{-1}((-\infty, t]),
\end{equation*}

Mapping the above sets through $Q$ yields the desired statement. Now if $\rank({\widehat{\Sigma}_{n}}) < d$, then $\dim(\im(\widehat{\Sigma}_{n}^{1/2})) < d$ and

\begin{equation}
\label{eq:pf_thm_3_8}
0 \leq \Prob\paren*{Z \in \frac{\sqrt{n}}{\sigma} \widehat{\Sigma}_{n}^{1/2} \widetilde{\mathcal{E}}^{-1}((-\infty, t]) \st (X_i)_{i=1}^{n}} \leq \Prob\paren*{Z \in \im(\widehat{\Sigma}_{n}^{1/2})} = 0
\end{equation}

where the last equality follows since $Z$ is a standard normal vector, so its distribution is absolutely continuous with respect to Lebesgue measure on $\R^{d}$, and Lebesgue measure assigns zero measure to all hyperplanes. Otherwise, $\rank(\widehat{\Sigma}_{n}) = d$, and we get

\begin{equation}
\label{eq:pf_thm_3_9}
\Prob\paren*{Z \in \frac{\sqrt{n}}{\sigma} \widehat{\Sigma}_{n}^{1/2} \widetilde{\mathcal{E}}^{-1}((-\infty, t]) \st (X_i)_{i=1}^{n}} = \Prob\paren*{\widetilde{\mathcal{E}}\paren*{\frac{\sigma}{\sqrt{n}} \widehat{\Sigma}_{n}^{-1/2}Z} \leq t \st (X_i)_{i=1}^{n}}
\end{equation}

Combining (<ref>), (<ref>), (<ref>), and (<ref>) proves that

\begin{equation*}
\lim_{k \to \infty} p_{k}(t) = \Exp\brack*{\Prob\paren*{\widetilde{\mathcal{E}}\paren*{\frac{\sigma}{\sqrt{n}} \widehat{\Sigma}_{n}^{-1/2}Z} \leq t \st (X_i)_{i=1}^{n}} \mathbbm{1}_{\brace*{\rank(\widehat{\Sigma}_{n}) = d}}((X_i)_{i=1}^{n})}
\end{equation*}

which can be interpreted as the CDF of the random variable

\begin{equation*}
A((X_i)_{i=1}^{n}, Z) \defeq \begin{dcases*}
\widetilde{\mathcal{E}}\paren*{\frac{\sigma}{\sqrt{n}} \widehat{\Sigma}_{n}^{-1/2} Z} & if $\rank(\widehat{\Sigma}_{n}) = d$ \\
\infty & otherwise
\end{dcases*}
\end{equation*}

so we write $\lim_{k \to \infty} p_{k}(t) = F_{A}(t)$.
It remains to show that the worst case risk of the procedures defined in the theorem is $Q_{A}(1-\delta)$. Let $\hat{w}$ be a procedure satisfying the condition stated in the theorem and fix $w^{*} \in \R^{d}$. Then, on the event that $\rank(\widehat{\Sigma}_{n}) = d$, and through an elementary explicit calculation, we have $\hat{w} - w^{*} = \widehat{\Sigma}_{n}^{-1} (\frac{1}{n} \sum_{i=1}^{n} \eta_i X_i)$ where $\eta_{i} \sim \mathcal{N}(0, \sigma^{2})$ are . Therefore, $\frac{1}{n} \sum_{i=1}^{n} \eta_i X_i \mid (X_i)_{i=1}^{n} \sim \mathcal{N}(0, \sigma^{2}/n \cdot \widehat{\Sigma}_{n})$, and hence $\hat{w} - w^{*} \mid (X_i)_{i=1}^{n} \sim \mathcal{N}(0, \sigma^{2}/n \cdot \widehat{\Sigma}_{n}^{-1})$, so the worst case risk of this procedure is upper bounded by $Q_{A}(1-\delta)$. Applying Theorem <ref> concludes the proof.

We start with the lower bound. Let $k \in \N$, and let $\lambda_{k}$ be a strictly positive sequence converging to $0$. We have

\begin{align}
\sup_{P \in \mathcal{P}_{\text{Gauss}}(P_{X}, \sigma^2)} R_{n, \delta}(P, \hat{w}) &= \sup_{P \in \mathcal{P}_{\text{Gauss}}(P_{X}, \sigma^2)} Q_{\mathcal{E}(\hat{w}((X_i, Y_i)_{i=1}^{n}))}(1 - \delta) \nonumber \\
&= \sup_{w^{*} \in \R^{d}} F^{-1}_{\mathcal{E}(\hat{w}((X_i, Y_i)_{i=1}^{n}))}(1 - \delta) \nonumber \\
&= \paren*{\inf_{w^{*} \in \R^{d}} F_{\mathcal{E}(\hat{w}((X_i, Y_i)_{i=1}^{n}))}}^{-1}(1-\delta) \nonumber \\
&\geq \paren*{\Exp_{w^{*} \sim \mathcal{N}(0, \sigma^{2}(\lambda_k n)^{-1} I_{d})}\brack*{F_{\mathcal{E}(\hat{w}((X_i, Y_i)_{i=1}^{n})) \mid w^{*}}}}^{-1}(1-\delta) \nonumber \\
&= F^{-1}_{\mathcal{E}(\hat{w}((X_i, Y_i)_{i=1}^{n}))}(1-\delta) \nonumber \\
&= F^{-1}_{\ell(\hat{w}((X_i, Y_i)_{i=1}^{n})) - w^{*})}(1-\delta) \label{eq:pf_thm_3_1}
\end{align}

Where the first five steps are justified by the same reasoning as in the analogous argument in the proof of Theorem <ref>, and where the last step uses the definition of $\ell$ given by Theorem. Now define

\begin{equation*}
\hat{w}_{k} \defeq \Sigma_{k}^{-1} \paren*{\frac{1}{n}\sum_{i=1}^{n}Y_{i}X_i}, \quad \Sigma_{k} \defeq \widehat{\Sigma} + \lambda_k I_{d}, \quad \widehat{\Sigma} \defeq \frac{1}{n}\sum_{i=1}^{n} X_{i}X_{i}^{T}
\end{equation*}

Then by a classical Bayesian calculation, we have

\begin{equation*}
w^{*} \mid (X_i, Y_i)_{i=1}^{n} \sim \mathcal{N}\paren*{\hat{w}_{k}, \frac{\sigma^2}{n}\Sigma_{k}^{-1}}.
\end{equation*}

Now for any $\hat{w}$, we have

\begin{align}
F_{\ell\paren*{\hat{w}((X_i, Y_i)_{i=1}^{n}) - w^{*}} \mid (X_i, Y_i)_{i=1}^{n}}(r) &= \Prob\paren*{\ell\paren*{\hat{w}((X_i, Y_i)_{i=1}^{n}) - w^{*}} \leq r \mid (X_i, Y_i)_{i=1}^{n}} \nonumber \\
&= \Prob\paren*{w^{*} - \hat{w}((X_i, Y_i)_{i=1}^{n}) \in \ell^{-1}((-\infty, r]) \st (X_i, Y_i)_{i=1}^{n}} \nonumber \\
&= \Prob\paren*{w^{*} - \hat{w}_{k} \in \ell^{-1}((-\infty, r]) + \hat{w}((X_i, Y_i)_{i=1}^{n}) - \hat{w}_{k} \st (X_i, Y_i)_{i=1}^{n}} \nonumber \\
&\leq \Prob\paren*{w^{*} - \hat{w}_{k} \in \ell^{-1}((-\infty, r]) \st (X_i, Y_i)_{i=1}^{n}} \nonumber \\
&= \Prob\paren*{\ell(\hat{w}_{k} - w^{*}) \leq r \st (X_i, Y_i)_{i=1}^{n}} \nonumber \\
&= F_{\ell(\hat{w}_{k} - w^{*}) \mid (X_i, Y_i)_{i=1}^{n}}(r) \label{eq:pf_thm_3_2}
\end{align}

where again the steps are justified by the same reasoning as the analogous argument in the proof of Theorem <ref>, with the only modification that the quasiconvexity and symmetry of $\ell$ is deduced from Lemma <ref>. Taking expectation with respect to $(X_i, Y_i)_{i=1}^{n}$ on both sides of (<ref>), and using the sixth item of Lemma <ref>, we obtain

\begin{equation}
\label{eq:pf_thm_3_3}
\inf_{\hat{w}} F^{-1}_{\ell(\hat{w}((X_i, Y_i)_{i=1}^{n})) - w^{*})}(1-\delta) = F^{-1}_{\ell(\hat{w}_{k} - w^{*})}(1-\delta) = F^{-1}_{\ell(Z_k)} (1-\delta) = Q_{\ell(Z_k)}(1-\delta),
\end{equation}

where $Z_k \mid (X_i)_{i=1}^{n} \sim \mathcal{N}\paren*{0, \frac{\sigma^2}{n}\Sigma^{-1}_{k}}$.

Now we claim that for all $r \in \R$ and all $k \in \N$

\begin{equation}
\label{eq:pf_thm_3_4}
F_{\ell(Z_k)}(r) \geq F_{\ell(Z_{k+1})}(r)
\end{equation}

Indeed, let $k \in \N$. Note that since $\lambda_{k} \geq \lambda_{k+1}$,  $\Sigma_{k} \succeq \Sigma_{k+1}$, and therefore $\Sigma_{k}^{-1} \preceq \Sigma_{k+1}^{-1}$. We conclude that $Z_{k+1} \overset{d}{=} Z_{k} + Y_{k}$ where $Y_{k} \indep Z_{k} \mid (X_i)_{i=1}^{n}$ and $Y_k \mid (X_i)_{i=1}^{n} \sim \mathcal{N}(0, \frac{\sigma^{2}}{n} \brace*{\Sigma_{k+1}^{-1} - \Sigma_{k}^{-1}})$. Now

\begin{align*}
F_{\ell(Z_{k+1}) \mid (X_i)_{i=1}^{n}}(r) &= \Prob\paren*{\ell(Z_{k+1}) \leq r} \\
&= \Prob\paren*{Z_{k+1} \in \ell^{-1}((-\infty, r]) \st (X_i)_{i=1}^{n}} \\
&= \Prob\paren*{Z_{k} + Y_{k} \in \ell^{-1}((-\infty, r]) \st (X_i)_{i=1}^{n}} \\
&= \Exp\brack*{\Prob\paren*{Z_k \in \ell^{-1}((-\infty, r]) - Y_k \st (X_i)_{i=1}^{n}, Y_k}} \\
&\leq \Exp\brack*{\Prob\paren*{Z_k \in \ell^{-1}((-\infty, r]) \st (X_i)_{i=1}^{n}, Y_k}} \\
&= F_{\ell(Z_{k}) \mid (X_i)_{i=1}^{n}}(r),
\end{align*}

where the inequality follows from Lemma <ref> and the fact that, given $(X_i)_{i=1}^{n}, Y_k$, $Z_k$ is a centred Gaussian vector. Taking expectation of both sides with respect to $(X_i)_{i=1}^{n}$ finishes the proof of the first item.

We now further claim that

\begin{equation}
\label{eq:pf_thm_3_5}
\lim_{k \to \infty} F_{\ell(Z_k)}(r) = \Exp\brack*{\Prob\paren*{\ell\paren*{\frac{\sigma}{\sqrt{n}} \widehat{\Sigma}^{-1/2}Z} \leq r \st (X_i)_{i=1}^{n}} \mathbbm{1}_{\brace*{\rank\paren*{\widehat{\Sigma}} = d}}((X_i)_{i=1}^{n})} \eqdef \phi_{n}(r)
\end{equation}

Indeed, by the monotone convergence theorem, we have

\begin{align}
\lim_{k \to \infty} F_{\ell(Z_k)}(r) &= \lim_{k \to \infty} \Prob\paren*{\ell(Z_k) \leq r} \nonumber \\
&= \lim_{k \to \infty} \Exp\brack*{\Prob\paren*{\ell(Z_k) \leq r \st (X_i)_{i=1}^{n}}} \nonumber \\
&= \Exp\brack*{\lim_{k \to \infty} \Prob\paren*{\ell(Z_k) \leq r \st (X_i)_{i=1}^{n}}}. \label{eq:pf_thm_3_6}
\end{align}

Furthermore, letting $Z \sim \mathcal{N}(0, I_{d \times d})$, we have

\begin{align}
\lim_{k\to \infty} \Prob\paren*{\ell(Z_k) \leq r \st (X_i)_{i=1}^{n}} &= \lim_{k\to \infty} \Prob\paren*{Z_k \in \ell^{-1}((-\infty, r]) \st (X_i)_{i=1}^{n}} \nonumber \\
&= \lim_{k\to \infty} \Prob\paren*{Z \in \frac{\sqrt{n}}{\sigma}\Sigma_k^{1/2} \ell^{-1}((-\infty, r]) \st (X_i)_{i=1}^{n}} \nonumber \\
&= \Prob\paren*{Z \in \bigcap_{k=1}^{\infty} \brace*{\frac{\sqrt{n}}{\sigma}\Sigma_k^{1/2} \ell^{-1}((-\infty, r])} \mid (X_i)_{i=1}^{n}} \nonumber \\
&= \Prob\paren*{Z \in \frac{\sqrt{n}}{\sigma} \widehat{\Sigma}^{1/2} \ell^{-1}((-\infty, r]) \st (X_i)_{i=1}^{n}}, \label{eq:pf_thm_3_7}
\end{align}

where the second line follows from the fact that $Z_k \overset{d}{=} \frac{\sigma}{\sqrt{n}}\Sigma^{1/2}_{k} Z$ and the third line from the continuity of probability and the fact that for all $k \in \N$,

\begin{equation*}
\frac{\sqrt{n}}{\sigma}\Sigma_{k+1}^{1/2} \ell^{-1}((-\infty, r]) \subset \frac{\sqrt{n}}{\sigma}\Sigma_k^{1/2} \ell^{-1}((-\infty, r]).
\end{equation*}

Indeed, by the spectral theorem, there exists an orthogonal matrix $Q$ and a diagonal matrix $\Lambda$ such that $\widehat{\Sigma} = Q \Lambda Q^{T}$, so that $\Sigma_{k}^{1/2} = Q (\Lambda^{1/2} + \lambda_k^{1/2} I) Q^{T}$. Now since $\lambda_{k+1} \leq \lambda_{k}$, we have by Lemma <ref>

\begin{equation*}
(\Lambda^{1/2} + \lambda_{k+1}^{1/2}) Q^{T}\ell^{-1}((-\infty, r]) \subset (\Lambda^{1/2} + \lambda_{k}^{1/2}) Q^{T}\ell^{-1}((-\infty, r]),
\end{equation*}

Mapping the above sets through $Q$ yields the desired statement. Now if $\rank\paren*{\widehat{\Sigma}} < d$. Then $\dim(\im(\widehat{\Sigma}^{1/2})) < d$ and

\begin{equation}
\label{eq:pf_thm_3_8}
0 \leq \Prob\paren*{Z \in \frac{\sqrt{n}}{\sigma} \widehat{\Sigma}^{1/2} \ell^{-1}((-\infty, r]) \st (X_i)_{i=1}^{n}} \leq \Prob\paren*{Z \in \im(\Sigma^{1/2})} = 0
\end{equation}

where the last equality follows since $Z$ is a standard normal vector, so its distribution is absolutely continuous with respect to Lebesgue measure on $\R^{d}$, and Lebesgue measure assigns zero measure to all hyperplanes. Otherwise, $\rank\paren*{\widehat{\Sigma}} = d$, and we get

\begin{equation}
\label{eq:pf_thm_3_9}
\Prob\paren*{Z \in \frac{\sqrt{n}}{\sigma} \widehat{\Sigma}^{1/2} \ell^{-1}((-\infty, r]) \st (X_i)_{i=1}^{n}} = \Prob\paren*{\ell\paren*{\frac{\sigma}{\sqrt{n}} \widehat{\Sigma}^{-1/2}Z} \leq r \st (X_i)_{i=1}^{n}}
\end{equation}

Combining (<ref>), (<ref>), (<ref>), and (<ref>) proves (<ref>). Combining (<ref>) and (<ref>) and appealing to the last item of Lemma <ref>, we obtain

\begin{equation}
\label{eq:pf_thm_3_10}
\sup_{k \in \N} Q_{\ell(Z_k)}(1 - \delta) = \phi_{n}^{-}(1 - \delta)
\end{equation}

Finally, recalling that (<ref>) holds for all $k \in \N$, and using (<ref>) and (<ref>) yields

\begin{equation*}
\inf_{\hat{w}} \sup_{P \in \mathcal{P}_{\text{Gauss}}(P_{X}, \sigma^{2})} R_{n, \delta}(P, \hat{w}) \geq \sup_{k \in \N} Q_{\ell(Z_k)}(1 - \delta) = \phi_{n}^{-}(1 - \delta).
\end{equation*}

The upper bound follows from the following reasoning. (ADD PROOF).

§.§ Proof of Proposition <ref>

The proof is a simple application of the second-order delta method. Let $(Z_{n}, (X_i)_{i=1}^{n})$ be such that $(X_i)_{i=1}^{n} \sim P_{X}^{n}$ and $Z_{n} \mid (X_i)_{i=1}^{n} \sim \mathcal{N}(0, \frac{\sigma^2}{n} \widehat{\Sigma}_{n}^{-1})$ whenever $\widehat{\Sigma}_{n}$ is invertible and set $Z_{n} = 0$ otherwise. The conclusion of Theorem <ref> can then be rewritten as

\begin{equation*}
R^{*}_{n, \delta}(\mathcal{P}_{\text{Gauss}}(P_{X}, \sigma^{2})) = Q_{\widetilde{\mathcal{E}}(Z_n)}(1-\delta),
\end{equation*}

with the additional specification that $\widetilde{\mathcal{E}}(Z_{n}) \defeq \infty$ whenever $(X_i)_{i=1}^{n}$ is such that $\widehat{\Sigma}_{n}$ is singular. Recall that $Z \sim \mathcal{N}(0, I_{d \times d})$. By a property of Gaussian vectors, we have that on the event that $\widehat{\Sigma}_{n}$ is invertible, $Z_{n} \overset{d}{=} \frac{\sigma}{\sqrt{n}} \widehat{\Sigma}_{n}^{-1/2} Z$.
By the weak law of large numbers and the continuous mapping theorem, we have $
\widehat{\Sigma}_{n}^{-1/2} \overset{p}{\to} \Sigma^{-1/2}$, so that an application of Slutsky's theorem yields $\sqrt{n} \cdot Z_{n} \overset{d}{\to} \mathcal{N}(0, \sigma^{2} \Sigma^{-1})$. Now by assumption, $\widetilde{\mathcal{E}}$ is twice differentiable at $0$ where its gradient vanishes by Lemma <ref>, and where its Hessian is given by $\nabla^{2} \widetilde{\mathcal{E}}(0) = \Exp\brack*{e''(\eta) XX^{T}} = 2 \alpha \Sigma$ by independence of $\eta$ and $X$. Therefore, by an application of the delta method, we obtain

\begin{equation*}
\lim_{n \to \infty} n \cdot \widetilde{\mathcal{E}}(Z_n) \overset{d}{\to}
\sigma^{2} \alpha \norm{Z}_2^2
\end{equation*}

Since convergence in distribution implies the pointwise convergence of quantiles, we obtain the first equality in the proposition. The second statement follows from Lemma <ref>.

§.§ Proof of Lemma <ref>

We start with the first statement. Let $\delta \in (\eps_{n}, 1)$. By the monotone convergence theorem and the fact that $\widetilde{\mathcal{E}}(w) < \infty$ for all $w \in \R^{d}$ by assumption on $P_{X}$, we have

\begin{equation*}
\lim_{t \to \infty} F_{\widetilde{\mathcal{E}}(Z)}(t) = \lim_{t \to \infty} \Exp\brack*{\Prob\paren*{\widetilde{\mathcal{E}}(Z) \leq t \st (X_i)_{i=1}^{n}} \mathbbm{1}_{\brace*{\rank(\widehat{\Sigma}_{n}) = d}}((X_i)_{i=1}^{n})} = 1 - \eps_{n}
\end{equation*}

Therefore, since $1-\delta < 1-\eps_{n}$ there exists a $t \in \R$, such that $F_{\widetilde{\mathcal{E}}(Z)}(t) \geq 1-\delta$, so $Q_{\widetilde{\mathcal{E}}(Z)}(1-\delta) < \infty$. On the other hand, for all $t \in \R$, $F_{\widetilde{\mathcal{E}}(Z)}(t) < 1-\eps_{n}$, so for any $\delta \in [0, \eps_{n}]$, $Q_{\widetilde{\mathcal{E}}(Z)}(1-\delta) = \infty$. As for the lower bound on $\eps_{n}$, <cit.> proved that there exists a $w_{0} \in S^{d-1}$ such that $\rho(P_{X}) = \sup_{w \in \R^{d} \setminus \brace{0}} \Prob\paren*{\inp{w}{X} = 0} = \Prob\paren*{\inp{w_0}{X} = 0} < 1$. Therefore

\begin{equation*}
\eps_{n} = \Prob\paren*{\lambdamin(\widehat{\Sigma}_{n}) = 0} \geq \Prob\paren*{\bigcap_{i=1}^{n} \brace*{\inp{w_0}{X_i} = 0}} = \rho(P_{X})^{n}.
\end{equation*}

The upper bound on $\eps_{n}$ follows from the proof of <cit.>.

§.§ Proof of Proposition <ref>

In this proof we will let $Z \sim \mathcal{N}(0, \frac{\sigma^2}{n}\widetilde{\Sigma}^{-1}_{n})$, so that the minimax risk is given by $Q_{\norm{Z}_2^2}(1-\eps_{n} - \delta)/2$.
Define the random variables

\begin{equation*}
M((X_i)_{i=1}^{n}) \defeq \begin{dcases*}
\Exp\brack*{\norm{Z}_{2} \st (X_i)_{i=1}^{n}} & if $\rank(\widehat{\Sigma}_{n}) = d$ \\
\infty & otherwise
\end{dcases*}
\end{equation*}

\begin{equation*}
R((X_i)_{i=1}^{n}) \defeq \begin{dcases*}
\lambdamax\paren*{\frac{\sigma^2}{n}\widetilde{\Sigma}_{n}^{-1}} & if $\rank(\widehat{\Sigma}_{n}) = d$ \\
\infty & otherwise
\end{dcases*}
\end{equation*}

To simplify notation, we will write $M$ and $R$ only, and leave the dependence on $(X_i)_{i=1}^{n}$ implicit.

Upper bound. We have, for all $r \in \R$,

\begin{align*}
F_{\norm{Z}_2^{2}}(r^2) &= \Exp\brack*{\Prob\paren*{\norm{Z}_2 \leq r \st (X_i)_{i=1}^{n}} \mathbbm{1}_{\brace*{\rank(\widehat{\Sigma}_{n}) = d}}((X_{i})_{i=1}^{n})} \\
&= \Exp\brack*{\brace*{1 - \Prob\paren*{\norm{Z}_{2} > r \st (X_i)_{i=1}^{n}}} \mathbbm{1}_{\brace*{\rank(\widehat{\Sigma}_{n}) = d}}((X_{i})_{i=1}^{n})} \\
&\geq \Exp\brack*{\brace*{1 - \exp\paren*{-\frac{\abs{r-M}^2}{2R}}}\mathbbm{1}_{[M, \infty)}(r) \mathbbm{1}_{\brace*{\rank(\widehat{\Sigma}_{n}) = d}}((X_{i})_{i=1}^{n})} \\
&= \Exp\brack*{\brace*{1 - \exp\paren*{-\frac{\abs{r-M}^2}{2R}}}\mathbbm{1}_{[0, r]}(M)} \\
&= \Prob\paren*{M \leq r} - \Exp\brack*{\exp\paren*{-\frac{\abs{r - M}^2}{2R}} \mathbbm{1}_{[0, r]}(M)} \eqdef L(r)
\end{align*}

where the inequality follows from the Gaussian concentration (Lemma <ref>), and where the expression inside the expectation is defined to be $0$ whenever $\rank(\widehat{\Sigma}) < d$. The penultimate equality follows from the fact that $\mathbbm{1}_{[M, \infty)}(r) \mathbbm{1}_{\rank(\widehat{\Sigma}) = d}((X_{i})_{i=1}^{n}) = \mathbbm{1}_{[0, r]}(M)$.
Now let $0 < c \leq 1$ and define $q \defeq Q_{M}(1 - \eps_{n} - c\delta)$. Then, recalling the definition of $W$ from the statement,

\begin{align*}
L(r + q) &\geq \Prob\paren*{M \leq q} + \Prob\paren*{M \in (q, r + q]} \\ &\quad - \Exp\brack*{\exp\paren*{-\frac{r^2}{2R}} \mathbbm{1}_{[0, q]}(M)} - \Exp\brack*{\underbrace{\exp\paren*{-\frac{\abs{r - M}^2}{2R}}}_{\textstyle \leq 1}\mathbbm{1}_{(q, r + q]}(M)} \\
&\geq \Prob\paren*{M \leq q} - \Exp\brack*{\exp\paren*{-\frac{r^2}{2R}} \mathbbm{1}_{[0, q]}(M)} \\
&\geq 1 - \eps_{n} - c\delta - \Exp\brack*{\exp\paren*{-\frac{r^2}{2R}}\mathbbm{1}_{\rank(\widehat{\Sigma}) = d}((X_{i})_{i=1}^{n})} \\
&=\Exp\brack*{\brace*{1 - \exp\paren*{-\frac{r^{2}}{2R}}} \mathbbm{1}_{\rank(\widehat{\Sigma}) = d}((X_{i})_{i=1}^{n})} - c\delta \\
&= \Prob\paren*{\sqrt{\frac{2\sigma^{2}}{n}W} \leq r} - c\delta
\end{align*}

hence taking $r = \sqrt{\frac{2\sigma^{2}}{n}Q_{W}(1 - \eps_{n} - c \delta)}$ and $c = 1/2$ in the last display yields

\begin{equation*}
L\paren*{Q_{M}(1 - \eps_{n} - \delta/2) + \sqrt{\frac{2\sigma^{2}}{n}Q_{W}(1 - \eps_{n} - \delta/2)}} \geq 1 - \eps_{n} - \delta
\end{equation*}

And since $F_{\norm{Z}_2^2} \circ \varphi \geq L$ where $\varphi(r) = r^2$, we get by the second item of Lemma <ref> that $\varphi^{-1} \circ Q_{\norm{Z}_2^2} \leq L^{-}$. Applying $\varphi$ to both sides yields and using Lemma <ref> we obtain,

\begin{align*}
Q_{\norm{Z}_2^2}(1 - \eps_{n} - \delta) &\leq (L^{-}(1 - \eps_{n} - \delta))^{2} \\
&\leq \paren*{Q_{M}(1 - \eps_n - \delta/2) + \sqrt{\frac{2\sigma^{2}}{n}Q_{W}(1 - \eps_{n} - \delta/2)}}^2 \\
&\leq 2 \brack*{Q_{M^{2}}(1 - \eps_{n} - \delta/2) + \frac{2\sigma^{2}}{n}Q_{W}(1 - \eps_{n} - \delta/2)} \\
&\leq \frac{2\sigma^{2}}{n} \paren*{Q_{\Tr\paren*{\widetilde{\Sigma}^{-1}}}(1-\eps_{n}-\delta/2) + 2 Q_{W}(1 - \eps_{n} - \delta/2)} \\
&\leq 4 \cdot \frac{\sigma^{2}}{n} \paren*{Q_{\Tr\paren*{\widetilde{\Sigma}^{-1}}}(1-\eps_{n}-\delta/2) + Q_{W}(1 - \eps_{n} - \delta/2)},
\end{align*}

where in the penultimate inequality, we used the fact that $M^2 \leq \Tr\paren*{\widetilde{\Sigma}_{n}^{-1}}$ by Jensen's inequality.

Lower bound. For any $(X_i)_{i=1}^{n}$, define $v((X_i)_{i=1}^{n})$ to be the eigenvector corresponding to the smallest eigenvalue of $\widetilde{\Sigma}_{n}$. Then we have.

\begin{align*}
F_{\norm{Z}_2^2}(r^2) &= \Exp\brack*{\Prob\paren*{\norm{Z}_2 \leq r \st (X_i)_{i=1}^{n}} \mathbbm{1}_{\rank(\widehat{\Sigma}) = d}((X_{i})_{i=1}^{n})} \\
&\leq \Exp\brack*{\Prob\paren*{\abs{\inp{v((X_i)_{i=1}^{n})}{Z}} \leq r \st (X_i)_{i=1}^{n}}\mathbbm{1}_{\rank(\widehat{\Sigma}) = d}((X_{i})_{i=1}^{n})} \\
&\leq \Exp\brack*{\sqrt{1 - \exp\paren*{-\frac{2r^{2}}{\pi R}}} \mathbbm{1}_{\rank(\widehat{\Sigma}) = d}((X_{i})_{i=1}^{n})} \\
&\leq \Exp\brack*{\brace*{1 - \frac{1}{2}\exp\paren*{-\frac{2r^{2}}{\pi R}}} \mathbbm{1}_{\rank(\widehat{\Sigma}) = d}((X_{i})_{i=1}^{n})} \\
&= \frac{1}{2}(1 - \eps_{n}) + \frac{1}{2} \Exp\brack*{\brace*{1 - \exp\paren*{-\frac{2r^{2}}{\pi R}}} \mathbbm{1}_{\rank(\widehat{\Sigma}) = d}((X_{i})_{i=1}^{n})} \\
&= \frac{1}{2}\paren*{1 - \eps_{n} + \Prob\paren*{\sqrt{\frac{\pi \sigma^2}{2n}W} \leq r}} \eqdef U_1(r)
\end{align*}

Where the third line follows from Lemma <ref>. Now let $\eps > 0$ and define

\begin{equation*}
r(\eps) \defeq \sqrt{\frac{\pi \sigma^2}{2n} Q_{W}(1 - \eps_{n} - 2\delta)} - \eps
\end{equation*}

\begin{equation*}
U_1(r(\eps)) < \frac{1}{2}\paren*{1 - \eps_{n} + 1 - \eps_{n} - 2\delta} = 1 - \eps_{n} - \delta.
\end{equation*}

Since this holds for all $\eps > 0$, we obtain $U_{1}^{-}(1 - \eps_{n} - \delta) \geq r(0)$. Therefore,

\begin{equation*}
Q_{\norm{Z}_2^2}(1 - \eps_{n} - \delta) \geq (U_{1}^{-}(1 - \eps_{n} - \delta))^{2} \geq r^2(0) = \frac{\pi \sigma^2}{2n} Q_{W}(1 - \eps_{n} - 2\delta)
\end{equation*}

This finishes the proof of the first part of the lower bound.
For the second part of the lower bound, we also have by Gaussian concentration, and in particular Lemma <ref>,

\begin{align*}
F_{\norm{Z}_2^2}(r^2) &= \Exp\brack*{\Prob\paren*{\norm{Z}_2 \leq r \st (X_i)_{i=1}^{n}} \mathbbm{1}_{\rank(\widehat{\Sigma}) = d}((X_{i})_{i=1}^{n})} \\
&\leq \Exp\brack*{\exp\paren*{-\frac{\abs{M - r}^{2}}{\pi M^2}} \mathbbm{1}_{[0, M]}(r)\mathbbm{1}_{\rank(\widehat{\Sigma}) = d}((X_{i})_{i=1}^{n}) + \mathbbm{1}_{(M, \infty)}(r)\mathbbm{1}_{\rank(\widehat{\Sigma}) = d}((X_{i})_{i=1}^{n})} \\
&= \Exp\brack*{\exp\paren*{-\frac{\abs{M-r}^2}{\pi M^2}} \mathbbm{1}_{[r, \infty)}(M) + \mathbbm{1}_{[0, r)}(M)} \\
&= \Prob\paren*{M < r} + \Exp\brack*{\exp\paren*{-\frac{\abs{M-r}^2}{\pi M^2}} \mathbbm{1}_{[r, \infty)}(M)} \eqdef U_2(r)
\end{align*}

Let $a \in (0, 1)$, $c > 1$, and $q \defeq Q_{M}(1 - \eps_n - c\delta)$. Then we have,

\begin{align*}
U((1-a)q) &= \Exp\brack*{\underbrace{\exp\paren*{-\frac{\abs*{M - (1-a)q}^2}{\pi M^2}}}_{\textstyle \leq 1} \mathbbm{1}_{[(1-a)q, q)}(M)} + \Exp\brack*{\exp\paren*{-\frac{\abs*{M-(1-a)q}^2}{\pi M^2}} \mathbbm{1}_{[q, \infty)}(M)} \\
&\quad + \Prob\paren*{M < q} - \Prob\paren*{(1-a)q \leq M < q} \\
&\leq \Prob\paren*{M < q} + \Exp\brack*{\exp\paren*{-\frac{\abs{M-(1-a)q}^2}{\pi M^2}} \mathbbm{1}_{[q, \infty)}(M)} \\
&\leq \Prob\paren*{M < q} + \exp\paren*{-\frac{a^2}{\pi}} \Prob\paren*{q \leq M < \infty} \\
&\leq \Prob\paren*{M < q} + \exp\paren*{-\frac{a^2}{\pi}} (1 - \eps_{n} - \Prob\paren*{M < q}) \\
&\leq \paren*{1 - \exp\paren*{-\frac{a^2}{\pi}}} \Prob\paren*{M < q} + \exp\paren*{-\frac{a^2}{\pi}}(1 - \eps_{n}) \\
&\leq \paren*{1 - \exp\paren*{-\frac{a^2}{\pi}}} (1 - \eps_{n} - c\delta) + \exp\paren*{-\frac{a^2}{\pi}}(1-\eps_{n}) \\
&= 1 - \eps_{n} - \paren*{1 - \exp\paren*{-\frac{a^2}{\pi}}} c \delta \\
&< 1 - \eps_{n} - \delta
\end{align*}

where the last line follows from taking $a = 0.96$, and $c = 4$, and noticing that with these choices $c \paren*{1 - \exp\paren*{-\frac{a^2}{\pi}}} > 1$. Now since $F_{\norm{Z}_2^2} \circ \varphi \leq U_2$ where $\varphi(r) = r^2$, we get by the second item of Lemma <ref> and an application of Lemma <ref>,

\begin{align*}
Q_{\norm{Z}_2^2}(1 - \eps_{n} - \delta) &\geq (U^{-}(1 - \eps_{n} - \delta))^2 \\
&\geq \paren*{\frac{1}{25}Q_{M}(1 - \eps_{n} - 4\delta)}^2 \\
&= \frac{1}{625} Q_{M^{2}}(1 - \eps_{n} - 4\delta) \\
& \geq \frac{1}{625 (1 + \pi/2)} \frac{\sigma^2}{n} Q_{\Tr\paren*{\widetilde{\Sigma}^{-1}}}(1 - \eps_{n} - 4\delta).
\end{align*}

Averaging the two lower bounds yields the result.

§.§ Are the bounds in Proposition <ref> tight ?

We start with a general lemma.

Let $X \in [0, \infty]$ be random variable and let $p \defeq \Prob\paren*{X = \infty}$. Assume that

\begin{equation*}
\lim_{x \to \infty} x^{\alpha}(1 - p - F_{X}(x)) = 0,
\end{equation*}

for some $\alpha > 0$. Then, for all $c > 1$, we have

\begin{equation*}
\liminf_{\delta \downarrow 0} \frac{Q_{X}(1 - p - \delta/c)}{Q_{X}(1 - p - \delta)} \leq c^{1/\alpha}.
\end{equation*}

Suppose not. Define $\Delta \defeq M - c^{1/\alpha} > 0$ and the function

\begin{equation*}
r(\delta) \defeq \frac{Q_{X}(1 - p - \delta/c)}{Q_{X}(1 - p - \delta)}.
\end{equation*}

Then, since $\liminf_{\delta \downarrow 0} r(\delta) = M > c^{1/\alpha}$, there exists $\delta_{*} \in (0, 1)$ such that

\begin{equation*}
\inf\brace*{r(\delta) \st \delta \in (0, \delta_*]} \geq M - \frac{\Delta}{2}
\end{equation*}

On the other hand, there exists $x_{*} \in [0, \infty)$ such that for all $x \geq x_{*}$, we have $x^{\alpha}(1 - F_{X}(x)) \leq 1$, or equivalently

\begin{equation*}
F_{X}(x) \geq \paren*{1 - p - \frac{1}{x^{\alpha}}} \mathbbm{1}_{[x_{*}, \infty)}(x)
\end{equation*}

This in turn implies, by Lemma (REFERENCE), that

\begin{equation*}
Q_{X}(1 - p - \delta) \leq \max\brace*{x_{*}, \frac{1}{\delta^{1/\alpha}}}
\end{equation*}

so that, for $\delta \in (0, x_{*}^{-a}]$, we obtain

\begin{equation*}
Q_{X}(1 - p - \delta) \leq \frac{1}{\delta^{1/\alpha}}
\end{equation*}

Define $\delta_{0} \defeq \min\brace*{x_{*}^{-\alpha}, \delta_{*}} > 0$, and let $k \in N$. Then by induction, we have

\begin{equation*}
Q_{X}(1 - \delta_{0}/c^{k}) = Q_{X}(1-\delta_{0}/c^{k-1}) r(\delta_{0}/c^k) \geq \dotsc \geq (M - \Delta/2)^k Q_{X}(1 - \delta_{0})
\end{equation*}

On the other, we have

\begin{equation*}
Q_{X}(1-\delta_{0}/c^k) \leq \paren*{\frac{c^{k}}{\delta_{0}}}^{1/\alpha} = \frac{c^{k/\alpha}}{\delta_{0}^{1/\alpha}}
\end{equation*}

which leads to the contradiction

\begin{equation*}
0 < \delta_{0}^{1/\alpha} Q_{X}(1-\delta_{0}) \leq \paren*{\frac{c^{1/\alpha}}{M - \Delta/2}}^{k} \to 0 \text{ as } k \to \infty,
\end{equation*}

where the last limit converges to $0$ since $M - \Delta/2 > M - \Delta = c^{1/\alpha}$.

Suppose that there exists an $\alpha > 0$ such that

\begin{equation*}
\lim_{t \to \infty} t^{\alpha} \Prob\paren*{\lambdamin(\widetilde{\Sigma}_{n}) < \frac{1}{t}} = 0
\end{equation*}

Then there exists a sequence $(\delta_k)_{k=1}^{\infty}$ in $(0, 1-\eps_n)$ satisfying $\delta_k \to 0$ as $k \to \infty$ such that

\begin{equation*}
R_{n, \eps_{n} + \delta}^{*}(\mathcal{P}_{\text{Gauss}}(P_{X}, \sigma^2)) \asymp Q_{\Tr\paren*{\widetilde{\Sigma}_{n}^{-1}}}(1 - \eps_n - \delta_{k}) + Q_{W}(1 - \eps_n - \delta_{k}).
\end{equation*}

We note that a sufficient condition for the hypothesis of Corollary <ref> to hold is the finiteness of $\Exp\brack*{\lambdamax(\widetilde{\Sigma}^{-1}_{n}) \mathbbm{1}_{[0, \infty)}(\lambdamax(\widetilde{\Sigma}_{n}^{-1}))}$ for some $\alpha > 0$.

§.§ Proof of Lemma <ref>

We start with the bounds on $Q_{\Tr(\widetilde{\Sigma}^{-1}_{n})}(1 - \delta)$, and in particular the lower bound. If $(a_i)_{i=1}^{d}$ is a finite sequence of non-negative real numbers, then twice applying the AM-GM inequality we obtain

\begin{equation*}
\frac{d}{\sum_{i=1}^{d}{\frac{1}{a_i}}} \leq \paren*{\prod_{i=1}^{d} a_i}^{1/d} \leq \frac{\sum_{i=1}^{n}a_{i}}{d} \implies \sum_{i=1}^{d} \frac{1}{a_i} \geq \frac{d^{2}}{\sum_{i=1}^{d}a_i}.
\end{equation*}

Using this, we have

\begin{equation*}
\Tr\paren*{\widetilde{\Sigma}_{n}^{-1}} = \sum_{i=1}^{d} \lambda_i(\widetilde{\Sigma}_{n}^{-1}) = \sum_{i=1}^{d} \frac{1}{\lambda_i(\widetilde{\Sigma}_{n})} \geq \frac{d^{2}}{\Tr(\widetilde{\Sigma}_{n})}.
\end{equation*}

Now, since $\Exp\brack{\Tr(\widetilde{\Sigma}_{n})} = d$, we have

\begin{equation*}
\Prob\paren*{\frac{d^2}{\Tr(\widetilde{\Sigma}_{n})} \leq t} = \Prob\paren*{\Tr(\widetilde{\Sigma}_{n}) \geq \frac{d^2}{t}} \leq \frac{\Exp\brack{\Tr(\widetilde{\Sigma}_{n})}}{d^{2}/t} = \frac{t}{d}.
\end{equation*}

Applying the second item of Lemma <ref>, we obtain the desired lower bound

\begin{equation*}
Q_{\Tr(\widetilde{\Sigma}_{n}^{-1})}(1 - \delta) \geq Q_{d^{2}/\Tr(\widetilde{\Sigma}_{n})}(1-\delta) \geq d \cdot (1-\delta).
\end{equation*}

The upper bound follows from the simple observation $\Tr(\widetilde{\Sigma}_{n}^{-1}) \leq d \cdot \lambdamax(\widetilde{\Sigma}^{-1}_{n})$. We now move to bounds on $Q_{W}(1-\delta)$, and we start with the lower bound. By definition, we have

\begin{equation*}
1-\delta \leq \Prob\paren*{W \leq Q_{W}(1-\delta)} = 1 - \Exp\brack*{\exp(-Q_{W}(1-\delta) \cdot \lambdamin(\widetilde{\Sigma}_{n}))},
\end{equation*}

hence, by Jensen's inequality

\begin{equation*}
\delta \geq \Exp\brack*{\exp(-Q_{W}(1-\delta) \cdot \lambdamin(\widetilde{\Sigma}_{n}))} \geq \exp\paren*{-Q_{W}(1-\delta) \cdot \Exp\brack*{\lambdamin(\widetilde{\Sigma}_{n})}},
\end{equation*}

and using the variational characterization of the smallest eigenvalue we get, for any $v \in S^{d-1}$,

\begin{equation*}
\Exp\brack*{\lambdamin(\widetilde{\Sigma}_{n})} = \Exp\brack*{\inf_{v \in S^{d-1}} \frac{1}{n} \sum_{i=1}^{n} \inp{v}{\Sigma^{-1/2}X_i}^{2}} \leq \Exp\brack*{\inp{v}{\Sigma^{-1/2}X}^{2}} = 1.
\end{equation*}

Therefore $Q_{W}(1-\delta) \geq \log(1/\delta)$ as desired. For the upper bound, let $q \defeq Q_{\lambdamax(\widetilde{\Sigma}_{n}^{-1})}(1-\delta/2)$ and define the event $A \defeq \brace*{\lambdamax(\widetilde{\Sigma}^{-1}_{n}) \leq q}$ which satisfies $\Prob\paren*{A} \geq 1-\delta/2$. Notice that

\begin{equation*}
\Prob\paren*{W \leq t} \geq \Exp\brack*{\brace*{1 - \exp\paren*{-\frac{t}{\lambdamax(\widetilde{\Sigma}^{-1}_{n})}}} \mathbbm{1}_{A}((X_i)_{i=1}^{n})} \geq (1-\delta/2)\paren*{1 - \exp(t/q)}.
\end{equation*}

Taking $t \geq q \cdot \log(2/\delta)$ ensures that the above probability is at least $1-\delta$. By the minimality of the quantile, we get that $Q_{W}(1-\delta) \leq Q_{\lambdamax(\widetilde{\Sigma}_{n}^{-1})}(1-\delta/2) \cdot \log(2/\delta)$, which is the desired upper bound.

§.§ Proof of Corollary <ref>

We claim that for all the allowed sample sizes,

\begin{equation*}
Q_{\lambdamax(\widetilde{\Sigma}_{n}))}(1-\delta/2) \leq 2.
\end{equation*}

Indeed, the restriction on the sample size $n$ is chosen in such a way that by the upper bound in Proposition <ref>, we have

\begin{equation*}
Q_{1 - \lambdamin(\widetilde{\Sigma}_{n})}(1-\delta/2) \leq \frac{1}{2}
\end{equation*}

Now if $1 - \lambdamin(\widetilde{\Sigma}_{n}) \leq 1/2$, then $\lambdamin(\widetilde{\Sigma}_{n}) \geq 1/2$ and $\lambdamax(\widetilde{\Sigma}_{n}^{-1}) = \lambdamin^{-1}(\widetilde{\Sigma}_{n}) \leq 2$. Therefore

\begin{equation*}
\Prob\paren*{\lambdamax(\widetilde{\Sigma}^{-1}_{n}) \leq 2} \geq \Prob\paren*{\lambdamin(\widetilde{\Sigma}_{n}) \leq 1/2} \geq \Prob\paren*{\lambdamin(\widetilde{\Sigma}_{n}) \leq Q_{1 - \lambdamin(\widetilde{\Sigma}_{n})}(1-\delta/2)} \geq 1-\delta/2.
\end{equation*}

which finishes the proof of the bound on $Q_{\lambdamax(\widetilde{\Sigma}_{n}))}(1-\delta/2)$. Now appealing to Lemma <ref> proves the result.

§.§ Proof of Proposition <ref>

Using Lemma 2.5 in [Adil et al., 2023], we have for the $p$-th power error $e(t) = \abs{t}^{p}/[p(p-1)]$,

\begin{equation*}
\widetilde{\mathcal{E}}(\Delta) = \Exp\brack*{e(\inp{\Delta}{X} + \eta)} - \Exp\brack*{e(\eta)} \geq \frac{1}{8(p-1)} \Delta^{T}\Exp\brack*{e''(\eta) XX^{T}}\Delta.
\end{equation*}

Since $e''(t) = \abs{t}^{p-2}$, and $\eta$ and $X$ are independent,

\begin{equation*}
\widetilde{\mathcal{E}}(\Delta) \geq \frac{1}{8(p-1)} \cdot m(p-2) \sigma^{p-2} \Delta^{T} \Sigma \Delta.
\end{equation*}

Therefore, by Theorem <ref>,

\begin{equation*}
R_{n, \delta}(\mathcal{P}_{\text{Gauss}}(P_{X}, \sigma^{2})) = Q_{\widetilde{\mathcal{E}}(Z)}(1-\delta) \geq \frac{m(p-2) \sigma^{p-2}}{8(p-1)} \cdot \frac{\sigma^{2}}{n} Q_{\norm{A}_{2}^{2}}(1 - \delta)
\end{equation*}

where $A \sim \mathcal{N}(0, \widetilde{\Sigma}_{n}^{-1})$. Now noting that $\frac{\sigma^2}{n} Q_{\norm{A}_2^{2}}(1-\delta)$ is the minimax risk under the square error, applying Proposition <ref> and Lemma <ref>, and using the constraint on $\delta$, we obtain the desired lower bound.

§ PROOFS OF SECTION <REF>

§.§ Proof of Theorem <ref>

Fix a distribution $P \in \mathcal{P}_{2}(P_{X}, \sigma^2)$. We will prove an upper bound on the risk of the proposed procedure under $P$. We follow the approach developed by Lugosi and Mendelson, 2019. Define

\begin{equation*}
\phi(w) = \max_{v \in \R^{d}} \psi_{k}(w, v),
\end{equation*}

and note that by definition of $\hat{w}_{n, \delta}$, we have

\begin{equation}
\label{eq:g_0_1}
\psi_{k}(\hat{w}_{n, k}, w^{*})\leq \phi(\hat{w}_{n, k}) \leq \phi(w^{*}).
\end{equation}

The key idea of the proof is to show that $\norm{\hat{w}_{n, k} - w^{*}}_{\Sigma}$ is small, by simultaneously showing that

* For all $w \in \R^{d}$, if $\norm{w - w^{*}}_{\Sigma}$ is large, then so is $\psi_{k}(w, w^{*})$,

* $\phi(w^{*})$ is small.

The combination of these statements combined with (<ref>) will show that $\norm{\hat{w}_{n,k} - w^{*}}_{\Sigma}$ is indeed small. Define

\begin{equation*}
\Delta(\delta) \defeq 50 \sqrt{\frac{\sigma^{2} [d + \log(4/\delta)]}{n}}
\end{equation*}

All the following lemmas are stated under the conditions of Theorem <ref>.
The first step of the proof is a simple application of Lemma <ref>.

\begin{equation*}
\Prob\paren*{\sup_{\norm{v}_{\Sigma} \leq 1} n^{-1}\varphi_{k}\brack*{(\inp{\nabla e(\inp{w^{*}}{X_i} - Y_{i})}{v})_{i=1}^{n}} > \Delta(\delta)} \leq \delta/2
\end{equation*}

For $v \in \R^{d}$ such that $\norm{v}_{\Sigma} \leq 1$ and $i \in [n]$, define

\begin{equation*}
Z_{i, v} \defeq \frac{1}{n} \inp{\nabla e(\inp{w^{*}}{X_i} - Y_{i})}{v} = \frac{1}{n} \xi_i \inp{X_{i}}{v}
\end{equation*}

Our aim is to apply Lemma <ref>, so we make the necessary computations here. We have

\begin{align*}
\Exp\brack*{Z_{i, v}} &= \frac{1}{n} \inp{\Exp\brack*{\nabla e(\inp{w^{*}}{X_i} - Y_{i})}}{v} = \frac{1}{n}\inp{\nabla E(w^{*})}{v} = 0, \\
\sup_{\norm{v}_{\Sigma} \leq 1} \sum_{i=1}^{n} \Exp\brack*{Z_{i, v}^{2}} &= \frac{1}{n} \sup_{\norm{v}_{\Sigma} = 1} \Exp\brack*{\xi^{2}\inp{X}{v}^{2}} \leq \frac{\sigma^{2}}{n}.
\end{align*}

where the last inequality follows from the assumption $\Exp\brack*{\xi^{2} \mid X} \leq \sigma^{2}$. Now, for independent Rademacher variables $(\eps_i)_{i=1}^{n}$, we have

\begin{align*}
\Exp\brack*{\sup_{\norm{v}_{\Sigma}=1} \sum_{i=1}^{n} \eps_i Z_{i, v}}
&= \Exp\brack*{\sup_{\norm{v}_{\Sigma} = 1} \inp*{\frac{1}{n}\sum_{i=1}^{n} \eps_{i} \xi_i X_{i}}{v}} \\
&= \Exp\brack*{\norm*{\frac{1}{n} \sum_{i=1}^{n} \eps_i \xi_i X_i}_{\Sigma^{-1}}} \\
&\leq \Exp\brack*{\norm*{\frac{1}{n} \sum_{i=1}^{n} \eps_i \xi_i X_i}_{\Sigma^{-1}}^{2}}^{1/2} \\
&= \sqrt{\frac{\Exp\brack{\xi^{2} \norm{X}_{\Sigma^{-1}}^{2}}}{n}} \leq \sqrt{\frac{\sigma^{2} d}{n}}.
\end{align*}

Where again we have used the assumption $\Exp\brack*{\xi^{2} \mid  X} \leq \sigma^{2}$. Recalling that $k = 8\log(2/(\delta/2))$ from the statement of the theorem, and applying Lemma <ref> with the above constants yields the result.

From this result, we can deduce the following estimate, which will help us bound $\phi(w^{*})$ later on.

For any $r \in (0, \infty)$,

\begin{equation*}
\Prob\paren*{\sup_{\norm{v - w^{*}}_{\Sigma} < r} \psi_{k}(w^{*}, v) > r \cdot \Delta(\delta)} \leq \delta/2.
\end{equation*}

We have

\begin{align*}
\sup_{\norm{v - w^{*}}_{\Sigma} < r} \psi_{k}(w^{*}, v) &= \sup_{\norm{v - w^{*}}_{\Sigma} < r} \varphi_{k}\brack*{\paren*{e(\inp{w^{*}}{X_{i}} - Y_{i}) - e(\inp{v}{X_{i}} - Y_{i})}_{i=1}^{n}} \\
&= \sup_{\norm{v - w^{*}}_{\Sigma} < r} \varphi_{k}\brack*{\paren*{-\inp{\nabla e(\inp{w^{*}}{X_i} - Y_i)}{v - w^{*}} - \frac{1}{2}\inp{X_i}{v - w^{*}}^{2}}_{i=1}^{n}} \\
&\leq \sup_{\norm{v - w^{*}}_{\Sigma} < r} \varphi_{k}\brack*{\paren*{-\inp{\nabla e(\inp{w^{*}}{X_i} - Y_i)}{v - w^{*}}}_{i=1}^{n}} \\
&= \sup_{\norm{v - w^{*}}_{\Sigma} < r} r \cdot \varphi_{k}\brack*{\paren*{\inp*{\nabla e(\inp*{w^{*}}{X_i} - Y_i)}{\frac{v - w^{*}}{r}}}_{i=1}^{n}} \\
&= r \cdot \sup_{\norm{v}_{\Sigma} < 1} \varphi_{k}\brack*{\paren*{\inp{\nabla e(\inp*{w^{*}}{X_i} - Y_i)}{v}}_{i=1}^{n}}
\end{align*}

where the first line is by definition, the second holds since $e$ is quadratic so its second order Taylor expansion is exact, the third by the third item of Lemma <ref>, and the fourth by the first item of Lemma <ref>. Applying Lemma <ref> to the last line yields the result.

The key technical novelty of this proof is the following lemma, which uses our new results Proposition <ref> and Lemma <ref>.

Let $r \in [8\Delta(\delta), \infty)$. Then

\begin{equation*}
\Prob\paren*{\inf_{\norm{v - w^{*}} \geq r} \psi_{k}(v, w^{*}) < \frac{r^{2}}{8} - r\Delta(\delta)} \leq \delta
\end{equation*}

We start with the case $\norm{v - w^{*}}_{\Sigma} = r$. We have

\begin{align*}
\inf_{\norm{v - w^{*}}_{\Sigma} = r} \psi_{k}(v, w^{*}) &= \inf_{\norm{v - w^{*}}_{\Sigma} = r} n^{-1} \varphi_{k}\brack*{\paren*{e(\inp{v}{X_{i}} - Y_{i}) - e(\inp{w^{*}}{X_{i}} - Y_{i})}_{i=1}^{n}} \\
&= \inf_{\norm{v - w^{*}}_{\Sigma} = r} n^{-1} \varphi_{k}\brack*{\paren*{\inp{\nabla e(\inp{w^{*}}{X_i} - Y_i)}{v - w^{*}} + \frac{1}{2} \inp{v - w^{*}}{X_i}^{2} }_{i=1}^{n}} \\
&= \inf_{v \in S^{d-1}} n^{-1} \varphi_{k}\brack*{\paren*{r \cdot \inp{\nabla e(\inp{w^{*}}{X_i} - Y_i)}{\Sigma^{-1/2}v} + \frac{r^{2}}{2} \inp{v}{\Sigma^{-1/2}X_i}^{2} }_{i=1}^{n}}.
\end{align*}

Define $\widetilde{X}_{i} = \Sigma^{-1/2}X_{i}$, and $Z_{i, v} \defeq \inp{v}{\widetilde{X}_i}^{2}$ for $(i, v) \in [n] \times S^{d-1}$. Then we have by Lemma <ref>,

\begin{align*}
&\inf_{\norm{v - w^{*}}_{\Sigma} = r} \psi_{k}(v, w^{*}) \\
&\geq r \cdot \inf_{v \in S^{d-1}} n^{-1} \varphi_k\brack*{\paren*{\inp{\nabla e(\inp{w^{*}}{X_i} - Y_i)}{\Sigma^{-1/2}v}}_{i=1}^{n}} + r^{2} \cdot \inf_{v \in S^{d-1}} n^{-1} \sum_{i=1}^{n - 2k} Z_{i, v}^{*} \\
&= \frac{r^{2}}{2} \cdot \inf_{v \in S^{d-1}} n^{-1} \sum_{i=1}^{n - 2k} Z_{i, v}^{*} - r\cdot \sup_{\norm{v}_{\Sigma} = 1} n^{-1} \varphi_k\brack*{\paren*{\inp{\nabla e(\inp{w^{*}}{X_i} - Y_i)}{v}}_{i=1}^{n}}
\end{align*}

The second term is bounded with probability $1-\delta/2$ by $r \cdot \Delta(\delta)$ by Lemma <ref>. For the first term, the restriction on the sample size in Theorem <ref> is chosen such that by Proposition <ref>, with probability at least $1 - \delta^{2}/2 \geq 1-\delta/2$

\begin{equation*}
\inf_{v \in S^{d-1}} n^{-1} \sum_{i=1}^{n - 2k} Z_{i, v}^{*} \geq \frac{1}{4}
\end{equation*}

Therefore, with probability at least $1-\delta$

\begin{equation*}
\inf_{\norm{v - w^{*}}_{\Sigma} = r} \psi_{k}(v, w^{*}) \geq \frac{r^{2}}{8} - r \Delta(\delta).
\end{equation*}

We now extend this to all vectors $w \in \R^{d}$ such that $\norm{w - w^{*}}_{\Sigma} \geq r$. On the same event, if $\norm{w - w^{*}}_{\Sigma} = R > r$, then $v \defeq w^{*} + \frac{r}{R} (w-w^{*})$ satisfies $\norm{v - w^{*}}_{\Sigma} = r$, and

\begin{align*}
\psi_k(w, w^{*}) &= n^{-1} \varphi_{k}\paren*{(\inp{\nabla e(\inp{w^{*}}{X_i} - Y_{i})}{w - w^{*}} + \frac{1}{2} \inp{w - w^{*}}{X_i}^{2})_{i=1}^{n}} \\
&= n^{-1} \varphi_{k}\brack*{\paren*{ \frac{R}{r} \inp{\nabla e(\inp{w^{*}}{X_i} - Y_{i})}{v - w^{*}} + \frac{R^2}{r^2}\frac{1}{2} \inp{v - w^{*}}{X_i}^{2}}_{i=1}^{n}} \\
&\geq n^{-1} \varphi_{k}\brack*{\paren*{ \frac{R}{r} \inp{\nabla e(\inp{w^{*}}{X_i} - Y_{i})}{v-w^{*}} + \frac{R}{r}\frac{1}{2} \inp{v - w^{*}}{X_i}^{2})_{i=1}^{n}}_{i=1}^{n}} \\
&= \frac{R}{r} \cdot \psi_{k}(v, w^{*}) \\
&\geq \psi_{k}(v, w^{*})
\end{align*}

where the first inequality follows from the fact that $R/r > 1$, $\inp{v - w^{*}}{X_{i}}^{2} > 0$, and Lemma <ref>, and the second inequality follows from the fact that by the condition on $r$, we have $\psi_{k}(v, w^{*}) \geq 0$ on the event we are considering.

We are now ready to state the proof of Theorem <ref>. Set $r \defeq 20 \Delta(\delta)$, and recall from (<ref>) that

\begin{align*}
\psi_{k}(\hat{w}_{n, k}, w^{*}) \leq \phi(w^{*}) &= \sup_{v \in \R^{d}} \psi_k(w^{*}, v) \\
&= \max\brace*{\sup_{\norm{v - w^{*}}_{\Sigma} \geq r} \psi_{k}(w^{*}, v), \sup_{\norm{v - w^{*}}_{\Sigma} < r} \psi_{k}(w^{*}, v)} \\
&= \max\brace*{- \inf_{\norm{v - w^{*}} \geq r} \psi_{k}(v, w^{*}),  \sup_{\norm{v - w^{*}}_{\Sigma} < r} \psi_{k}(w^{*}, v)},
\end{align*}

where the last line uses the fact that $\psi_k(w, v) = -\psi_{k}(v, w)$.
Now by combining Corollary <ref> and Lemma <ref>, we have with probability $1-\delta$ that the first term in the above maximum is negative, while the second is bounded by $r \cdot \Delta(\delta) = 20 \Delta^{2}(\delta)$. On the other hand, we have on the same event by Lemma <ref> that

\begin{equation*}
\inf_{\norm{v - w^{*}}_{\Sigma} \geq r} \psi_{k}(v, w^{*}) \geq \frac{r^{2}}{8} - r \Delta(\delta) = 30 \Delta^{2}(\delta)
\end{equation*}

Therefore, we conclude that with probability at least $1-\delta$

\begin{equation*}
\norm{\hat{w}_{n, k} - w^{*}}_{\Sigma} \leq 20 \Delta(\delta).
\end{equation*}

finally, noticing that this implies, with probability at least $1-\delta$

\begin{equation*}
\mathcal{E}(\hat{w}_{n, k}) = \frac{1}{2}\norm{\hat{w}_{n,k} - w^{*}}_{\Sigma}^{2} \leq 20^{2} \Delta^{2}(\delta),
\end{equation*}

finishes the proof.

§.§ Proof of Theorem <ref>

The high-level idea behind the proof of Theorem <ref> is similar to that of Theorem <ref>, but with a few more challenges. Fix $P \in \mathcal{P}_{p}(P_{X}, \sigma^{2}, \mu)$. We prove an upper bound on the risk of $\hat{w}_{n, k}$ under this fixed $P$. Define $H \defeq \nabla^{2} E(w^{*})$, $c \defeq \essinf(\Exp\brack*{\abs{\xi}^{p-2}\mid X})$, $C \defeq \esssup(\Exp\brack*{\abs{\xi}^{2(p-1)} \mid X})$. Note that

\begin{equation}
\label{eq:tired_1}
H = \Exp\brack*{\abs{\xi}^{p-2} XX^{T}} \succeq c \cdot \Sigma
\end{equation}

\begin{equation*}
\Delta_{p}(\delta) \defeq 50 \sqrt{\frac{m(2p-2)}{m(p-2)} \cdot \frac{\sigma^{p}[d + \log(4/\delta)]}{n}}
\end{equation*}

Our first statement is an analogue to Lemma <ref>.

\begin{equation*}
\Prob\paren*{\sup_{\norm{v}_{H} \leq 1} n^{-1}\varphi_{k}\brack*{(\inp{\nabla e(\inp{w^{*}}{X_i} - Y_{i})}{v})_{i=1}^{n}} > \Delta_{p}(\delta)} \leq \delta/2
\end{equation*}

For $v \in \R^{d}$ such that $\norm{v}_{H} \leq 1$ and $i \in [n]$, define

\begin{equation*}
Z_{i, v} \defeq \frac{1}{n} \inp{\nabla e(\inp{w^{*}}{X_i} - Y_{i})}{v}
\end{equation*}

Our aim is to apply Lemma <ref>, so we make the necessary computations here. We have

\begin{align*}
\Exp\brack*{Z_{i, v}} &= \frac{1}{n} \inp{\Exp\brack*{\nabla e(\inp{w^{*}}{X_i} - Y_{i})}}{v} = \frac{1}{n}\inp{\nabla E(w^{*})}{v} = 0
\end{align*}

\begin{align*}
\sup_{\norm{v}_{H} \leq 1} \sum_{i=1}^{n} \Exp\brack*{Z_{i, v}^{2}} &= \frac{1}{n} \sup_{\norm{v}_{H} \leq 1} \Exp\brack*{\xi^{2(p-1)}\inp{X}{v}^{2}} \\
&\leq \frac{1}{n} \sup_{\norm{v}_{\Sigma} = 1} \frac{\esssup\paren*{\Exp\brack*{\xi^{2(p-1)} \mid X}}}{\essinf(\Exp\brack*{\xi^{p-2} \mid X}))} \Exp\brack*{\inp{X}{v}^{2}} \\
&\leq \frac{m(2p-2)}{m(p-2)} \frac{\sigma^{p}}{n}
\end{align*}

where the first inequality follows from (<ref>), and the second from the assumption on the class of distributions. Now, for independent Rademacher variables $(\eps_i)_{i=1}^{n}$, we have

\begin{align*}
\Exp\brack*{\sup_{\norm{v}_{H}=1} \sum_{i=1}^{n} \eps_i Z_{i, v}}
&= \Exp\brack*{\sup_{\norm{v}_{H} = 1} \inp*{\frac{1}{n}\sum_{i=1}^{n} \eps_{i} \nabla e(\inp{w^{*}}{X_i} - Y_{i})}{v}} \\
&= \Exp\brack*{\norm*{\frac{1}{n} \sum_{i=1}^{n} \eps_i \nabla e(\inp{w^{*}}{X_i} - Y_{i})}_{H^{-1}}} \\
&\leq \Exp\brack*{\norm*{\frac{1}{n} \sum_{i=1}^{n} \eps_i \nabla e(\inp{w^{*}}{X_i} - Y_{i})}_{H^{-1}}^{2}}^{1/2} \\
&= \sqrt{\frac{\Exp\brack{\xi^{2(p-1)} \norm{X}_{H^{-1}}^{2}}}{n}} \\
&\leq \sqrt{\frac{\esssup\paren*{\Exp\brack*{\xi^{2(p-1)} \mid X}}}{\essinf(\Exp\brack*{\xi^{p-2} \mid X}))} \cdot \frac{\Exp\brack*{\norm{X}_{\Sigma^{-1}}^{2}}}{n}} \\
&\leq \sqrt{\frac{m(2p-2)}{m(p-2)} \cdot \frac{\sigma^{p} d}{n}}
\end{align*}

Where again we have used the assumption on the class of distributions, and where we used (<ref>) in the penultimate line. Recalling that $k = 8\log(2/(\delta/2))$ from the statement of the theorem, and applying Lemma <ref> with the above constants yields the result.

The second statement is also similar to Corollary <ref>. The additional challenge here is that second order Taylor expansion is not exact.

\begin{equation*}
\Prob\paren*{\sup_{\norm{v - w^{*}}_{H} < r} \psi_{k}(w^{*}, v) > r \cdot \Delta_{p}(\delta)} \leq \delta/2.
\end{equation*}

By Lemma 2.5 in [Adil et al., 2023], we have that, for all $t, s \in \R$,

\begin{equation*}
e(t) - e(s) - e'(s)(t-s) \geq \frac{1}{8(p-1)} e''(s) (t-s)^{2}
\end{equation*}

\begin{align*}
\sup_{\norm{v - w^{*}}_{H} < r} \psi_{k}(w^{*}, v) &= \sup_{\norm{v - w^{*}}_{H} < r} \varphi_{k}\brack*{\paren*{e(\inp{w^{*}}{X_{i}} - Y_{i}) - e(\inp{v}{X_{i}} - Y_{i})}_{i=1}^{n}} \\
&\leq \sup_{\norm{v - w^{*}}_{H} < r} \varphi_{k}\brack*{\paren*{-\inp{\nabla e(\inp{w^{*}}{X_i} - Y_i)}{v - w^{*}} - \frac{\abs{\xi_i}^{p-2}}{8(p-1)}\inp{X_i}{v - w^{*}}^{2}}_{i=1}^{n}} \\
&\leq \sup_{\norm{v - w^{*}}_{H} < r} \varphi_{k}\brack*{\paren*{-\inp{\nabla e(\inp{w^{*}}{X_i} - Y_i)}{v - w^{*}}}_{i=1}^{n}} \\
&= \sup_{\norm{v - w^{*}}_{H} < r} r \cdot \varphi_{k}\brack*{\paren*{\inp*{\nabla e(\inp*{w^{*}}{X_i} - Y_i)}{\frac{v - w^{*}}{r}}}_{i=1}^{n}} \\
&= r \cdot \sup_{\norm{v}_{H} < 1} \varphi_{k}\brack*{\paren*{\inp{\nabla e(\inp*{w^{*}}{X_i} - Y_i)}{v}}_{i=1}^{n}}
\end{align*}

where the second line is by the inequality cited above, and the third by dropping negative terms. Applying Lemma <ref> to the last line finishes the proof.

It remains to show the analogue of Lemma <ref>. This is the most technical part of the proof.

Let $r \in [32(p-1)\Delta_{p}(\delta), \infty)$. Then

\begin{equation*}
\Prob\paren*{\inf_{\norm{v - w^{*}}_{H} \geq r} \psi_{k}(v, w^{*}) < \frac{r^{2}}{32(p-1)} - r\Delta_{p}(\delta)} \leq \delta
\end{equation*}

We start with the case $\norm{v - w^{*}}_{H} = r$. We have, using the quoted lemma in the proof of Corollary <ref>,

\begin{align*}
&\inf_{\norm{v - w^{*}}_{H} = r} \psi_{k}(v, w^{*}) \\
&= \inf_{\norm{v - w^{*}}_{H} = r} n^{-1} \varphi_{k}\brack*{\paren*{e(\inp{v}{X_{i}} - Y_{i}) - e(\inp{w^{*}}{X_{i}} - Y_{i})}_{i=1}^{n}} \\
&\geq \inf_{\norm{v - w^{*}}_{H} = r} n^{-1} \varphi_{k}\brack*{\paren*{\inp{\nabla e(\inp{w^{*}}{X_i} - Y_i)}{v - w^{*}} + \frac{\abs{\xi_i}^{p-2}}{8(p-1)} \inp{v - w^{*}}{X_i}^{2} }_{i=1}^{n}} \\
&= \inf_{v \in S^{d-1}} n^{-1} \varphi_{k}\brack*{\paren*{r \cdot \inp{\nabla e(\inp{w^{*}}{X_i} - Y_i)}{H^{-1/2}v} + r^{2} \cdot \frac{\abs{\xi_i}^{p-2}}{8(p-1)} \inp{v}{H^{-1/2}X_i}^{2} }_{i=1}^{n}}.
\end{align*}

Now define the random vector $W \defeq \abs{\xi}^{(p-2)/2} \cdot X$, whose (uncentered) covariance matrix is $H$. Further define $\widetilde{W}_{i} \defeq H^{-1/2} W_i$, and $Z_{i, v} \defeq \inp{v}{\widetilde{W}_i}^{2}$ for $(i, v) \in [n] \times S^{d-1}$. Then we have by Lemma <ref>,

\begin{align*}
&\inf_{\norm{v - w^{*}}_{H} = r} \psi_{k}(v, w^{*}) \\
&\geq r \cdot \inf_{v \in S^{d-1}} n^{-1} \varphi_k\brack*{\paren*{\inp{\nabla e(\inp{w^{*}}{X_i} - Y_i)}{H^{-1/2}v}}_{i=1}^{n}} + \frac{r^{2}}{8(p-1)} \cdot \inf_{v \in S^{d-1}} n^{-1} \sum_{i=1}^{n - 2k} Z_{i, v}^{*} \\
&= \frac{r^{2}}{8(p-1)} \cdot \inf_{v \in S^{d-1}} n^{-1} \sum_{i=1}^{n - 2k} Z_{i, v}^{*} - r\cdot \sup_{\norm{v}_{H} = 1} n^{-1} \varphi_k\brack*{\paren*{\inp{\nabla e(\inp{w^{*}}{X_i} - Y_i)}{v}}_{i=1}^{n}}
\end{align*}

The second term is bounded with probability $1-\delta/2$ by $r \cdot \Delta_{p}(\delta)$ by Lemma <ref>. For the first term, we claim
that the restriction on the sample size in Theorem <ref> is chosen such that by Proposition <ref>, with probability at least $1 - \delta^{2}/2 \geq 1-\delta/2$

\begin{equation}
\label{eq:exh}
\inf_{v \in S^{d-1}} n^{-1} \sum_{i=1}^{n - 2k} Z_{i, v}^{*} \geq \frac{1}{4}
\end{equation}

Let us show why this is true. Let $P_{W}$ be the distribution of $W$, and notice that

\begin{align*}
\lambdamax(S(P_{W})) + 1 &= \sup_{v \in S^{d-1}} \Exp\brack*{\norm{W}^{2}_{H^{-1}} \inp{v}{H^{-1/2} W}^{2}} \\
&= \sup_{v \in S^{d-1}} \Exp\brack*{\abs{\xi}^{2(p-2)} \cdot \norm{X}^{2}_{H^{-1}} \inp{H^{-1/2} v}{X}^{2}} \\
&\leq \esssup(\Exp\brack{\abs{\xi}^{2(p-2)} \mid X}) \cdot \sup_{\norm{v}_{H} = 1} \Exp\brack*{\norm{X}^{2}_{H^{-1}} \inp{v}{X}^{2}} \\
&\leq \frac{C^{(p-2)/(p-1)}}{c^{2}} \cdot \sup_{\norm{v}_{\Sigma} = 1} \Exp\brack*{\norm{X}_{\Sigma^{-1}} \inp{v}{X}^{2}} \\
&\leq \paren*{\frac{m(2p-2) \sigma^{p}}{m(p-2)}}^{\frac{p-2}{p-1}} \frac{1}{\mu^{p/(p-1)}} \cdot [\lambdamax(S(P_{X})) + 1]
\end{align*}

where the fourth line follows by Jensen's inequality, and the last line by the  properties of the class of distributions. Note that this upper bound holds uniformly over all members of $\mathcal{P}_{p}(P_{X}, \sigma^{2}, \mu)$. Through a  very similar argument, one may show

\begin{equation*}
R(P_{W}) + 1 \leq \paren*{\frac{m(2p-2) \sigma^{p}}{m(p-2)}}^{\frac{p-2}{p-1}} \frac{1}{\mu^{p/(p-1)}} \cdot [R(P_{X}) + 1]
\end{equation*}

It is then straightforward to apply Proposition <ref> under the above bounds and the sample size restriction and conclude that the claim (<ref>) is true.

Therefore, with probability at least $1-\delta$

\begin{equation*}
\inf_{\norm{v - w^{*}}_{H} = r} \psi_{k}(v, w^{*}) \geq \frac{r^{2}}{32(p-1)} - r \Delta_{p}(\delta).
\end{equation*}

We now extend this to all vectors $w \in \R^{d}$ such that $\norm{w - w^{*}}_{H} \geq r$. On the same event, if $\norm{w - w^{*}}_{H} = R > r$, then $v \defeq w^{*} + \frac{r}{R} (w-w^{*})$ satisfies $\norm{v - w^{*}}_{H} = r$, and

\begin{align*}
\psi_k(w, w^{*}) &\geq n^{-1} \varphi_{k}\brack*{\paren*{\inp{\nabla e(\inp{w^{*}}{X_i} - Y_{i})}{w - w^{*}} + \frac{\abs{\xi_i}^{p-2}}{8(p-1)} \inp{w - w^{*}}{X_i}^{2}}_{i=1}^{n}} \\
&= n^{-1} \varphi_{k}\brack*{\paren*{ \frac{R}{r} \inp{\nabla e(\inp{w^{*}}{X_i} - Y_{i})}{v - w^{*}} + \frac{R^2}{r^2}\frac{\abs{\xi_i}^{p-2}}{8(p-1)} \inp{v - w^{*}}{X_i}^{2}}_{i=1}^{n}} \\
&\geq n^{-1} \varphi_{k}\brack*{\paren*{ \frac{R}{r} \inp{\nabla e(\inp{w^{*}}{X_i} - Y_{i})}{v-w^{*}} + \frac{R}{r}\frac{\abs{\xi_i}^{p-2}}{8(p-1)} \inp{v - w^{*}}{X_i}^{2}}_{i=1}^{n}} \\
&= \frac{R}{r} \cdot \paren*{\frac{r^{2}}{32(p-1)} - r\Delta_{p}(\delta)} \\
&\geq \frac{r^{2}}{32(p-1)} - r\Delta_{p}(\delta)
\end{align*}

where the first inequality follows from the fact that $R/r > 1$, $\inp{v - w^{*}}{X_{i}}^{2} > 0$, and Lemma <ref>, and the second inequality follows from the fact that by the condition on $r$, we have $\frac{r^{2}}{32(p-1)} - r\Delta_{p}(\delta) \geq 0$ on the event we are considering.

Finally, we present the main proof. For the first step, we localize $\hat{w}_{n,k}$ using the lemmas we just proved. In particular, let $r \defeq 96(p-1)\Delta_{p}(\delta)$. Then following the same argument as in the proof of Theorem <ref>, we obtain that with probability at least $1-\delta$

\begin{equation*}
\psi_k(\hat{w}_{n, k}, w^{*}) \leq r \cdot \Delta_{p}(\delta) = 96(p-1)\Delta^{2}_{p}(\delta)
\end{equation*}

On the other hand, and on the same event,

\begin{equation*}
\inf_{\norm{v - w^{*}}_{H} \geq r} \psi_{k}(v, w^{*}) \geq \frac{r^{2}}{32(p-1)} - r \Delta_p(\delta) = 192 (p-1)^{2} \Delta^{2}_{p}(\delta).
\end{equation*}

\begin{equation*}
\norm{\hat{w}_{n, k} - w^{*}}_{H} \leq 96(p-1)\Delta_{p}(\delta)
\end{equation*}

It remains to bound the excess expected error. By Lemma 2.5 in [Adil et al., 2023], we have the upper bound

\begin{equation*}
e(t) - e(s) - e'(s)(t-s) \leq 4 e''(s)(t-s)^{2} + 2 p^{p-2} \abs*{t-s}^{p}
\end{equation*}

Integrating this bound we obtain

\begin{equation*}
\mathcal{E}(\hat{w}_{n,k}) \leq 4 \norm{\hat{w}_{n,k} - w^{*}}_{H}^{2} + 2p^{p-2} \Exp\brack*{\abs{\inp{\hat{w}_{n,k} - w^{*}}{X}}^{p}}.
\end{equation*}

We have control over the first term. We need to control the second, in a noise-independent way. We have, for any $w \in \R^{d}$, by (<ref>)

\begin{equation*}
\norm{w}_{H} \geq \sqrt{c} \cdot \norm{w}_{\Sigma} \geq \sqrt{\mu} \cdot  \Exp\brack*{\inp{w}{X}^{2}}^{1/2}
\end{equation*}

\begin{equation*}
\sup_{w \in \R^{d} \setminus \brace*{0}} \frac{\Exp\brack*{\abs*{\inp{w}{X}}^{p}}^{1/p}}{\norm{w}_{H}} \leq \frac{1}{\sqrt{\mu}} \sup_{w \in \R^{d} \setminus \brace*{0}} \frac{\Exp\brack*{\abs*{\inp{w}{X}}^{p}}^{1/p}}{\Exp\brack*{\inp{w}{X}^{2}}^{1/2}} = \frac{N(P_{X}, p)}{\sqrt{\mu}}.
\end{equation*}

Using this we obtain

\begin{equation*}
\mathcal{E}(\hat{w}_{n,k}) \leq 4\norm{\hat{w}_{n,k} - w^{*}}_{H}^{2} + 2p^{p-2} \frac{N^{p}(P_{X}, p)}{\mu^{p/2}} \cdot \norm{\hat{w}_{n,k} - w^{*}}_{H}^{p}
\end{equation*}

Under the restriction on the sample size stated in the theorem, in particular the second term, we have on the same event

\begin{equation*}
2p^{p-2} \frac{N^{p}(P_{X}, p)}{\mu^{p/2}} \cdot \norm{\hat{w}_{n,k} - w^{*}}_{H}^{p} \leq 4 \norm{\hat{w}_{n,k} - w^{*}}_{H}^{2}.
\end{equation*}

Hence with probability at least $1-\delta$

\begin{equation*}
\mathcal{E}(\hat{w}_{n,k}) \leq 8 \cdot \brack*{96 (p-1)\Delta_{p}(\delta)}^{2}
\end{equation*}

Replacing $\Delta_{p}(\delta)$ with its value we recover the desired bound.

We start with the following Lemma.

Let $\delta \in (0, 1)$ be such that $k \defeq 8\log(2/\delta)$ is an integer satisfying $1 \leq k \leq \floor{n/2}$. Then

\begin{equation*}
\Prob\paren*{\sup_{v \in S^{d-1}} \frac{\varphi_{k}\paren*{(\eta_i \inp{v}{\tilde{X}_i})_{i=1}^{n}}}{n} > \Delta((X_i)_{i=1}^{n}, \delta) \st (X_i)_{i=1}^{n}} < \delta,
\end{equation*}

\begin{equation*}
\Delta((X_i)_{i=1}^{n}, \delta) \defeq 50 \max\brace*{\sqrt{\frac{\sigma^{2}\Tr(\tilde{\Sigma})}{n}}, \sqrt{\frac{\sigma^{2}\lambdamax(\tilde{\Sigma})\log(2/\delta)}{n}}}.
\end{equation*}

We have

\begin{align*}
&\Exp\brack*{\eta_i \inp{v}{\tilde{X}_i} \st (X_i)_{i=1}^{n}} = 0, \\
&\sup_{v \in S^{d-1}} \sum_{i=1}^{n} \Exp\brack*{\eta_i^{2}\inp{v}{\tilde{X}_{i}}^{2} \st (X_i)_{i=1}^{n}} \leq n \sigma^{2} \sup_{v \in S^{d-1}}\frac{1}{n}\sum_{i=1}^{n}\inp{v}{\tilde{X}_{i}^{2}} = n\sigma^{2} \lambdamax(\tilde{\Sigma}), \\
& \Exp\brack*{\sup_{v \in S^{d-1}} \inp*{v}{\frac{1}{n} \sum_{i=1}^{n}\eps_i \eta_i \tilde{X}_{i}} \st (X_i)_{i=1}^{n}} = \Exp\brack*{\norm*{\frac{1}{n} \sum_{i=1}^{n} \eps_i \eta_i \tilde{X}_{i}}_{2} \st (X_i)_{i=1}^{n}} \leq \sqrt{n \sigma^{2} \Tr(\tilde{\Sigma})}
\end{align*}

Therefore, applying Lemma <ref> and dividing both sides by $n$ yields the result.

Let $\delta \in (0, 1)$ be such that $k \defeq 8\log(2/\delta)$ is an integer satisfying $1 \leq k \leq \floor{n/8}$. For $(i, v) \in [n] \times S^{d-1}$, define $Z_{i, v} \defeq \inp{v}{\tilde{X}_{i}}^{2}$. Let $(X_i)_{i=1}^{n}$ be such that

\begin{equation*}
\inf_{v \in S^{d-1}} \frac{1}{n} \sum_{i=2k+1}^{n-2k} Z_{i,v}^{*} \geq \frac{1}{4}
\end{equation*}

Let $r > 0$ satisfy

\begin{equation*}
r \geq 4 \Delta((X_i)_{i=1}^{n}, \delta)
\end{equation*}

\begin{equation*}
\Prob\paren*{\inf_{\norm{w - w^{*}}_{\Sigma} \geq r} \psi_{k}(w, w^{*}) < -r \cdot \Delta((X_i)_{i=1}^{n}, \delta) + \frac{r^{2}}{4}  \st (X_i)_{i=1}^{n}} < \delta
\end{equation*}

\begin{align}
\inf_{\norm{w - w^{*}}_{\Sigma} = r} \psi_{k}(v, w^{*}) &= \inf_{\norm{w - w^{*}}_{\Sigma} = r} n^{-1} \varphi_{k}\paren*{(-\eta_i \inp{w - w^{*}}{X_i} + \frac{1}{2} \inp{w - w^{*}}{X_i}^2)_{i=1}^{n}} \nonumber \\
&= \inf_{\norm{v}_{\Sigma} = r} n^{-1} \varphi_{k}\paren*{(-\eta_i\inp{v}{X_i} + \frac{1}{2}\inp{v}{X_i}^{2})_{i=1}^{n}} \nonumber \\
&= \inf_{v \in S^{d-1}} n^{-1}\varphi_{k}\paren*{(-r\eta_i\inp{v}{\tilde{X}_i} + \frac{r^{2}}{2}\inp{v}{\tilde{X}_i}^{2})_{i=1}^{n}} \nonumber \\
&\geq - r \cdot \sup_{v \in S^{d-1}} \frac{\varphi_{k}\paren*{(\eta_i \inp{v}{\tilde{X}_{i}})_{i=1}^{n}}}{n} + \frac{r^{2}}{4}
\label{eq:pf_lem8_1}
\end{align}

so that applying Lemma <ref> shows the statement holds for $\norm{w - w^{*}}_{\Sigma} = r$. Now on the same event, if $\norm{w - w^{*}}_{\Sigma} = R > r$, then $v \defeq w^{*} + \frac{r}{R} (w-w^{*})$ satisfies $\norm{v - w^{*}} = r$, and

\begin{align*}
\psi_k(w, w^{*}) &= n^{-1} \varphi_{k}\paren*{(-\eta_i \inp{w - w^{*}}{X_i} + \frac{1}{2} \inp{w - w^{*}}{X_i}^{2})_{i=1}^{n}} \\
&= n^{-1} \varphi_{k}\paren*{(- \frac{R}{r}\eta_i \inp{v - w^{*}}{X_i} + \frac{R^2}{r^2}\frac{1}{2} \inp{v - w^{*}}{X_i}^{2})_{i=1}^{n}} \\
&\geq n^{-1} \varphi_{k}\paren*{- \frac{R}{r}\eta_i \inp{v - w^{*}}{X_i} + \frac{R}{r}\frac{1}{2} \inp{v - w^{*}}{X_i}^{2})_{i=1}^{n}} \\
&= \frac{R}{r} \cdot \psi_{k}(v, w^{*}) \\
&\geq \psi_{k}(v, w^{*})
\end{align*}

where the first inequality follows from the fact that $R/r > 1$ and $\inp{v - w^{*}}{X_{i}}^{2} > 0$, and the second inequality follows from the fact that by the condition on $r$, we have $\psi_{k}(v, w^{*}) > 0$.

Under the conditions of Lemma <ref>, with probability at least $1-\delta$

\begin{equation*}
\norm{\hat{w}_{k} - w^{*}}_{\Sigma} \leq 8 \Delta((X_i)_{i=1}^{n}, \delta)
\end{equation*}

Set $r = 8 \Delta((X_i)_{i=1}^{n}, \delta)$ and define $\gamma(w) \defeq \sup_{v \in \R^{d}} \psi_{k}(w, v)$. Notice that by definition of $\hat{w}_{k}$, we have

\begin{equation}
\psi_{k}(\hat{w}_{k}, w^{*}) \leq \gamma(\hat{w}_k) \leq \gamma(w^{*})
\end{equation}

Now on the one hand we have

\begin{equation*}
\gamma(w^{*}) = \sup_{v \in \R^{d}} \psi_{k}(w^{*}, v) = - \inf_{v \in R^{d}}\psi_{k}(v, w^{*}) \leq - \min \brace*{\inf_{\norm{v - w}_{\Sigma} \geq r} \psi_{k}(v, w^{*}), \inf_{\norm{v - w}_{\Sigma} < r} \psi_{k}(v, w^{*})}
\end{equation*}

By Lemmas (REFERENCE) and (REFERENCE), we obtain on event (REFERENCE)

\begin{equation}
\gamma(w^{*}) < r \Delta((X_i)_{i=1}^{n}, \delta)
\end{equation}

and by Lemma (REFERENCE) we obtain

\begin{equation}
\inf_{\norm{w - w^{*}}_{\Sigma} \geq r} \psi_{k}(v, w^{*}) \geq r \Delta((X_i)_{i=1}^{n}, \delta)
\end{equation}

which implies that $\norm{w - w^{*}}_{\Sigma} \leq r$

Define the events

\begin{align*}
A &\defeq \brace*{(x_i)_{i=1}^{n} \st \Tr\paren*{\widetilde{\Sigma}^{-1}} \leq Q_{\Tr\paren*{\widetilde{\Sigma}^{-1}}}(1 - \eps_{n} - \delta/6)} \\
B(a) &\defeq \brace*{(x_i)_{i=1}^{n} \st Q_{W \mid (X_i)_{i=1}^{n}}(1 - \delta) \leq a Q_{W}(1 - \eps_{n} - \delta/6)} \\
C &\defeq \brace*{(x_i)_{i=1}^{n} \st \inf_{v \in S^{d-1}} \frac{1}{n}\sum_{i=2k+1}^{n-2k} Z_{i,v}^{*} \geq \frac{1}{4}} \\
D &\defeq \brace*{(x_i)_{i=1}^{n} \st \rank(\widetilde{\Sigma}) = d}
\end{align*}

where $a > 0$ is a free-parameter we set later. Note that $A, B(a), C \subset D$ for all $a > 0$. Now by definition of the event $A$, we have

\begin{equation*}
\Prob\paren*{A \st D} \Prob\paren*{D} = \Prob\paren*{A \cap D} = \Prob\paren*{A} \geq 1 - \eps_{n} - \delta/3 \Rightarrow \Prob\paren*{A \st D} \geq 1 - \frac{\delta/3}{1 - \eps_{n}}
\end{equation*}

Furthermore by the condition on $n$, we have

\begin{equation*}
\Prob\paren*{C \st D} \Prob\paren*{D} = \Prob\paren*{C} \geq 1 - \delta^2/3 \geq 1 - \delta/3 \Rightarrow \Prob\paren*{C \st D} \geq \frac{1 - \delta/3}{1 - \eps_{n}} \geq 1 - \frac{\delta/3}{1 - \eps_{n}}
\end{equation*}

Define $a_{*} \defeq \frac{\log(1/\delta)}{\log(2)}$ and $B_{*} \defeq B(a_{*})$. We claim that $\Prob\paren*{B_{*}} \geq 1 - \eps_{n} - \delta/3$. Indeed, we have on the one hand

\begin{equation*}
\Prob\paren*{\brace*{W \leq Q_{W}(1 - \eps_{n} - \delta/3}} \geq 1 - \eps_{n} - \delta/6,
\end{equation*}

On the other, we have

\begin{align*}
&\Prob\paren*{W \leq Q_{W}(1 - \eps_{n} - \delta/3)} \\
&= \Exp\brack*{\Prob\paren*{W \leq Q_{W}(1 - \eps_{n} - \delta/3) \st (X_i)_{i=1}^{n}}} \\
&= \Exp\brack*{\Prob\paren*{W \leq Q_{W}(1 - \eps_{n} - \delta/3) \st (X_i)_{i=1}^{n}} \mathbbm{1}_{B_{*}}((X_i)_{i=1}^{n})} + \Exp\brack*{\Prob\paren*{W \leq Q_{W}(1 - \eps_{n} - \delta/3) \st (X_i)_{i=1}^{n}} \mathbbm{1}_{B_{*}^{c}}((X_i)_{i=1}^{n})} \\
&\leq \Prob\paren*{B_{*} \cap D} + \Exp\brack*{\Prob\paren*{W < a_{*}^{-1} \cdot Q_{W \mid (X_i)_{i=1}^{n}}(1 - \delta) \st (X_i)_{i=1}^{n}} \mathbbm{1}_{B_{*}^{c} \cap D}((X_i)_{i=1}^{n})} \\
&= \Prob\paren*{B_{*} \cap D} + \Exp\brack*{\Prob\paren*{W < Q_{W \mid (X_i)_{i=1}^{n}}(1 -\delta^{1/a_{*}}) \st (X_i)_{i=1}^{n}} \mathbbm{1}_{B_{*}^{c} \cap D}((X_i)_{i=1}^{n})} \\
&\leq \Prob\paren*{B_{*} \cap D} + (1 -\delta^{1/a_{*}}) \Prob\paren*{B_{*}^{c} \cap D}  \\
&= (1 - \delta^{1/a_{*}})(1 - \eps_{n}) + \delta^{1/a_{*}} \Prob\paren*{B_{*}} \\
&= \frac{1}{2}(1 - \eps_{n}) + \frac{1}{2}\Prob\paren*{B_{*}}
\end{align*}

Combining the upper and lower bounds yields the desired lower bound on $\Prob\paren*{B_{*}}$ and by the same argument as for the events $A$ and $B$, we obtain $\Prob\paren*{B_{*} \st D} \geq 1 - \frac{\delta/3}{1 - \eps_{n}}$.
Now by the union bound

\begin{equation*}
\Prob\paren*{A \cap B \cap C} = \Prob\paren*{A \cap B \cap C \st D} \Prob\paren*{D} \geq \paren*{1 - \frac{\delta}{1-\eps_{n}}} \paren*{1 - \eps_{n}} = 1 - \eps_{n} - \delta
\end{equation*}

From which the claim follows (ADD JUSTIFICATION).

§ PROOFS OF SECTION <REF>

§.§ Proof of Proposition <ref>

Asymptotic lower bound. By the central limit theorem, as $n \to \infty$, and by the finiteness of the fourth moments of $P_{X}$,

\begin{equation*}
\sqrt{n} (\widetilde{\Sigma}_{n} - I) \overset{d}{\to} G,
\end{equation*}

where $G$ is a centred symmetric Gaussian matrix with covariance

\begin{equation*}
\Exp\brack*{g_{ij}g_{st}} = \Exp\brack*{(\widetilde{X}_i\widetilde{X}_j - I_{i,j})(\widetilde{X}_s\widetilde{X}_t - I_{s, t})},
\end{equation*}

for $i,j,s,t \in [d]$. Now since $G$ is Gaussian and centred, we have $G \overset{d}{=} -G$. On the one hand, by the continuous mapping theorem, this implies

\begin{equation*}
\sqrt{n}(1 - \lambdamin(\widetilde{\Sigma}_{n}))= \sqrt{n}\lambdamax(I - \widetilde{\Sigma}_{n}) \overset{d}{\to} \lambdamax(G).
\end{equation*}

On the other, $\lambdamax(G) \overset{d}{=} \lambdamax(-G) = -\lambdamin(G)$, and therefore for $t \geq 0$,

\begin{multline*}
\Prob\paren*{\norm{G}_{\text op} > t} = \Prob\paren*{\lambdamax(G) > t \text{ or } \lambdamin(G) < -t} \\ \leq \Prob\paren*{\lambdamax(G) > t} + \Prob\paren*{\lambdamin(G) < -t} = 2 \Prob\paren*{\lambdamax(G) > t}.
\end{multline*}

so we conclude that

\begin{equation*}
\lim_{n \to \infty} \Prob\paren*{1 - \lambdamin(\widetilde{\Sigma}_{n}) \leq \frac{t}{\sqrt{n}}} = \Prob\paren*{\lambdamax(G) \leq t} \leq \frac{1}{2} \paren*{1 + \Prob\paren*{\norm{G}_{\text op} \leq t}}.
\end{equation*}

Now since convergence in distribution implies the pointwise convergence of quantiles, we obtain

\begin{equation*}
\lim_{n \to \infty} \sqrt{n} \cdot Q_{1 - \lambdamin(\widetilde{\Sigma}_{n})}(1-\delta) = Q_{\lambdamax(G)}(1-\delta) \geq Q_{\norm{G}_{\text{op}}}(1-2\delta)
\end{equation*}

It remains to lower bound this last quantile. We do this by deriving two upper bounds on the CDF of $\norm{G}_{\text{op}}$.
Let $v_{*} \defeq \argmax_{v \in S^{d-1}} \Exp\brack*{\paren*{\inp{v}{\widetilde{X}}^2 - 1}^2}$ and note that $v^{T}_{*} G v_{*} \sim \mathcal{N}(0, R(P_{X}))$. Therefore by Lemma <ref>,

\begin{equation*}
\Prob\paren*{\norm{G}_{\text op} \leq t} \leq \Prob\paren*{\abs*{v_{*}^{T} G v_{*}^{T}} \leq t} \leq \sqrt{1 - \exp\paren*{-\frac{2t^2}{\pi R(P_{X})}}}
\end{equation*}

On the other hand, it can be shown that $\norm{G}_{\text{op}}$ is a Lipschitz function of a standard normal vector (see e.g. Van Handel, 2017), with Lipschitz constant $\sqrt{R(P_{X})}$. Therefore by Gaussian concentration (Lemma <ref>)

\begin{equation*}
\Prob\paren*{\norm{G}_{op} \leq t} = \Prob\paren*{\Exp\brack*{\norm{G}_{op}} - \norm{G}_{op} >  \Exp\brack*{\norm{G}_{op}} - t } \leq \exp\paren*{-\frac{(\Exp\brack*{\norm{G}_{op}} - t)^2}{2R(P_{X})}}.
\end{equation*}

Now note that since $v^{T} G v$ is a Gaussian random variable for any $v \in \R^{d}$,

\begin{equation*}
\Exp\brack*{\norm{G}_{\text{op}}} \geq \sup_{v \in \S^{d-1}} \Exp\brack*{\abs*{v^{T}Gv}} = \sqrt{\frac{2}{\pi}} \Exp\brack*{(v^{T}Gv)^{2}}^{1/2} = \sqrt{\frac{2}{\pi}} \sqrt{R(P_{X})}
\end{equation*}

where the first equality is an explicit calculation of the first absolute moment of a Gaussian random variable. Bounding the right-most term in the previous display, we obtain

\begin{equation*}
\Prob\paren*{\norm{G}_{\text{op}} \leq t} \leq \exp\paren*{-\frac{(\Exp\brack*{\norm{G}_{op}} - t)^2}{\pi \Exp\brack*{\norm{G}_{\text{op}}}^{2}}}
\end{equation*}

Using the two bounds on the CDF of $\norm{G}_{\text{op}}$ and the second item of Lemma <ref>, we obtain the following lower bound

\begin{equation*}
Q_{\norm{G}_{op}}(1-2\delta) \geq \frac{1}{2} \Exp\brack*{\norm{G}_{\text{op}}} \paren*{1 - \sqrt{\pi \log\paren*{\frac{1}{1-2\delta}}}} + \frac{1}{2} \sqrt{\frac{\pi}{2}} \sqrt{R(P_{X})\log\paren*{\frac{1}{4\delta}}}
\end{equation*}

using the restriction on $\delta \in (0, 0.1)$, we obtain

\begin{equation*}
Q_{\norm{G}_{op}}(1-2\delta) \geq \frac{1}{20} \Exp\brack*{\norm{G}_{\text{op}}} + \frac{1}{2}\sqrt{R(P_{X}) \log(1/4\delta)}
\end{equation*}

Finally by the Gaussian Poincare inequality (Lemma <ref>)

\begin{equation*}
\Exp\brack*{\norm{G}^{2}_{\text{op}}} - (\Exp\brack*{\norm{G}_{\text{op}}})^{2} \leq R(P_{X}) \leq \frac{\pi}{2} (\Exp\brack*{\norm{G}_{\text{op}}})^{2}
\end{equation*}

rearranging yields

\begin{equation*}
\Exp\brack*{\norm{G}_{\text{op}}} \geq \frac{1}{\sqrt{1 + \pi/2}} \Exp\brack*{\norm{G}_{\text{op}}^{2}}^{1/2} \geq \frac{\norm*{\Exp\brack*{G^2}}^{1/2}_{\text{op}}}{\sqrt{1+\pi/2}} = \sqrt{\frac{\lambdamax(S)}{1+\pi/2}}
\end{equation*}

and therefore

\begin{equation*}
Q_{\norm{G}_{\text{op}}}(1-2\delta) \geq \frac{\sqrt{\lambdamax(S)}}{40} + \frac{1}{2} \sqrt{R(P_{X}) \log(1/4\delta)}
\end{equation*}

This concludes the proof of the lower bound.

Upper bound.
We have the variational representation

\begin{equation}
\label{eq:one}
1 - \lambdamin(\widetilde{\Sigma}_{n}) = \lambdamax(I - \widetilde{\Sigma}_{n}) = \sup_{v \in S^{d-1}} \sum_{i=1}^{n} \underbrace{\frac{1}{n} (\Exp\brack*{\inp{v}{\widetilde{X}}^{2}} - \inp{v}{\widetilde{X}_{i}}^{2})}_{\textstyle Z_{i,v} \defeq}.
\end{equation}

Now the processes $(\brace{Z_{i, v}}_{v \in S^{d-1}})_{i=1}^{d}$ are , $\Exp\brack*{Z_{i, v}} = 0$, and $Z_{i, v} \leq n^{-1}$ for all $(i, v) \in [n] \times S^{d-1}$, so that by Bousquet's inequality [Bousquet, 2002], with probability at least $1-\delta$

\begin{equation}
\label{eq:two}
\sup_{v \in S^{d-1}} \sum_{i=1}^{n} Z_{i, v} < 2 \Exp\brack*{\sup_{v \in S^{d-1}} \sum_{i=1}^{n} Z_{i, v}} + \sqrt{\frac{2 R(P_{X}) \log(1/\delta)}{n}} + \frac{4 \log(1/\delta)}{3n}
\end{equation}

It remains to bound the expectation in (<ref>). We may rewrite it as

\begin{equation*}
\Exp\brack*{\sup_{v \in S^{d-1}} \sum_{i=1}^{n} Z_{i, v}} = \Exp\brack*{\sup_{v \in S^{d-1}} v^{T} \brace*{\sum_{i=1}^{n}\frac{1}{n}(I - \widetilde{X}_{i}\widetilde{X}_{i}^{T})}v} = \Exp\brack*{\lambdamax\paren*{\sum_{i=1}^{n}\frac{1}{n}(I - \widetilde{X}_{i}\widetilde{X}_{i}^{T})}}
\end{equation*}

Define the matrices $Y_{i} \defeq \frac{1}{n}(I - \widetilde{X}_{i}\widetilde{X}_{i}^{T})$ and notice that they are and satisfy $\lambdamax(Y_i) = n^{-1}$, so that by the Matrix Bernstein inequality <cit.> we obtain

\begin{equation}
\label{eq:three}
\Exp\brack*{\lambdamax\paren*{\sum_{i=1}^{n} Y_{i}}} \leq \sqrt{\frac{2\lambdamax(S)\log(3d)}{n}} + \frac{\log(3d)}{3n}.
\end{equation}

Combining (<ref>), (<ref>), and (<ref>) yields the desired result.

We start by proving the asymptotic lower bound. By the central limit theorem, as $n \to \infty$, and by the finiteness of the fourth moments of $P_{X}$,

\begin{equation*}
\sqrt{n} (\widehat{\Sigma}_{n} - \Sigma) \overset{d}{\to} G,
\end{equation*}

where $G$ is a centred symmetric Gaussian matrix with covariance

\begin{equation*}
\Exp\brack*{g_{ij}g_{st}} = \Exp\brack*{(X_iX_j - \Sigma_{i,j})(X_sX_t - \Sigma_{s, t})},
\end{equation*}

for $i,j,s,t \in [d]$. By the continuous mapping theorem and the continuity of the smallest eigenvalue,

\begin{equation*}
\sqrt{n}\lambdamin(\widehat{\Sigma}_{n} - \Sigma) \overset{d}{\to} \lambdamin(G).
\end{equation*}

Now $\norm{G}_{\text op} = \max\brace*{\lambdamax(G), -\lambdamin(G)}$, and

\begin{equation*}
\lambdamin(G) = \inf_{v \in S^{d-1}} v^{T} G v = - \sup_{v \in S^{d-1}} - v^{T}Gv \overset{d}{=} - \sup_{v \in S^{d-1}} v^{T} G v = -\lambdamax(G),
\end{equation*}

where the penultimate equality follows from the fact that $G$ is a centred Gaussian random matrix, so all the random variables $v^{T}Gv$ are symmetric, and therefore so is their supremum over a countable dense set of $S^{d-1}$. Therefore, for $t > 0$,

\begin{equation*}
\Prob\paren*{\norm{G}_{\text op} > t} = \Prob\paren*{\lambdamax(G) > t \text{ or } \lambdamin(G) < -t} \leq \Prob\paren*{\lambdamax(G) > t} + \Prob\paren*{\lambdamin(G) < -t} = 2 \Prob\paren*{\lambdamin(G) < -t}.
\end{equation*}

so that

\begin{equation*}
\lim_{n \to \infty} \Prob\paren*{\lambdamin(\widehat{\Sigma}_{n} - \Sigma) < -\frac{t}{\sqrt{n}}} = \Prob\paren*{\lambdamin(G) < -t} \geq \frac{1}{2} \Prob\paren*{\norm{G}_{\text op} > t}.
\end{equation*}

Now note that $\lambdamin(\widehat{\Sigma}_{n} - \Sigma) = - \lambdamax(\Sigma - \widehat{\Sigma}_{n})$. Therefore

\begin{equation*}
\lim_{n \to \infty} \Prob\paren*{\lambdamax(\Sigma - \widehat{\Sigma}_{n}) \leq \frac{t}{\sqrt{n}}} \leq \frac{1}{2}\paren*{1 + \Prob\paren*{\norm{G}_{\text op} \leq t}}
\end{equation*}

It remains to upper bound the last probability. Let $v_{*} \defeq \argmax_{v \in S^{d-1}} \Exp\brack*{\paren*{\inp{v}{X}^2 - \Exp\brack*{\inp{v}{X}^{2}}}^2}$ and note that $v^{T}_{*} G v_{*} \sim \mathcal{N}(0, R)$ (this follows from the fact that it is a linear combination of jointly Gaussian variables and that the variance of $v^{T}_{*}Gv_{*}$ is the same as that of $v^{T}_{*}(XX^{T} - \Sigma)v_{*}$). Therefore

\begin{equation*}
\Prob\paren*{\norm{G}_{\text op} \leq t} \leq \Prob\paren*{\abs*{v_{*}^{T} G v_{*}^{T}} \leq t} \leq \sqrt{1 - \exp\paren*{-\frac{2t^2}{\pi R}}}
\end{equation*}

We also have that $-\norm{G}_{\text op}$ is a $\sqrt{R}$-Lipschitz function of standard Gaussian random variables (REFERENCE Van Handel), therefore, for $t < \Exp\brack*{\norm{G}_{\text op}}$,

\begin{equation*}
\Prob\paren*{\norm{G}_{op} \leq t} = \Prob\paren*{\Exp\brack*{\norm{G}_{op}} - \norm{G}_{op} >  \Exp\brack*{\norm{G}_{op}} - t } \leq \exp\paren*{-\frac{(\Exp\brack*{\norm{G}_{op}} - t)^2}{2R}}.
\end{equation*}

Lower bounding $\Exp\brack*{\norm{G}_{op}} \geq C \cdot \lambdamax(S)$, replacing and taking pseudo-inverse of both sides, and noting that the distribution of $\lambdamax(G)$ has a density (so that the quantiles converge at all point, since continuity points of CDF are all of of the points) yields the result.

§.§ Proof of Proposition <ref>

We have

\begin{equation}
\label{eq:one}
\lambdamax(\Sigma - \widehat{\Sigma}_{n}) = \sup_{v \in S^{d-1}} \sum_{i=1}^{n} \underbrace{\frac{1}{n} (\Exp\brack*{\inp{v}{X}^{2}} - \inp{v}{X_{i}}^{2})}_{\textstyle Z_{i,v} \defeq}
\end{equation}

Now the processes $(\brace{Z_{i, v}}_{v \in S^{d-1}})_{i=1}^{d}$ are , $\Exp\brack*{Z_{i, v}} = 0$, and $Z_{i, v} \leq n^{-1}\lambdamax(\Sigma)$ for all $(i, v) \in [n] \times S^{d-1}$, so that by Bousquet's inequality (REFERENCE), with probability at least $1-\delta$

\begin{equation}
\label{eq:two}
\sup_{v \in S^{d-1}} \sum_{i=1}^{n} Z_{i, v} < 2 \Exp\brack*{\sup_{v \in S^{d-1}} \sum_{i=1}^{n} Z_{i, v}} + \sqrt{\frac{2 R \log(1/\delta)}{n}} + \frac{4 \lambdamax(\Sigma)\log(1/\delta)}{3n}
\end{equation}

It remains to bound the expectation in (<ref>). We may rewrite it as

\begin{equation*}
\Exp\brack*{\sup_{v \in S^{d-1}} \sum_{i=1}^{n} Z_{i, v}} = \Exp\brack*{\sup_{v \in S^{d-1}} v^{T} \brace*{\sum_{i=1}^{n}\frac{1}{n}(\Sigma - X_{i}X_{i}^{T})}v} = \Exp\brack*{\lambdamax\paren*{\sum_{i=1}^{n}\frac{1}{n}(\Sigma - X_{i}X_{i}^{T})}}
\end{equation*}

Define the matrices $Y_{i} \defeq \frac{1}{n}(\Sigma - X_{i}X_{i}^{T})$ and notice that they are and satisfy $\lambdamax(Y_i) = n^{-1}\lambdamax(\Sigma)$, so that by the Matrix Bernstein inequality (REFERENCE TROPP), we obtain

\begin{equation}
\label{eq:three}
\Exp\brack*{\lambdamax\paren*{\sum_{i=1}^{n} Y_{i}}} \leq \sqrt{\frac{2\lambdamax(S)\log(d)}{n}} + \frac{\lambdamax(\Sigma)\log(d)}{3n}
\end{equation}

Combining (<ref>), (<ref>), and (<ref>) yields the desired result.

§.§ Proof of Proposition <ref>

Define $\tilde{S} \defeq S(P_{X}) + I = \Exp\brack*{\norm{\widetilde{X}}_2^{2}\widetilde{X}\widetilde{X}^{T}}$ and $\tilde{R} \defeq R(P_{X}) + 1 = \sup_{v \in S^{d-1}}\Exp\brack*{\inp{v}{\widetilde{X}}^{4}}$. Let

\begin{equation*}
B \defeq \sqrt{\frac{n \lambdamax(\tilde{S})}{4(1 + 2 \ceil{\log(d)})}},
\end{equation*}

and define $X_{B} \defeq \widetilde{X} \cdot \mathbbm{1}_{[0, B)}(\norm{\widetilde{X}}_{2}^{2})$, $\Sigma_{B} \defeq \Exp\brack*{X_{B}X_{B}^{T}}$, $\tilde{S}_{B} \defeq \Exp\brack*{(X_{B}X_{B}^{T})^{2}}$, and $\tilde{R}_{B} \defeq \sup_{v \in S^{d-1}}\Exp\brack*{\inp{v}{X_{B}}^{4}}$. Note that $\lambdamax(\tilde{S}_{B}) \leq \lambdamax(\tilde{S})$ and $\tilde{R}_{B} \leq \tilde{R}$. For $(i, v) \in [n] \times S^{d-1}$, define $Z_{i,v} \defeq \inp{v}{X_{B, i}}^{2}$, and note that $(Z_{i, v})_{i=1}^{n}$ are with mean $m(v) \defeq \Exp\brack{\inp{v}{X_{B}}^{2}}$ and $Y_{i, v} \geq Z_{i, v}$.
Now we have by Lemma <ref>

\begin{equation*}
\sup_{v \in S^{d-1}} \sum_{i=k+1}^{n-k} \Exp\brack*{\inp{v}{\widetilde{X}}^{2}} - Y_{i, v}^{*} \leq (n-2k) \sup_{v \in S^{d-1}} \Exp\brack*{\inp{v}{\widetilde{X}}^{2}} - \Exp\brack*{\inp{v}{X_{B}}^{2}} + \sup_{v \in S^{d-1}} \sum_{i=k+1}^{n-k} \Exp\brack*{\inp{v}{X_{B}}^{2}} - Z_{i,v}^{*}
\end{equation*}

The first term is bounded by

\begin{align*}
\sup_{v \in S^{d-1}} \Exp\brack*{\inp{v}{\widetilde{X}}^{2}} - \Exp\brack*{\inp{v}{X_{B}}^{2}} &= \sup_{v \in S^{d-1}} \Exp\brack*{\inp{v}{\widetilde{X}}^{2} \mathbbm{1}_{[B, \infty)}(\norm{\widetilde{X}}_{2}^{2})} \\
&= \sup_{v \in S^{d-1}} \Exp\brack*{\inp{v}{\widetilde{X}}^{2} \norm{\widetilde{X}}_2^2 \frac{1}{\norm{\widetilde{X}}_{2}^{2}} \mathbbm{1}_{[B, \infty)}(\norm{\widetilde{X}}_{2}^{2})} \\
&\leq \frac{\lambdamax(\tilde{S})}{B} = \sqrt{4(1 + 2 \ceil{\log(d)})} \sqrt{\frac{\lambdamax(\tilde{S})}{n}}
\end{align*}

For the second term, define, for $(i,v) \in [n] \times S^{d-1}$, $W_{i,v} \defeq \Exp\brack*{\inp{v}{X_{B}}^2} - Z_{i, v}$, and note that $\Exp\brack*{W_{i, v}} = 0$, $\Exp\brack*{W_{i, v}^{2}} \leq \tilde{R}$. Furthermore

\begin{align*}
&2\Exp\brack*{\sup_{v \in S^{d-1}} \sum_{i=1}^{n} \eps_i W_{i, v}} \\
&=2\Exp\brack*{\sup_{v \in S^{d-1}} v^{T} \brace*{\sum_{i=1}^{n} \eps_i (\Sigma_{B} - X_{B, i}X_{B, i}^{T})}v} \\
&\leq 2\Exp\brack*{\norm*{\sum_{i=1}^{n} \eps_i (\Sigma_{B} - X_{B, i}X_{B, i}^{T})}_{op}} \\
&\leq \sqrt{4 (1+ 2\ceil{\log(d)})} \sqrt{n \lambdamax(\tilde{S}_{B})} + 4(1 + 2\ceil{\log(d)}) \Exp\brack*{\max_{i \in [n]} \norm{X_{B, i}X_{B, i}^{T} - \Sigma_{B}}_{op}^{2}}^{1/2}  \\
%&\leq \sqrt{n (1+ 2\ceil{\log(d)}) \lambdamax(\tilde{S})} + (1 + 2\ceil{\log(d)}) \cdot B \\
&\leq \sqrt{4(1+ 2\ceil{\log(d)})} \sqrt{n \lambdamax(\tilde{S})} + 4(1 + 2\ceil{\log(d)}) \Exp\brack*{\max\brace*{\max_{i \in [n]}\norm{X_{B, i}}_2^2, \lambdamax(\Sigma_{B})}^2}^{1/2} \\
&\leq \sqrt{4(1+ 2\ceil{\log(d)})} \sqrt{n \lambdamax(\tilde{S})} + 4(1 + 2\ceil{\log(d)}) \max\brace*{B, 1} \\
%&\leq \sqrt{1+ 2\ceil{\log(d)}} \sqrt{n \lambdamax(\tilde{S})} + (1 + 2\ceil{\log(d)}) B \\
&= 4 \sqrt{1+ 2\ceil{\log(d)}} \sqrt{n \lambdamax(\tilde{S})}
\end{align*}

where the fourth line follows from the proof of the second item of Theorem 5.1 in Tropp, 2015, the sixth line follows from the fact that $\norm{X_{B}}_{2}^{2} \leq B$, and the last line follows from the condition on $n$ and the fact that $\lambdamax(\tilde{S}) \geq 1$, which itself follows from the positive semi-definiteness of $S(P_{X})$. Defining $W_{v} = (W_{i, v})_{i=1}^{n}$ for $v \in S^{d-1}$, and appealing to Lemma <ref>, we may therefore bound the second term as follows, with probability at least $1-\delta$

\begin{align*}
\sup_{v \in S^{d-1}} \sum_{i=k+1}^{n-k} \Exp\brack*{\inp{v}{X_{B}}^{2}} - Z_{i,v}^{*} &= \sup_{v \in S^{d-1}} \sum_{i=k+1}^{n-k} W_{i, v}^{*} \\
&\leq \sup_{v \in S^{d-1}} \varphi_{k}(W_{v}) + \sup_{v \in S^{d-1}} k (\abs{W_{1+k, v}} + \abs{W_{n-k, v}}) \\
&\leq 96 \cdot  \paren*{\sqrt{4(1 + 2 \ceil{\log(d)})} \sqrt{n \lambdamax(\tilde{S})} + \sqrt{n \tilde{R} \log(2/\delta)}}
\end{align*}

Combining the bounds, and bounding $\sqrt{4(1+\ceil{\log(d)})} \leq 8 \log(6d)$ yields the result.