Consider the standard Gaussian linear regression model @math , where @math is a response vector and @math is a design matrix. Numerous work have been devoted to building efficient estimators of @math when @math is much larger than @math . In such a situation, a classical approach amounts to assume that @math is approximately sparse. This paper studies the minimax risks of estimation and testing over classes of @math -sparse vectors @math . These bounds shed light on the limitations due to high-dimensionality. The results encompass the problem of prediction (estimation of @math ), the inverse problem (estimation of @math ) and linear testing (testing @math ). Interestingly, an elbow effect occurs when the number of variables @math becomes large compared to @math . Indeed, the minimax risks and hypothesis separation distances blow up in this ultra-high dimensional setting. We also prove that even dimension reduction techniques cannot provide satisfying results in an ultra-high dimensional setting. Moreover, we compute the minimax risks when the variance of the noise is unknown. The knowledge of this variance is shown to play a significant role in the optimal rates of estimation and testing. All these minimax bounds provide a characterization of statistical problems that are so difficult so that no procedure can provide satisfying results.
@cite_30: The problem of consistently estimating the sparsity pattern of a vector β* ∈ RP based on observations contaminated by noise arises in various contexts, including signal denoising, sparse approximation, compressed sensing, and model selection. We analyze the behavior of l1-constrained quadratic programming (QP), also referred to as the Lasso, for recovering the sparsity pattern. Our main result is to establish precise conditions on the problern dimension p, the number k of nonzero elements in β*, and the number of observations n that are necessary and sufficient for sparsity pattern recovery using the Lasso. We first analyze the case of observations made using deterministic design matrices and sub-Gaussian additive noise, and provide sufficient conditions for support recovery and l∞-error bounds, as well as results showing the necessity of incoherence and bounds on the minimum value. We then turn to the case of random designs, in which each row of the design is drawn from a N(0, Σ) ensemble. For a broad class of Gaussian ensembles satisfying mutual incoherence conditions, we compute explicit values of thresholds 0 0, if n > 2(θu + δ)k log(p - k), then the Lasso succeeds in recovering the sparsity pattern with probability converging to one for large problems, whereas for n < 2(θl - δ)k log(p - k), then the probability of successful recovery converges to zero. For the special case of the uniform Gaussian ensemble (Σ = I p×p), we show that θl = θu = 1, so that the precise threshold n = 2k log (p - k) is exactly determined.
@cite_18: 
@cite_15: We consider the problem of estimating the conditional mean of a real Gaussian variable @math where the vector of the covariates @math follows a joint Gaussian distribution. This issue often occurs when one aims at estimating the graph or the distribution of a Gaussian graphical model. We introduce a general model selection procedure which is based on the minimization of a penalized least-squares type criterion. It handles a variety of problems such as ordered and complete variable selection, allows to incorporate some prior knowledge on the model and applies when the number of covariates @math is larger than the number of observations @math . Moreover, it is shown to achieve a non-asymptotic oracle inequality independently of the correlation structure of the covariates. We also exhibit various minimax rates of estimation in the considered framework and hence derive adaptiveness properties of our procedure.
@cite_41: Testing for the significance of a subset of regression coefficients in a linear model, a staple of statistical analysis, goes back at least to the work of Fisher who introduced the analysis of variance (ANOVA). We study this problem under the assumption that the coefficient vector is sparse, a common situation in modern high-dimensional settings. Suppose we have p covariates and that under the alternative, the response only depends upon the order of p^(1−α) of those, 0 ≤ α ≤ 1. Under moderate sparsity levels, that is, 0 ≤ α ≤ 1 2, we show that ANOVA is essentially optimal under some conditions on the design. This is no longer the case under strong sparsity constraints, that is, α > 1 2. In such settings, a multiple comparison procedure is often preferred and we establish its optimality when α ≥ 3 4. However, these two very popular methods are suboptimal, and sometimes powerless, under moderately strong sparsity where 1 2 1 2. This optimality property is true for a variety of designs, including the classical (balanced) multi-way designs and more modern “p > n” designs arising in genetics and signal processing. In addition to the standard fixed effects model, we establish similar results for a random effects model where the nonzero coefficients of the regression vector are normally distributed.
@cite_48: The problem of sparsity pattern or support set recovery refers to estimating the set of nonzero coefficients of an unknown vector beta* isin Ropfp based on a set of n noisy observations. It arises in a variety of settings, including subset selection in regression, graphical model selection, signal denoising, compressive sensing, and constructive approximation. The sample complexity of a given method for subset recovery refers to the scaling of the required sample size n as a function of the signal dimension p, sparsity index k (number of non-zeroes in beta*), as well as the minimum value betamin of beta* over its support and other parameters of measurement matrix. This paper studies the information-theoretic limits of sparsity recovery: in particular, for a noisy linear observation model based on random measurement matrices drawn from general Gaussian measurement matrices, we derive both a set of sufficient conditions for exact support recovery using an exhaustive search decoder, as well as a set of necessary conditions that any decoder, regardless of its computational complexity, must satisfy for exact support recovery. This analysis of fundamental limits complements our previous work on sharp thresholds for support set recovery over the same set of random measurement ensembles using the polynomial-time Lasso method (lscr1-constrained quadratic programming).
@cite_42: We study the problem of detection of a p-dimensional sparse vector ofparameters in the linear regression model with Gaussian noise. We establishthe detection boundary, i.e., the necessary and sufficient conditions for thepossibility of successful detection as both the sample size n and the dimensionp tend to the infinity. Testing procedures that achieve this boundary arealso exhibited. Our results encompass the high-dimensional setting (p » n).The main message is that, under some conditions, the detection boundaryphenomenon that has been proved for the Gaussian sequence model, extendsto high-dimensional linear regression. Finally, we establish the detectionboundaries when the variance of the noise is unknown. Interestingly, thedetection boundaries sometimes depend on the knowledge of the variance ina high-dimensional setting.
@cite_1: We consider the estimation of regression coefficients in a high-dimensional linear model. For regression coefficients in lr balls, we provide lower bounds for the minimax lq risk and minimax quantiles of the lq loss for all design matrices. Under an l0 sparsity condition on a target coefficient vector, we sharpen and unify existing oracle inequalities for the Lasso and Dantzig selector. We derive oracle inequalities for target coefficient vectors with many small elements and smaller threshold levels than the universal threshold. These oracle inequalities provide sufficient conditions on the design matrix for the rate minimaxity of the Lasso and Dantzig selector for the lq risk and loss in lr balls, 0≤ r≤ 1≤ q≤ ∞. By allowing q=∞, our risk bounds imply the variable selection consistency of threshold Lasso and Dantzig selectors.
@cite_31: 
@cite_34: In high-dimensional linear regression, the goal pursued here is to estimate an unknown regression function using linear combinations of a suitable set of covariates. One of the key assumptions for the success of any statistical procedure in this setup is to assume that the linear combination is sparse in some sense, for example, that it involves only few covariates. We consider a general, nonnecessarily linear, regression with Gaussian noise and study a related question, that is, to find a linear combination of approximating functions, which is at the same time sparse and has small mean squared error (MSE). We introduce a new estimation procedure, called Exponential Screening, that shows remarkable adaptation properties. It adapts to the linear combination that optimally balances MSE and sparsity, whether the latter is measured in terms of the number of nonzero entries in the combination (l 0 norm) or in terms of the global weight of the combination (l 1 norm). The power of this adaptation result is illustrated by showing that Exponential Screening solves optimally and simultaneously all the problems of aggregation in Gaussian regression that have been discussed in the literature. Moreover, we show that the performance of the Exponential Screening estimator cannot be improved in a minimax sense, even if the optimal sparsity is known in advance. The theoretical and numerical superiority of Exponential Screening compared to state-of-the-art sparse procedures is also discussed.
@cite_17: 
Recently, some high-dimensional problems have been studied from a minimax point of view. Wainwright @cite_48 @cite_30 provides minimax lower bounds for the problem of support estimation ( @math ). @cite_17 and Rigollet and Tsybakov @cite_34 have provided minimax upper bounds and lower bounds for @math and @math over @math balls for general fixed designs @math when the variance @math is known (see also Ye and Zhang @cite_1 and Abramovich and Grinshtein @cite_31 ). Arias- @cite_41 and @cite_42 have computed the asymptotic minimax detection boundaries for the testing problem @math for some specific designs. However, their study only encompasses reasonable dimensional problems ( @math grows polynomially with @math ). Some minimax lower bounds have also been stated for testing ( @math ) and prediction ( @math ) problems with Gaussian design @cite_15 @cite_18 . All the aforementioned results do not cover the ultra-high dimensional case and do not tackle the problem of adaptation to both @math and @math .