Minimax risks for sparse regressions: Ultra-high-dimensional phenomenons

Introduction

In many important statistical applications, including remote sensing, functional MRI and gene expressions studies the number $p$ of parameters is much larger than the number $n$ of observations. An active line of research aims at developing computationally fast procedures that also achieve the best possible statistical performances in this “$p$ larger than $n$” setting. A typical example is the study of $l_{1}$-based penalization methods for the estimation of linear regression models. However, if $p$ is really too large compared to $n$, all these new procedures fail to achieve a good estimation.

Thus, there is a need to understand the intrinsic limitations of a statistical problem: what is the best rate of estimation or testing achievable by a procedure? Is it possible to design good procedures for arbitrarily large $p$ or are there theoretical limitations when $p$ becomes “too large”? These limitations tell us what kind of data analysis problems are too complex so that no statistical procedure is able to provide reasonable results. Furthermore, the knowledge of such limitations may drive the research towards areas where computationally efficient procedures are shown to be suboptimal.

where the vector $\theta_{0}$ of size $p$ is unknown and the random vector $\boldsymbol{\epsilon}$ follows a centered normal distribution $\mathcal{N}(0_{n},\sigma^{2}I_{n})$. Here, $0_{n}$ stands for the null vector of size $n$ and $I_{n}$ for the identity matrix of size $n$.

In some cases, the design ${\bf X}$ is considered as fixed either because it has been previously chosen or because we work conditionally to the design. In other cases, the rows of the design matrix ${\bf X}$ correspond to a $n$-sample of a random vector $X$ of size $p$. The design ${\bf X}$ is then said to be random. A specific class of random design is made of Gaussian designs where $X$ follows a centered normal distribution $\mathcal{N}(0_{p},\Sigma)$. The analysis of fixed and Gaussian designs share many common points. In this work, we shall enhance the similarities and the differences between both settings.

There are various statistical problems arising in the linear regression model (1.1). Let us list the most classical issues:

$({\bf P_{4}}):$ Support estimation aims at recovering the support of $\theta_{0}$, that is the set of indices corresponding to non-zero coefficients. The easier problem of dimension reduction amounts to estimate a set $\widehat{M}\subset\{1,\ldots p\}$ of “reasonable” size that contains the support of $\theta_{0}$ with high probability.

Much work have been devoted to these statistical questions in the so-called high-dimensional setting, where the number of covariates $p$ is possibly much larger than $n$. A classical approach to perform a statistical analysis in this setting is to assume that $\theta_{0}$ is sparse, in the sense that most of the components of $\theta_{0}$ are equal to $0$. For the problem of prediction (${\bf P_{2}}$), procedures based on complexity penalization are proved to provide good risk bounds for known variance and unknown variance but are computationally inefficient. In contrast, convex penalization methods such as the Lasso or the Dantzig selector are fast to compute, but only provide good performances under restrictive assumptions on the design ${\bf X}$ (e.g. ). Exponential weighted aggregation methods are another example of fast and efficient methods. The $l_{1}$ penalization methods have also been analyzed for the inverse problem (${\bf P_{3}}$) and for support estimation (${\bf P_{4}}$) . Dimension reduction methods are often studied in more general settings than linear regression . In the linear regression model, the SIS method based on the correlation between the response and the covariates allows to perform dimension reduction. The problem of high-dimensional hypothesis testing (${\bf P_{1}}$) has so far attracted less attention. Some testing procedures are discussed in for fixed design and in for Gaussian design.

2 Sparsity and ultra-high dimensionality

In linear regression, most of the results about classical procedures require that the triplet $(k,n,p)$ satisfies $k[1+\log(p/k)]<n$. When $k$ is “small”, this corresponds to assuming that $p$ is subexponential with respect to $n$. The analysis of the Lasso in prediction, inverse problems , and support estimation entail such assumptions. In dimension reduction, the SIS method also requires this assumption. If the multiple testing procedure of can be analyzed for $k[1+\log(p/k)]$ larger than $n$, it exhibits a much slower rate of testing in this case. In noiseless problems ($\sigma=0$), compressed sensing methods fail when $k[1+\log(p/k)]$ is large compared to $n$ (see for numerical illustrations). In the sequel, we say that the problem is ultra-high dimensional In some papers, the expression ultra-high dimensional has been used to characterize problems such that $\log(p)=O(n^{\beta})$ with $\beta<1$. We argue in this paper that that as soon as $k\log(p)/n$ goes to $0$, the case $\log(p)=O(n^{\beta})$ is not intrinsically more difficult than conditions such as $p=O(n^{\delta})$ with $\delta>0$. when $k[1+\log(p/k)]$ is large compared to $n$. Observe that ultra-high dimensionality does not necessarily imply that $p$ is exponential with respect to $n$. As an example, taking $p=n^{3}$ and $k=n/\log\log(n)$ asymptotically yields an ultra-high dimensional problem.

Why should we care about ultra-high dimensional problem? In this setting, there are so many variables that statistical questions such as the estimation of $\theta_{0}$ (${\bf P_{3}}$) or its support (${\bf P_{4}}$) are likely to be difficult. Nevertheless, if the signal over noise ratio is large, do there exist estimators that perform relatively well? The answer is no. We prove in this paper that a phase transition phenomenon occurs in an ultra-high dimensional setting and that most of the estimation and testing problems become hopeless. This phase transition phenomenon implies that some statistical problems that are tackled in postgenomic of functional MRI cannot actually be addressed properly.

In some gene network inference problems (e.g. ), the number $p$ of genes can be as large as 5000 while the number $n$ of microarray experiments is only of order 50. Let us consider a gene $A$. We note $\mathcal{G}_{A}$ the set of genes that interact with the gene $A$ and $k$ stands for the cardinality of $\mathcal{G}_{A}$. How large can be $k$ so that it is still “reasonable” to estimate $\mathcal{G}_{A}$ from the microarray experiments? In statistical terms, inferring the set of genes interacting with $A$ amounts to estimate the support of a vector $\theta_{0}$ in a linear regression model (see e.g. ). Our answer is that if $k$ is larger than $4$, then the problem of network estimation becomes extremely difficult. We will come back to this example and explain this answer in Section 7.

3 Minimax risks

We say that an estimator $\widehat{\theta}$ is minimax if its maximal risk over $\Theta[k,p]$ is close to the minimax risk.

In practice, we do not know the number $k$ of non-zero components of $\theta_{0}$ and we seldom know the variance $\sigma^{2}$ of the error. If an estimator $\widehat{\theta}$ does not require the knowledge of $k$ and nearly achieves the minimax risk over $\Theta[k,p]$ for a range of $k$, we say that $\widehat{\theta}$ is adaptive to the sparsity. Similarly, an estimator $\widehat{\theta}$ is adaptive to the variance $\sigma^{2}$, if it does not require the knowledge of $\sigma^{2}$ and nearly achieves the minimax risk for all $\sigma^{2}>0$. When possible, the main challenge is to build adaptive procedures. In some statistical problems considered here, adaptation is in fact impossible and there is an unavoidable loss when the variance or the sparsity parameter is unknown. In such situations, it is interesting to quantify this unavoidable loss.

4 Our contribution and related work

In the specific case of the Gaussian sequence model, where $n=p$ and ${\bf X}=I_{n}$, the minimax risks over $k$-sparse vectors have been studied for a long time. Donoho and Johnstone have provided the asymptotic minimax risks of prediction $({\bf P_{2}})$. Baraud has studied the optimal rate of testing from a non-asymptotic point of view while Ingster has provided the asymptotic optimal rate of testing with exact constants.

Recently, some high-dimensional problems have been studied from a minimax point of view. Wainwright provides minimax lower bounds for the problem of support estimation (${\bf P_{4}}$). Raskutti et al. and Rigollet and Tsybakov have provided minimax upper bounds and lower bounds for $({\bf P_{2}})$ and $({\bf P_{3}})$ over $l_{q}$ balls for general fixed designs ${\bf X}$ when the variance $\sigma^{2}$ is known (see also Ye and Zhang and Abramovich and Grinshtein ). Arias-Castro et al. and Ingster et al. have computed the asymptotic minimax detection boundaries for the testing problem $({\bf P_{1}})$ for some specific designs. However, their study only encompasses reasonable dimensional problems ($p$ grows polynomially with $n$). Some minimax lower bounds have also been stated for testing (${\bf P_{1}}$) and prediction (${\bf P_{2}}$) problems with Gaussian design . All the aforementioned results do not cover the ultra-high dimensional case and do not tackle the problem of adaptation to both $k$ and $\sigma$.

This paper provides minimax lower bounds and upper bounds for the problems (${\bf P_{1}}$), (${\bf P_{2}}$), (${\bf P_{3}}$) when the regression vector $\theta_{0}$ is $k$-sparse for fixed and random designs, known and unknown variance, known and unknown sparsities. The lower and upper bounds match up to possible differences in the logarithmic terms. The main discoveries are the following:

Phase transition in an ultra-high dimensional setting. Contrary to previous work, our results cover both the high-dimensional and ultra-high dimensional setting. We establish that for each of the problems (${\bf P_{1}}$), (${\bf P_{2}}$) and (${\bf P_{3}}$), an elbow effect occurs when $k\log(p/k)$ becomes large compared to $n$. Let us emphasize the difference between the high-dimensional and the ultra-high dimensional regimes for two problems: prediction (${\bf P_{2}}$) and support estimation (${\bf P_{4}}$).

Prediction with random design. In the (non-ultra) high-dimensional setting, the minimax risk of prediction for a random design regression is of order $\sigma^{2}k\log(p/k)/n$ (see Section 3). Thus, the effect of the sparsity $k$ is linear and the effect of the number of variables $p$ is logarithmic. In an ultra-high dimensional setting, that is when $k\log(p/k)/n$ is large, we establish that an elbow effect occurs in the minimax risk. In this setting, the minimax risk becomes of order $\sigma^{2}\exp[Ck\{1+\log(p/k)\}/n]$, where $C$ is a positive constant : it grows exponentially fast with $k$ and polynomially with $p$ (see the red curve in Figure 1). If it was expected that the minimax risk cannot be small for such problems, we prove here that the minimax risk is in fact exponentially larger than the usual $k\log(p/k)/n$ term.

Support estimation. In a non-ultra high dimensional setting it is known that under some assumptions on the design ${\bf X}$ (e.g. each component of ${\bf X}$ is drawn from iid. standard normal distribution) the support of a $k$-sparse vector $\theta_{0}$ is recoverable with high probability if

where $C$ is a numerical constant. In an ultra-high dimensional setting, even if

Adaptation to the sparsity $k$ and to the variance $\sigma^{2}$. Most theoretical results for the problems (${\bf P_{1}}$) and (${\bf P_{2}}$) require that the variance $\sigma^{2}$ is known. Here, we establish these minimax bounds for both known and unknown variance and known and unknown sparsity. The knowledge of the variance is proved to play a fundamental role for the testing problem (${\bf P_{1}}$) when $k[1+\log(p/k)]$ is large compared to $\sqrt{n}$. The knowledge of $\sigma^{2}$ is also proved to be crucial for (${\bf P_{2}}$) in an ultra-high dimensional setting. Thus, specific work is needed to develop fast and efficient procedures that do not require the knowledge of the variance. Furthermore, variance estimation is extremely difficult in an ultra-high dimensional setting.

Effect of the design. Lastly, the minimax bounds of $({\bf P_{1}})$, $({\bf P_{2}})$ and $({\bf P_{3}})$ are established for fixed and Gaussian designs. Except for the problem of prediction $({\bf P_{2}})$, the minimax risks are shown to be of the same nature for both forms of the design. Furthermore, we investigate the dependency of the minimax risks on the design ${\bf X}$ (resp. $\Sigma$) in Sections 4-6.

The minimax bounds stated in this paper are non asymptotic. While some upper bounds are consequences of recent results in the literature, most of the effort is spent here to derive the lower bound. These bounds rely on Fano’s and Le Cam’s methods and on geometric considerations. In each case, near optimal procedures are exhibited.

5 Organization of the paper

In Section 3, we summarize the minimax bounds for specific designs called “worst-case” and “best-case” designs in order to emphasize the effects of dimensionality. The general results are stated in Section 4 for the tests and Section 5 for the problem of prediction. The problems of inverse estimation, support estimation, and dimension reduction are studied in Section 6. In Section 7, we address the following practical question: For exactly what range of $(k,p,n)$ should we consider a statistical problem as ultra-high dimensional? A small simulation study illustrates this answer. Section 8 contains the final discussion and side results about variance estimation. Section 9 is devoted to the proof of the mains minimax lower bounds. Specific statistical procedures allow to establish the minimax upper bounds. Most of these procedures are used as theoretical tools but should not be applied in a high dimensional setting because they are computationally inefficient. In order to clarify the statements of the results in Sections 4–6, we postpone the definition of these procedures to Section 10. The remaining proofs are described in a technical appendix .

Notations and preliminaries

As explained later, the minimax risk over $\Theta[k,p]$ strongly depends on the design ${\bf X}$. This is why we introduce some relevant quantities on ${\bf X}$.

Consider some integer $k>0$ and some design ${\bf X}$.

In fact, $\varPhi_{k,+}({\bf X})$ and $\varPhi_{k,-}({\bf X})$ respectively correspond to the largest and the smallest restricted eigenvalue of order $k$ of ${\bf X}^{T}{\bf X}$.

Given a symmetric real square matrix $A$, $\varphi_{\max}(A)$ stands for the largest eigenvalue of $A$. Finally, $C$, $C_{1}$,$\ldots$ denote positive universal constants that may vary from line to line. The notation $C(.)$ specifies the dependency on some quantities.

In the propositions, the constants involved in the assumptions are not always expressly specified. For instance, sentences of the form “Assume that $n\geq C$. Then, $\ldots$” mean that “There exists an universal $C>0$ such that if $n\geq C$, then $\ldots$”.

Main results

The exact bounds are stated in Section 4–6. In order to explain these results, we now summarize the main minimax bounds by focusing on the role of $(k,n,p)$ rather than on the dependency on the design ${\bf X}$. In order to keep the notations short, we do not provide in this section the minimal assumptions of the results. Let us simply mention that all of them are valid if the sparsity $k$ satisfies $k\leq(p^{1/3})\wedge(n/5)$ and that $p\geq n\geq C$ where $C$ a positive numerical constant.

First, the results are described for the problem of prediction (${\bf P_{2}}$) since the problem of minimax estimation is more classical in this setting. Different prediction loss functions are used for fixed and Gaussian designs. When the design is considered as fixed, we study the loss $\|{\bf X}(\theta_{1}-\theta_{2})\|_{n}^{2}/(n\sigma^{2})$. For Gaussian design, we consider the integrated prediction loss function:

Given a design ${\bf X}$, the minimax risk of prediction over $\Theta[k,p]$ with respect to ${\bf X}$ is

For a Gaussian design with covariance $\Sigma$, we study the quantity

These minimax risks of prediction do not only depend on $(k,n,p)$ but also on the design ${\bf X}$ (or on the covariance $\Sigma$). The computation of the exact dependency of the minimax risks on ${\bf X}$ or $\Sigma$ is a challenging question. To simplify the presentation in this section, we only describe the minimax prediction risks for worst-case designs defined by

the supremum being taken over all designs ${\bf X}$ of size $n\times p$ (resp. all covariance matrices $\Sigma$). The quantity $\mathcal{R}_{F}[k]$ corresponds to the smallest risk achievable uniformly over $\Theta[k,p]$ and all designs ${\bf X}$. It is shown in Section 5 that the quantity $\mathcal{R}_{R}[k]$ is achieved (up to constants) for a covariance $\Sigma=I_{p}$ while the quantity $\mathcal{R}_{F}[k]$ is achieved with high probability for designs ${\bf X}$ that are realizations of the standard Gaussian design (all the components of ${\bf X}$ are drawn independently from a standard normal distribution). This corresponds to designs used in compressed sensing . In fact, the maximal risks $\mathcal{R}_{F}[k]$ and $\mathcal{R}_{R}[k]$ for the prediction problem correspond to typical situations where the designs is well-balanced, that is as close as possible to orthogonality.

1.2 Results

In the sequel, we say that $\mathcal{R}_{F}[k]$ is of order $f(k,p,n,C)$, where $C$ is positive constant when there exist two positive universal constants $C_{1}$ and $C_{2}$ such that

These minimax risks are computed in Section 5 and are gathered in Table 1. They are also depicted on Figure 1.

When $k\log(p/k)$ remains small compared to $n$, the minimax risk of prediction is of the same order for fixed and Gaussian design. The $k\log(p/k)/n$ risk is classical and has been known for a long time in the specific case of the Gaussian sequence model . Some procedures based on complexity penalization or aggregation (e.g. ) are proved to achieve these risks uniformly over all designs ${\bf X}$. Computationally efficient procedures like the Lasso or the Dantzig selector are only proved to achieve a $k\log(p)/n$ risk under assumption on the design ${\bf X}$ . If the support of $\theta_{0}$ is known in advance, the parametric risk is of order $k/n$. Thus, the price to pay for not knowing the support of $\theta_{0}$ is only logarithmic in $p$.

In Section 5, we also study the adaptation to the sparsity index $k$ and to the variance $\sigma^{2}$. We prove that adaptation to $k$ and $\sigma^{2}$ is possible for a Gaussian design. In fixed design, no procedure can be simultaneously adaptive to the sparsity $k$ and the variance $\sigma^{2}$ (see the red curve in Figure 1 that corresponds to fixed design, $\sigma$ and $k$ unknown).

2 Testing

Let us turn to the problem $({\bf P_{1}})$ of testing ${\bf H_{0}}$: $\{\theta_{0}=0_{p}\}$ against ${\bf H_{1}}$: $\{\theta_{0}\in\Theta[k,p]\setminus\{0_{p}\}\}$. We fix a level $\alpha>0$ and a type II error probability $\delta>0$. Minimax lower and upper bounds for this problem are discussed in Section 4.

Suppose we are given a test procedure $\Phi_{\alpha}$ of level $\alpha$ for fixed design ${\bf X}$ and known variance $\sigma^{2}$. The $\delta$-separation distance of $\Phi_{\alpha}$ over $\Theta[k,p]$, noted $\rho_{F}[\Phi_{\alpha},k,{\bf X}]$ is the minimal number $\rho$, such that $\Phi_{\alpha}$ rejects ${\bf H_{0}}$ with probability larger than $1-\delta$ if $\|{\bf X}\theta_{0}\|_{n}/\sqrt{n}\geq\rho\sigma$. Hence, $\rho_{F}[\Phi_{\alpha},k,{\bf X}]$ corresponds to the minimal distance such that the hypotheses $\{\theta_{0}=0_{p}\}$ and $\{\theta_{0}\in\Theta[k,p]$, $\|{\bf X}\theta_{0}\|_{n}^{2}\geq n\rho_{F}^{2}[\Phi_{\alpha},k,{\bf X}]\sigma^{2}\}$ are well separated by the test $\Phi_{\alpha}$.

Although the separation distance also depends on $\delta$, $n$, and $p$, we only write $\rho_{F}[\Phi_{\alpha},k,{\bf X}]$ for the sake of conciseness. By definition, the test $\Phi_{\alpha}$ has a power larger than $1-\delta$ for $\theta_{0}\in\Theta[k,p]$ such that $\|{\bf X}\theta_{0}\|_{n}^{2}\geq\rho_{F}^{2}[\Phi_{\alpha},k,{\bf X}]$. Then, we consider

The infimum runs over all level-$\alpha$ tests. We call this quantity the $(\alpha,\delta)$-minimax separation distance over $\Theta[k,p]$ with design ${\bf X}$ and variance $\sigma^{2}$. The minimax separation distance is a non-asymptotic counterpart of the detection boundaries studied in the Gaussian sequence model .

Similarly, we define the $(\alpha,\delta)$-minimax separation distance over $\Theta[k,p]$ with Gaussian design by replacing the distance $\|{\bf X}\theta_{0}\|_{n}/\sqrt{n}$ by the distance $\|\sqrt{\Sigma}\theta_{0}\|_{p}$:

Various bounds on $\rho^{*}_{F}[k,{\bf X}]$, $\rho^{*}_{R}[k,\Sigma]$ are stated in Section 4. In this section, we only provide the orders of magnitude of the minimax separation distances in the “worst case” designs in order to emphasize the effect of dimensionality:

This is the smallest separation distance that can be achieved by a procedure $\Phi_{\alpha}$ uniformly over all designs ${\bf X}$ (resp. $\Sigma$). As for the prediction problem, it will be proved in Section 4, that the quantity $\rho^{*}_{F}[k]$ and $\rho^{*}_{R}[k]$ are achieved for well-balanced designs.

It is not always possible to achieve the minimax separation distances with a procedure $\Phi_{\alpha}$ that does not require the knowledge of the variance $\sigma^{2}$. This is why we also consider $\rho^{*}_{F,U}[k]$ and $\rho^{*}_{R,U}[k]$ the minimax separation distance for fixed and Gaussian design when the variance is unknown. Roughly, $\rho^{*}_{F,U}[k]$ corresponds to the minimal distances $\rho^{2}$ that allows to separate well the hypotheses $\{\theta_{0}=0_{p}\ \text{ and }\ \sigma>0\}$ and $\{\theta_{0}\in\Theta[k,p]\text{ and }\sigma>0\ ,\ \|{\bf X}\theta_{0}\|_{n}^{2}/\sigma^{2}\geq n\rho^{2}\}$ when $\sigma$ is unknown. We shall provide a formal definition at the beginning of Section 4.

2.2 Results

In Table 2, we provide the orders of the minimax separation distances over $\Theta[k,p]$ for fixed and Gaussian designs, known and unknown variance (see also Figure 2).

In contrast to $({\bf P_{2}})$, the minimax separation distances are of the same order for fixed and Gaussian design.

When $k\log(p)\leq\sqrt{n}$, all the minimax separation distances are of order $k\log(p)/n$. This quantity also corresponds to the minimax risk of prediction $({\bf P_{2}})$ stated in the previous subsection. This separation distance has already been proved in the specific case of the Gaussian sequence model .

If the variance is unknown, the minimax separation distance over $\Theta[k,p]$ is still of order $k\log(p)/n$ if $k\log(p)$ is small compared to $n$. In contrast, the minimax separation distance blows up to the order $C_{1}p^{C_{2}k/n}$ in a ultra-high dimensional setting. This blow up phenomenon has also been observed in the previous section for the problem of prediction $({\bf P_{2}})$ in Gaussian design. In conclusion, the knowledge of the variance is of great importance for $k\log(p)$ larger than $\sqrt{n}$.

3 Inverse problem and support estimation

In the inverse problem (${\bf P_{3}}$), we are primarily interested in the estimation of $\theta_{0}$ rather than ${\bf X}\theta_{0}$. This is why the loss function under study is $\|\theta_{1}-\theta_{2}\|_{p}^{2}$. Minimax lower and upper bounds for this loss function are discussed in Section 6. For a fixed design ${\bf X}$, the minimax risk of estimation is

If one transforms the design ${\bf X}$ by an homothety of factor $\lambda>0$, then this multiplies the minimax risk for the inverse problem by a factor $1/\lambda^{2}$. For the sake of simplicity, we restrict ourselves to designs ${\bf X}$ such that each column has been normed to $\sqrt{n}$. The collection of such designs is noted $\mathcal{D}_{n,p}$. The supremum of the minimax risks over the designs $\mathcal{D}_{n,p}$ is $+\infty$. Take for instance a design where the two first columns are equal. In this section, we only present the infimum of the minimax risks over $\Theta[k,p]$ as ${\bf X}$ varies across $\mathcal{D}_{n,p}$:

The quantity $\mathcal{RI}_{F}[k]$ is interpreted the following way: given $(k,n,p)$ what is the smallest risk we can hope if we use the best possible design? Alternatively, given $n$ observations, what is the intrinsic difficulty of estimating a $k$-sparse vector of size $p$? We call this quantity the minimax risks for the inverse problem over $\Theta[k,p]$.

In Section 6, we also study the corresponding the minimax risks of the inverse problem in the random design case. Let $\mathcal{S}_{p}$ stand for the set of covariance matrices that contain only ones on the diagonal. We respectively define the minimax risk of estimation over $\Theta[k,p]$ for a covariance $\Sigma$ and the minimax risk of estimation over $\Theta[k,p]$ as

3.2 Results

In Table 3, we provide the minimax risks in fixed design for different values of $(k,n,p)$ (see also Figure 3).

If $k\log(p/k)$ remains smaller than $n$, it is possible to recover the risk $Ck\log(p/k)$ for “good” designs. This risk is for instance achieved by the Dantzig selector of Candès and Tao for nearly-orthogonal designs, that roughly means that the restricted eigenvalues $\varPhi_{3k,+}({\bf X})$ and $\varPhi_{3k,-}({\bf X})$ of ${\bf X}^{T}{\bf X}$ are close to one. In an ultra high-dimensional setting, it is not anymore possible to build nearly-orthogonal designs ${\bf X}$ and the minimax risk of the inverse problem blows up as for testing problems (${\bf P_{1}}$) or prediction problems in Gaussian design (${\bf P_{2}}$). Moreover, adaptation to the sparsity $k$ and to the variance $\sigma^{2}$ is possible for the inverse problem. As explained in Section 6, the quantities $\mathcal{RI}_{R}[k,\Sigma]$ and $\mathcal{RI}_{R}[k]$ behave somewhat similarly to their fixed design counterpart.

In Section 6, we also discuss the consequences of the minimax bounds on the problem of support estimation (${\bf P_{4}}$). We prove that, in an ultra-high dimensional setting, it is not possible to estimate with high probability the support of $\theta_{0}$ unless the ratio $\|\theta_{0}\|_{p}^{2}/\sigma^{2}$ is larger than $C_{1}(p/k)^{C_{2}k/n}$. In fact, even the problems of support estimation is almost hopeless in an ultra-high dimensional setting.

Hypothesis Testing

We start by the testing problem (${\bf P_{1}}$) because some minimax lower bounds in prediction and inverse estimation derive from testing considerations.

As mentioned in the introduction, the knowledge of $\sigma^{2}=\mbox{Var}(Y|X)$ is really unlikely in many practical applications. Nevertheless, we study this case to enhance the differences between known and unknown conditional variances. Furthermore, these results turn out to be useful for analyzing the minimax separation distances in fixed design problems. We recall that the notions of minimax separation distances $\rho^{*}_{F}[k,{\bf X}]$, $\rho^{*}_{F}[k]$, $\rho^{*}_{R}[k,\Sigma]$, and $\rho^{*}_{R}[k]$ have been defined in Section 3.2.

Assume that $\alpha+\delta\leq 53\%$, $p\geq n^{2}$, and that $n\geq 8\log(2/\delta)$. For any $1\leq k\leq n$, the $(\alpha,\delta)$-minimax separation distance (3.6) with covariance $I_{p}$ is lower bounded by

For any $1\leq k\leq p$ and any covariance $\Sigma$, we have

Furthermore, this upper bound is simultaneously achieved for all $k$ and $\Sigma$ by a procedure $T_{\alpha}^{*}$ (defined in Section 10.1.1).

[Adaptation to sparsity] It follows from Theorem 4.1 that adaptation to the sparsity is possible and that the optimal optimal separation distance is of order

for all sparsities $k$ between $1$ and $n$.

[Correlated design] The upper bound (4.2) is valid for any covariance matrix $\Sigma$. In contrast, the minimax lower bound (4.1) is restricted to the case $\Sigma=I_{p}$. This implies that there exists some constant $C(\alpha,\delta)$ such that ,

In other words, the testing problem is more complex (up to constants) for an independent design than for a correlated design.

[Which logarithmic term in the bound: $\log(p)$ or $\log(p/k)$?] In the proof of Theorem 4.1, we derive the following bounds

These two bounds are of order of (4.3) as it is assumed that $p\geq n^{2}$. However, the dependency of the logarithmic terms on $k$ in the last bounds do not allow to provide the minimax separation distance when $p=n$ and $k$ is close to $\sqrt{n}$. For instance, if $p=n$ and $k=\sqrt{n}/\log(n)$, the two bounds only match up to a factor $\log(n)/\log\log(n)$. The non-asymptotic minimax bounds of Baraud in the Gaussian sequence model suffer the same weakness. Up to our knowledge the dependency on $\log(k)$ of the minimax separation distances has only been captured in an asymptotic setting ($(k,p,n)\rightarrow\infty$).

1.2 Fixed design

The separation distances are similar to the Gaussian design case.

Assume that $\alpha+\delta\leq 33\%$, $p\geq n^{2}\geq C(\alpha,\delta)$, and that $n\geq 8\log(2/\delta)$. For any $1\leq k\leq n$, there exist some $n\times p$ designs ${\bf X}$ such that

For any $1\leq k\leq p$ and any design ${\bf X}$, we have

Furthermore, this upper bound is simultaneously achieved for all $k$ and ${\bf X}$ by a procedure $T_{\alpha}^{*}$ (defined in Section 10.1.1).

As for the random design case, we conclude that adaptation to the sparsity is possible and that $(\rho_{F}^{*}[k])^{2}$ is of order $\frac{k}{n}\log\left(p\right)\wedge\frac{1}{\sqrt{n}}$. In fact, the proof shows that, with large probability, designs ${\bf X}$ whose components are independently sampled from a standard normal variable satisfy (4.4).

Arias-Castro et al. and Ingster et al. have recently provided the asymptotic minimax separation distance with exact constant for known variance when the design satisfies very specific conditions. Theorem 4.2 provides the non-asymptotic counterpart of their result, but the constants in (4.4) and (4.5) are not optimal.

2 Unknown variance

We now turn to the study of the minimax separation distances when the variance $\sigma^{2}$ is unknown. In Section 3.2, we have introduced the notions of $\delta$-separation distances and $(\alpha,\delta)$-minimax separation distances when the variance $\sigma^{2}$. We now define their counterpart for an unknown variance $\sigma^{2}$.

Let us consider a test $\Phi_{\alpha}$ of the hypothesis ${\bf H_{0}}$ for the linear regression model with fixed design ${\bf X}$. We say that $\Phi_{\alpha}$ has a level $\alpha$ under unknown variance if

This means that the type I error probability is controlled uniformly over all variance $\sigma^{2}$. Similarly, we want to control the type II error probabilities uniformly over all variances. The $\delta$-separation distance $\rho_{F,U}[\Phi_{\alpha},k,{\bf X}]$ of $\Phi_{\alpha}$ over $\Theta[k,p]$ for unknown variance is defined by

Hence, $\rho_{F,U}[\Phi_{\alpha},k,{\bf X}]$ corresponds to the minimal distance such that the hypotheses $\{\theta_{0}=0_{p}\text{ and }\sigma>0\}$ and $\{\theta_{0}\in\Theta[k,p]\text{ and }\sigma>0\ ,\ \|{\bf X}\theta_{0}\|_{n}^{2}\geq n\rho_{F,U}^{2}[\Phi_{\alpha},k,{\bf X}]\sigma^{2}\}$ are well separated by the test $\Phi_{\alpha}$. Taking the infimum over all level $\alpha$ tests, we get the $(\alpha,\delta)$ minimax separation distance over $\Theta[k,p]$ with design ${\bf X}$ and unknown variance is

Finally, $\rho^{*}_{F,U}[k]:=\sup_{\bf X}\rho^{*}_{F,U}[k,{\bf X}]$ corresponds to the $(\alpha,\delta)$-minimax separation distance over $\Theta[k,p]$ with the “worst-case designs”.

In the Gaussian design, we define $\rho_{R,U}[\Phi_{\alpha},k,\Sigma]$, $\rho^{*}_{R,U}[k,\Sigma]$, and $\rho^{*}_{R,U}[k]$ analogously to (4.2.1) and (4.9) by replacing the norm $\|{\bf X}\theta_{0}\|_{n}/\sqrt{n}$ by $\|\sqrt{\Sigma}\theta_{0}\|_{p}$.

2.2 Gaussian design

Minimax bounds have been proved in in the non ultra-high dimensional setting. The next theorem encompasses high dimensional and ultra-high dimensional settings.

Suppose that $\alpha+\delta\leq 53\%$ and that $p\geq n\geq 8\log(2/\delta)$. For any $1\leq k\leq\lfloor p^{1/3}\rfloor$, the $(\alpha,\delta)$-minimax separation distance over $\Theta[k,p]$ with covariance $I_{p}$ and unknown variance satisfies

For any $1\leq k\leq n/2$ and any covariance $\Sigma$, we have

Furthermore, this upper bound is simultaneously achieved for all $k$ and $\Sigma$ by a procedure $T_{\alpha}$ (defined in Section 10.1.2).

[Minimax adaptation] It follows from Theorem 4.3 that, under unknown variance, adaptation to the sparsity is possible and that the minimax separation distance $(\rho^{*}_{RU}[k])^{2}$ over $\Theta[k,p]$ is of order

The condition $k\leq p^{1/3}$ can be replaced by $k\leq p^{1/2-\gamma}$ with $\gamma>0$, the only difference being that the constants involved in (4.10) would depend on $\gamma$. These conditions are not really restrictive for a sparse high-dimensional regression since the usual setting is $k\leq n\ll p$.

Note $k\leq p^{3}$ implies that $\log(p)\leq 3/2\log(p/k)\leq 3\log(p/k^{2})$ so that we cannot distinguish terms $C_{1}\log(p)$ from $C_{2}\log(p/k^{2})$ or $C_{3}\log(p/k)$. As a consequence (4.12) does not necessarily capture the right dependency on $k$ in the logarithmic terms. This observation also holds for all the next results that require $k\leq p^{1/3}$.

[Dependent design] As for the known variance case, we have $\rho^{*}_{R,U}[k,I_{p}]\geq C(\alpha,\delta)\rho^{*}_{R,U}[k]$, that is the testing problem is more complex for an independent design than for a correlated design. For some covariance matrices $\Sigma$, the minimax separation distance with covariance $\Sigma$ is much smaller than $\rho^{*}_{R,U}[k,I_{p}]$. Verzelen and Villers provide such an example of a matrix $\Sigma$ in (see Propositions 8 and 9). However, the arguments used in the proof of their example are not generalizable to other covariances. In fact, the computation of sharp minimax bounds that capture the dependency of $\rho^{*}_{R,U}[k,\Sigma]$ on $\Sigma$ remains an open problem.

2.3 Fixed design

Ingster et al. derive the asymptotic minimax separation distance for some specific design when $k\log(p)/n$ goes to $0$. Here, we provide the non asymptotic counterpart that encompass all the regimes.

Assume that $\alpha+\delta\leq 26\%$ and that $p\geq n\geq C(\alpha,\delta)$. For any $1\leq k\leq\lfloor p^{1/3}\rfloor$, there exist some $n\times p$ designs ${\bf X}$ such that

For any $1\leq k\leq n/2$ and any $n\times p$ design ${\bf X}$, we have

Furthermore, this upper bound is simultaneously achieved for all $k$ and ${\bf X}$ by a procedure $T_{\alpha}$ (defined in Section 10.1.2).

Again, we observe a phenomenon analogous to the random design case.

3 Comparison between known and unknown variance

There are three regimes depending on $(k,p,n)$. They are depicted on Figure 2:

${\bf k\boldsymbol{\log}(p)\leq\sqrt{n}}$. The minimax separation distances are of the same order for known and unknown $\sigma^{2}$. The minimax distance $k\log(p)/n$ is also of the same order as the minimax risk of prediction.

${\bf k\boldsymbol{\log}(p)\geq n}$. If $\sigma^{2}$ is unknown, the minimax separation distance blows up. It is of order $(p/k)^{Ck/n}$. Consequently, the problem of testing $\{\theta_{0}=0_{p}\}$ becomes extremely difficult in this setting.

Prediction

In contrast to the testing problem, the minimax risks of prediction (${\bf P_{2}}$) exhibit really different behaviors in fixed and in random design. The big picture is summarized in Figure 1. We recall that the minimax risks $\mathcal{R}_{F}[k,{\bf X}]$, $\mathcal{R}_{F}[k]$, $\mathcal{R}_{R}[k,\Sigma]$, and $\mathcal{R}_{R}[k]$ are defined in Section 3.1.

[Minimax lower bound for prediction] Assume that $p\geq C$. For any $1\leq k\leq\lfloor p^{1/3}\rfloor$, we have

[General covariances $\Sigma$] The lower bound (5.1) is only stated for the identity covariance $\Sigma=I_{p}$. For general covariance matrices $\Sigma$, we have

for any $k\leq n\leq p/2$. This statement has been proved in (Proposition 4.5) in the special case of restricted isometry, but the proof straightforwardly extends to restricted eigenvalue conditions. For $\Sigma=I_{p}$, the lower bound (5.2) does not capture the elbow effect in an ultra-high dimensional setting (compare with (5.1)).

[Minimax upper bound] Assume that $n\geq C$. There exists an estimator $\widetilde{\theta}^{V}$ (defined in Section 10.2.1) such that the following holds:

The computation of $\widetilde{\theta}^{V}$ does not require the knowledge of $\sigma^{2}$ or $k$.

For any covariance $\Sigma$, any $\sigma>0$, any $1\leq k\leq\lfloor(n-1)/4\rfloor$, and any $\theta_{0}\in\Theta[k,p]$ we have

In contrast to similar results such as Theorem 1 in Giraud or Theorem 3.4 in Verzelen , we do not restrict $k$ to be smaller than $n/(2\log p)$, that is we encompass both high-dimensional and ultra-high dimensional setting. The proof of the theorem is based on a new deviation inequality for the spectrum of Wishart matrices stated in Lemma 11.2.

[Minimax risk] We derive from Theorem 5.2 and Proposition 5.1 that the minimax risk $\mathcal{R}_{R}[k]$ is of order

If $k\log(p/k)$ is small compared to $n$, the minimax risk of estimation is of order $Ck\log(p/k)/n$. In an ultra-high dimensional setting, we again observe a blow up.

[Adaptation to sparsity and the variance] The estimator $\widetilde{\theta}^{V}$ does not requires the knowledge of $k$ and of the variance $\sigma^{2}=\mbox{Var}(Y|X)$. It follows that $\widetilde{\theta}^{V}$ is minimax adaptive to all $1\leq k\leq p^{1/3}\wedge[(n-1)/4]$ and to all $\sigma^{2}>0$. As a consequence, adaptation to the sparsity and to the variance is possible for this problem.

[Dependent design] The risk upper bound of $\widetilde{\theta}^{V}$ stated in Theorem 5.2 is valid for any covariance matrix $\Sigma$ of the covariance $X$. In contrast, the minimax lower bound of Theorem 4.3 is restricted to the identity covariance. This implies that the minimax prediction risk for a general matrix $\Sigma$ is at worst of the same order as in the independent case: there exists a universal constant $C>0$ such that for all covariance $\Sigma$,

In Remark 5.1, we have stated a minimax lower bound for prediction that depends on the restricted eigenvalues of $\Sigma$. Fix some $0<\gamma<1$. If we consider some covariance matrices $\Sigma$ such that $\varPhi_{2k,-}(\sqrt{\Sigma})/\varPhi_{2k,+}(\sqrt{\Sigma})\geq 1-\gamma$ , the minimax lower bound (5.2) and the upper bound (5.3) match up to a constant $C(\gamma)$. In general, the lower bound (5.2) and the upper bound (5.3) do not exhibit the same dependency with respect to $\Sigma$, especially when $\varPhi_{2k,-}(\sqrt{\Sigma})/\varPhi_{2k,+}(\sqrt{\Sigma})$ is close to zero.

2 Fixed design

The minimax prediction risk with known variance has been studied in Raskutti et al. and Rigollet and Tsybakov (see also ). For any design ${\bf X}$ and any $1\leq k\leq n$, these authors have proved that the minimax risk $\mathcal{R}_{F}[k,{\bf X}]$ satisfies

Next, we bound the supremum $\sup_{{\bf X}}R_{F}[k,{\bf X}]$ and we study the possibility of adaptation to the sparsity.

For any $1\leq k\leq n$, the supremum $\sup_{{\bf X}}\mathcal{R}_{F}[k,{\bf X}]$ is lower bounded as follows

This upper bound (5.6) is a consequence of Birgé and Massart .

[Dependency of $\mathcal{R}_{F}[k,{\bf X}]$ on ${\bf X}$] For designs ${\bf X}$, such that the ratio $\varPhi_{2k,-}({\bf X})/\varPhi_{2k,+}({\bf X})$ is close to one, the lower bounds and upper bounds of (5.4) agree with each other. This is for instance the case of the realizations (with high probability) of a Gaussian standard independent design (see the proof of Proposition 5.3 for more details).

However, the dependency of the minimax lower bound in (5.4) on ${\bf X}$ is not sharp when the ratio $\varPhi_{2k,-}({\bf X})/\varPhi_{2k,+}({\bf X})$ is away from one. Take for instance an orthogonal design with $p=n$ and duplicate the last column. Then, the lower bound (5.4) for this new design ${\bf X}$ is $0$ while the minimax risk is of order $k\log(p/k)/n$.

Similarly, the dependency of the minimax upper bound in (5.4) on ${\bf X}$ is not sharp. For very specific design, it is possible to obtain a minimax risk $\mathcal{R}_{F}[k,{\bf X}]$ that is much smaller than $k/n\log(p/k)\wedge 1$ (see Abramovich and Grinshtein ).

[Comparison with $l_{1}$ procedures] The designs ${\bf X}$ for which $l_{1}$ procedures such as the Lasso or the Dantzig selector are proved to perform well require that $\varPhi_{2k,-}({\bf X})/\varPhi_{2k,+}({\bf X})$ is close to one. It is interesting to notice that these designs ${\bf X}$ precisely correspond to situations where the minimax risk is close to its maximum $k\log(p/k)/n$ (see Equation (5.4)). We refer to for a more complete discussion.

We easily retrieve from (5.4) a result of asymptotic geometry first observed by Baraniuk et al. in the special of restricted isometry property . For any $0<\delta\leq 1$, there exists a constant $C(\delta)>0$ such that no $n\times p$ matrix ${\bf X}$ can fulfill $\varPhi_{k,-}({\bf X})/\varPhi_{k,+}({\bf X})\geq\delta$ if $k(1+\log(p/k))\geq C(\delta)n$.

2.2 Unknown variance

We now consider the problem of prediction when the variance $\sigma^{2}$ is unknown.

For any $1\leq k\leq n$, there exists an estimator $\widehat{\theta}^{(k)}$ that does not require the knowledge of $\sigma^{2}$ such that

Thus, the optimal risk of prediction over $\Theta[k,p]$ remains of the same order for known and unknown $\sigma^{2}$.

[Risk bound for $\widetilde{\theta}^{V}$ and $\widehat{\theta}_{n}$] Assume that $n\geq 14$. For any $1\leq k\leq\lfloor(n-1)/4\rfloor$, the maximal risk of $\widehat{\theta}^{V}$ over $\Theta[k,p]$ is upper bounded as follows

For any $1\leq k\leq n$, the maximal risk of $\widehat{\theta}_{n}$ over $\Theta[k,p]$ is upper bounded as follows

The risk bound (5.8) is also satisfied by the procedure of Baraud et al. . The proof of (5.8) is a consequence of one of their results.

In contrast, $\widehat{\theta}_{n}$ is minimax adaptive over all $\Theta[k,p]$ such that $k(1+\log(p)/k)\geq n$, but its behavior is suboptimal in a non-ultra-high dimensional setting.

In order to get an estimator that is adaptive to all indexes $k$, we would need to merge the properties of $\widetilde{\theta}^{V}$ (for non-ultra-high dimensional cases) and of $\widehat{\theta}_{n}$ (for ultra-high dimensional cases). The following proposition tells us that it is in fact impossible.

[Adaptation to the sparsity is impossible under unknown variance] Consider any $p\geq n\geq C_{1}$ and $1\leq k\leq\lfloor p^{1/3}\rfloor$ such that $k\log(ep/k)\geq C_{2}n$. There exists a design ${\bf X}$ of size $n\times p$ such that for any estimator $\widehat{\theta}$, we have either

As a benchmark, we recall the minimax upper bounds:

The proof of proposition 5.6 is based on the minimax lower bounds (4.13) for the testing problem (${\bf P_{1}}$) under unknown variance. The proof uses designs ${\bf X}$ that are realizations of standard Gaussian designs.

In the setup of Proposition 5.6, any estimator $\widehat{\theta}$ that does not require the knowledge of $k$ and $\sigma^{2}$ has to pay at least one of these two prices:

This is the price for adaptation when $\sigma^{2}$ is unknown. The estimator $\widetilde{\theta}^{V}$ exhibits this behavior.

As a conclusion, it is impossible to merge the qualities of $\widetilde{\theta}^{V}$ and of $\widehat{\theta}_{n}$.

The best prediction risk that can be achieved by a procedure that aim to adaptation to the sparsity is of order

In other words, the unavoidable loss for adaptation for unknown variance is a factor $\exp[Ck/n\log(p/k)]$ In this sense, the estimator $\widetilde{\theta}^{V}$ (and as a byproduct the procedure of Baraud et al. ) achieves the optimal prediction risk under unknown variance and unknown sparsity.

In conclusion, the minimax risks of prediction are of the same order for fixed and Gaussian design and for known and unknown variance when $k\log(p/k)$ is small compared to $n$. In an ultra-high dimensional setting, the minimax risks behave differently. For Gaussian design, the minimax risk is of the order $(p/k)^{Ck/n}$. In contrast, the minimax risk of prediction remains smaller than one for fixed design regression with known variance. When the sparsity and the variance are unknown, there is a price to pay for adaptation under fixed design. All these behaviors are depicted on Figure 1.

Inverse problem and support estimation

We recall that the minimax risks of estimation for the inverse problem $\mathcal{RI}_{F}[k,{\bf X}]$, $\mathcal{RI}_{F}[k]$, $\mathcal{RI}_{R}[k,\Sigma]$, and $\mathcal{RI}_{R}[k]$ have been defined in Section 3.3.

First, we consider the problem (${\bf P_{3}}$) for a fixed design regression model. The minimax risk of estimation over $\Theta[k,p]$ with a design ${\bf X}$ is noted $\mathcal{RI}_{F}[k,{\bf X}]$ and is defined in (3.8). Raskutti et al. have recently provided the following bounds

that holds for any fixed design ${\bf X}$ and any $1\leq k\leq n$. The lower and upper bounds match up to the factor $\varPhi_{2k\wedge p,+}({\bf X})/\varPhi_{2k\wedge p,-}({\bf X})$. The upper bound is achieved by least-squares estimator over $\Theta[k,p]$ . If the restricted eigenvalues of ${\bf X}$ are close to one, then the minimax risk is of order $k\log(ep/k)$. Next, we improve the lower bound in (6.1) in order to grasp the behavior of the minimax risk for non orthogonal design.

For any design ${\bf X}$ and any $1\leq k\leq n$, we have

In order to interpret these bounds let us restrict ourselves to design ${\bf X}$ such that each column has $\sqrt{n}$ norm, as justified in Section 3.3. The collection of such designs is noted $\mathcal{D}_{n,p}$. Observe that ${\bf X}\in\mathcal{D}_{n,p}$ enforces $\varPhi_{1,+}\left({\bf X}\right)=n$.

In the sequel, we are interested in the smallest minimax risk $\mathcal{RI}_{F}[k,{\bf X}]$ that is achievable if we can choose the $n\times p$ design ${\bf X}\in\mathcal{D}_{n,p}$, that is we want to bound $\mathcal{RI}_{F}[k]=\inf_{{\bf X}\in\mathcal{D}_{n,p}}\mathcal{RI}_{F}[k,{\bf X}]$. The minimax risk $\mathcal{RI}_{F}[k]$ tells us the intrinsic difficulty of estimating a $k$ sparse vector of size $p$ with $n$ observations.

Assume that $k[1+\log(p/k)]\leq Cn$. Then, we have

This bound is for instance achieved for designs ${\bf X}$ that are realizations (with a high probability) of normalized standard Gaussian design.

For any design ${\bf X}\in\mathcal{D}_{n,p}$ and any $k\leq n\wedge p/2$, we have

The bound (6.3) tells us that the best minimax risk that is achievable in a non-ultra-high dimensional setting is of order $k\log(ep/k)/n$. The Lasso achieves the (almost optimal) risk bound $k\log(p)/n$ under some assumptions on the design matrix.

The lower bound (6.4) is of geometric nature. Combined with (6.2), it implies the lower bound of (6.5). In an ultra-high dimensional setting, it is not possible to build a design ${\bf X}$ such that $\varPhi_{2k,+}\left({\bf X}\right)/\varPhi_{2k,-}\left({\bf X}\right)$ is close to one (see Remark 5.8). In fact, the quantity $\varPhi^{-1}_{2k,-}({\bf X})$ blows up because of geometric constrains. When $k[1+\log(p/k)]$ is larger compared to $n\log(n)$, both bounds in (6.5) are comparable and the minimax risk is of order $\exp[Ck/n\log(p/k)]$. As a consequence, the inverse problem becomes extremely difficult in an ultra-high dimensional setting.

While the quantity $k\log(p/k)$ in (6.3) is due to the “size” of the parameter space $\Theta[k,p]$, the exponential term of the minimax risk in ultra-high dimension is essentially driven by geometrical constrains on the design ${\bf X}$.

As in the prediction case, we consider the estimator $\widetilde{\theta}^{V}$ (defined in Section 10.2.1). Assume that $p\geq 2n$. For any design ${\bf X}$, any $\sigma>0$, any $1\leq k\leq\lfloor(n-1)/4\rfloor$, and any $\theta_{0}\in\Theta[k,p]$, we have

with probability larger than $1-e^{-n}-C/p$.

Although the bound (6.6) is in probability and not in expectation, it suggests that adaptation to the sparsity and to the variance are possible.

1.2 Random design

Let us turn to the Gaussian design case. We are interested in bounding $\mathcal{RI}_{R}[k,\Sigma]$ and $\mathcal{RI}_{R}[k]$ as defined in (3.9).

For any $1\leq k\leq(n-1)/4$, and any covariance $\Sigma$ we have

As long as $k[1\log(p/k)]\leq n$, we derive that $\mathcal{RI}_{R}[k]:=\inf_{\Sigma\in\mathcal{S}_{p}}\mathcal{RI}_{R}[k,\Sigma]$ satisfies

We observe that $\mathcal{RI}_{R}[k]$ and $\mathcal{RI}_{F}[k]$ behave similarly in a non-ultra-high dimensional setting.

[Ultra-high dimensional case] Proposition 6.4 does not allow to derive the order of magnitude of $\mathcal{RI}_{R}[k]$ in an ultra-high dimensional setting. While the upper bound in (6.7) is blowing up, the lower bound remains as small as $k\log(p/k)/n$. Nevertheless, we know from Proposition 5.1 that

This suggests that $\mathcal{RI}_{R}[k]$ is blowing up in an ultra-high dimensional setting but the problem remains open.

In the next proposition, we state the counterpart of Proposition 6.3 in the random design case.

As in the prediction case, we consider the estimator $\widetilde{\theta}^{V}$ (defined in Section 10.2.1). Assume that $p\geq 2n$. For any covariance $\Sigma$, any $\sigma>0$, any $1\leq k\leq\lfloor(n-1)/12\rfloor$, and any $\theta_{0}\in\Theta[k,p]$, we have

with probability larger than $1-e^{-n}-C/p$.

2 Consequences on support estimation

We deduce from the minimax lower bounds for the inverse problem $(\bf{P_{3}})$ some consequences for the support estimation problem $(\bf{P_{4}})$ in a ultra-high dimensional setting. The case $k[1+\log(p/k)]$ small compared to $n$ has been studied in Wainwright .

For any $\rho>0$ and any $k\leq p$, the set $\mathcal{C}_{k}^{p}(\rho)$ is made of all vectors $\theta$ in $\Theta[k,p]$ such that $\theta$ contains exactly $k$ non-zero coefficients that are all equal to $\rho/\sqrt{k}$.

In a non-ultra high dimensional setting, Wainwright has proved, that under suitable conditions on a design ${\bf X}\in\mathcal{D}_{n,p}$, it is possible to recover the support of any vector $\theta_{0}$ that belong to $\mathcal{C}_{k}^{p}(\rho)$ with $\rho$ of order of $\sqrt{k\log(p)/n}\sigma$. Here, we prove that $\rho$ has to be much larger in an ultra-high dimensional setting.

[Support recovery is almost impossible] For any $\rho^{2}\leq C_{1}/n\left(\frac{ep}{k}\right)^{C_{2}k/n}$ and any $k\leq n\wedge p/2$, we have

For any design ${\bf X}\in\mathcal{D}_{n,p}$ it is not possible to recover the support of $\theta_{0}$ with high probability, unless $\theta_{0}$ satisfies: