Minimax risks for sparse regressions : ultra-high dimensional phenomenons

Overview & Synopsis

Consider the standard Gaussian linear regression model Y = X theta(0) + epsilon, where Y is an element of R-n is a response vector and X is an element of R-nxp is a design matrix. Numerous work have been devoted to building efficient estimators of theta(0) when p is much larger than n. In such a situation, a classical approach amounts to assume that theta(0) is approximately sparse. This paper studies the minimax risks of estimation and testing over classes of k-sparse vectors theta(0). These bounds shed light on the limitations due to high-dimensionality. The results encompass the problem of prediction (estimation of X theta(0)), the inverse problem (estimation of theta(0)) and linear testing (testing X theta(0) = 0) . Interestingly, an elbow effect occurs when the number of variables k log(p/k) becomes large compared to n. 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