Minimax risks for sparse regressions: ultra-high dimensional phenomenons

DOI10.1214/12-EJS666zbMATH Open1334.62120arXiv1008.0526OpenAlexW2964097857MaRDI QIDQ1950804FDOQ1950804

Authors: Nicolas Verzelen 

Publication date: 28 May 2013

Published in: Electronic Journal of Statistics (Search for Journal in Brave)

Abstract: Consider the standard Gaussian linear regression model $Y=Xheta+epsilon$, where $Yin{R}^n$ is a response vector and $Xin{R}^{n\ast p}$ is a design matrix. Numerous work have been devoted to building efficient estimators of $heta$ when $p$ is much larger than $n$. In such a situation, a classical approach amounts to assume that $het{a}_0$ is approximately sparse. This paper studies the minimax risks of estimation and testing over classes of $k$-sparse vectors $heta$. These bounds shed light on the limitations due to high-dimensionality. The results encompass the problem of prediction (estimation of $Xheta$), the inverse problem (estimation of $het{a}_0$) and linear testing (testing $Xheta=0$). Interestingly, an elbow effect occurs when the number of variables $klog(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.

Full work available at URL: https://arxiv.org/abs/1008.0526

Recommendations

• Minimax-optimal nonparametric regression in high dimensions
• Nearly optimal minimax estimator for high-dimensional sparse linear regression
• Detection boundary in sparse regression
• Minimax \(\ell_q\) risk in \(\ell_p\) balls
• High-dimensional regression with unknown variance

zbMATH Keywords

dimension reductionhigh-dimensional regressionadaptive estimationminimax riskhigh-dimensional geometry

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Minimax procedures in statistical decision theory (62C20)

Cites Work

• Least angle regression. (With discussion)
• Detection boundary in sparse regression
• Simultaneous analysis of Lasso and Dantzig selector
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• High-dimensional graphs and variable selection with the Lasso
• Title not available (Why is that?)
• Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
• Regularization and Variable Selection Via the Elastic Net
• Global testing under sparse alternatives: ANOVA, multiple comparisons and the higher criticism
• Gaussian model selection with an unknown variance
• Minimax detection of a signal for \(l^ n\)-balls.
• Higher criticism for detecting sparse heterogeneous mixtures.
• Title not available (Why is that?)
• Gaussian model selection
• Minimax risk over \(l_ p\)-balls for \(l_ q\)-error
• Kernel dimension reduction in regression
• Local operator theory, random matrices and Banach spaces.
• Decoding by Linear Programming
• A simple proof of the restricted isometry property for random matrices
• Dimension reduction for conditional mean in regression
• Non-asymptotic minimax rates of testing in signal detection
• Estimation of Gaussian graphs by model selection
• Compressed sensing
• Minimal penalties for Gaussian model selection
• Rate minimaxity of the Lasso and Dantzig selector for the \(l_{q}\) loss in \(l_{r}\) balls
• Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
• Minimax risks for sparse regressions: ultra-high dimensional phenomenons
• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
• Asymptotically minimax hypothesis testing for nonparametric alternatives. I
• Asymptotically minimax hypothesis testing for nonparametric alternatives. II
• Exponential screening and optimal rates of sparse estimation
• Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
• Title not available (Why is that?)
• Near-ideal model selection by \(\ell _{1}\) minimization
• Smallest singular value of a random rectangular matrix
• An alternative point of view on Lepski's method
• Asymptotically minimax hypothesis testing for nonparametric alternatives. III
• Adaptive tests of linear hypotheses by model selection
• Goodness-of-fit tests for high-dimensional Gaussian linear models
• Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
• Adaptive detection of a signal of growing dimension. II
• Aggregation by Exponential Weighting and Sharp Oracle Inequalities
• On minimax estimation of a sparse normal mean vector
• A New Lower Bound for Multiple Hypothesis Testing
• High-dimensional Gaussian model selection on a Gaussian design
• MAP model selection in Gaussian regression
• Adaptive detection of a signal of growing dimension. I

Cited In (53)

• Optimal and Safe Estimation for High-Dimensional Semi-Supervised Learning
• Statistical inference for high-dimensional linear regression with blockwise missing data
• Adaptive estimation of high-dimensional signal-to-noise ratios
• Adaptive robust estimation in sparse vector model
• Adaptive estimation of the baseline hazard function in the Cox model by model selection, with high-dimensional covariates
• Robust regression via mutivariate regression depth
• Nearly optimal minimax estimator for high-dimensional sparse linear regression
• Detection boundary in sparse regression
• Estimating minimum effect with outlier selection
• Asymptotic risk and phase transition of \(l_1\)-penalized robust estimator
• Accuracy assessment for high-dimensional linear regression
• A global homogeneity test for high-dimensional linear regression
• Title not available (Why is that?)
• Minimax optimal estimation in partially linear additive models under high dimension
• Estimation of linear projections of non-sparse coefficients in high-dimensional regression
• High-dimensional asymptotics of likelihood ratio tests in the Gaussian sequence model under convex constraints
• Greedy variance estimation for the LASSO
• Optimal adaptive estimation of linear functionals under sparsity
• Slope meets Lasso: improved oracle bounds and optimality
• Minimax-optimal nonparametric regression in high dimensions
• Optimal sparsity testing in linear regression model
• SLOPE is adaptive to unknown sparsity and asymptotically minimax
• Estimation and variable selection with exponential weights
• Sharp oracle inequalities for low-complexity priors
• Minimax rate of testing in sparse linear regression
• Regularization and the small-ball method. II: Complexity dependent error rates
• Solution of linear ill-posed problems by model selection and aggregation
• Detecting positive correlations in a multivariate sample
• Minimax risks for sparse regressions: ultra-high dimensional phenomenons
• Adaptive confidence sets in shape restricted regression
• Block-Diagonal Covariance Selection for High-Dimensional Gaussian Graphical Models
• Tight conditions for consistency of variable selection in the context of high dimensionality
• A posterior probability approach for gene regulatory network inference in genetic perturbation data
• Inference for high-dimensional linear expectile regression with de-biasing method
• Estimation of functionals of sparse covariance matrices
• Sparse regression and support recovery with \(\mathbb{L}_2\)-boosting algorithms
• Variable selection consistency of Gaussian process regression
• Minimax adaptive tests for the functional linear model
• How can we identify the sparsity structure pattern of high-dimensional data: an elementary statistical analysis to interpretable machine learning
• Estimation of the \(\ell_2\)-norm and testing in sparse linear regression with unknown variance
• Optimization of sampling designs for pedigrees and association studies
• Honest Confidence Sets for High-Dimensional Regression by Projection and Shrinkage
• The all-or-nothing phenomenon in sparse linear regression
• Global and Simultaneous Hypothesis Testing for High-Dimensional Logistic Regression Models
• Optimal detection of sparse principal components in high dimension
• Inferring large graphs using \(\ell_1\)-penalized likelihood
• Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix
• Beyond support in two-stage variable selection
• Adaptive estimation of the sparsity in the Gaussian vector model
• Empirical priors for prediction in sparse high-dimensional linear regression
• Inference for High-Dimensional Linear Mixed-Effects Models: A Quasi-Likelihood Approach
• High-dimensional regression with unknown variance
• Comments on: ``Statistical inference and large-scale multiple testing for high-dimensional regression models.

This page was built for publication: Minimax risks for sparse regressions: ultra-high dimensional phenomenons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1950804)