We study the problem of designing minimax procedures in linear regression under the quantile risk. We start by considering the realizable setting with independent Gaussian noise, where for any given noise level and distribution of inputs, we obtain the exact minimax quantile risk for a rich family of error functions and establish the minimaxity of OLS. This improves on the lower bounds obtained by Lecué and Mendelson, 2016 and Mendelson, 2017 for the special case of square error, and provides us with a lower bound on the minimax quantile risk over larger sets of distributions.

Under the square error and a fourth moment assumption on the distribution of inputs, we show that this lower bound is tight over a larger class of problems. Specifically, we prove a matching upper bound on the worst-case quantile risk of a variant of the procedure proposed by Lecué and Lerasle, 2020, thereby establishing its minimaxity, up to absolute constants. We illustrate the usefulness of our approach by extending this result to all $p$-th power error functions for $p \in (2, \infty)$.

Along the way, we develop a generic analogue to the classical Bayesian method for lower bounding the minimax risk when working with the quantile risk, as well as a tight characterization of the quantiles of the smallest eigenvalue of the sample covariance matrix.

minimax procedures, linear regression, sample covariance matrix, quantile risk.

§ INTRODUCTION

We study the problem of designing minimax procedures in linear regression under the quantile risk over large classes of distributions. Specifically, for some $d \in \N$, there is an input random vector $X \in \R^{d}$ and an output random variable $Y \in \R$, and we are provided with $n \in \N$ samples $(X_i, Y_i)_{i=1}^{n}$ from their joint distribution $P$, with the goal of constructing a predictor of $Y$ given $X$. We consider the set of linear predictors $\brace*{x \mapsto \inp{w}{x} \mid w \in \R^{d}}$, and measure the error of a predictor $w \in \R^{d}$ on an input/output pair $(X, Y)$ through $e(\inp{w}{X} - Y)$ for an error function of our choice $e: \R \to \R$. We evaluate the overall error of a predictor $w \in \R^{d}$ through the expected error $E(w) \defeq \Exp\brack*{e(\inp{w}{X} - Y)}$, and define $\mathcal{E}(w) \defeq E(w) - \inf_{v \in \R^{d}} E(v)$.

For a user-chosen failure probability $\delta \in (0, 1)$, we evaluate the performance of a procedure $\hat{w}_{n, \delta}: (\R^{d} \times \R)^{n} \to \R^{d}$ on a particular distribution $P$ through its quantile risk

\begin{equation}
\label{eq:quantile_risk}
R_{n, \delta}(P, \hat{w}_{n, \delta}) \defeq Q_{\mathcal{E}(\hat{w}_{n,\delta})}(1 - \delta) = \inf\brace*{t \geq 0 \st \Prob\paren*{\mathcal{E}(\hat{w}_{n, \delta}) \leq t} \geq 1-\delta},
\end{equation}

where we shortened $\hat{w}_{n, \delta}((X_i, Y_i)_{i=1}^{n})$ to $\hat{w}_{n, \delta}$.
We consider the scenario where all that is known about $P$ is that it belongs to a class of distributions $\mathcal{P}$ on $\R^{d} \times \R$. This justifies evaluating the overall performance of a procedure through its worst-case risk

\begin{equation*}
R_{n,\delta}(\mathcal{P}, \hat{w}_{n, \delta}) \defeq \sup_{P \in \mathcal{P}} R_{n, \delta}(P, \hat{w}_{n, \delta}).
\end{equation*}

Our goal is to characterize the minimax risk $R^{*}_{n, \delta}(\mathcal{P}) \defeq \inf_{\hat{w}_{n, \delta}} R_{n,\delta}(\mathcal{P}, \hat{w}_{n, \delta})$ and design minimax procedures for rich classes of distributions and error functions.

Note on terminology. In this paper, we reserve the terms `risk' and `loss' to refer to the corresponding decision-theoretic concepts, see e.g. Lehmann and Casella, 2006 for background on these notions. To avoid any confusion, we have used the terms `error' and `expected error' to refer to what is commonly called `prediction loss' and `prediction risk' in statistical learning theory.

Motivation. Our motivation for studying this problem has its roots in the work of Catoni, 2012, who showed that the empirical mean is no longer minimax over the set of all distributions with finite variance under the square loss if one replaces the classical notion of risk, given by the expected loss, with the quantile risk, given by the $1-\delta$ quantile of the loss, for any user-chosen failure probability $\delta \in (0, 1)$. Since then, minimax procedures were discovered for this problem [Devroye et al., 2016, Lee and Valiant, 2022], and there has been a lot of effort to construct minimax procedures under this new notion of risk for a variety of statistical problems [Lugosi and Mendelson, 2019, Lugosi and Mendelson, 2019, Mendelson and Zhivotovskiy, 2020]. We view our work as part of this larger effort.

Known results. To understand why previous results are insufficient to accomplish our stated goal, let us briefly review the most relevant ones. Most previous work has focused on the case of square error $e(t) = t^{2}/2$ [Audibert and Catoni, 2011, Hsu and Sabato, 2016, Lugosi and Mendelson, 2019, Lecué and Lerasle, 2020]. In this case, a natural class of distributions to consider is

\begin{equation}
\label{eq:class_2}
\mathcal{P}_{2}(P_{X}, \sigma^2) \defeq \brace*{P \st (X, Y) \sim P : X \sim P_{X} \text{ and } \esssup(\Exp\brack{\xi^{2} \mid X}) \leq \sigma^2},
\end{equation}

for a given distribution $P_{X}$ of inputs, noise level $\sigma^2 \in (0, \infty)$, and where $\xi \defeq Y - \inp{w^{*}}{X}$ is the noise and $w^{*}$ is the unique minimizer of the expected error $E(w)$ under square error. The best lower bound on the minimax risk over this class has been obtained by considering the subclass

\begin{equation*}
\mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^2) \defeq \brace{P \mid (X, Y) \sim P : (X, \eta) \sim P_{X} \times \mathcal{N}(0, \sigma^2), Y = \inp{w^{*}}{X} + \eta \text{ for } w^{*} \in \R^{d}}.
\end{equation*}

The following results yield the best upper and lower bounds on the minimax risk over $\mathcal{P}_{2}(P_{X}, \sigma^2)$.

Suppose that $e(t) = t^{2}/2$. There exist absolute constants $C, c > 0$ such that for all $\delta \in (0, 1/8)$, it holds that

\begin{equation*}
R^{*}_{n,\delta}(\mathcal{P}_{\normalfont\textrm{Gauss}}(P_{X}, \sigma^2)) \geq \begin{dcases*}
\infty & if $n \leq d/C$, \\
c \cdot \frac{\sigma^{2}(d + \log(1/\delta))}{n} & otherwise.
\end{dcases*}
\end{equation*}

Suppose that $e(t) = t^{2}/2$. There exists a procedure $\hat{w}_{n, \delta}$ and absolute constants $C, c > 0$ such that the following holds. If

\begin{equation*}
n \geq c \cdot \theta^2(P_{X}) (d + \log(1/\delta)), \quad \text{ where } \quad \theta(P_{X}) \defeq \sup_{w \in \R^{d}\setminus\brace*{0}}\frac{\Exp\brack*{\inp{w}{X}^{2}}^{1/2}}{\Exp\brack*{\abs{\inp{w}{X}}}},
\end{equation*}

\begin{equation*}
R_{n,\delta}(\mathcal{P}_2(P_{X}, \sigma^2), \hat{w}_{n, \delta}) \leq
C \cdot \theta^{2}(P_{X}) \cdot \frac{\sigma^{2} \cdot (d + \log(1/\delta))}{n}.
\end{equation*}

In the prescribed regime $(n, \delta)$ stated in Proposition <ref>, and on the set of distributions for which $\theta(P_{X})$ is upper bounded by an absolute constant, the combination of Propositions <ref> and <ref> proves the minimaxity, up to an absolute constant, of the procedure in Proposition <ref> over $\mathcal{P}_2(P_{X}, \sigma^2)$.

Unfortunately, this minimaxity result is unsatisfactory for two important reasons. First, the set of distributions for which $\theta(P_{X})$ is bounded by an absolute constant is both difficult to characterize and too small to cover classes of problems of interest. Indeed, by using the relationship between $\theta(P_{X})$ and the small-ball constants [Lecué and Lerasle, 2019], and using the lower bounds derived on the latter by [Saumard, 2018], it is possible to derive dimension-dependent lower bounds on $\theta(P_{X})$ for standard linear regression problems with bounded inputs. Second, this minimaxity result is specific to the square error function. While procedures with guarantees have been studied for other error functions [Chinot et al., 2020], no lower bounds are known outside of Proposition <ref>.

Main challenges and our approach

The first challenge we are faced with is to derive lower bounds on the minimax quantile risk for a richer class of error functions beyond the square error. Unfortunately, the argument leading to Proposition <ref> is quite specific to the square error. In related work, still for the square error, and under the classical notion of risk given by the expected excess error $\Exp\brack*{\mathcal{E}(\hat{w}(D_{n})}$ (c.f. (<ref>)), Mourtada, 2022 recently computed the exact minimax risk over $\mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^{2})$. His proof strategy relies on a classical Bayesian argument: lower bounding the minimax risk by a sequence of increasing Bayes risks, and showing that ERM achieves the limit of the Bayes risks, see e.g. <cit.> for more details. However, an inspection of Mourtada's argument shows that it can be generalized to a rich class of error functions by an application of Anderson's Lemma, see e.g. <cit.>.

Our strategy is to try to adapt Mourtada's argument to the case of the quantile risk. Unfortunately, it is not obvious how to translate his argument to our setting. Indeed, it is not even clear what the notions of average risk and Bayes risk should be in this case, and whether the technical tools used in his proof carry over when working with quantiles instead of expectations. This turns out to to be the main obstacle in obtaining the exact minimax quantile risk over the class $\mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^2)$ for a rich class of error functions, and we overcome this by developing a generic analogue to the above-described classical Bayesian method when working with the quantile risk.

On the upper bound side, one way to settle the case of square error is to derive a better upper bound on the procedure of Oliveira and Resende, 2023. We will argue that it is more appropriate to study the performance of this procedure under a fourth moment assumption on $P_{X}$. Even with this additional assumption, we are faced with two additional challenges. Firstly, the proof of Proposition <ref> is a refinement of arguments developed by Lugosi and Mendelson, 2019, Lecué and Lerasle, 2020 which are in some places tailored for the use of the small-ball method. We overcome this by carefully studying the truncation function used in the design of some of these estimators [Lugosi and Mendelson, 2021, Oliveira and Resende, 2023]. Secondly, once this is overcome, we are faced with the problem of lower bounding with high probability the smallest eigenvalue of the sample covariance matrix, subject to a direction-dependent adversarial truncation. We achieve this by obtaining a generic upper bound on the suprema of truncated empirical processes, and combining it with the use of matrix Khintchine inequalities <cit.>.

Below we summarize our main results related to linear regression.

* We compute the exact minimax quantile risk over the class $\mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^2)$ for a rich set of error functions, and show that OLS is minimax in this setting (Theorem <ref>). We deduce from this result the asymptotic minimax quantile risk over this class (Proposition <ref>).

* Focusing on the non-asymptotic setting with $e(t)=t^2/2$, we complement our exact computation with tight upper and lower bounds (Proposition <ref>). We then recover the lower bound of Proposition <ref> and identify a setting in which it is tight (Corollary <ref>). We give an analogous result under the error function $e(t)=\abs{t}^{p}/[p(p-1)]$ for $p \in (2,\infty)$ (Proposition <ref>).

* We then turn to finding minimax procedures on larger classes of distributions. For the square error, we establish the minimaxity, up to an absolute constant, of a variant of the min-max regression procedure [Audibert and Catoni, 2011, Lecué and Lerasle, 2020] over the class $\mathcal{P}_{2}(P_{X}, \sigma^2)$, and under a fourth moment assumption on $P_{X}$ (Theorem <ref>).

* Finally, we study minimax linear regression under the error function $e(t)=\abs{t}^{p}/[p(p-1)]$ for $p \in (2, \infty)$. Guided by our results, we identify a rich class of distributions analogous to $\mathcal{P}_{2}(P_{X}, \sigma^2)$, and show that the min-max regression procedure is minimax, up to a constant that depends only on $p$, and under a fourth moment assumption on $P_{X}$ (Theorem <ref>).

Our contributions on linear regression are supported by the following more general results.

* We consider the quantile risk in full generality. We develop an analogue to the Bayesian method for lower bounding the minimax quantile risk (Theorem <ref>). We then prove that the minimaxity of procedures under the quantile risk is invariant to strictly increasing left-continuous transformations of the loss (Proposition <ref>).

* We illustrate the generality of our methods by applying them to two unrelated problems: multivariate mean estimation with Gaussian data, in which we recover a strengthening of the recent result of [Depersin and Lecué, 2022] (Proposition <ref>), and variance estimation with Gaussian data and known mean, where we show that, surprisingly, the sample variance is suboptimal, and design a new minimax estimator (Proposition <ref>).

* We conclude by studying the smallest eigenvalue of the sample covariance matrix. We prove a new tight asymptotic lower bound on its quantiles, and a nearly matching fully non-asymptotic upper bound (Proposition <ref>), both under a fourth moment assumption on $P_{X}$.

Organization The rest of the paper is organized as follows. In Section <ref>, we present our results on the minimax quantile risk over the class $\mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^2)$. In Section <ref>, we present new upper bounds on the worst-case quantile risk of the min-max regression procedure for the error functions $e(t) = \abs{t}^{p}/[p(p-1)]$ for $p \in [2,\infty)$, showing its minimaxity over suitable classes of distributions up to constants. In Section <ref> we study the quantile risk in full generality. Finally, in Section <ref>, we present our results on the smallest eigenvalue of the sample covariance matrix.

Notation. We call a function $f: \R \to \R$ increasing if $x \leq x'$ implies $f(x) \leq f(x')$. If $f: \R \to \R$ is an increasing function, we define its pseudo-inverse $f^{-}: [-\infty, \infty] \to [-\infty, \infty]$ by $f^{-}(y) \defeq \inf\brace*{x \in \R \st f(x) \geq y}$. For a random variable $X: \Omega \to \R$, we denote its CDF by $F_{X}$ and its quantile function by $Q_{X} \defeq F^{-}_{X}$. We allow random variables of the form $X: \Omega \to [0, \infty]$, but we restrict the definition of their CDFs to $[0, \infty)$. Without loss of generality, we assume throughout that the support of the distribution of inputs $P_{X}$ is not contained in any hyperplane. We write $\Sigma = \Exp\brack*{XX^{T}}$ for the covariance matrix of the random vector $X$. We write $a \asymp b$ to mean that there exist absolute constants $C, c > 0$ such that $c \cdot b \leq a \leq C \cdot b$.

§ MINIMAX QUANTILE RISK OVER TEXT

The following is the main result of this section.

Let $P_{X}$ be a distribution on $\R^{d}$ and $\sigma^{2} \in (0, \infty)$. Assume that $e$ is strictly convex, differentiable, and symmetric i.e. $e(t) = e(-t)$ for all $t \in \R$. Define, for $(X, \eta) \sim P_{X} \times \mathcal{N}(0, \sigma^2)$,

\begin{equation*}
\widetilde{E}(\Delta) \defeq \Exp\brack*{e(\inp{\Delta}{X} + \eta)}, \quad\quad \widetilde{\mathcal{E}}(\Delta) \defeq \widetilde{E}(\Delta) - \widetilde{E}(0).
\end{equation*}

If $P_{X}$ is such that $\widetilde{E}$ is finite everywhere and differentiable at $0$ with $\nabla \widetilde{E}(0) = \Exp\brack*{\nabla e(\eta)}$, then

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

where the random variable $Z$ is jointly distributed with $(X_i)_{i=1}^{n} \sim P_{X}^{n}$ such that $Z \mid (X_i)_{i=1}^{n} \sim \mathcal{N}(0, \frac{\sigma^{2}}{n} \widehat{\Sigma}_{n}^{-1})$ on the event that the sample covariance matrix $\widehat{\Sigma}_{n} \defeq n^{-1} \sum_{i=1}^{n} X_{i}X_{i}^{T}$ is invertible, otherwise  $\widetilde{\mathcal{E}}(Z) \defeq \infty$. Moreover, all procedures satisfying the following condition are minimax

\begin{equation*}
\hat{w}_{n, \delta}((X_i, Y_i)_{i=1}^{n}) \in \argmin_{w \in \R^{d}} \frac{1}{n}\sum_{i=1}^{n} (\inp{w}{X_i} - Y_i)^{2}.
\end{equation*}

Assume that $e$ is strictly convex, differentiable, and symmetric. If $P_{X}$ is such that $E$ is finite and differentiable with $\nabla E(w) = \Exp\brack*{\nabla e(\inp{w}{X} - Y)}$ for all $w \in \R^{d}$, and $\sigma^2 \in (0, \infty)$, then

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

where, for $(X, \eta) \sim P_{X} \times \mathcal{N}(0, \sigma^2)$,

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

and where the random variable $Z$ is jointly distributed with $(X_i)_{i=1}^{n} \sim P_{X}^{n}$ such that $Z \mid (X_i)_{i=1}^{n} \sim \mathcal{N}(0, \frac{\sigma^{2}}{n} \widehat{\Sigma}_{n}^{-1})$ on the event that the sample covariance matrix $\widehat{\Sigma}_{n} \defeq n^{-1} \sum_{i=1}^{n} X_{i}X_{i}^{T}$ is invertible, otherwise  $\widetilde{\mathcal{E}}(Z) \defeq \infty$. Moreover, all the procedures satisfying the following condition are minimax

\begin{equation*}
\hat{w}_{n, \delta}((X_i, Y_i)_{i=1}^{n}) \in \argmin_{w \in \R^{d}} \frac{1}{n}\sum_{i=1}^{n} (\inp{w}{X_i} - Y_i)^{2}.
\end{equation*}

We make a few remarks about this result before interpreting its content. First, Theorem <ref> improves on the best known comparable result, Proposition <ref>, in two distinct ways: it provides the exact minimax risk over the class $\mathcal{P}_{\normalfont \text{Gauss}}(P_{X}, \sigma^{2})$ for the error function $e(t) = t^2/2$, and it generalizes this result to a rich collection of error functions. Second, and as can readily be seen from the proof, the strict convexity hypothesis on $e(t)$ in Theorem <ref> can be weakened to the strict quasiconvexity of $E(w)$, and the strictness can be replaced by the existence of a unique minimizer of $E(w)$. Finally, the proof of Theorem <ref> is based on the Bayesian method we develop in Theorem <ref>, an adaptation of an argument of Mourtada, 2022, and Anderson's Lemma <cit.>.

While exact, the result in Theorem <ref> is both difficult to interpret and hard to manipulate. In particular, the dependence of the minimax risk on the problem parameters $(n, \delta, P_{X}, \sigma^2)$ as well as the error function $e$ remains implicit in Theorem <ref>. This is not too surprising as the error function can interact with the parameters of the problems in quite complicated ways.

In the rest of this section, we develop tools to make these dependencies explicit. Specifically, in Section <ref>, we compute the asymptotic minimax risk for generic error functions as $n \to \infty$ and show that it takes on a simple form. In Section <ref>, we focus on the case of square error function, and identify a setting where the lower bound of Proposition <ref> is tight. In Section <ref>, we extend this result to the case of the $p$-th power error function for $p \in (2,\infty)$.

§.§ General error functions

The following result shows that under a mild assumption on the error function, the asymptotic minimax risk is a pleasingly simple function of the parameters of the problem. In particular, this result shows that the lower bound of Proposition <ref> is asymptotically tight.

Under the setup of Theorem <ref>, further assume that $e$ is twice differentiable and $\widetilde{E}$ is twice differentiable at $0$ with $\nabla^2 \widetilde{E}(0) = \Exp\brack*{\nabla^{2}e(\eta)}$, and let $\alpha \defeq \Exp\brack*{e''(\eta)}/2$. Then

\begin{equation*}
\lim_{n \to \infty} n \cdot R_{n, \delta}^{*}(\mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^2)) = \sigma^{2} \alpha \cdot  Q_{\norm{Z}_2^2}(1 - \delta) \asymp \sigma^2 \alpha \cdot \brack*{d + \log(1/\delta)},
\end{equation*}

where $Z \sim \mathcal{N}(0, I_{d \times d})$, and where the relation $\asymp$ holds when $\delta \in (0, 1/2)$.

Non-asymptotically, and with no more assumptions on the error function, it is difficult to say much more about the minimax risk than Proposition <ref>. However, determining when the minimax risk is infinite is tractable, as the next result shows.

Under the setup of Theorem <ref>, let $\eps_{n} \defeq \Prob\paren*{\rank(\widehat{\Sigma}_{n}) < d}$. Then

\begin{equation*}
R_{n, \delta}^{*}(\mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^2)) = \infty \Leftrightarrow \delta \leq \eps_{n} \quad \text{ and } \quad
\rho(P_{X})^{n} \leq \eps_{n} \leq \left(\genfrac{}{}{0pt}{}{n}{d-1}\right) \rho(P_{X})^{n - d - 1},
\end{equation*}

where $\rho(P_{X}) \defeq \sup_{w \in \R^{d} \setminus \brace*{0}} \Prob(\inp{w}{X} = 0) < 1$.

The upper bound on $\eps_{n}$ as well as the statement $\rho(P_{X}) < 1$ in Lemma <ref> are due to El Hanchi and Erdogdu, 2023. At a high level, Lemma <ref> says that the range of failure probabilities for which the risk is infinite gets exponentially small as a function of $n$. This is in sharp contrast with the result of Mourtada, 2022 under the classical notion of risk and the square error, where it was shown that the minimax risk in that case is infinite for all sample sizes as soon as $\rho(P_{X}) > 0$.

§.§ Square error

We assume throughout this section that $e(t) = t^2/2$. We derive increasingly loose but more interpretable upper and lower bounds on the minimax risk in this setting. Our motivation is to better understand the influence of each of the parameters $(n, \delta, P_{X}, \sigma^2)$ of the problem on the minimax risk. Practically, the main result of this section is the identification of a general sufficient condition under which the lower bound in Proposition <ref> is tight. With that achievement to look forward to, we start with a simple Corollary of Theorem <ref>.

Under the setup of Theorem <ref>,

\begin{equation*}
R_{n, \delta}^{*}(\mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^2)) = \frac{\sigma^2}{2n} \cdot Q_{\norm{Z}_2^2}(1 - \delta),
\end{equation*}

where the random variable $Z$ is jointly distributed with $(X_i)_{i=1}^{n} \sim P_{X}^{n}$ such that $Z \mid (X_i)_{i=1}^{n} \sim \mathcal{N}(0, \widetilde{\Sigma}_{n}^{-1})$ on the event that the sample covariance matrix $\widehat{\Sigma}_{n}$ is invertible, and where $\widetilde{\Sigma}_{n} = \Sigma^{-1/2} \widehat{\Sigma}_{n} \Sigma^{-1/2}$ is the whitened sample covariance matrix; otherwise $\norm{Z}_2^2 \defeq \infty$.

Corollary <ref> already makes explicit the dependence of the minimax risk on $(n, \sigma^2)$, but the dependence on $(P_{X}, \delta)$ remains implicit. The next result is a step towards clarifying this relationship.

Under the setup of Theorem <ref>, and for all $\delta \in (0, (1-\eps_n)/4)$,

\begin{equation*}
R_{n, \eps_{n} + \delta}^{*}(\mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^2)) \begin{dcases}
&\leq 2 \cdot \frac{\sigma^2}{n} \brack*{Q_{\Tr\paren*{\widetilde{\Sigma}_{n}^{-1}}}(1 - \eps_n - \delta/2) + Q_{W}(1 - \eps_n - \delta/2)}, \\
&\geq \frac{1}{6428} \cdot \frac{\sigma^{2}}{n} \brack*{Q_{\Tr\paren*{\widetilde{\Sigma}_{n}^{-1}}}(1 - \eps_n - 4\delta) + Q_{W}(1 - \eps_n - 4\delta)},
\end{dcases}
\end{equation*}

where we defined $\Tr(\widetilde{\Sigma}_{n}^{-1}) \defeq \infty$ when $\widetilde{\Sigma}_{n}$ is not invertible, and $W$ is a random variable jointly distributed with $(X_i)_{i=1}^{n} \sim P_{X}^{n}$ and with conditional distribution $W \mid (X_i)_{i=1}^{n} \sim {\normalfont\text{Exp}}(\lambdamin(\widetilde{\Sigma}_{n}))$, with the convention that the exponential distribution ${\normalfont\text{Exp}}(0)$ refers to the unit mass at $\infty$.

It is interesting to compare this result with the exact minimax risk under the classical notion of risk computed by Mourtada, 2022, and given by $(\sigma^{2}/n) \cdot \Exp\brack{\Tr({\widetilde{\Sigma}_{n}^{-1})}}$. Proposition <ref> says that the minimax quantile risk is upper and lower bounded by a `strong' term given by a quantile of $\Tr({\widetilde{\Sigma}_{n}^{-1})}$, and a `weak' term governed by the distribution of $\lambdamin(\widetilde{\Sigma}_{n})$. Our next result shows that the lower bound from Proposition <ref> improves on the one from Proposition <ref>.

Let $\delta \in (\eps_{n}, 1)$. Then

d ·(1  - δ)    ≤   Q_*Σ_n^-1(1 - δ)    ≤Q_(Σ_n^-1)(1 - δ) ·d,

log(1/δ)    ≤   Q_W(1 - δ)    ≤Q_(Σ_n^-1)(1 - δ/2) ·log(2/δ).

This lemma further shows that a sufficient condition for the lower bound of Proposition <ref> to be tight is the boundedness of $Q_{\lambdamax(\widetilde{\Sigma}_{n}^{-1})}(1 - \delta/2)$ by an absolute constant. Under what conditions on $(n, \delta, P_{X})$ does this hold ? Our results from Section <ref> provide a satisfying answer.

Assume that $P_{X}$ has fourth moments. If $\delta \in (0, 1/2)$ and

\begin{equation*}
n \geq \max\brace*{128 \brack*{4 \log(3d) \lambdamax(S(P_{X})) + R(P_{X}) \log(2/\delta)}, \frac{\log(3d)}{18 \lambdamax(S(P_{X}))}, \frac{\log(2/\delta)}{R(P_{X})}},
\end{equation*}

\begin{equation*}
R_{n, \delta}^{*}(\mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^2)) \asymp \frac{\sigma^2 (d + \log(1/\delta))}{n},
\end{equation*}

where the parameters $S(P_{X})$, $R(P_{X})$ are as defined in (<ref>).

Corollary <ref> can be interpreted as a non-asymptotic version of Proposition <ref> for the square error function. As we argue in Section <ref>, the fourth moment assumption is very natural in this setting, and the sample size restriction is, in a sense, optimal. The main restriction on the sample size comes from the first term, as both $\lambdamax(S(P_{X}))$ and $R(P_{X})$ are expected to be large.

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}_{\normalfont\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$. We also mention that the conclusion can be strengthened to the existence of a $\delta_0 \in (0, 1-\eps_n)$ such that the statement holds for all $\delta \in (0, \delta_0)$ under an additional mild hypothesis, we discuss this more in Appendix (REFERENCE).

§.§.§ When is the lower bound of Proposition <ref> tight ?

Let $\delta \in (0, 1-\eps_{n})$. Then

d ·(1  - δ)    ≤   Q_*Σ_n^-1(1 - _n - δ)    ≤d ·Q_(Σ_n^-1)(1 - _n - δ),

(1-_n) log((1-_n)/δ)    ≤   Q_W(1 - _n - δ)    ≤Q_(Σ_n^-1)(1 - _n - δ/2) log(2/δ).

Lemma <ref> shows that the lower bound from Proposition <ref> improves on the one from Proposition <ref>. Furthermore, the Lemma shows that a sufficient condition for the lower bound of Proposition <ref> to be tight is that $Q_{\lambdamax(\widetilde{\Sigma}_{n}^{-1})}(1 - \eps_{n} - \delta/2)$ be bounded by an absolute constant. Under what conditions on $P_{X}$, $n$ and $\delta$ does this hold ? This is what we address next.

To gain some intuition about what a reasonable set of conditions would be, we recall the fact that $\widetilde{\Sigma}_{n}$ is an empirical average of the random matrices $\tilde{X}\tilde{X}^{T}$ where $\tilde{X} \defeq \Sigma^{-1/2}X$ and $X \sim P_{X}$. Therefore, by the law of large numbers, $\Sigma_{n} \overset{d}{\to} I_{d \times d}$, and by the continuous mapping theorem, $\lambdamax(\widetilde{\Sigma}_{n}^{-1}) \overset{d}{\to} 1$ as $n \to \infty$. To say something about the rate of this convergence, the most natural assumption to make is that the second moment of the random matrix $\tilde{X}\tilde{X}^{T}$ exists so that the central limit theorem holds, which is equivalent to assuming that $P_{X}$ has fourth moments. Under this assumption, our results in Section <ref> provide a full characterization of $Q_{\lambdamax(\widetilde{\Sigma}_{n}^{-1})}(1 - \delta)$. Building on these results, we obtain the following sufficient joint conditions on $(P_{X}, n, \delta)$ that guarantee that the lower bound of Proposition <ref> is tight.

Assume that $P_{X}$ has fourth moments and define

\begin{equation*}
S(P_{X}) \defeq \Exp\brack*{\paren*{\tilde{X}\tilde{X}^{T} - I}^{2}}, \quad\quad R(P_{X}) \defeq \sup_{v \in S^{d-1}} \Exp\brack*{\paren*{\inp{v}{\tilde{X}}^{2} - 1}^2}.
\end{equation*}

and assume that $n \geq 64 (1 + \log(d)) \lambdamax(S(P_{X}))$ and $\delta \in [\delta_{0}(P_{X}), 1)$. Then

\begin{equation*}
\inf_{\hat{w}_{n}} \sup_{P \in \mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^{2})} R_{n, \delta}(P, \hat{w}_{n}) \asymp \frac{\sigma^2 (d + \log(1/\delta))}{n},
\end{equation*}

\begin{equation*}
\delta_{0}(P_{X}) \defeq \exp\paren*{-\min\brace*{\frac{3n - 4(1 + \log(d))}{16}, \frac{n}{128 R(P_{X})}}}.
\end{equation*}

§.§ TEXT-th power error

The results of the last section are quite specific to the case of the square error, and it is a priori unclear how the minimax risk of other error functions can be studied non-asymptotically. Let us build on the observation that Corollary <ref> is a non-asymptotic version of Proposition <ref> for the square error. Can we do this for more general error functions ?
The underlying proof idea of Proposition <ref> is a simple second order Taylor expansion, which becomes exact as $n \to \infty$. If we have non-asymptotic control over the error in this expansion, we can carry out the argument behind Proposition <ref> non-asymptotically. We implement this idea here, and conclude this section with the following non-asymptotic lower bound on the minimax risk under a $p$-th power error function.

Assume that $e(t) = \abs{t}^{p}/[p(p-1)]$ for some $p \in (2,\infty)$. Under the setup of Theorem <ref>, and for $\delta \in (0, 1/2)$, we have

\begin{equation*}
R_{n, \delta}^{*}(\mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^2)) \geq \frac{m(p-2)}{16 (p-1)} \cdot \frac{\sigma^{p}\brack*{d + \log(1/\delta)}}{n}
\end{equation*}

where $m(p) \defeq 2^{p/2-1}\Gamma(p/2-1)/\sqrt{\pi}$ is the $p$-th absolute moment of a standard normal variable.

Finally, we use our result to compute the asymptotic minimax risk for any fixed $\delta$ when the number of samples diverges.

In the context of Theorem <ref>, it holds that

\begin{equation*}
\lim_{n \to \infty} n \cdot \paren*{\inf_{\hat{w}_{n}} \sup_{P \in \mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^2)} R_{n, \delta}(P, \hat{w}_{n})} =
\end{equation*}

where we used $a \asymp b$ to mean that there exists absolute constants $C, c > 0$ such that $c \cdot b \leq a \leq C \cdot b$.

§.§ Square error function

In this subsection, we focus on the canonical case $e(t) = t^2$, which is trivially convex and symmetric.

When $e(t) = t^{2}/2$, the statement of Theorem <ref> holds with

\begin{equation*}
p_{n}(t) = \Exp\brack*{\Prob\paren*{\norm{Z}_2 \leq \sqrt{t} \st (X_i)_{i=1}^{n}} \mathbbm{1}_{\rank(\widehat{\Sigma}) = d}((X_{i})_{i=1}^{n})}
\end{equation*}

where $Z \mid (X_{i})_{i=1}^{n} \sim \mathcal{N}\paren*{0, \frac{\sigma^{2}}{n}\widetilde{\Sigma}^{-1}}$ and $\widetilde{\Sigma} \defeq \Sigma^{-1/2} \widehat{\Sigma} \Sigma^{-1/2}$.

As $n\to \infty$, $\widehat{\Sigma} \overset{d}{\to} I$, $\eps_{n} \to 0$, so that $W \overset{d}{\to} \text{Exp}(1)$ and $\Tr\paren{\widetilde{\Sigma}^{-1}} \overset{d}{\to} d$ and therefore the minimax risk converges, up to an absolute constant, to

\begin{equation*}
\frac{\sigma^2 (d + \log(1/\delta))}{n}
\end{equation*}

which is what one would expect from the local minimax theorems of Hajek and LeCam, as well as from the asymptotic normality of ERM.

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*}

We make the following remarks.

* A sufficient condition for the hypothesis of the above Lemma is $\Exp\brack*{X^{\alpha} \mathbbm{1}_{[0, \infty)}(X)} < \infty$ for some $\alpha > 0$.

* A consequence of the above Lemma is the existence of a sequence $(\delta_k)_{k=1}^{\infty}$ such that $\delta_k \to 0$ as $k \to \infty$, and $Q_{X}(1-p-\delta_k/c)/Q_{X}(1 - p - \delta_k) \leq c^{1/\alpha}$ for all $k \in \N$. When the limit exists, this is strengthened to the existence of $\delta_{0} \in (0,1-p)$ such that $Q_{X}(1-p-\delta/c)/Q_{X}(1 - p - \delta) \leq c^{1/\alpha}$ for all $\delta \in (0, \delta_0]$.

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

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

and assume that the following limits exist

\begin{equation*}
\lim_{\delta \downarrow 0} \frac{Q_{\Tr\paren*{\widetilde{\Sigma}^{-1}}}(1 - \eps_n - \delta/2)}{Q_{\Tr\paren*{\widetilde{\Sigma}^{-1}}}(1 - \eps_n - \delta/4)} \quad\quad \lim_{\delta \downarrow 0}  \frac{Q_{W}(1 - \eps_n - \delta/2)}{Q_{W}(1 - \eps_n - \delta/4)}.
\end{equation*}

Then there exists a $\delta_{0} \in (0, 1-\eps_{n})$ such that, for all $\delta \in (0, \delta_0]$,

\begin{equation*}
\inf_{\hat{w}} \sup_{P \in \mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^{2})} R_{\eps_n + \delta,n}(P, \hat{w}) \asymp Q_{\Tr\paren*{\widetilde{\Sigma}^{-1}}}(1 - \eps_n - \delta) + Q_{W}(1 - \eps_n - \delta)
\end{equation*}

where we used $a \asymp b$ to mean that there exists absolute constants $0 < c < C < \infty$ such that $c \cdot b \leq a \leq C \cdot b$.

CAN I GET THE RESULTS WITHOUT ASSUMING THE EXISTENCE OF THE LIMITS ? May have to reprove the Lemma from scratch. PROVE THIS.

Assume that the error function $e$ is convex and symmetric. Then

\begin{equation*}
w^{*} \in \argmin_{w \in \R^{d}} \Exp\brack*{e(\inp{w}{X}-Y)}
\end{equation*}

and for all distributions $P_{X}$ on $\R^{d}$ and all $\sigma^{2} > 0$,

\begin{equation*}
\inf_{\hat{w}} \sup_{P \in \mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^{2})} R_{\delta,n}(P, \hat{w}) = p_{n}^{-}(1 - \delta),
\end{equation*}

\begin{equation*}
p_{n}(t) \defeq \Exp\brack*{\Prob\paren*{\ell\paren*{\frac{\sigma}{\sqrt{n}} \widehat{\Sigma}^{-1/2}Z} \leq t \st (X_i)_{i=1}^{n}} \mathbbm{1}_{\rank\paren*{\widehat{\Sigma}} = d}((X_i)_{i=1}^{n})},
\end{equation*}

and $Z \sim \mathcal{N}(0, I_{d})$ is independent of $(X_i)_{i=1}^{n}$, $\widehat{\Sigma} = n^{-1} \sum_{i=1}^{n} X_{i}X_{i}^{T}$ is the sample covariance matrix, and $\ell(v) \defeq \Exp\brack*{e(\inp{v}{X} - \eps)} - \Exp\brack*{e(\eps)}$. Furthermore, all the estimators satisfying

\begin{equation*}
\hat{w}((X_i, Y_i)_{i=1}^{n}) \in \argmin_{w \in \R^{d}} \frac{1}{n}\sum_{i=1}^{n} e\paren*{\inp{w}{X_i} - Y_i}
\end{equation*}

are minimax.

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*}

and assume that the following limits exist

\begin{equation*}
\lim_{\delta \downarrow 0} \frac{Q_{\Tr\paren*{\widetilde{\Sigma}^{-1}}}(1 - \eps_n - \delta/2)}{Q_{\Tr\paren*{\widetilde{\Sigma}^{-1}}}(1 - \eps_n - \delta/4)} \quad\quad \lim_{\delta \downarrow 0}  \frac{Q_{W}(1 - \eps_n - \delta/2)}{Q_{W}(1 - \eps_n - \delta/4)}.
\end{equation*}

Then there exists a $\delta_{0} \in (0, 1-\eps_{n})$ such that, for all $\delta \in (0, \delta_0]$,

\begin{equation*}
\inf_{\hat{w}} \sup_{P \in \mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^{2})} R_{\eps_n + \delta,n}(P, \hat{w}) \asymp Q_{\Tr\paren*{\widetilde{\Sigma}^{-1}}}(1 - \eps_n - \delta) + Q_{W}(1 - \eps_n - \delta)
\end{equation*}

where we used $a \asymp b$ to mean that there exists absolute constants $0 < c < C < \infty$ such that $c \cdot b \leq a \leq C \cdot b$.

Let $\delta \in (0, 1-\eps_{n})$. Then

d ·(1  - δ)    ≤   Q_*Σ_n^-1(1 - _n - δ)    ≤d ·Q_(Σ_n^-1)(1 - _n - δ),

(1-_n) log((1-_n)/δ)    ≤   Q_W(1 - _n - δ)    ≤Q_(Σ_n^-1)(1 - _n - δ/2) log(2/δ).

§ MINIMAXITY OF THE MIN-MAX LINEAR REGRESSION PROCEDURE

In this section, we establish the minimaxity of a variant of the popular min-max regression procedure, e.g. Audibert and Catoni, 2011, Lecué and Lerasle, 2020, Oliveira and Resende, 2023 over suitably large classes of problems under the $p$-th power error functions $e(t) = \abs{t}^{p}/[p(p-1)]$, for $p \in [2, \infty)$. Before stating our results, we briefly describe the construction of the procedure.

Let $\alpha, \beta \in \R$ such that $\alpha \leq \beta$ and define $\phi_{\alpha,\beta}(x) \defeq \alpha \mathbbm{1}_{(-\infty, \alpha)}(x) + x \mathbbm{1}_{[\alpha, \beta]}(x) + \beta \mathbbm{1}_{(\beta,\infty)}(x)$. For a real valued sequence $a \defeq (a_i)_{i=1}^{n}$, define the sequence $a^{*} = (a^{*}_{i})_{i=1}^{n}$ by $a^{*}_i \defeq a_{\pi(i)}$ where $\pi$ is a permutation that orders $a$ increasingly.

Fix $k \in \brace*{1, \dotsc, \floor{n/2}}$, and define $\varphi_{k}[a] \defeq \sum_{i=1}^{n} \phi_{a^{*}_{1+ k}, a^{*}_{n-k}}(a_i)$. Given samples $(X_i, Y_i)_{i=1}^{n}$, and for $w, v \in \R^{d}$, define

\begin{gather*}
\psi_{k}(w, v) \defeq n^{-1} \varphi_{k}\brack*{\paren*{e(\inp{w}{X_i} - Y_i) - e(\inp{v}{X_i} - Y_i)}_{i=1}^{n}},
\end{gather*}

and consider the procedure

\begin{equation}
\label{eq:procedure}
\hat{w}_{n, k}((X_i, Y_i)_{i=1}^{n}) \in \argmin_{w \in \R^{d}} \max_{v \in \R^{d}} \psi_{k}(w, v).
\end{equation}

§.§ Square error

Our first result shows that for the square error, and under appropriate conditions, the procedure (<ref>) is minimax up to absolute constants over $\mathcal{P}_{2}(P_{X}, \sigma^2)$ when $P_{X}$ has finite fourth moments.

Under the square error $e(t) = t^2/2$, let $\delta \in (0,1/4)$ be such that $k \defeq 8 \log(4/\delta)$ is an integer satisfying $1 \leq k \leq \floor{n/8}$. Assume that $P_{X}$ has finite fourth moments. If

\begin{equation*}
n \geq 800^{2} \cdot \paren*{8 \log(6d) \cdot \brack*{\lambdamax(S(P_{X})) + 1} + \brack*{R(P_{X}) + 1} \log(1/\delta)},
\end{equation*}

where $S(P_{X})$ and $R(P_{X})$ are as defined in (<ref>), then

\begin{equation*}
R_{n,\delta}(\mathcal{P}_{2}(P_{X}, \sigma^2), \hat{w}_{n,k}) \leq (100)^{2} \cdot \frac{\sigma^2 (d + \log(1/\delta))}{n}.
\end{equation*}

Compared to Proposition <ref>, the upper bound in Theorem <ref> contains no distribution-dependence, showing the minimaxity of the procedure $(\ref{eq:procedure})$ up to an absolute constant by Proposition <ref>. On the other hand, we require the existence of fourth moments, which is more than what is required in Proposition <ref>. As we argue in Section <ref> however, the fourth moment assumption is quite natural. We also note that the sample size restriction in Theorem <ref> nearly matches that in Corollary <ref>, which as we discuss in Section <ref> is optimal in a certain sense.

We claim however assuming the existence of fourth moments of $P_{X}$ is in some sense the most natural setting to consider.
Indeed, the difference between these two

However, recall the fact that $\widetilde{\Sigma}_{n}$ is an empirical average of the random matrices $\tilde{X}\tilde{X}^{T}$ where $\tilde{X} \defeq \Sigma^{-1/2}X$ and $X \sim P_{X}$. Therefore, by the law of large numbers, $\Sigma_{n} \overset{d}{\to} I_{d \times d}$, and by the continuous mapping theorem, $\lambdamax(\widetilde{\Sigma}_{n}^{-1}) \overset{d}{\to} 1$ as $n \to \infty$. To say something about the rate of this convergence, the most natural assumption to make is that the second moment of the random matrix $\tilde{X}\tilde{X}^{T}$ exists so that the central limit theorem holds, which is equivalent to assuming that $P_{X}$ has fourth moments. Under this assumption, our results in Section <ref> provide a full characterization of $Q_{\lambdamax(\widetilde{\Sigma}_{n}^{-1})}(1 - \delta)$. Building on these results, we obtain the following sufficient joint conditions on $(P_{X}, n, \delta)$ that guarantee that the lower bound of Proposition <ref> is tight.

§.§ p-th power error

We now move to the case $p \in (2, \infty)$. The first difficulty we are faced with here is that it is a priori unclear what set of problems we should select that is both tractable and large enough to model realistic scenarios. Using our insights from Section <ref>, we propose the following analogue to the class $\mathcal{P}_{2}(P_{X}, \sigma^2)$, under the necessary conditions that $P_{X}$ and the noise $\xi$ have finite $p$-th moments

\begin{equation*}
\mathcal{P}_{p}(P_{X}, \sigma^2, \mu) \defeq \brace*{P \st (X, Y) \sim P : X \sim P_{X} \text{ and  (\ref{eq:condition}) holds.} },
\end{equation*}

where $\mu \in (0, m(p) \cdot \sigma^{p-2}]$, $m(p)$ is as in Proposition <ref>, and (<ref>) is the condition

\begin{equation}
\label{eq:condition}
\frac{\esssup(\Exp\brack{\abs{\xi}^{2(p-1)} \mid X})}{\essinf(\Exp\brack*{\abs{\xi}^{p-2} \mid X})} \leq \frac{m(2p-2)}{m(p-2)} \cdot \sigma^{p} \eqdef r(p) \quad \text{ and } \quad  \essinf(\Exp\brack{\abs{\xi}^{p-2} \mid X}) \geq \mu \tag{$\star$},
\end{equation}

where $\xi \defeq Y-\inp{w^{*}}{X}$ and $w^{*} \in \R^{d}$ is the unique minimizer of the expected error $E(w)$.
It is straightforward to check that $\mathcal{P}_{\normalfont \text{Gauss}}(P_{X}, \sigma^{2}) \subset \mathcal{P}_{p}(P_{X}, \sigma^2, \mu)$, for all legal choices of $\mu$.

While at first this seems like an overly special class of distributions, let us now argue that this far from the case. In fact, we claim that this class is a natural extension of $\mathcal{P}_{2}(P_{X}, \sigma^2)$. Firstly, by setting $p=2$, we recover $\mathcal{P}_{2}(P_{X}, \sigma^2, \mu) = \mathcal{P}_{2}(P_{X}, \sigma^2)$ for all legal $\mu$. Secondly, we note that $\mathcal{P}_{p}(P_{X}, \sigma^2, \mu) \subset \mathcal{P}_{p}(P_{X}, \sigma^2, \mu')$ whenever $\mu \geq \mu'$. Ideally, we would like to take as large a class as possible, which would correspond to the choice $\mu=0$. Unfortunately, our bounds diverge in this setting. On the positive side however, this means that the upper constraint on $\mu$ is benign as the interesting regime is when $\mu$ is near zero. Finally, note that much like with the set $\mathcal{P}_{2}(P_{X}, \sigma^2)$, one can capture a large set of problems by varying $\sigma^{2}$. As an example, for any linear regression problem where the noise $\xi$ is non-zero, symmetric, and independent of $X$, there exists $(\sigma^{2}, \mu)$ such that $\mathcal{P}_{p}(P_{X}, \sigma^2, \mu)$ contains this problem.

Remarkably, we show that the procedure (<ref>) is minimax over this class under mild assumptions.

Under the $p$-th power error $e(t) = \abs{t}^{p}/[p(p-1)]$ for $p \in (2, \infty)$, let $\delta \in (0,1)$ be such that $k \defeq 8 \log(4/\delta)$ is an integer satisfying $1 \leq k \leq \floor{n/8}$. Assume that $P_{X}$ has finite fourth moments. If

\begin{multline*}
n \geq r^{\frac{p-2}{p-1}}(p) \mu^{-\frac{p}{p-1}} \cdot \brack*{8\log(6d)(\lambdamax(S(P_{X}))+1)+(R(P_{X})+1)\log(1/\delta)} \\ + (2400)^{2} \cdot r(p) \mu^{-\frac{p}{p-2}} p^{4} N^{\frac{2p}{p-2}}(P_{X}, p) \cdot [d + \log(4/\delta)]
\end{multline*}

Define $a(p) \defeq \paren*{\frac{m(2p-2)\sigma^{p}}{m(p-2)}}^{\frac{p-2}{p-1}} \mu^{-\frac{p}{p-1}}$. If

\begin{equation*}
n \geq a(p) \cdot \brack*{\paren*{8\log(6d) [\lambdamax(S(P_{X})) + 1] + [R(P_{X}) + 1] \log(1/\delta)} + (d + \log(1/\delta)) p^{4} N(P_{X}, p)^{\frac{2p}{p-2}}}
\end{equation*}

where $r(p)$ and $\mu$ are as in (<ref>), $S(P_{X})$ and $R(P_{X})$ are as in (<ref>), and $N(P_{X}, p)$ is the norm equivalence constant between the $L^{p}$ and $L^{2}$ norms induced by $P_{X}$ on the set of linear functions on $\R^{d}$, given by $N(P_{X}, p) = \sup_{w \in \R^{d}\setminus \brace{0}} \Exp\brack*{\abs{\inp{w}{X}}^{p}}^{1/p}/\Exp\brack*{\inp{w}{X}^{2}}^{1/2}$, then

\begin{equation*}
R_{n,\delta}(\mathcal{P}_{p}(P_{X}, \sigma^2, \mu), \hat{w}_{n,k}) \leq 120^{2} \cdot K(p) \cdot \frac{\sigma^{p}[d + \log(1/\delta)]}{n},
\end{equation*}

where $K(p) \defeq (p-1)^{2} \cdot m(2p-2)/m(p-2)$.

Combining this result with Proposition <ref> shows the minimaxity of the procedure (<ref>) on this class of problems, up to a constant that depends only on $p$. The closest related result is due to El Hanchi and Erdogdu, 2023 who studied the performance of ERM on linear regression under $p$-th power error. Their result however is specific to ERM, and, as expected, only yields a polynomial dependence on $1/\delta$ instead of the needed $\log(1/\delta)$ to establish minimaxity. Our result combines the insights of that work with the proof techniques used to study the procedure (<ref>) developed by Lugosi and Mendelson, 2019, as well as our new insights on how to leverage the fourth moment assumption to obtain absolute constants instead of distribution-dependent constants in the upper bound.

\begin{equation*}
\sup_{P \in \mathcal{P}_{\text{well}}(P_{X}, \sigma^{2})}R_{\eps_{n} + \delta, n}(P, \hat{w}_{k}) \leq C \cdot \frac{\sigma^2}{n}\paren*{Q_{\Tr\paren*{\widetilde{\Sigma}^{-1}}}(1 - \eps_n - \delta/4) + \log(1/\delta) Q_{W}(1 - \eps_n - \delta/4)}
\end{equation*}

where $C_{2} \defeq $, and where we defined $\Tr(\widetilde{\Sigma}^{-1}) \defeq \infty$ when $\widetilde{\Sigma}$ is not invertible, and $W$ is a random variable with conditional distribution $W \mid (X_i)_{i=1}^{n} \sim \text{Exponential}(1/\lambdamax(\widetilde{\Sigma}^{-1}))$ where we defined $\lambdamax(\widetilde{\Sigma}^{-1}) \defeq \infty$ when $\widetilde{\Sigma}$ is not invertible, and the distribution $\text{Exponential}(0)$ is defined as the unit mass at $\infty$.

show that, under a mild deviation from the conditions of Corollary <ref> on $(P_{X}, n, \delta)$, a slighght variant of the estimators, itself based on the ideas of , is minimax under the square error over the minmax estimators introduced by Audibert and Catoni, 2011, Lugosi and Mendelson, 2019, Lecué and Lerasle, 2020, Oliveira and Resende, 2023 are minimax under the square error $e(t) = t^{2}/2$ over the class $\mathcal{P}_{well}(P_{X}, \sigma^2)$. Before stating our result, we briefly recall the construction of the estimator.

\begin{equation*}
\widetilde{S}(P_{X}) \defeq \Exp\brack*{\norm{\tilde{X}}_2^2 \tilde{X}\tilde{X}^{T}}, \quad\quad \widetilde{R}(P_{X}) \defeq \sup_{v \in S^{d-1}} \Exp\brack*{\inp{v}{\tilde{X}}^{4}}.
\end{equation*}

§ THE QUANTILE RISK

In this section, we study the quantile risk in full generality. Our motivation for doing so is to provide the tools necessary for proving Theorem <ref>. The results we obtain are however more general and can be used to tackle other problems. We illustrate this with two examples at the end of the section.

Before we formulate our results, let us briefly introduce some basic decision-theoretic concepts. To avoid overloading the notation, the symbols we introduce here will be specific to this section. A decision problem has the following components: a set of possible observations $\mathcal{O}$, a subset $\mathcal{P}$ of probability measures on $\mathcal{O}$, a set of available actions $\mathcal{A}$, a loss function $\ell: \mathcal{P} \times \mathcal{A} \to \R$, and a decision rule $d: \mathcal{O} \to \mathcal{A}$. For a fixed distribution $P$, the performance of a decision rule is classically evaluated through its expected loss $\Exp\brack*{\ell(P, d(O))}$ where $O \sim P$. Here instead, for a user-chosen failure probability $\delta \in (0, 1)$, we evaluate the performance of a decision rule through its quantile risk $R_{\delta}(\ell, P, d) \defeq Q_{\ell(P, d(O))}(1 - \delta)$. We define the associated worst-case and minimax risks by $R_{\delta}(\ell, d) \defeq \sup_{P \in \mathcal{P}} R_{\delta}(\ell, P, d)$ and $R^{*}_{\delta}(\ell) \defeq \inf_{d} R_{\delta}(\ell, d)$ respectively. Our aim is to develop methods to understand the minimax risk and establish the minimaxity of candidate decision rules.

§.§ A Bayesian criterion for minimaxity and an invariance principle

A classical way to establish the minimaxity of a decision rule is by computing its worst-case risk and showing that it matches the limit of a sequence of Bayes risks [Lehmann and Casella, 2006]. The following result provides an analogue to this method when working under the quantile risk.

For a distribution $\pi$ on $\mathcal{P}$, define $F^{\pi}_{\ell(P, d(O))}$ to be the cumulative distribution function of the random variable $\ell(P, d(O))$, where $P \sim \pi$ and $O \mid P \sim P$.
Let $(\pi_{k})_{k \in \N}$ be a sequence of distributions on $\mathcal{P}$. For any $t \in \R$, define

\begin{equation*}
p_{\ell, k}(t) \defeq \sup_{d} F^{\pi_{k}}_{\ell(P, d(O))}(t).
\end{equation*}

Assume that the functions $(p_{\ell, k})_{k \in \R}$ are right-continuous and that the sequence is decreasing, i.e. $p_{\ell, k} \geq p_{\ell, k+1}$ and let $p_{\ell} \defeq \inf_{k \in N} p_{\ell, k} = \lim_{k \to \infty} p_{\ell, k}$. If $\hat{d}$ is a decision satisfying

\begin{equation*}
\sup_{P \in \mathcal{P}} R_{\delta}(\ell, P, \hat{d}) = p_{\ell}^{-}(1-\delta),
\end{equation*}

where $p^{-}_{\ell}$ is the pseudo-inverse of $p_{\ell}$, then $\hat{d} \in \argmin_{d} R_{\delta}(\ell, d)$, i.e. it is minimax.

We mention that instantiations of the arguments leading to Theorem <ref> have been used by Depersin and Lecué, 2022 and Gupta et al., 2023 to tackle specific problems. The general form we present here is new, and relies on new analytical results concerning collections of quantile functions.

In applications, it is desirable that the optimality of a decision rule depends as little as possible on the loss function, or conversely, that a single decision rule be minimax for as large a number of loss functions as possible. The following result shows that the minimaxity of a decision rule in the quantile risk is invariant to at least one form of transformation of the loss function.

Let $\varphi: \R \to \R$ be a strictly increasing left-continuous function, and define $\varphi(\infty) \defeq \infty$ and $\varphi(-\infty) \defeq -\infty$. Then $R_{\delta}(\varphi \circ \ell, P, d) = \varphi\paren*{R_{\delta}(\ell, P, d)}$. Furthermore, if $R_{\delta}(\ell, d) < \infty$, then $R_{\delta}(\varphi \circ \ell, d) = \varphi(R_{\delta}(\ell, d))$. Finally, if $R^{*}_{\delta}(\ell) < \infty$, then

\begin{equation*}
d^{*} \in \argmin_{d} R_{\delta}(\ell, d) \implies d^{*} \in \argmin_{d} R_{\delta}(\varphi \circ \ell, d).
\end{equation*}

§.§ Mean estimation revisited

To exhibit the usefulness of the above results, we briefly revisit the problem of mean estimation under Gaussian data. This problem can be embedded in the above decision-theoretic setting as follows. The observations are random vectors $(X_i)_{i=1}^{n} \in (\R^{d})^{n}$ for some $d, n \in \N$, the subset of distributions is the $n$-product of distributions in the class $\mathcal{P}_{\normalfont\text{Gauss}}(\Sigma) \defeq \brace*{\mathcal{N}(\mu, \Sigma) \st \mu \in \R^{d}}$, for a fixed $\Sigma \in S_{++}^{d}$. The set of available actions is $\R^{d}$, and the loss function is given by $\ell(P^{n}, \mu) \defeq e(\mu - \mu(P))$ for some error function $e$ and where $\mu(P)$ is the mean of the distribution $P$. Finally, a decision rule is given by an estimator $\hat{\mu}: (\R^{d})^{n} \to \R^{d}$. The following result gives the minimax quantile risk for this problem under a mild assumption on the error function $e$, generalizing the recent result of [Depersin and Lecué, 2022] which holds under stronger assumptions on $e$.

Assume that the error function $e$ satisfies $e = \varphi \circ s$, where $\varphi$ is a left-continuous strictly increasing function, and $s$ is both quasiconvex, i.e. $s(tv + (1-t)u) \leq \max\brace*{s(v), s(u)}$ for all $t \in [0,1]$ and $u,v \in \R^{d}$, and symmetric, i.e. $s(v) = s(-v)$. Then for all $\Sigma \in S_{++}^{d}$

\begin{equation*}
\inf_{\hat{\mu}}\sup_{P \in \mathcal{P}_{\normalfont\text{Gauss}}(\Sigma)} R_{\delta}(\ell, P^{n}, \hat{\mu}) = Q_{e(Z)}(1- \delta),
\end{equation*}

where $Z \sim \mathcal{N}(0, \Sigma/n)$. Furthermore, the sample mean $\hat{\mu}((X_i)_{i=1}^{n})\defeq n^{-1}\sum_{i=1}^{n}X_i$ is minimax.

Suppose $\delta \in (0, 0.1]$, and $\ell(v) = \norm{v}$ for an arbitrary norm $\norm{\cdot}$. Let $S$ denote the unit sphere of the dual norm, and let $R \defeq \sup_{v \in S} v^{T} \Sigma v$. Then

\begin{equation*}
\inf_{\hat{\mu}}\sup_{P \in \mathcal{P}_{\normalfont\text{Gauss}}(\Sigma)} R_{n, \delta}(P, \hat{\mu}) \asymp \frac{\Exp\brack*{\norm{Z}}}{\sqrt{n}} + \sqrt{\frac{R \log(1/\delta)}{n}}.
\end{equation*}

Furthermore, if $\norm{v}$ is induced by an inner product $\inp{v}{u} = v^{T} A u$, then, with $\widetilde{\Sigma} \defeq A^{1/2} \Sigma A^{1/2}$,

\begin{equation*}
\inf_{\hat{\mu}}\sup_{P \in \mathcal{P}_{\normalfont\text{Gauss}}(\Sigma)} R_{n, \delta}(P, \hat{\mu}) \asymp \sqrt{\frac{\Tr({\widetilde{\Sigma}})}{n}} + \sqrt{\frac{\lambda_{\text{max}}(\widetilde{\Sigma}) \log(1/\delta)}{n}}.
\end{equation*}

In the special case where $d=1$, $\Sigma = \sigma^2$, and $\ell(t) = \abs{t}$, we have

\begin{equation*}
\inf_{\hat{\mu}}\sup_{P \in \mathcal{P}_{\normalfont\text{Gauss}}(\Sigma)} R_{n, \delta}(P, \hat{\mu}) \asymp \sqrt{\frac{\sigma^2 \log\paren*{1/\delta}}{n}}
\end{equation*}

The constraint $\delta \in (0, 0.1]$ is only assumed in Corollary <ref> to ease the exposition. Upper and lower bounds that hold for all $\delta \in (0, 1)$, from which the statements in Corollary <ref> are deduced, are available in the Appendix.

§.§ Minimax estimation of the variance of a Gaussian with known mean

As a second application of our results, we consider the problem of variance estimation with one-dimensional Gaussian data. For this problem, the observations are random variables $(X_i)_{i=1}^{n} \in \R^{n}$ for some $n \in \N$, the subset of distributions is the $n$-product of distributions in the class $\mathcal{P}_{\normalfont\text{Gauss}}(\mu) \defeq \brace*{\mathcal{N}(\mu, \sigma^{2}) \st \sigma \in (0, \infty)}$,
for a fixed $\mu$. The set of available actions is $(0, \infty)$, and we consider the following loss function which captures the problem of estimating $\sigma^{2}$ in relative error: $\ell(P^{n}, \sigma^{2}) \defeq \abs*{\log(\sigma^2(P)/\sigma^2)}$ where $\sigma^{2}(P)$ is the variance of the distribution $P$. Finally, a decision rule is given by an estimator $\hat{\sigma}^{2}: \R^{n} \to (0, \infty)$. Using Theorem <ref>, we obtain the following result.

For $\alpha \in (0, \infty)$ and $Z \sim {\normalfont\text{Inv-Gamma}}(\alpha, \alpha)$, define $p_{\alpha}:(0,\infty) \to [0,1)$ by

\begin{equation*}
p_{\alpha}(t) \defeq \Prob\paren*{\frac{1-\exp(-2t)}{2t} \leq Z \leq \frac{\exp(2t) - 1}{2t}}.
\end{equation*}

Then for all $\mu \in \R$

\begin{equation*}
\inf_{\hat{\sigma}^{2}} \sup_{P \in \mathcal{P}_{\normalfont\text{Gauss}}(\mu)} R_{\delta}(\ell, P^{n}, \hat{\sigma}^{2}) = p_{n/2}^{-}(1-\delta).
\end{equation*}

Furthermore, the sample variance is not minimax and the estimator

\begin{equation*}
\hat{\sigma}^{2}((X_i)_{i=1}^{n}) \defeq \frac{\sum_{i=1}^{n}(X_i - \mu)^{2}}{n} \phi\paren*{p_{n/2}^{-}(1-\delta)}
\end{equation*}

is minimax, where $\phi(x) \defeq \sinh(x)/x$, and $p_{n/2}^{-}$ is the pseudo-inverse of $p_{n/2}$.

Surprisingly, Proposition <ref> shows that the sample variance is suboptimal under the quantile risk, but that a careful reweighting of it is. We note that as $n \to \infty$, the weight converges to $1$, so that the sample variance is asymptotically minimax. We are not aware of a similar result in the literature.

§ SMALLEST EIGENVALUE OF THE SAMPLE COVARIANCE MATRIX

The results of Sections <ref> and <ref>, and in particular the sample size conditions in Corollary <ref> and Theorems <ref> and <ref>, rely on new high probability lower bounds on the smallest eigenvalue of the sample covariance matrix we describe in this section. We briefly formalize our problem, we then state our main results, and conclude this section by discussing and relating them to the literature.

Let $P_{X}$ be a distribution on $\R^{d}$ with finite second moments, $X \sim P_{X}$, and denote by $\Sigma \defeq \Exp\brack*{XX^{T}}$ its covariance matrix. For samples $(X_i)_{i=1}^{n} \sim P_{X}^{n}$, define the sample covariance matrix $\widehat{\Sigma}_{n} \defeq  n^{-1} \sum_{i=1}^{n} X_{i}X_{i}^{T}$. In this section, we want to identify how close $\widehat{\Sigma}_{n}$ is to $\Sigma$ in a relative error sense and in a one-sided fashion. Specifically, we want to characterize the quantiles of the random variable $\lambdamax(I -\Sigma^{-1/2}\widehat{\Sigma}_{n}\Sigma^{-1/2}) = 1 - \lambdamin(\Sigma^{-1/2}\widehat{\Sigma}_{n}\Sigma^{-1/2})$. To ease notation, we introduce the whitened random vector $\widetilde{X} \defeq \Sigma^{-1/2} X$. Notice that $\Exp\brack{\widetilde{X}\widetilde{X}^{T}} = I_{d \times d}$, and that $\widetilde{\Sigma}_{n} \defeq n^{-1}\sum_{i=1}^{n} \widetilde{X}_{i}\widetilde{X}_{i}^{T} = \Sigma^{-1/2}\widehat{\Sigma}_{n}\Sigma^{-1/2}$. We want to understand the quantiles of $1 - \lambdamin(\widetilde{\Sigma}_{n})$.

As already mentioned, our motivation for studying this problem stems from the fact that upper bounds on these quantiles form a crucial step in the analysis of linear regression in general, e.g. Oliveira, 2016, Mourtada, 2022, and in particular our results from Section <ref> and <ref>.

We are now ready to state our results. Define the following variance-like parameters

\begin{equation}
\label{eq:matrix_param}
S(P_{X}) \defeq \Exp\brack*{\paren*{\widetilde{X}\widetilde{X}^{T} - I}^{2}}, \quad\quad R(P_{X}) \defeq \sup_{v \in S^{d-1}} \Exp\brack*{\paren*{\inp{v}{\widetilde{X}}^{2} - 1}^2}.
\end{equation}

Our first result is the following proposition, which provides an asymptotic lower bound on the quantiles of $1 - \lambdamin(\widetilde{\Sigma}_{n})$, and a nearly matching non-asymptotic upper bound.

Assume that $P_{X}$ has finite fourth moments. Then for all $\delta \in (0, 0.1)$,

\begin{equation*}
\lim_{n \to \infty} \sqrt{n} \cdot Q_{1 - \lambdamin(\widetilde{\Sigma}_{n})}(1 - \delta) \geq \frac{1}{40} \cdot \paren*{\sqrt{\lambdamax(S(P_{X}))} + \sqrt{R(P_{X}) \log(1/\delta)}}.
\end{equation*}

Furthermore, for all $n \in \N$ and $\delta \in (0, 1)$,

\begin{equation*}
Q_{1 - \lambdamin(\widetilde{\Sigma}_{n})}(1-\delta) \leq \sqrt{\frac{8\lambdamax(S(P_{X}))\log(3d)}{n}} + \sqrt{\frac{2R(P_{X}) \log(1/\delta)}{n}} + \frac{(2\log(3d) + 4 \log(1/\delta))}{3n}.
\end{equation*}

Our second result extends the upper bound in Proposition <ref> to the case where $\lambdamin(\widetilde{\Sigma}_{n}) = \inf_{v \in S^{d-1}} n^{-1} \sum_{i=1}^{n} \inp{v}{\widetilde{X}_i}^{2}$ is subject to a direction dependent adversarial truncation. This result is needed in our analyses of Section <ref>, from which we recall the definition of $a^{*}$ for a sequence $a$.

Let $\delta \in (0, 1/2)$ such that $k = 8\log(2/\delta)$ is an integer satisfying $1 \leq k \leq \floor{n/2}$. For $(v, i) \in S^{d-1} \times [n]$, define $Y_{i, v} \defeq \inp{v}{\widetilde{X}_i}^{2}$ and $\overline{\lambda}_{\normalfont\text{min}}(\widetilde{\Sigma}_{n}) \defeq \inf_{v \in S^{d-1}} n^{-1}\sum_{i=k+1}^{n-k} Y_{i, v}^{*}$. Then, if $n \geq 8\log(6d)$,

\begin{equation*}
Q_{(1-2k/n) - \overline{\lambda}_{\normalfont\text{min}}(\widetilde{\Sigma}_{n})}(1 - \delta) \leq 100 \paren*{\sqrt{\frac{8\log(6d)(\lambdamax(S(P_{X})) + 1)}{n}} + \sqrt{\frac{(R(P_{X}) + 1) \log(1/\delta)}{n}}}.
\end{equation*}

Comparison with existing results. To the best of our knowledge, the only known lower bound, asymptotic or not, on the quantiles of $1-\lambdamin(\widetilde{\Sigma}_{n})$ is due to <cit.>. This bound however is distribution-free and decays fast, as $\log(1/\delta)/n$. In terms of upper bounds comparable to that of Proposition <ref>, the closest result we are aware of is due to Oliveira, 2016 (see also Zhivotovskiy, 2024), who proved $\sqrt{n} Q_{1 - {\lambda}_{\text{min}}(\widetilde{\Sigma}_{n})}(1 - \delta) \lesssim \sqrt{(R(P_{X})+1)\brack*{d + \log(1/\delta)}}$. In general, our upper bound and theirs are not comparable, and when combined they yield the best of both. Nevertheless, we suspect that our bound is better on heavy-tailed problems. Indeed, by Jensen's inequality, it is not hard to see that $\lambdamax(S(P_{X})) \leq R(P_{X}) \cdot d$, so our upper bound from Proposition <ref> can be at most worse by $\sqrt{\log(d)}$. This occurs when $X$ is a centred Gaussian, for which it is known that Oliveira's bound is tight [Koltchinskii and Lounici, 2017]. On the other hand, consider $X$ with centred independent coordinates, and where the first coordinate has kurtosis $\kappa \gg 1$, while the other coordinates have constant kurtosis. Then Oliveira's bound scales as $\sqrt{\kappa \cdot d}$, while ours scales as $\sqrt{\kappa \cdot \log(d)}$. Finally, versions of Proposition <ref> that mimic Oliveira's bound can be deduced from the recent literature [Abdalla and Zhivotovskiy, 2023, Oliveira and Rico, 2022]. The same considerations apply when comparing these results.

On the fourth moment assumption.
We carried out our analysis under a fourth moment assumption on $P_{X}$. We argue here that this is in some sense the most natural assumption to study this problem. Indeed, recall the fact that $\widetilde{\Sigma}_{n}$ is an empirical average of the random matrix $\widetilde{X}\widetilde{X}^{T}$. Therefore, by the law of large numbers, $\widetilde{\Sigma}_{n} \overset{d}{\to} I_{d \times d}$, and by the continuous mapping theorem, $\lambdamin(\widetilde{\Sigma}_{n}) \overset{d}{\to} 1$ as $n \to \infty$. To say something about the rate of this convergence, the most natural assumption to make is that the entries of the random matrix $XX^{T}$ have finite variance so that the CLT holds. This is equivalent to assuming that $P_{X}$ has fourth moments.

On the critical sample size. Our main application of Propositions <ref> and <ref> is in providing upper bounds on the critical sample size $n^{*}(P_{X}, \delta) \defeq \min\brace*{n \in \N \st Q_{1 - \lambdamin(\widetilde{\Sigma}_{n})}(1-\delta/2) \leq 1/4}$. In particular, these upper bounds correspond to the sample size restrictions in Corollary <ref> and Theorems <ref> and <ref>. We claimed after the statement of these results that these restrictions were in some sense optimal; we expand on this here. Let $L \defeq \lim_{n \to \infty} \sqrt{n} \cdot Q_{1 - \lambdamin(\widetilde{\Sigma}_{n})}(1 - \delta)$, and define $n_{0}(P_{X}, \delta) \defeq \min\brace*{n \in \N \st m \geq n \Rightarrow Q_{1 - \lambdamin(\widetilde{\Sigma}_{m})}(1 - \delta/2) \geq \frac{L}{4\sqrt{m}}}$. If $n_{0}(P_{X}, \delta) \leq n^{*}(P_{X}, \delta)$, then we can reverse the above-mentioned upper bounds using the first item of Proposition <ref>, up to a $\sqrt{\log(d)}$ factor.
In words, if the critical sample size is determined by the asymptotic behaviour of the $1-\delta/2$ quantile of $1-\lambdamin(\widetilde{\Sigma}_{n})$, then our bounds on the critical sample size are tight. When the hypothesis in this last statement is true remains unclear however. The choice of the constant $1/4$ in the above argument is arbitrary, and can be replaced with any absolute constant.

Characterizing the quantiles of $\lambdamax(\Sigma - \Sigma_{n})$ requires deriving matching upper and lower bounds on it. To the best of our knowledge, upper bounds are

This problem is has been studied intensely over the last decade, starting.

We define two variance-like parameters

\begin{equation*}
S(P_{X}) \defeq \Exp\brack*{\paren*{XX^{T} - \Sigma}^{2}}, \quad\quad R(P_{X}) \defeq \sup_{v \in S^{d-1}} \Exp\brack*{\paren*{\inp{v}{X}^{2} - \Exp\brack*{\inp{v}{X}}^{2}}^2}.
\end{equation*}

Our first result is a lower bound on the asymptotic quantiles of $\lambdamax(\Sigma - \widehat{\Sigma}_{n})$.

Assume that $\Exp\brack*{\abs{X^{j}}^{4}} < \infty$ for all $j \in [d]$. Let $Y_{n} \defeq \lambdamax(\Sigma - \widehat{\Sigma}_{n})$. Let $\delta \in (0, 0.1)$. Then

\begin{equation*}
\lim_{n \to \infty} \sqrt{n} \cdot Q_{Y_{n}}(1 - \delta) \geq C \cdot \paren*{\sqrt{\lambdamax(S)} + \sqrt{R \log(1/2\delta)}}
\end{equation*}

where $C \defeq$.

Let $(X_i)_{i=1}^{n}$ be random vectors of dimension $d \geq 2$ with $\Exp\brack{XX^{T}} = \Sigma$. Assume that $\Exp\brack*{\abs{X^{j}}^{4}} < \infty$ for all $j \in [d]$. Let $\widehat{\Sigma}_{n} \defeq n^{-1}\sum_{i=1}^{n} X_{i}X_{i}^{T}$ be the sample covariance matrix. Then with probability at least $1 - \delta$

\begin{equation*}
\lambdamax(\Sigma - \hat{\Sigma}) \leq \sqrt{\frac{8\lambdamax(S)\log(d)}{n}} + \sqrt{\frac{2R \log(1/\delta)}{n}} + \frac{\lambdamax(\Sigma) (2\log(d) + 4 \log(1/\delta))}{3n}
\end{equation*}

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

\begin{equation*}
n \geq 4(1 + 2 \ceil{\log(d)}),
\end{equation*}

then with probability at least $1-\delta$

\begin{equation*}
\sup_{v \in S^{d-1}} \sum_{i=k+1}^{n-k} \Exp\brack*{\inp{v}{X}^{2}} - Y_{i, v}^{*} \leq C \cdot \paren*{\sqrt{4(1 + 2\ceil{\log(d)}) n \lambdamax(\tilde{S})} + \sqrt{n \tilde{R} \log(2/\delta)}}
%165 \sqrt{n(1 + 2\ceil{\log(d)}) \lambdamax(\tilde{S})} + 132 \sqrt{n \tilde{R} \log(2/\delta)}.
\end{equation*}

for some universal constant $C$.

Assume that $P_{X}$ has fourth moments, i.e. $\Exp\brack{\norm{X}_{4}^{4}} < \infty$ for $X \sim P_{X}$. Define

\begin{equation*}
S(P_{X}) \defeq \Exp\brack*{\paren*{\tilde{X}\tilde{X}^{T} - I}^{2}}, \quad\quad R(P_{X}) \defeq \sup_{v \in S^{d-1}} \Exp\brack*{\paren*{\inp{v}{\tilde{X}}^{2} - 1}^2}.
\end{equation*}

Let $\delta \in (0, 1)$. If

\begin{equation*}
n \geq \max\brace*{64 \lambdamax(S(P_{X})) (1 + \log(d)), 128 R(P_{X}) \log(1/\delta), \frac{4(1 + \log(d) + 4\log(1/\delta))}{3}}
\end{equation*}

\begin{equation*}
Q_{\lambdamax(\widetilde{\Sigma}_{n}^{-1})}(1 - \delta) \leq 1 + 2\paren*{\sqrt{\frac{8\lambdamax(S)[1+\log(d)]}{n}} + \sqrt{\frac{2R \log(1/\delta)}{n}} + \frac{1 + \log(d) + 4 \log(1/\delta)}{3n}}
\end{equation*}

When do the lower and upper bounds match ? Mention that if $X^1 = 1$, then $\lambdamax(S) \geq d-1$, so it is large enough. Need to also write down the corollary for relative error (i.e. when covariance is identity). Need to compare to previous results (Oliveira's result, Mourtada's result, small-ball results).

§ CONCLUSION

In this paper, we studied minimax linear regression under the quantile risk. We gave an in-depth characterization of the minimax risk over the Gaussian class $\mathcal{P}_{\normalfont\text{Gauss}}(P_{X}, \sigma^2)$, and leveraged these results to establish the minimaxity, up to absolute constants, of the min-max regression procedure for $p$-norm regression problems. While the problem of estimation with high confidence has been studied intensely recently, we are not aware of its formalization through quantiles as was done in this paper. We hope this new perspective proves fruitful in advancing both our understanding of learning problems and our ability to design efficient solutions for them.

Resources used in preparing this research were provided in part by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute. CM acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), RGPIN-2021-03445. MAE was partially supported by NSERC Grant [2019-06167], CIFAR AI Chairs program, and CIFAR AI Catalyst grant.

[Abdalla and Zhivotovskiy, 2023]
Pedro Abdalla and Nikita Zhivotovskiy.
Covariance Estimation: Optimal Dimension-free Guarantees for Adversarial Corruption and Heavy Tails, July 2023.

[Adil et al., 2023]
Deeksha Adil, Rasmus Kyng, Richard Peng, and Sushant Sachdeva.
Fast Algorithms for $\ell_{p}$-Regression, October 2023.

[Audibert and Catoni, 2011]
Jean-Yves Audibert and Olivier Catoni.
Robust Linear Least Squares Regression.
The Annals of Statistics, 2011.

[Bousquet, 2002]
Olivier Bousquet.
A Bennett concentration inequality and its application to suprema of empirical processes.
Comptes Rendus Mathematique, January 2002.

[Catoni, 2012]
Olivier Catoni.
Challenging the empirical mean and empirical variance: A deviation study.
Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, November 2012.

[Catoni, 2016]
Olivier Catoni.
Pac-bayesian bounds for the gram matrix and least squares regression with a random design.
arXiv preprint arXiv:1603.05229, 2016.

[Chinot et al., 2020]
Geoffrey Chinot, Guillaume Lecué, and Matthieu Lerasle.
Robust statistical learning with Lipschitz and convex loss functions.
Probability Theory and Related Fields, April 2020.

[Depersin and Lecué, 2022]
Jules Depersin and Guillaume Lecué.
Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms.
Probability Theory and Related Fields, August 2022.

[Devroye et al., 2016]
Luc Devroye, Matthieu Lerasle, Gabor Lugosi, and Roberto I. Oliveira.
Sub-Gaussian mean estimators.
The Annals of Statistics, December 2016.

[El Hanchi and Erdogdu, 2023]
Ayoub El Hanchi and Murat A. Erdogdu.
Optimal Excess Risk Bounds for Empirical Risk Minimization on $p$-Norm Linear Regression.
In Thirty-Seventh Conference on Neural Information Processing Systems, November 2023.

[Gupta et al., 2023]
Shivam Gupta, Jasper C. H. Lee, Eric Price, and Paul Valiant.
Minimax-Optimal Location Estimation.
In Thirty-Seventh Conference on Neural Information Processing Systems, November 2023.

[Hsu and Sabato, 2016]
Daniel Hsu and Sivan Sabato.
Loss Minimization and Parameter Estimation with Heavy Tails.
Journal of Machine Learning Research, 2016.

[Keener, 2010]
Robert W Keener.
Theoretical statistics: Topics for a core course.
Springer Science & Business Media, 2010.

[Klein and Rio, 2005]
T. Klein and E. Rio.
Concentration around the mean for maxima of empirical processes.
The Annals of Probability, May 2005.

[Koltchinskii and Lounici, 2017]
Vladimir Koltchinskii and Karim Lounici.
Concentration inequalities and moment bounds for sample covariance operators.
Bernoulli, February 2017.

[Lecué and Lerasle, 2019]
Guillaume Lecué and Matthieu Lerasle.
Learning from MOM's principles: Le Cam's approach.
Stochastic Processes and their Applications, November 2019.

[Lecué and Lerasle, 2020]
Guillaume Lecué and Matthieu Lerasle.
Robust machine learning by median-of-means: Theory and practice.
The Annals of Statistics, April 2020.

[Lecué and Mendelson, 2016]
Guillaume Lecué and Shahar Mendelson.
Learning subgaussian classes : Upper and minimax bounds, September 2016.

[Lee and Valiant, 2022]
Jasper C.H. Lee and Paul Valiant.
Optimal Sub-Gaussian Mean Estimation $\mathbb{R}$.
In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), Denver, CO, USA, February 2022.

[Lehmann and Casella, 2006]
Erich L Lehmann and George Casella.
Theory of point estimation.
Springer Science & Business Media, 2006.

[Lugosi and Mendelson, 2019]
Gábor Lugosi and Shahar Mendelson.
Risk minimization by median-of-means tournaments.
Journal of the European Mathematical Society, December 2019a.

[Lugosi and Mendelson, 2019]
Gábor Lugosi and Shahar Mendelson.
Sub-Gaussian estimators of the mean of a random vector.
The Annals of Statistics, April 2019b.

[Lugosi and Mendelson, 2021]
Gábor Lugosi and Shahar Mendelson.
Robust multivariate mean estimation: The optimality of trimmed mean.
The Annals of Statistics, February 2021.

[Mendelson, 2017]
Shahar Mendelson.
“Local” vs. “global” parameters—breaking the Gaussian complexity barrier.
The Annals of Statistics, October 2017.

[Mendelson and Zhivotovskiy, 2020]
Shahar Mendelson and Nikita Zhivotovskiy.
Robust covariance estimation under $L_{4}-L_{2}$ norm equivalence.
The Annals of Statistics, June 2020.

[Mourtada, 2022]
Jaouad Mourtada.
Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices.
The Annals of Statistics, August 2022.

[Oliveira and Resende, 2023]
Roberto I. Oliveira and Lucas Resende.
Trimmed sample means for robust uniform mean estimation and regression, February 2023.

[Oliveira and Rico, 2022]
Roberto I. Oliveira and Zoraida F. Rico.
Improved covariance estimation: Optimal robustness and sub-Gaussian guarantees under heavy tails, September 2022.

[Oliveira, 2016]
Roberto Imbuzeiro Oliveira.
The lower tail of random quadratic forms with applications to ordinary least squares.
Probability Theory and Related Fields, 2016.

[Saumard, 2018]
Adrien Saumard.
On optimality of empirical risk minimization in linear aggregation.
Bernoulli, August 2018.

[Tropp, 2015]
Joel A. Tropp.
The Expected Norm of a Sum of Independent Random Matrices: An Elementary Approach, October 2015a.

[Tropp, 2015]
Joel A. Tropp.
An Introduction to Matrix Concentration Inequalities, January 2015b.

[Van Handel, 2017]
Ramon Van Handel.
Structured random matrices.
Convexity and concentration, pages 107–156, 2017.

[Zhivotovskiy, 2024]
Nikita Zhivotovskiy.
Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle.
Electronic Journal of Probability, January 2024.

§ PRELIMINARIES

§.§ Pseudo-inverses and quantile function

We say a function $f: \R \to \R$ is increasing if $x < y$ implies $f(x) \leq f(y)$, and strictly increasing if $x < y$ implies $f(x) < f(y)$. For a function $f: \R \to \R$, we define $\im(f) = \brace*{f(x) \st x \in \R}$.

Let $f: \R \to \R$ be an increasing function. We define $f^{-}: [-\infty, \infty] \to [-\infty, \infty]$, the pseudo-inverse of $f$, by

\begin{equation*}
f^{-}(y) \defeq \inf\brace*{x \in \R \st f(x) \geq y},
\end{equation*}

with the conventions $\inf \varnothing \defeq \infty$ and $\inf \R \defeq -\infty$.

The following holds.

* Let $f: \R \to \R$ be an increasing function. Then for all $x \in \R$, $f^{-}(f(x)) \leq x$.

* Let $f, g$ be increasing functions from $\R$ to $\R$. If $f \geq g$ then $f^{-} \leq g^{-}$.

* Let $I$ be an index set and let $\brace*{f_i}_{i \in I}$ be a collection of increasing functions from $\R$ to $\R$. Then

\begin{equation*}
\paren*{\sup_{i \in I} f_{i}}^{-} \leq \inf_{i \in I} f_{i}^{-} \leq \sup_{i \in I} f_{i}^{-} \leq \paren*{\inf_{i \in I} f_{i}}^{-}.
\end{equation*}

* Let $f: \R \to \R$ be a strictly increasing function, so that it is a bijection from $\R$ to $\im(f)$. Denote by $f^{-1}:\im(f) \to \R$ the inverse of $f$. Then for all $y \in \im(f)$, $f^{-}(y) = f^{-1}(y)$.

* Let $f: \R \to \R$ be an increasing right-continuous function. Then for all $y \in [-\infty, \infty]$,

\begin{equation*}
f^{-}(y) = \min\brace*{x \in \R \st f(x) \geq y},
\end{equation*}

with the conventions $\min \varnothing \defeq \infty$ and $\min \R \defeq -\infty$.

* Let $I$ be an index set and let $\brace*{f_i}_{i \in I}$ be a collection of increasing right-continuous functions from $\R$ to $\R$. Then

\begin{equation*}
\sup_{i \in I} f_{i}^{-} = \paren*{\inf_{i \in I} f_{i}}^{-}.
\end{equation*}

* Let $f: \R \to \R$ be increasing and right-continuous, and let $g: \R \to \R$ be increasing. Then

\begin{equation*}
(f \circ g)^{-} = g^{-} \circ f^{-}.
\end{equation*}

* Let $(f_k)_{k \in \N}$ be a decreasing sequence of increasing right-continuous functions, and assume that $f_{n} \to f$ pointwise as $n \to \infty$. Then,

\begin{equation*}
\sup_{n \in \N} f_{n}^{-1} = f^{-1}.
\end{equation*}

* We have, since $f(x) \geq f(x)$,

\begin{equation*}
f^{-}(f(x)) = \inf\brace*{z \in \R \st f(z) \geq f(x)} \leq x.
\end{equation*}

* Fix $y \in [-\infty, \infty]$, and define $S_{f} \defeq \brace*{x \in \R \st f(x) \geq y}$, and $S_{g} \defeq \brace*{x \in \R \st g(x) \geq y}$. We claim that $S_{g} \subset S_{f}$ from which the statement follows. If $S_{g} = \varnothing$, the statement follows trivially. Otherwise let $x \in S_{g}$. Then $f(x) \geq g(x) \geq y$, so $x \in S_{f}$.

* We prove the last inequality. The first follows from a similar argument. By definition, for all $j \in I$, $\sup_{i \in I} f_i \geq f_j$. Applying the second item yields that for all $j \in I$, $\paren*{\sup_{i \in I} f_i}^{-} \leq f_{j}^{-}$. Taking the infimum over $j \in I$ yields the result.

* Let $y \in \im(f)$ and let $S \defeq \brace*{x \in \R \st f(x) \geq y}$. We claim that $f^{-1}(y) = \min S$ from which the claim follows since then $f^{-}(y) = \min S$. Indeed, since $f(f^{-1}(y)) = y$, we have $f^{-1}(y) \in S$. Now suppose that there exists an $x \in S$ such that $f^{-1}(y) > x$. Since $f$ is strictly increasing, we would have $y = f(f^{-}(y)) > f(x)$, which contradicts the fact that $x \in S$. Therefore $f^{-1}(y) \leq x$ for all $x \in S$. This proves that $f^{-1}(y) = \min S$.

* The statement holds trivially if $f^{-}(y) \in \brace*{-\infty, \infty}$. Otherwise, $f^{-}(y) \in \R$, and by definition of the infimum, for all $k \in \N$, we have $x_k \defeq f^{-}(y) + 1/k \in S$ and therefore $f(x_k) \geq y$. Furthermore, $\lim_{k \to \infty} x_k = f^{-1}(y)$ and $x_k > f^{-1}(y)$, so by the right-continuity of $f$ we obtain

\begin{equation*}
f(f^{-1}(y)) = \lim_{k \to \infty} f(x_k) \geq y.
\end{equation*}

Therefore $f^{-1}(y) \in S$ which implies $f^{-1}(y) = \min S$.

* The inequality $(\leq)$ is covered by the third item, therefore it is enough to prove the inequality $(\geq)$. Let $y \in [-\infty, \infty]$. We claim that

\begin{equation*}
\sup_{i \in I}f^{-}_{i}(y) \geq \paren*{\inf_{i \in I}f_i}^{-}(y).
\end{equation*}

The statement follows trivially if $\sup_{i \in I}f^{-}_{i}(y) = \infty$. Otherwise, we have $f^{-}_{i}(y) < \infty$ for all $i \in I$. If $\sup_{i \in I}f^{-}_{i}(y) = -\infty$, then $f_{i}^{-}(y) = -\infty$ for all $i \in I$, which implies that $f_{i}(x) \geq y$ for all $x \in \R$. This in turn implies that for all $x \in \R$, $\inf_{i \in I}f_{i}(x) \geq y$ and therefore $\paren*{\inf_{i \in I}f_i}^{-}(y) = -\infty$. It remains to consider the case where $\sup_{i \in I}f^{-}_{i}(y) \in \R$. We claim that

\begin{equation*}
\inf_{i \in I} f_{i}\paren*{\sup_{j \in I}f^{-}_{j}(y)} \geq y
\end{equation*}

from which the main claim follows by definition of the pseudo-inverse. Indeed, let $i \in I$. If $f^{-}_{i}(y) \in \R$, then we have

\begin{equation*}
f_{i}\paren*{\sup_{j \in I}f^{-}_{j}(y)} \geq f_{i}(f_{i}^{-}(y)) \geq y
\end{equation*}

where the first inequality holds since $f_i$ is increasing, and the second by the fifth item and the fact that $f^{-}_{i}(y) \in \R$. Otherwise $f_{i}^{-}(y) = -\infty$, and therefore $f_{i}(x) \geq y$ for all $x \in \R$, which in particular implies the desired statement since $\sup_{i \in I}f^{-}_{i}(y) \in \R$.

* Let $y \in [-\infty, \infty]$. By the assumed properties of $f$ and the fifth item, we have $f(g(x)) \geq y$ if and only if $g(x) \geq f^{-}(y)$. Therefore

\begin{align*}
(f \circ g)^{-}(y) &= \inf\brace*{x \in \R \st f(g(x)) \geq y} \\
&= \inf\brace*{x \in \R \st g(x) \geq f^{-}(y)} \\
&= g^{-}(f^{-}(y)) = (g^{-} \circ f^{-})(y).
\end{align*}

* We start with the inequality ($\leq$). Let $x \in \R$. Since $(f_{n}(x))_{n \in \N}$ is decreasing, we have $f(x) = \lim_{n \to \infty} f_{n}(x) = \inf_{n \in \N} f_{n}(x)$. Therefore, for all $n \in \N$, we have $f_{n} \geq f$. By the second item, we therefore have $f^{-}_{n} \leq f^{-}$. Taking supremum over $n$ yields the result.

For the inequality $(\geq)$, let $y \in \R$, and suppose that $\sup_{n \in \N} f_{n}^{-}(y) < f^{-}(y)$. If $\sup_{n \in \N} f_{n}^{-}(y) = -\infty$, then for all $x \in \R$ and for all $n \in \N$, $f_{n}(x) \geq y$, which implies that for all $x \in \R$, $f(x) = \lim_{n \to \infty} f_{n}(x) \geq y$, and therefore $f^{-1}(y) = -\infty$, contradicting the strict inequality. Otherwise $x^{*} \defeq \sup_{n \in \N} f_{n}^{-}(y) \in \R$, and either $f^{-}(y) = \infty$ or $f^{-}(y) \in \R$.

If $f^{-}(y) = \infty$, then on the one hand, for all $x \in \R$, $\lim_{n \to \infty} f_{n}(x) = f(x) < y$. On the other hand, for all $n \in \N$, $f_{n}\paren*{x^{*}} \geq y$. Indeed, if $f^{-}_{n}(y) \in \R$, then by the fifth item $f_{n}(x^{*}) \geq f_{n}(f^{-}_{n}(y)) \geq y$. Otherwise, $f^{-}_{n}(y) = -\infty$ so that $f(x) \geq y$ for all $x \in \R$, and in particular $f_{n}(x^{*}) \geq y$. But then we get the contradiction $y > \lim_{n \to \infty} f_{n}\paren*{x^{*}} \geq y$.

Finally, if $f^{-}(y) \in \R$, define $\eps \defeq f^{-}(y) - x^{*} > 0$. By definition of $x^{*}$, $f^{-}(y) - \eps \geq f^{-}_{n}(y)$ for all $n \in \N$. We claim that for all $n \in \N$

\begin{equation*}
f_{n}(f^{-}(y) - \eps) \geq y.
\end{equation*}

Indeed, if $f^{-}_{n}(y) \in \R$, then by the fifth item $f_{n}(f^{-}(y) - \eps) \geq f_{n}(f^{-}_{n}(y)) \geq y$. Otherwise, $f^{-}_{n}(y) = -\infty$ so that $f(x) \geq y$ for all $x \in \R$, and in particular $f_{n}(f^{-}(y) - \eps) \geq y$ since $f^{-}(y) - \eps \in \R$. Taking the limit as $n \to \infty$ yields

\begin{equation*}
\lim_{n \to \infty} f_{n}(f^{-}(y) - \eps) = f(f^{-}(y)-\eps) \geq y
\end{equation*}

contradicting the minimality of $f^{-}(y)$.

For a random variable $X$, we denote by $F_{X}: \R \to \R$ its cumulative distribution function $F_{X}(x) \defeq \Prob\paren*{X \leq x}$, and by $Q_{X}: [-\infty, \infty] \to [-\infty, \infty]$ its quantile function $Q_{X}(p) \defeq F_{X}^{-}(p)$. Since $F_{X}$ is right-continuous, then by the fifth item of Lemma <ref> we have

\begin{equation*}
Q_{X}(p) = \min\brace*{x \in \R \st F_{X}(x) \geq p}.
\end{equation*}

Furthermore, since $\lim_{x \to -\infty} F_{X}(x) = 0$ and $\lim_{x \to \infty} F_{X}(x) = 1$, it is easy to verify that $Q_{X}(p) \in \R$ for all $p \in (0, 1)$ and $Q_{X}(0) = -\infty$. If $X, Y$ are two random variables, we define the random variable $F_{X \mid Y}(x) \defeq \Prob\paren*{X \leq x \st Y}$ and we note that $F_{X}(x) = \Exp\brack{F_{X \mid Y}(x)}$ for all $x \in \R$.

Let $\varphi: \R \to \R$ be strictly increasing and left continuous. Then for all $p \in (0, 1)$

\begin{equation*}
Q_{\varphi(X)}(p) = \varphi(Q_{X}(p)).
\end{equation*}

where we define $\varphi(\infty) \defeq \infty$ and $\varphi(-\infty) \defeq -\infty$.

The statement, or more precisely the obvious modification to it to accommodate $Q_{X}(p)$ taking values in $\brace*{-\infty, \infty}$, fails in general for $p \in \brace*{0, 1}$. Indeed take $X \sim \mathcal{N}(0,1)$ and $\varphi(x) = \exp(x)$. Then $Q_{X}(0) = -\infty$, and $\lim_{x \to -\infty} \exp(x) = 0$. On the other hand

\begin{equation*}
Q_{\exp(X)}(0) = \min\brace*{x \in \R \st \Prob\paren*{\exp(X) \leq x} \geq 0} = -\infty
\end{equation*}

Similarly, taking $\varphi(x) = \frac{1}{1+\exp(-x)}$ and $p=1$ with $X \sim \mathcal{N}(0, 1)$ gives the counter example for the case $p=1$.

Let $\eps_{-} \defeq \Prob\paren*{X = \infty}$ and $\eps_{+} = \Prob\paren*{X = \infty}$. By definition, $\varphi(X) = \infty \Leftrightarrow X = -\infty$, so the identity holds trivially for all $p \in (0, \eps_{-}] \cup [1-\eps_{+}, 1)$. Now consider the case $p \in I \defeq (\eps_{-}, 1-\eps_{+})$. First, since $\lim_{x \to -\infty} F_{X}(x) = \eps_{-}$ and $\lim_{x \to \infty} F_{X}(x) = 1- \eps_{+}$ by continuity of probability measures, we have $Q_{X}(p) \in \R$. The same argument shows that $Q_{\varphi(X)}(p) \in \R$. Now, since $\varphi$ is strictly increasing,

\begin{equation*}
F_{X}(x) = \Prob\paren*{X \leq x} = \Prob\paren*{\varphi(X) \leq \varphi(x)} = F_{\varphi(X)}(\varphi(x)) = (F_{\varphi(X)} \circ \varphi)(x).
\end{equation*}

Therefore, by the penultimate item of Lemma <ref>, we have

\begin{equation}
\label{eq:pf_lem_2_1}
Q_{X} = F_{X}^{-} = \varphi^{-} \circ F_{\varphi(X)}^{-} = \varphi^{-} \circ Q_{\varphi(X)}.
\end{equation}

We claim that for all $p \in I$,

\begin{equation}
\label{eq:pf_lem_2_2}
(\varphi \circ \varphi^{-} \circ Q_{\varphi(X)})(p) = Q_{\varphi(X)}(p).
\end{equation}

By the fourth item of Lemma <ref>, it is enough to show that $Q_{\varphi(X)}(p) \in \im(\varphi)$ for all $p \in I$. This will be the goal of the proof. Let $p \in I$, and define
$S \defeq \brace*{x \in \R \st \varphi(x) \leq Q_{\varphi(X)}(p)}$. We claim that $S$ is non-empty and upper bounded. Indeed, suppose not. Then either $\varphi(x) > Q_{\varphi(X)}(p)$ for all $x \in \R$ or $\varphi(x) \leq Q_{\varphi(X)}(p)$ for all $x \in \R$. In the former case, this implies that for all $x \in \R$

\begin{equation*}
F_{X}(x) = \Prob\paren*{X \leq x} = \Prob\paren*{\varphi(X) \leq \varphi(x)} \geq \Prob\paren*{\varphi(X) \leq Q_{\varphi(X)}(p)} \geq p > \eps_{-},
\end{equation*}

where the second inequality follows from the fifth item of Lemma <ref> and the fact that $Q_{\varphi(X)}(p) \in \R$. This leads to the contradiction

\begin{equation*}
\eps_{-} = \lim_{x \to -\infty} F_{X}(x) \geq p > \eps_{-}.
\end{equation*}

In the latter case, we get that for all $x \in \R$

\begin{equation*}
F_{X}(x) = \Prob\paren*{X \leq x} = \Prob\paren*{\varphi(X) \leq \varphi(x)} \leq \Prob\paren*{\varphi(X) \leq Q_{\varphi(X)}(p)}.
\end{equation*}

This leads to

\begin{equation*}
1 - \eps_{+} = \lim_{x \to \infty} F_{X}(x) \leq \Prob\paren*{\varphi(X) \leq Q_{\varphi(X)}(p)} \leq 1 - \eps_{+}.
\end{equation*}

where the last inequality follows from the fact that $Q_{\varphi(X)}(p) \in \R$. Now, since

\begin{equation*}
\Prob\paren*{\varphi(X) \leq \lim_{x \to \infty} \varphi(x)} = 1-\eps_{+}
\end{equation*}

and $\varphi(x) \leq Q_{\varphi(X)}(p)$ for all $x \in \R$, we get by the minimality property of $Q_{\varphi(X)}(p)$

\begin{equation*}
Q_{\varphi(X)}(p) = \lim_{x \to \infty}\varphi(x).
\end{equation*}

But, on the one hand, we have by continuity of probability,

\begin{equation*}
\lim_{n \to \infty} \Prob\paren*{\varphi(X) \leq \varphi(n)} = \Prob\paren*{\varphi(X) \leq \lim_{n \to \infty} \varphi(n)} = 1 - \eps_{+}
\end{equation*}

yet on the other, since $\varphi$ is strictly increasing, we have $\varphi(n) < \lim_{x \to \infty}\varphi(x) = Q_{\varphi(X)}(p)$ for all $n \in \N$, so by the minimality of $Q_{\varphi(X)}(p)$, $\Prob\paren*{\varphi(X) \leq \varphi(n)} < p$ for all $n \in \N$, from which we obtain the contradiction

\begin{equation*}
1 - \eps_{+} = \lim_{n \to \infty} \Prob\paren*{\varphi(X) \leq \varphi(n)} \leq p
\end{equation*}

This proves that $S$ is non-empty and upper bounded. Now define $x_0 \defeq \sup S$, which is guaranteed to satisfy $x_{0} \in \R$ by the upper boundedness of $S$ and its non-emptiness. We claim that $\varphi(x_0) =Q_{\varphi(X)}(p)$. Indeed, by the left-continuity of $\varphi$, we have, for any sequence $(x_n)_{n \in \N}$ in $S$ such that $x_n \to x_0$

\begin{equation}
\label{eq:pf_lem_2_3}
\varphi(x_0) = \lim_{n \to \infty} \varphi(x_n) \leq Q_{\varphi(X)}(p)
\end{equation}

where the last inequality follows from the definition of $S$ and the fact that $x_n \in S$ for all $n \in \N$. On the other hand, by the maximality of $x_0$, we have for all $x > x_0$, $\varphi(x) > Q_{\varphi(X)}(p)$, which implies that

\begin{equation}
\label{eq:pf_lem_2_4}
Q_{\varphi(X)}(p) \leq \lim_{x \to x_{0}^{+}} \varphi(x)
\end{equation}

Combining (<ref>) and (<ref>), we obtain

\begin{equation*}
Q_{\varphi(X)}(p) \in \brack*{\varphi(x_0), \lim_{x \to x_{0}^{+}} \varphi(x)}
\end{equation*}

But for any $y \in \brack*{{\varphi(x_0), \lim_{x \to x_{0}^{+}} \varphi(x)}}$, we have

\begin{equation*}
\Prob\paren*{\varphi(X) \leq y} = \Prob\paren*{\varphi(X) \leq \varphi(x_0)}
\end{equation*}

Indeed on the one hand

\begin{equation*}
\Prob\paren*{\varphi(X) \leq y} \geq \Prob\paren*{\varphi(X) \leq \varphi(x_0)}
\end{equation*}

On the other, if $X > x_0$, then since $\varphi$ is strictly increasing, $\varphi(X) > \lim_{x \to x_{0}^{+}} \varphi(x) \geq y$. Therefore

\begin{equation*}
\Prob\paren*{\varphi(X) \leq y} \leq \Prob\paren*{\varphi(X) \leq \lim_{x \to x_{0}^{+}} \varphi(x)} \leq \Prob\paren*{X \leq x_0} = \Prob\paren*{\varphi(X) \leq \varphi(x_0)}
\end{equation*}

but then, by the minimality of $Q_{\varphi(X)}(p)$, we obtain $Q_{\varphi(X)}(p) = \varphi(x_0)$. This proves (<ref>). Now applying $\varphi$ to both sides of (<ref>) and using (<ref>) yields the result.

§.§ Convexity

A subset $A \subset \R^{d}$ is

* convex if for all $x, y \in A$ and $t \in [0, 1]$, $(1-t) x + t y \in A$.

* symmetric if for all $x \in A$, $-x \in A$.

Let $A$ be a non-empty convex symmetric set. Then for all $\lambda \geq 1$, $A \subseteq \lambda A$.

We start by proving that $\lambda A$ is convex. Indeed let $x, y \in \lambda A$ and $t \in [0,1]$. Then by definition $x/\lambda, y/\lambda \in A$, so by convexity of $A$

\begin{equation*}
(1-t)\frac{x}{\lambda} + t\frac{y}{\lambda} \in A,
\end{equation*}

which implies

\begin{equation*}
(1-t)x + ty = \lambda \cdot \paren*{(1-t)\frac{x}{\lambda} + t\frac{y}{\lambda}} \in \lambda A.
\end{equation*}

Next we prove that $0 \in A$. Let $v \in A$. Since $A$ is symmetric, $-v \in A$, and by convexity of $A$

\begin{equation*}
0 = \frac{1}{2}x - \frac{1}{2}x = \frac{1}{2}x + \frac{1}{2}(-x) \in A.
\end{equation*}

Finally, we prove the main claim. Let $x \in A$. Then by definition $\lambda x \in \lambda A$. But then by convexity of $\lambda A$ and since $\lambda \geq 1$

\begin{equation*}
x = \paren*{1 - \frac{1}{\lambda}} 0 + \frac{1}{\lambda} \lambda x \in \lambda A
\end{equation*}

A function $f:\R^{d} \to \R$ is

* quasiconvex if for all $x, y \in \R^{d}$ and $t \in [0,1]$, $f((1-t)x + ty) \leq \max\paren*{f(x), f(y)}$.

* symmetric if for all $v \in \R^{d}$, $f(v) = f(-v)$.

Every convex function is quasiconvex. The function $f(x) = \log(x)$ is quasiconvex but not convex. Every norm is quasiconvex (and, in fact, convex) and symmetric.

The following holds.

* $f: \R^{d} \to \R$ is quasiconvex and symmetric if and only if for all $y \in \R$, $f^{-1}((-\infty, y])$ is convex and symmetric.

* If $f: \R^{d} \to \R$ is quasiconvex and symmetric then $0 \in \argmin_{x \in \R}f(x)$.

Proof of first item (see Wikipedia entry). For the second, we have for any $x \in \R^{d}$

\begin{equation*}
f(0) = f\paren*{\frac{1}{2}x - \frac{1}{2}x} = f\paren*{\frac{1}{2}x + \frac{1}{2}(-x)} \leq \max\paren*{f(x), f(-x)} = f(x).
\end{equation*}

§.§ Gaussian measures

Let $Z \sim \mathcal{N}(0, \sigma^2)$. Then

\begin{equation*}
\sqrt{1 - \exp\paren*{-\frac{r^2}{2\sigma^2}}} \leq F_{\abs{Z}}(r) \leq \sqrt{1 - \exp\paren*{-\frac{2r^{2}}{\pi\sigma^2}}}.
\end{equation*}

Consider first the case where $\sigma^2 = 1/2$. Then

\begin{multline*}
\paren*{F_{\abs{Z}}(r)}^{2} = \paren*{\Prob\paren*{-r \leq Z \leq r}}^{2}
= \paren*{\frac{2}{\sqrt{\pi}}\int_{0}^{r} e^{-t^2} dt}^{2}
\\
= \frac{4}{\pi} \int_{0}^{r}\int_{0}^{r} e^{-(t^2 + s^2)} dt ds
= \frac{4}{\pi} \int_{S} e^{-(t^{2} + s^{2})} dtds
\end{multline*}

where $S \defeq \brace*{(x,y) \in \R^{2} \st 0 \leq x,y \leq r}$ is the square of length $r$ whose lower left corner is at $0$. For a radius $\rho > 0$, define the quarter disks $D(\rho) \defeq \brace*{(x, y) \subset \R^{2} \st x, y \geq 0, \sqrt{x^2 + y^{2}} \leq \rho}$. Clearly, $D(r) \subset S$, so that

\begin{align*}
\frac{4}{\pi} \int_{S} e^{-(t^{2} + s^{2})} dtds &\leq \frac{4}{\pi} \int_{D(r)} e^{-(t^{2} + s^{2})} dtds = 1 - \exp\paren*{-r^{2}}
\end{align*}

where the last equality is obtained by an explicit integration using polar coordinates. On the other hand, consider the quarter disk $D(2r/\sqrt{\pi})$, and define $A \defeq D(2r/\sqrt{\pi}) \setminus S$ and $B \defeq S \setminus D(2r/\sqrt{\pi})$. Since $S$ and $D(2r/\sqrt{\pi})$ have the same area, so do $A$ and $B$. But for all $(t, s) \in A$ and all $(x, y) \in B$, we have

\begin{equation*}
t^{2} + s^{2} \leq \frac{4r^{2}}{\pi} \leq x^{2} + y^{2} \Rightarrow \exp\paren*{-\paren{t^{2} + s^{2}}} \geq \exp\paren*{-\paren{x^{2} + y^{2}}}
\end{equation*}

\begin{align*}
\frac{4}{\pi} \int_{S} e^{-(t^{2} + s^{2})} dtds &= \frac{4}{\pi} \paren*{\int_{S \cap D(2r/\sqrt{\pi})} e^{-(t^{2} + s^{2})} dtds + \int_{B} e^{-(t^{2} + s^{2})} dtds} \\
&\leq \frac{4}{\pi} \paren*{\int_{S \cap D(2r/\sqrt{\pi})} e^{-(t^{2} + s^{2})} dtds + \int_{A} e^{-(t^{2} + s^{2})} dtds} \\
&= \frac{4}{\pi} \int_{D(2r/\sqrt{\pi})} e^{-(t^{2} + s^{2})} dtds = 1 - \exp\paren*{-\frac{4r^{2}}{\pi}}
\end{align*}

This proves the statement for $\sigma^{2} = 1/2$. For $\sigma^2 \in (0, \infty)$, note that $Z \overset{d}{=} \sqrt{2\sigma^2} \tilde{Z}$ where $\tilde{Z} \sim \mathcal{N}(0, 1/2)$, so

\begin{equation*}
F_{\abs{Z}}(r) = \Prob\paren*{-r \leq Z \leq r} = \Prob\paren*{-\frac{r}{\sqrt{2\sigma^2}} \leq \tilde{Z} \leq \frac{r}{\sqrt{2\sigma^2}}} = F_{\abs{\tilde{Z}}}\paren*{\frac{r}{\sqrt{2\sigma^2}}},
\end{equation*}

and applying the result for $\sigma^2 = 1/2$ yields the general result.

Let $X, Y$ be random vectors such that $X \mid Y = y \sim \mathcal{N}(y, \Sigma)$ for some fixed $\Sigma \in \S_{++}^{d}$ and for all $y$ in the image of $Y$. Then $X - Y \sim \mathcal{N}(0, \Sigma)$.

Let $B$ be a Borel subset of $\R^{d}$, and let $Z \sim \mathcal{N}(0, \Sigma)$. We have

\begin{equation*}
\Prob\paren*{X - Y \in B} = \Exp\brack*{\Prob\paren*{X - Y \in B \st Y}} = \Exp\brack*{\Prob\paren*{Z \in B}} = \Prob\paren*{Z \in B}.
\end{equation*}

Let $Z \sim \mathcal{N}(0, \Sigma)$ for some $\Sigma \in S_{++}^{d}$ and $d \in \N$. Let $A \subset \R^{d}$ be a convex symmetric set. Then for all $a \in \R^{d}$, we have

\begin{equation*}
\Prob\paren*{Z \in A} \geq \Prob\paren*{Z \in A + a}.
\end{equation*}

Let $d \in \N$, $Z \sim \mathcal{N}(0, I_{d \times d})$, and $f: \R^{d} \to \R$ be an $L$-Lipschitz function with respect to the Euclidean metric. Then $\Var\brack*{f(Z)} \leq L^{2}$ and

\begin{equation*}
\Prob\paren*{f(Z) - \Exp\brack*{f(Z)} \geq t} \leq \exp\paren*{-\frac{t^{2}}{2L^2}}.
\end{equation*}

§.§.§ Concentration of norms of Gaussian vectors

For this subsection, fix $d \in \N$, an arbitrary norm $\norm{\cdot}$ on $\R^{d}$, and a covariance matrix $\Sigma \in S_{++}^{d}$. Let $Z \sim \mathcal{N}(0, \Sigma)$, and define $M \defeq \Exp\brack*{\norm{Z}}$. Let $S$ denote the unit sphere of the dual norm $\norm{\cdot}_{*}$, and recall that $\norm{x} = \norm{x}_{**} = \sup_{v \in S} \abs{\inp{v}{x}}$. Define $R \defeq \sup_{v \in S} v^{T} \Sigma v$, and $v_{*} = \max_{v \in S} v^{T} \Sigma v$ where the maximum is attained since $S$ is compact and the function is continuous.

The function $f: \R^{d} \to \R$ given by $f(x) = \norm{\Sigma^{1/2}x}$ is $\sqrt{R}$-Lipschitz in the Euclidean metric.

\begin{multline*}
\abs{f(x) - f(y)} = \abs*{\norm{\Sigma^{1/2}x} - \norm{\Sigma^{1/2}y}} \leq \norm{\Sigma^{1/2}(x - y)} \\
= \sup_{v \in S} \inp{\Sigma^{1/2}v}{x-y}\leq \paren*{\max_{v \in S} \norm{\Sigma^{1/2}v}_{2}} \norm{x - y}_{2}
\end{multline*}

For all $t \geq 0$,

\begin{align*}
&M^{2} \leq \Exp\brack*{\norm{Z}^2} \leq \paren*{1 + \frac{\pi}{2}} M^2, \\
&\Prob\paren*{M - \norm{Z} \geq t} \leq \exp\paren*{-\frac{t^2}{\pi M^2}}.
\end{align*}

Notice that

\begin{equation*}
M = \Exp\brack*{\norm{Z}} = \Exp\brack*{\sup_{v \in S} \abs{\inp{v}{Z}}} \geq \sup_{v \in S} \Exp\brack*{\abs{\inp{v}{Z}}} = \sup_{v \in S} \sqrt{\frac{2}{\pi} v^{T} \Sigma v} = \sqrt{\frac{2}{\pi} v_{*}^{T} \Sigma v_{*}}.
\end{equation*}

where the inequality follows by convexity of the supremum and Jensen's inequality, and the third equality by the fact that $\inp{v}{Z} \sim \mathcal{N}(0, v^{T} \Sigma v)$ and an explicit calculation of the expectation. We now prove the first item. The first inequality follows from Jensen's inequality. For the second, notice that $\Sigma^{-1/2}Z \sim \mathcal{N}(0, I_{d \times d})$, so that an application of Lemmas <ref> and <ref> yields

\begin{equation*}
\Exp\brack*{\norm{Z}^2} - (\Exp\brack*{\norm{Z}})^{2} =  \Var\brack*{\norm{Z}} = \Var\brack*{f(\Sigma^{-1/2}Z)} \leq R = v_{*}^{T} \Sigma v_{*} \leq \frac{\pi}{2} (\Exp\brack*{\norm{Z}})^{2}.
\end{equation*}

where $f$ is as defined in Lemma <ref>. For the second item, notice that $-f$ is also $\sqrt{R}$-Lipschitz, so that again an application of Lemma <ref> yields

\begin{multline*}
\Prob\paren*{M - \norm{Z} > t} = \Prob\paren*{-f(\Sigma^{-1/2}Z) - \Exp\brack*{-f(\Sigma^{-1/2} Z)} > t} \\
\leq \exp\paren*{-\frac{t^{2}}{2v_{*}^{T}\Sigma v_{*}}} \leq \exp\paren*{-\frac{t^2}{\pi \paren*{\Exp\brack*{\norm{Z}}}^{2}}}.
\end{multline*}

For all $r \in \R$,

\begin{equation*}
l(r) \leq F_{\norm{Z}}(r) \leq \min\brace*{u_{1}(r), u_{2}(r)}
\end{equation*}

\begin{gather*}
l(r) \defeq \brack*{1 - \exp\paren*{- \frac{(r - M)^{2}}{2R}}} \mathbbm{1}_{[M, \infty)}, \\
u_1(r) \defeq \exp\paren*{\frac{-(M-r)^2}{\pi M^{2}}} \mathbbm{1}_{[0, M)}(r) + \mathbbm{1}_{[M, \infty)}(r), \quad
u_2(r) \defeq \sqrt{1 - \exp\paren*{-\frac{2r^2}{\pi R}}} \mathbbm{1}_{[0,\infty)}(r).
\end{gather*}

We start with the lower bound. Let $r \geq M$. Then

\begin{equation*}
F_{\norm{Z}}(r) = \Prob\paren*{\norm{Z} \leq r} = 1 - \Prob\paren*{\norm{Z} > r} = 1 - \Prob\paren*{\norm{Z} - M > r - M} \geq 1 - \exp\paren*{- \frac{(r - M)^{2}}{2R}}
\end{equation*}

where the last inequality follows from Lemmas <ref> and <ref>. For the lower bound, we have, by Lemma <ref>

\begin{equation*}
F_{\norm{Z}}(r) = \Prob\paren*{\norm{Z} \leq r} = \Prob\paren*{\norm{Z} - M \leq r - M} = \Prob\paren*{M - \norm{Z} \geq M - r} \leq u_1(r).
\end{equation*}

\begin{equation*}
F_{\norm{Z}}(r) = \Prob\paren*{\sup_{v \in S} \abs{\inp{v}{Z}} \leq r} \leq \Prob\paren*{\abs{\inp{v_{*}}{Z}} \leq r} \leq u_{2}(r),
\end{equation*}

where the second inequality follows from the fact that $\inp{v_{*}}{Z} \sim \mathcal{N}(0, R)$ and Lemma <ref>.

§.§ Inverse Gamma measure

Let $\alpha, \beta > 0$. The inverse gamma measure $\text{Inv-Gamma}(\alpha, \beta)$ on $(0, \infty)$ has density

\begin{equation*}
f_{\alpha, \beta}(x) \defeq \frac{\beta^{\alpha}}{\Gamma(\alpha)} x^{-\alpha-1}\exp\paren*{-\frac{\beta}{x}}
\end{equation*}

with respect to Lebesgue measure, where $\Gamma$ is the gamma function.

Let $X \sim \text{Inv-Gamma}(\alpha, \beta)$ and $Z \sim \text{Inv-Gamma}(\alpha, \alpha)$. Let $r > 0$, and define

\begin{equation*}
x_{\alpha, \beta}(r) \defeq \frac{\beta\brack*{\exp(r)-\exp(-r)}}{2\alpha r} \quad\quad p_{\alpha}(r) \defeq \Prob\paren*{\frac{1-\exp(-2r)}{2r} \leq Z \leq \frac{\exp(2r) - 1}{2 r}}
\end{equation*}

Then for all $x \in (0, \infty)$

\begin{equation*}
p_{\alpha}(r) = \Prob\paren*{\abs{\log(X/x_{\alpha, \beta}(r))} \leq r} \geq \Prob\paren*{\abs{\log(X/x)} \leq r}.
\end{equation*}

Fix $r \in (0, \infty)$. Define $h_r(x) \defeq \Prob\paren*{\abs{\log(X/x)} \leq r}$. Then we have

\begin{align*}
\frac{d}{dx}(h_r(x)) &= \frac{d}{dx}\paren*{\Prob\paren*{\abs{\log(X/x)} \leq r}} \\
&= \frac{d}{dx}\paren*{\Prob\paren*{x \exp(-r) \leq X \leq x \exp(r)}} \\
&= \frac{d}{dx} \paren*{\int_{x\exp(-r)}^{x\exp(r)}f_{\alpha, \beta}(t)dt} \\
&= \exp(r) f_{\alpha,\beta}(x\exp(r)) - \exp(-r) f_{\alpha, \beta}(x \exp(-r))
\end{align*}

where in the last line we used Leibniz integral rule. Setting the derivative to $0$ and solving yields $x_{\alpha, \beta}(r)$. Examining its derivative, we notice that $h_r$ is non-decreasing on $(0, x_{\alpha, \beta}(r)]$ and non-increasing on $[x_{\alpha, \beta}(r), \infty)$. Therefore $x_{\alpha, \beta}(r)$ is the global maximizer of $h_r$. Now

\begin{align*}
\Prob\paren*{\abs{\log(X/x_{\alpha, \beta}(r))} \leq r} &= \Prob\paren*{x_{\alpha, \beta}(r)\exp(-r) \leq X \leq x_{\alpha, \beta}(r)\exp(r)} \\
&= \Prob\paren*{\frac{1-\exp(-2r)}{2r} \leq \frac{\alpha}{\beta} X \leq \frac{\exp(2r) - 1}{2 r}} \\
&= p_{\alpha}(r)
\end{align*}

where in the last line we used that if $X \sim \text{Inv-Gamma}(\alpha, \beta)$, then $cX \sim \text{Inv-Gamma}(\alpha, c \cdot \beta)$ for all $c > 0$.

Let $p_{\alpha}$ be as defined in Lemma <ref>. The following holds.

* $p_{\alpha}(r)$ is non-decreasing in $\alpha$ for all $r > 0$.

* $p_{\alpha}(r)$ is strictly increasing in $r$ for all $\alpha > 0$ and $\im(p_{\alpha}) = (0, 1)$

§ SUPREMA OF TRUNCATED EMPIRICAL PROCESSES

§.§ Truncation function

Let $\alpha, \beta \in \R$ such that $\alpha \leq \beta$. Define

\begin{equation}
\label{eq:def_1}
\phi_{\alpha, \beta}(x) \defeq
\begin{dcases*}
\beta & \quad if \quad $x > \beta$, \\
x & \quad if \quad $x \in [\alpha, \beta]$, \\
\alpha & \quad if \quad $x < \alpha$.
\end{dcases*}
\end{equation}

The following holds for all $x \in \R$.

* $c \cdot \phi_{\alpha, \beta}(x) = \phi_{c \alpha, c \beta}(cx)$ for all $c \in [0, \infty)$.

* $-\phi_{\alpha, \beta}(x) = \phi_{-\beta, -\alpha}(-x)$.

* $\phi_{\alpha, \beta}(x) + y = \phi_{\alpha + y, \beta + y} (x + y)$ for all $y \in \R$.

Just check the three possible cases for each item.

Fix $n \in \N$. For a real valued sequence $a \defeq (a_i)_{i=1}^{n}$, define the sequence $a^{*} = (a^{*}_{i})_{i=1}^{n}$ by $a^{*}_i \defeq a_{\pi(i)}$ for all $i \in [n]$ and where $\pi: [n] \to [n]$ is a permutation that orders $a$ non-decreasingly, i.e. $a_{\pi(1)} \leq \dotsc \leq a_{\pi(n)}$. Note that this is well-defined since any such permutation gives the same $a^{*}$. Addition and scalar multiplication of sequences are as usual. For two sequences $a, b$, we say that $a \leq b$ if $a_{i} \leq b_i$ for all $i \in [n]$.

Let $a = (a_i)_{i=1}^{n}$ and $b = (b_i)_{i=1}^{n}$ be real valued sequences.

\begin{equation*}
a \leq b \Rightarrow a^{*} \leq b^{*}
\end{equation*}

Let $\pi$ and $\sigma$ be permutations of $[n]$ that order $a$ and $b$ non-decreasingly, respectively. Let $i \in [n]$. We show that $a_{\pi(i)} \leq b_{\sigma(i)}$. We consider two cases. If $\pi(i) \in \brace*{\sigma(1), \dotsc, \sigma(i)}$, then        $a_{\pi(i)} \leq b_{\pi(i)} \leq b_{\sigma(i)}$. Otherwise, $\pi(i) \in \brace*{\sigma(i+1), \dotsc, \sigma(n)}$. This implies that there exists a $j \in \brace*{i+1, \dotsc, n}$ such that $\pi(j) \in \brace*{\sigma(1), \dotsc, \sigma(i)}$, from which we conclude that $a_{\pi(i)} \leq a_{\pi(j)} \leq b_{\pi(j)} \leq b_{\sigma(i)}$.

Let $k \in \brace*{1, \dotsc, \floor{n/2}}$. Define

\begin{equation}
\label{eq:def_2}
\varphi_{k}(a) \defeq \sum_{i=1}^{n} \phi_{a^{*}_{1+ k}, a^{*}_{n-k}}(a_i).
\end{equation}

The following holds for all real-valued sequences $a = (a_i)_{i=1}^{n}$.

* $c \cdot \varphi_{k}(a) = \varphi_k(c \cdot a)$ for all $c \in \R$.

* $\varphi_{k}(a) + n \cdot c = \varphi_{k}(a + c)$ for all $c \in \R$.

* $\varphi_k(a) \leq \varphi_k(b)$ for all sequences $b = (b_i)_{i=1}^{n}$ such that $a \leq b$.

We start with the first item. Let $\pi: [n] \to [n]$ be a permutation that orders $a$ non-decreasingly. The case $c = 0$ is trivial. Now consider the case $c > 0$.  Then since $c > 0$, $\pi$ also orders $c \cdot a$ non-decreasingly. Therefore $(c \cdot a)_{i}^{*} = c \cdot a^{*}_i$ and

\begin{equation*}
c \cdot \varphi_{k}(a) = \sum_{i=1}^{n} c \cdot \phi_{a^{*}_{k}, a^{*}_{n-k}}(a_i) = \sum_{i=1}^{n} \phi_{c \cdot a^{*}_{k}, c \cdot a_{n-k}^{*}}(c \cdot a_i) =  \sum_{i=1}^{n} \phi_{(c \cdot a)^{*}_{k}, (c \cdot a)_{n-k}^{*}}(c \cdot a_i) = \varphi_{k}(c \cdot a),
\end{equation*}

where the second equality follows from the first item of Lemma <ref>.
Now consider the case $c = -1$. Then the permutation $\pi$ orders $-a$ non-increasingly so that $(-a)_{i}^{*} = -a_{n-i}^{*}$ and

\begin{equation*}
-\varphi_{k}(a) =  \sum_{i=1}^{n} - \phi_{a^{*}_{k}, a^{*}_{n-k}}(a_i) =  \sum_{i=1}^{n} \phi_{-a^{*}_{n-k}, -a^{*}_{k}}(-a_i) =  \sum_{i=1}^{n} \phi_{(-a)^{*}_{k}, (-a)^{*}_{n-k}}(-a_i) = \varphi_{k}(-a),
\end{equation*}

where the second equality follows from the second item of Lemma <ref>. For the case $c < 0$, we have

\begin{equation*}
c \cdot \varphi_{k}(a) = (-c) \cdot -\varphi_{k}(a) = (-c) \cdot \varphi_{k}(-a) = \varphi_{k}(c \cdot a).
\end{equation*}

For the second item, we have by Lemma <ref> that $a^{*} \leq b^{*}$, from which we conclude

\begin{equation*}
\varphi_{k}(a) =  \sum_{i=1}^{n} \phi_{a^{*}_{k}, a^{*}_{n-k}}(a_i) = k a^{*}_{k} +  \sum_{i=k+1}^{n-k-1} a_{i}^{*} + k a_{n-k}^{*} \leq k b^{*}_{k} +  \sum_{i=k+1}^{n-k-1} b_{i}^{*} + k b_{n-k}^{*} = \varphi_{k}(b)
\end{equation*}

Let $a = (a_i)_{i=1}^{n}$ and $b = (b_i)_{i=1}^{n}$ be real valued sequences such that $b \geq 0$. Then

\begin{equation*}
\varphi_{k}(a+b) \geq \varphi_k(a) + \sum_{i=1}^{n-2k} b_{i}^{*}
\end{equation*}

Let $\pi$ and $\sigma$ be permutations that order $a+b$ and $a$ non-decreasingly, respectively. By definition

\begin{equation*}
\varphi_k(a+b) = k (a+b)_{1+k}^{*} + \sum_{i=k+1}^{n-k} (a+b)_{i}^{*} + k (a+b)_{n-k}^{*}.
\end{equation*}

We lower bound each of the three terms separately. For the first, define the sets $I_{1} \defeq \brace*{\pi(1), \dotsc, \pi(1+k)}$ and $J_{1} \defeq \brace*{\sigma(1+k), \dotsc, \sigma(n)}$, and notice that

\begin{equation*}
\abs*{I_{1} \cap J_1} = \abs{I_1} + \abs{J_1} - \abs{I_1 \cup J_1} \geq (1+k) + (n-k) - n = 1.
\end{equation*}

Therefore, we have

\begin{equation*}
(a+b)_{1+k}^{*} = a_{\pi(1+k)} + b_{\pi(1 + k)} = \max\brace*{a_i + b_i \mid i \in I_1} \geq \max\brace*{a_i + b_{i} \mid i \in I_1 \cap J_1} \geq a_{\sigma(1+k)},
\end{equation*}

where the last inequality uses the non-negativity of $b$. Similarly, for the third term, define the sets $I_2 \defeq \brace*{\pi(1), \dotsc, \pi(n-k)}$ and $J_2 \defeq \brace*{\sigma(n-k), \dotsc, \sigma(n)}$, and notice that

\begin{equation*}
\abs*{I_{2} \cap J_2} = \abs{I_2} + \abs{J_2} - \abs{I_2 \cup J_2} \geq (n-k) + (1+k) - n = 1.
\end{equation*}

Therefore, we get

\begin{equation*}
(a+b)_{n-k}^{*} = a_{\pi(n-k)} + b_{\pi(n-k)} = \max\brace*{a_i + b_i \mid i \in I_2} \geq \max\brace*{a_i + b_{i} \mid i \in I_2 \cap J_2} \geq a_{\sigma(n-k)},
\end{equation*}

where again we used the non-negativity of $b$ in the last inequality. It remains to lower bound the second term. Let $S^{*} \subset I_2$ such that $\abs{S} = k$ and $\brace*{\sigma(1), \dotsc, \sigma(k)} \cap I_{2} \subset S$. Notice that

\begin{align*}
\sum_{i=k+1}^{n-k} (a+b)_{i}^{*} &=  \sum_{i=k+1}^{n-k} (a_{\pi(i)} + b_{\pi(i)}) \\
&= \max_{\substack{S \subset I_2 \\ \abs{S} = k}} \sum_{i \in I_2 \setminus S} (a_{i} + b_i) \\
&\geq  \sum_{i \in I_{2} \setminus S^{*}} a_i +  \sum_{i \in I_{2} \setminus S^{*}} b_i
\end{align*}

Let us further bound each term. For the first, notice that by definition of $S^{*}$, we have $(I_{2} \setminus S^{*}) \subset J_{1}$ and $\abs*{I_2 \setminus S^{*}} = n-2k$, therefore

\begin{equation*}
\sum_{i \in I_{2} \setminus S^{*}} a_i \geq \min_{\substack{T \subset J_1 \\ \abs*{T} = n-2k}}  \sum_{i \in T} a_i =  \sum_{i=k+1}^{n-k} a_{\sigma(i)}.
\end{equation*}

For the second, we have

\begin{equation*}
\sum_{i \in I_2 \setminus S^{*}} b_i \geq \min_{\substack{T \subset [n] \\ \abs*{T} = n-2k}}  \sum_{i \in T} b_i =  \sum_{i=1}^{n-2k} b_{i}^{*}
\end{equation*}

Combining the bounds yields the desired result.

§.§ Suprema of truncated empirical processes

Let $\mathcal{T}$ be a countable index set, and let $(\brace{Z_{i, s}}_{s \in \mathcal{T}})_{i=1}^{n}$ be independent real-valued $\mathcal{T}$-indexed stochastic processes. Define $Z \defeq \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} Z_{i, s}$. For $s \in \mathcal{T}$, define $Z_{s} \defeq (Z_{i, s})_{i=1}^{n}$. For Rademacher random variables $(\eps_i)_{i=1}^{n}$, define $\mu \defeq \Exp\brack*{\sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \eps_i Z_{i, s}}$. We assume throughout that $\sigma^{2} \defeq \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \Exp\brack*{Z_{i, s}^{2}} < \infty$. We start by recalling the following result.

Assume that for all $s \in \mathcal{T}$ and $i \in [n]$, $\Exp\brack*{Z_{i, s}} = 0$, and that $R \defeq \sup_{(s, i) \in \mathcal{T} \times [n]} \norm{Z_{i, s}}_{\infty} < \infty$. Define $v \defeq 2R\Exp\brack*{Z} + \sigma^{2}$. Then

\begin{equation*}
\Prob\paren*{Z \geq \Exp\brack*{Z} + t} \leq \exp\paren*{-\frac{4v}{9R^{2}}h\paren*{\frac{3Rt}{2v}}},
\end{equation*}

where $h(t) \defeq 1 + t - \sqrt{1 + 2t}$ with inverse $h^{-1}(t) = t + \sqrt{2t}$. Consequently, with probability at least $1-\delta$

\begin{equation*}
Z < \Exp\brack{Z} + \frac{3R \log(1/\delta)}{2} + \sqrt{2v\log(1/\delta)}. %\leq 2\Exp\brack*{Z} + \frac{5R\log(1/\delta)}{2} + \sqrt{2\sigma^{2} \log(1/\delta)}
\end{equation*}

The following result is due to Lugosi and Mendelson, 2021.

Let $T > 0$. Then with probability at least $1 - \delta$

\begin{multline*}
\sup_{s \in \mathcal{T}} \abs*{\brace*{i \in [n] \mid\abs{Z_{i, s}} > T}} \\
< \inf_{\eps \in (0, 1)} \brace*{\frac{2\mu}{\eps T} + \frac{\sigma^{2}}{(1-\eps)^{2}T^{2}} + \sqrt{\paren*{\frac{8\mu}{\eps T} + \frac{2\sigma^{2}}{(1-\eps)^{2}T^{2}}}\log(1/\delta)} + \frac{3\log(1/\delta)}{2}}.
\end{multline*}

Let $T > 0$ and $\eps \in (0, 1)$, and define the function $\chi_{T, \eps}: \R \to [0, 1]$ by

\begin{equation*}
\chi_{T, \eps}(x) \defeq \begin{dcases*}
0 & if $x \leq (1-\eps) T$ \\
\frac{x}{\eps T} - \frac{1-\eps}{\eps} & if $x \in ((1-\eps)T, T]$ \\
1 & if $x > T$.
\end{dcases*}
\end{equation*}

Note that $\mathbbm{1}_{(T, \infty)} \leq \chi_{T,\eps} \leq \mathbbm{1}_{((1-\eps)T, \infty)}$ and $\chi_{T, \eps}$ is $(1/\eps T)$-Lipschitz. Now we have

\begin{multline}
\label{eq:pf_lem5_1}
\sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \mathbbm{1}_{(T, \infty)}(\abs{Z_{i, s}}) \leq \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \chi_{T, \eps}(\abs{Z_{i, s}})
\\
\leq \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \underbrace{\chi_{T, \eps}(\abs{Z_{i, s}}) - \Exp\brack*{\chi_{T, \eps}(\abs{Z_{i, s}})}}_{\textstyle W_{i, s} \defeq } + \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \Exp\brack*{\chi_{T, \eps}(\abs{Z_{i, s}})}
\end{multline}

The second term of (<ref>) is bounded by

\begin{equation}
\label{eq:pf_lem5_2}
\sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \Exp\brack*{\chi_{T, \eps}(\abs{Z_{i, s}})} \leq \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \Prob\paren*{\abs{Z_{i, s}} > (1-\eps) T} \leq \frac{\sigma^{2}}{(1-\eps)^{2}T^{2}}.
\end{equation}

We now turn to the first term of (<ref>) which we denote by $W$. We note that $\Exp\brack{W_{i, s}} = 0$, $\abs{W_{i, s}} \leq 1$, so by Lemma <ref> we have with probability at least $1-\delta$

\begin{equation}
\label{eq:pf_lem5_3}
W < \Exp\brack*{W} + \frac{3\log(1/\delta)}{2} + \sqrt{2\paren*{2\Exp\brack{W} + \alpha^{2}} \log(1/\delta)},
\end{equation}

where $\alpha^{2} \defeq \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \Exp\brack{W_{i, s}^{2}}$.
It remains to bound $\Exp\brack{W}$ and $\alpha^2$. The former is bounded by

\begin{multline}
\label{eq:pf_lem5_4}
\Exp\brack*{W} = \Exp\brack*{\sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \chi_{T, \eps}(\abs{Z_{i, s}}) - \Exp\brack*{\chi_{T, \eps}(\abs{Z_{i, s}})}} \\
\leq 2 \Exp\brack*{\sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \eps_i \chi_{T, \eps}(\abs{Z_{i, s}})}
\leq \frac{2}{\eps T} \Exp\brack*{\sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \eps_i Z_{i,s}},
\end{multline}

where the first inequality is by symmetrization and the second by the contraction principle and the $(1/\eps T)$-Lipschitzness of $\chi_{T, \eps} \circ \abs{\cdot}$. The latter is bounded by

\begin{equation}
\label{eq:pf_lem5_5}
\alpha^2 = \sup_{s \in \mathcal{T}} \sum_{i=1}^{n}\Exp\brack*{W_{i, s}^{2}} \leq \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \Exp\brack*{\chi^{2}_{T, \eps}(\abs{Z_{i, s}})} \leq \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \Prob\paren*{\abs{Z_{i, s}} > (1 - \eps)T} \leq \frac{\sigma^{2}}{(1 - \eps)^{2}T^{2}}.
\end{equation}

Combining (<ref>), (<ref>), and (<ref>) yields that with probability at least $1 - \delta$

\begin{equation}
\label{eq:pf_lem5_6}
W < \frac{2\mu}{\eps T} + \sqrt{\paren*{\frac{8\mu}{\eps T} + \frac{2\sigma^{2}}{(1-\eps)^{2}T^{2}}} \log(1/\delta)} + \frac{3\log(1/\delta)}{2}
\end{equation}

Combining (<ref>), (<ref>), (<ref>), and optimizing over $\eps \in (0, 1)$ yields the result.

Using the same notation as in Lemma <ref>, we have with probability at least $1-\delta$

\begin{equation*}
\sup_{s \in \mathcal{T}} \abs*{\brace{i \in [n] \mid \abs{Z_{i, s}} > T_{0}}} < 8 \log(1/\delta),
\end{equation*}

\begin{equation*}
T_{0} \defeq 2 \max\brace*{\frac{\mu}{\log(1/\delta)}, \sqrt{\frac{\sigma^{2}}{\log(1/\delta)}}}.
\end{equation*}

The result follows from taking $\eps = 1/2$ in the bound of Lemma <ref>, replacing $T$ by $T_{0}$, and straightforwardly bounding the resulting expression.

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}$. Assume that for all $s \in \mathcal{T}$ and $i \in [n]$, $\Exp\brack*{Z_{i, s}} = 0$. Then with probability at least $1-\delta$

\begin{equation*}
\sup_{s \in \mathcal{T}} \abs*{\brace{i \in [n] \mid \abs{Z_{i, s}} > T_{0}}} < k,
\end{equation*}

\begin{equation*}
\sup_{s \in \mathcal{T}} \varphi_{k}(Z_{s}) \leq 50 \max\brace*{\mu, \sqrt{\sigma^{2} \log(2/\delta)}}.
\end{equation*}

\begin{equation*}
T_{0} \defeq 2 \max\brace*{\frac{\mu}{\log(1/\delta)}, \sqrt{\frac{\sigma^{2}}{\log(1/\delta)}}}.
\end{equation*}

By Lemma <ref>, with probability at least $1-\delta/2$, we have for all $s \in \mathcal{T}$

\begin{equation*}
-T_{0} \leq Z^{*}_{1 + k, s} \leq Z^{*}_{n - k, s} \leq T_{0}.
\end{equation*}

\begin{align}
\sup_{s \in \mathcal{T}} \varphi_{k}(Z_{s}) &= \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \phi_{Z^{*}_{1+k, s}, Z^{*}_{n-k, s}}(Z_{i, s}) \nonumber\\
&= \sup_{s \in \mathcal{T}}  \sum_{i=1}^{n} \phi_{-T_{0}, T_{0}}(Z_{i, s}) + k (Z_{1 + k, s} + T_{0}) + \underbrace{k(Z^{*}_{n-k, s} - T_{0})}_{\textstyle \leq 0} \nonumber \\
&\leq \sup_{s \in \mathcal{T}}  \sum_{i=1}^{n} \underbrace{\phi_{-T_{0}, T_{0}}(Z_{i, s}) - \Exp\brack*{\phi_{-T_{0}, T_{0}}(Z_{i, s})}}_{\textstyle W_{i, s} \defeq} + \sup_{s \in \mathcal{T}}  \sum_{i=1}^{n} \Exp\brack*{\phi_{-T_{0}, T_{0}}(Z_{i, s})} + 2kT_{0}. \label{eq:pf_lem7_1}
\end{align}

We now bound the second term of (<ref>) by

\begin{align}
\sup_{s \in \mathcal{T}}  \sum_{i=1}^{n} \Exp\brack*{\phi_{-T_{0}, T_{0}}(Z_{i, s})} &= \sup_{s \in \mathcal{T}}  \sum_{i=1}^{n} \underbrace{\Exp\brack*{Z_{i, s}}}_{\textstyle = 0} + \underbrace{\Exp\brack*{(T_{0} - Z_{i, s})\mathbbm{1}_{(T_0, \infty)}(Z_{i, s})}}_{\textstyle \leq 0} \\
&+ \Exp\brack*{(-T_{0} - Z_{i, s}) \mathbbm{1}_{(-\infty, -T_{0})}(Z_{i, s})} \nonumber \\
&\leq \sup_{s \in \mathcal{T}}  \sum_{i=1}^{n} \Exp\brack*{Z_{i, s}^{2}}^{1/2} \cdot \Prob\paren*{Z_{i, s} < -T_{0}}^{1/2} \leq \frac{\sigma^2}{T_{0}},
\label{eq:pf_lem7_2}
\end{align}

where we used the Cauchy-Schwarz inequality and Markov's inequality respectively. Denote the first term of (<ref>) by $W$, and note that $\Exp\brack*{W_{i, s}} = 0$ and $\abs{W_{i, s}} \leq 2T_{0}$, so by Lemma <ref> we have with probability at least $1-\delta/2$

\begin{equation}
\label{eq:pf_lem7_3}
W < \Exp\brack*{W} + 2T_{0} \log(2/\delta) + \sqrt{2 (4T_{0}\Exp\brack{W} + \alpha^{2}) \log(2/\delta)},
\end{equation}

where $\alpha \defeq \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \Exp\brack*{W_{i, s}^{2}}$. It remains to bound $\Exp\brack{W}$ and $\alpha^{2}$. The former is bounded by

\begin{multline}
\label{eq:pf_lem7_4}
\Exp\brack*{W} = \Exp\brack*{\sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \phi_{-T_{0}, T_{0}}(Z_{i, s}) - \Exp\brack*{\phi_{-T_{0}, T_{0}}(Z_{i, s})}} \\ \leq 2\Exp\brack*{\sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \eps_i \phi_{-T_{0}, T_{0}}(Z_{i, s})} \leq 2 \Exp\brack*{\sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \eps_i Z_{i, s}},
\end{multline}

where we used symmetrization and the contraction principle along with the $1$-Lipschitzness of $\phi_{-T_{0}, T_{0}}$ respectively. The latter is bounded by

\begin{equation}
\label{eq:pf_lem7_5}
\alpha^{2} \leq \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \Exp\brack*{W^{2}_{i, s}} \leq \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \Exp\brack*{\phi^{2}_{-T_0, T_0}(Z_{i, s})} \leq \sup_{s \in \mathcal{T}} \sum_{i=1}^{n} \Exp\brack*{Z^{2}_{i, s}}
\end{equation}

Combining (<ref>), (<ref>), (<ref>), and using the definition of $T_{0}$, we obtain with probability at least $1-\delta/2$

\begin{equation}
\label{eq:pf_lem7_6}
W < 16 \max\brace*{\mu, \sqrt{\sigma^{2} \log(1/\delta)}}
\end{equation}

Combining (<ref>), (<ref>), (<ref>), and the definition of $T_{0}$ yields the result.

§ PROOFS OF SECTION <REF>

§.§ Proof of Theorem <ref>

By definition of the minimax risk, we have

\begin{align*}
R^{*}_{\delta}(\ell) = \inf_{d} R_{\delta}(\ell, d)
= \inf_{d} \sup_{P \in \mathcal{P}} R_{\delta}(\ell, P, d)
= \inf_{d} \sup_{P \in \mathcal{P}} Q_{\ell(P, d(O))}(1-\delta)
= \inf_{d} \sup_{P \in \mathcal{P}} F^{-}_{\ell(P, d(O))}(1-\delta).
\end{align*}

Applying the sixth item of Lemma <ref> to the last expression yields

\begin{equation*}
R^{*}_{\delta}(\ell) = \inf_{d} \paren*{\inf_{P \in \mathcal{P}} F_{\ell(P, d(O))}}^{-}(1-\delta).
\end{equation*}

Now let $k \in \N$. Since $\inf_{P \in \mathcal{P}} F_{\ell(P, d(O))} \leq \Exp_{P \sim \pi_{k}}\brack*{F_{\ell(P, d(O)) \mid P}} =  F^{\pi_{k}}_{\ell(P, d(O))}$, where $O \mid P \sim P$ inside the expectation, we have by the second item of Lemma <ref>

\begin{equation*}
R^{*}_{\delta}(\ell) \geq \inf_{d} \paren*{F^{\pi_{k}}_{\ell(P, d(O))}}^{-1}(1-\delta) \geq \paren*{\sup_{d} F^{\pi_{k}}_{\ell(P, d(O))}}^{-}(1-\delta) = p_{\ell, k}^{-}(1-\delta).
\end{equation*}

where the second inequality follows from the third item of Lemma <ref>, and the last by definition of $p_{\ell, k}$. Taking supremum over $k$, and combining our assumptions on the sequence $(p_{\ell, k})_{k \in \N}$ with the last item of Lemma <ref>  yields the result.

§.§ Proof of Proposition <ref>

The first statement follows from the assumption on $\varphi$ and Lemma <ref>. For the second statement, define $S \defeq \brace*{R_{\delta}(\ell, P, d) \st P \in \mathcal{P}} \subset [-\infty, \infty)$ and $x_0 \defeq \sup S$. If $x_{0} = -\infty$, then $\varphi(x_0) = -\infty$, and $\varphi(\ell(P, d(O)))) = \ell(P, d(O)) = -\infty$ with probability at least $1-\delta$ for all $P$, so the statement holds. Otherwise $x_0 \in \R$. Now for any $x \in S$, we have $x \leq x_{0}$, so $\varphi(x) \leq \varphi(x_0)$, and hence $\sup_{x \in S} \varphi(x) \leq \varphi(x_0)$. On the other hand, let $(x_k)_{k \in \N}$ be an increasing sequence in $S$ such that $x_k \to x_{0}$ as $k \to \infty$. Then by the left-continuity of $\varphi$, we obtain $\sup_{x \in S} \varphi(x) \geq \lim_{k \to \infty}\varphi(x_k) = \varphi(x_0)$, which proves the statement. For the last statement, suppose that $d^{*} \in \argmin_{d} R_{\delta}(\ell, d)$, then by assumption $R_{\delta}(\ell, d^{*}) < \infty$, so that by the second statement $R_{\delta}(\varphi \circ \ell, d^{*}) = \varphi\paren*{R_{\delta}(\ell, d^{*})}$. Now let $d$ be any other decision rule. If $R_{\delta}(\ell, d) < \infty$, then by the minimality of $d^{*}$ we get $R_{\delta}(\ell, d^{*}) \leq R_{\delta}(\ell, d)$, and since $\varphi$ is increasing and using the second statement again, $R_{\delta}(\varphi \circ \ell, d^{*}) = \varphi\paren*{R_{\delta}(\ell, d^{*})} \leq \varphi\paren*{R_{\delta}(\ell, d)} = R_{\delta}(\varphi \circ \ell, d)$. If $R_{\delta}(\ell, d) = \infty$ then there exists $P_{0} \in \mathcal{P}$ such that $R_{\delta}(\ell, P_{0}, d) \geq R_{\delta}(\ell, d^{*})$, but then since $\varphi$ is increasing, $R_{\delta}(\varphi \circ \ell, d) = \sup_{P \in \mathcal{P}} R_{\delta}(\varphi \circ \ell, P, d) \geq \varphi(R_{\delta}(\ell, P_{0}, d)) \geq \varphi(R_{\delta}(\ell, d^{*})) = R_{\delta}(\varphi \circ \ell, d^{*})$. This proves the last statement.

§.§ Proof of Proposition <ref>

We present here the proof for the case $\varphi(x) = x$. The general statement follows from Proposition <ref>. Our aim is to apply Theorem <ref>. We select $\pi_k \defeq \mathcal{N}(0, \Sigma/\lambda_k)$ for a decreasing strictly positive sequence $(\lambda_k)_{k \in \N}$ satisfying $\lambda_k \to 0$ as $k \to \infty$. We want to compute, for all $t \in \R$,

\begin{equation*}
p_{\ell, k}(t) = \sup_{\hat{\mu}} \Prob\paren*{e\paren*{\hat{\mu}((X_i)_{i=1}^{n} - \mu)} \leq t},
\end{equation*}

where $\mu \sim \pi_k$ and $X_i \mid \mu \sim \mathcal{N}(\mu, \Sigma)$ for all $i \in [n]$ independently. A classical Bayesian calculation shows that
$\mu \mid (X_i)_{i=1}^{n} \sim \mathcal{N}\paren*{\overline{X}_k, \Sigma_{k}}$ where $\overline{X}_k \defeq \frac{n}{n+\lambda_k} \overline{X}$ and $\Sigma_k \defeq \frac{1}{n + \lambda_k} \Sigma$, where $\overline{X} \defeq n^{-1}\sum_{i=1}^{n}X_i$ is the sample mean.
Now we compute, for $Z_{k} \sim \mathcal{N}(0, \Sigma_{k})$,

\begin{align*}
p_{\ell, k}(t) &= \sup_{\hat{\mu}} \Prob\paren*{e\paren*{\hat{\mu}((X_i)_{i=1}^{n} - \mu)} \leq t} \\
&= \Exp\brack*{\sup_{a \in \R^{d}} \Prob\paren*{e\paren*{\mu - a} \leq t \st (X_i)_{i=1}^{n}}} \\
&= \Exp\brack*{\sup_{a \in \R^{d}} \Prob\paren*{\mu - a \in e^{-1}((-\infty, t]) \mid (X_i)_{i=1}^{n}}} \\
&= \Exp\brack*{\Prob\paren*{\mu - \overline{X}_{k} \in e^{-1}((-\infty, t] \mid (X_i)_{i=1}^{n}}} \\
&= \Prob\paren*{e(Z_{k}) \leq t} = F_{e(Z_k)}(t)
\end{align*}

The second line follows from conditioning on $(X_i)_{i=1}^{n}$ and the symmetry of $e$. The fourth line follows from combining the assumptions on $e$ with the first item of Lemma <ref>, as well as an application of Lemma <ref>, known as Anderson's Lemma. The last line follows from the fact that $\mu - \overline{X}_k \mid (X_i)_{i=1}^{n} \overset{d}{=} Z_k$. To conclude it remains to prove the needed properties for the sequence $(p_{\ell, k})_{k \in N}$. The right-continuity follows directly from the fact that $F_{e(Z_k)}$ is a CDF. To see that the sequence is decreasing, define $n_k \defeq n + \lambda_k$ and note that $n_{k} \geq n_{k+1}$. Then, for all $t \in \R$

\begin{multline*}
F_{e(Z_k)}(t) = \Prob\paren*{e(Z_k) \leq t}
= \Prob\paren*{Z_k \in e^{-1}((-\infty, t])}
= \Prob\paren*{\sqrt{\frac{n_{k+1}}{n_k}} \cdot Z_{k+1} \in e^{-1}((-\infty, t])} \\
= \Prob\paren*{Z_{k+1} \in \sqrt{\frac{n_{k}}{n_{k+1}}} \cdot  e^{-1}((-\infty, t])}
\geq \Prob\paren*{Z_{k+1} \in e^{-1}((-\infty, t])}
= F_{e(Z_{k+1})}(t),
\end{multline*}

where the inequality follows from the fact that $\sqrt{n_k/n_{k+1}} \geq 1$, $e^{-1}((-\infty, t]$ is convex and symmetric, and Lemma <ref>. Finally, let $Z \sim \mathcal{N}(0, \Sigma/n)$. We compute

\begin{multline*}
\lim_{k \to \infty} F_{e(Z_k)}(t) = \lim_{k \to \infty} \Prob\paren*{Z_k \in e^{-1}((-\infty, t])}
= \lim_{k \to \infty} \Prob\paren*{Z \in \sqrt{\frac{n_k}{n}} \cdot e^{-1}((-\infty, t])} \\
= \Prob\paren*{Z \in \bigcap_{k=1}^{\infty} \brace*{\sqrt{\frac{n_k}{n}} \cdot e^{-1}((-\infty,t])}}
= \Prob\paren*{Z \in e^{-1}((-\infty, t])}
= F_{e(Z)}(t),
\end{multline*}

Finally, the worst-case risk of the sample mean is given by $Q_{e(Z)}(1 - \delta)$ as can be checked with a simple explicit calculation. An application of Theorem <ref> concludes the proof.

§.§ Proof of Proposition <ref>

We aim at applying Theorem <ref>. We select $\pi_k \defeq \text{Inv-Gamma}(\lambda_k, \lambda_k)$ for a decreasing strictly positive sequence $(\lambda_k)_{k=1}^{\infty}$ satisfying $\lambda_k \to 0$ as $k \to \infty$. We need to compute

\begin{equation*}
p_{\ell, k}(t) = \sup_{\hat{\sigma}} \Prob\paren*{\log\paren*{\frac{\sigma^{2}}{\hat{\sigma}^{2}((X_i)_{i=1}^{n})}} \leq t},
\end{equation*}

where $\sigma^{2} \sim \pi_k$ and $X_i \mid \sigma^2 \sim \mathcal{N}(\mu, \sigma^2)$ for all $i \in [n]$ independently. A classical Bayesian calculation shows that $\sigma^2 \mid (X_i)_{i=1}^{n} \sim \text{Inv-Gamma}(\alpha_k, \beta_k)$, where $\alpha_k \defeq n/2 + \lambda_k$ and $\beta_k \defeq \lambda_k + \sum_{i=1}^{n}(X_i - \mu)^{2}/2$. Recalling the definition of the fucntion $p_{\alpha}$ from the statement, we obtain

\begin{align*}
\sup_{\hat{\sigma}} \Prob\paren*{\log\paren*{\frac{\sigma^{2}}{\hat{\sigma}^{2}((X_i)_{i=1}^{n})}} \leq t}
= \Exp\brack*{\sup_{b \in (0, \infty)} \Prob\paren*{\log\paren*{\frac{\sigma^{2}}{b}} \leq t \st (X_i)_{i=1}^{n}}} = \Exp\brack*{p_{\alpha_k}(t)} = p_{\alpha_k}(t)
\end{align*}

where the last equality follows from Lemma <ref>. It is straightforward to check that $p_{\alpha}$ is continuous for all values of $\alpha \in (0, \infty)$. Furthermore, by Lemma <ref>, the sequence $(p_{\alpha_k})_{k \in \N}$ is decreasing with limit $p_{n/2}$. This provides us with the first part needed for Theorem <ref>. Now note that, for any $\sigma^{2} \in (0, \infty)$ and $X_i \sim \mathcal{N}(\mu, \sigma^2)$ for all $i \in [n]$ and independently, we have $(n \cdot \sigma^2)/\sum_{i=1}^{n}(X_i - \mu)^{2} \sim \text{Inv-Gamma}(n/2, n/2)$, so that for the estimator $\hat{\sigma}^{2}$ 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*}

and therefore the worst-case risk of this estimator is equal to $p_{n/2}^{-1}(1-\delta)$. Applying Theorem <ref> proves the minimaxity of this estimator. An explicit calculation of the worst-case risk of the sample variance combined with the uniqueness of the minimizer in Lemma <ref> shows that it is not minimax.

We start with the lower bound. Let $k \in \N$. Then

\begin{align}
\inf_{\hat{\sigma}^{2}} \sup_{P \in \mathcal{P}_{\text{Gauss}}(\mu)} R_{n, \delta}(P, \hat{\sigma}^{2}) &= \inf_{\hat{\sigma}^{2}} \sup_{P \in \mathcal{P}_{\text{Gauss}}(\mu)} Q_{\abs{\log(\sigma^{2}/\hat{\sigma}^{2}((X_i)_{i=1}^{n}))}}(1-\delta) \nonumber \\
&= \inf_{\hat{\sigma}^{2}} \sup_{\sigma^{2} \in (0, \infty)} F^{-1}_{\abs{\log(\sigma^{2}/\hat{\sigma}^{2}((X_i)_{i=1}^{n}))}} (1-\delta) \nonumber \\
&= \inf_{\hat{\sigma}^{2}} \paren*{\inf_{\sigma^{2} \in (0, \infty)} F_{\abs{\log(\sigma^{2}/\hat{\sigma}^{2}((X_i)_{i=1}^{n}))}}}^{-1}(1-\delta) \nonumber \\
&\geq \inf_{\hat{\sigma}^{2}} \paren*{\Exp_{\sigma^{2} \sim \text{Inv-Gamma}(k^{-1}, k^{-1})}\brack*{F_{\abs{\log(\sigma^{2}/\hat{\sigma}^{2}((X_i)_{i=1}^{n}))} \mid \sigma^{2}}}}^{-1}(1-\delta) \nonumber \\
&= \inf_{\hat{\sigma}^{2}} F^{-1}_{\abs{\log(\sigma^{2}/\hat{\sigma}^{2}((X_i)_{i=1}^{n}))}}(1-\delta) \label{eq:pf_thm_2_1}
\end{align}

By a classical Bayesian calculation, we get that $\sigma^{2} \mid (X_i)_{i=1}^{n} \sim \Gamma^{-1}(\alpha_{k}, \beta_{k})$ where

\begin{equation*}
\alpha_k \defeq \frac{1}{k} + \frac{n}{2} \quad \beta_k \defeq \frac{1}{k} + \frac{\sum_{i=1}^{n} (X_i - \mu)^{2}}{2}.
\end{equation*}

Recall the definition of $p_{\alpha}(r)$ from Lemma <ref>, we have by the same Lemma, for all $r > 0$ and for all $\hat{\sigma}^{2}$

\begin{align*}
F_{\abs{\log(\sigma^2/\hat{\sigma}^{2}((X_i)_{i=1}^{n}))} \mid (X_i)_{i=1}^{n}}(r) \leq p_{\alpha_k}(r)
\end{align*}

Taking expectation of both sides, noticing that $p_{\alpha_k}(r)$ does not depend on $(X_i)_{i=1}^{n}$, and using the fourth item of Lemma <ref> yields

\begin{equation}
\label{eq:pf_thm_2_2}
\inf_{\hat{\sigma}^2} F^{-1}_{\abs{\log(\sigma^2/\hat{\sigma}^{2}((X_i)_{i=1}^{n}))}} \geq p_{\alpha_k}^{-1}
\end{equation}