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

By Nicolas Verzelen. 2010

145 citations recorded by the source corpus.

Consider the standard Gaussian linear regression model $Y=X\theta+\epsilon$, where $Y\in R^n$ is a response vector and $ X\in R^{n*p}$ is a design matrix. Numerous work have been devoted to building efficient estimators of $\theta$ 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$. These bounds shed light on the limitations due to high-dimensionality. The results encompass the problem of prediction (estimation of $X\theta$), the inverse problem (estimation of $\theta_0$) and linear testing (testing $X\theta=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.

Subfields: Computational Mechanics, Computer Networks and Communications, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/ccdfb9985ce6c83428715bc93dd5eb325a785b74

Citations in the corpus

• SLOPE is Adaptive to Unknown Sparsity and Asymptotically Minimax (2015, unknown): “Then For information, it is known that under some regularity conditions on the design [46, 54], the minimax risk is on the order of O ( σ 2 k log( p/k )), without a tight matching in the lower and upper bounds.”
• Robust regression via mutivariate regression depth (2017, unknown): “he order of κ. In contrast, Theorem 3.2 removes these two assumptions and the convergence rates hold uniformly for all β ∈ Θs. When ǫ = 0, the rates obtained in Theorem 3.2 are all minimax optimal by [37, 26, 34]. Though most lower bound results in the literature for sparse linear regression are for”
• Slope meets Lasso: Improved oracle bounds and optimality (2016, unknown): “Several papers have addressed this issue for the prediction risk [23, 18, 22, 2, 26], for the l2-estimation risk [22, 26, 8], and for the lq-estimation risk with general q [22, 28, 18].”
• Confidence intervals for high-dimensional linear regression: Minimax rates and adaptivity (2015, unknown): “where ‖β‖0 denotes the number of the nonzero coordinates of a vector β ∈ R; see, for example, [3, 12, 23, 26].”
• Detection boundary in sparse regression (2010, unknown): “Related work [27, 28] develop minimax bounds for detection in model (1.”
• High-dimensional regression with unknown variance (2011, unknown): “The minimax lower bound (6) has been first proved in [61, 62, 79] while (7) is stated in [77].”
• On the Fundamental Limits of Adaptive Sensing (2011, unknown): “See also [13]–[15] for other asymptotic results in this direction.”