The DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Minimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls
Open accessAbstract
Consider the high-dimensional linear regression modely=Xβ*+w, wherey∈ \BBRnis an observation vector,X∈ \BBRn×dis a design matrix withd>;n, β*∈ \BBRdis an unknown regression vector, andw~N(0, σ2I) is additive Gaussian noise. This paper studies the minimax rates of convergence for estimating β*in eitherl2-loss andl2-prediction loss, assuming that β*belongs to anlq-ball \BBBq(Rq) for someq∈ [0,1]. It is shown that under suitable regularity conditions on the design matrixX, the minimax optimal rate inl2-loss andl2-prediction loss scales as Θ(Rq([(logd)/(n)])1-q/2). The analysis in this paper reveals that conditions on the design matrixXenter into the rates forl2-error andl2-prediction error in complementary ways in the upper and lower bounds. Our proofs of the lower bounds are information theoretic in nature, based on Fano's inequality and results on the metric entropy of the balls \BBBq(Rq), whereas our proofs of the upper bounds are constructive, involving direct analysis of least squares overlq-balls. For the special caseq=0, corresponding to models with an exact sparsity constraint, our results show that although computationally efficientl1-based methods can achieve the minimax rates up to constant factors, they require slightly stronger assumptions on the design matrixXthan optimal algorithms involving least-squares over thel0-ball.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827596304010 · Cited by 6,845
Nearly unbiased variable selection under minimax concave penalty
Zhang, C.-H. (2010) · The Annals of Statistics · doi:10.1214/09-aos729 · Cited by 3,835
High dimensional graphs and variable selection with the Lasso
Meinshausen, N., & Bühlmann, P. (2006) · Cited by 2,539
High-dimensional graphs and variable selection with the Lasso
Meinshausen, N., & Bühlmann, P. (2006) · The Annals of Statistics · doi:10.1214/009053606000000281 · Cited by 2,521
Simultaneous analysis of Lasso and Dantzig selector
Bickel, P. J., Ritov, Y., & Tsybakov, A. B. (2009) · The Annals of Statistics · doi:10.1214/08-aos620 · Cited by 2,396
Convergence of Stochastic Processes.
Robinson, P. M., & Pollard, D. (1985) · Economica · doi:10.2307/2553898 · Cited by 2,184
Stable recovery of sparse overcomplete representations in the presence of noise
Donoho, D. L., Elad, M., & Temlyakov, V. N. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.860430 · Cited by 2,183
The Dantzig selector: Statistical estimation when p is much larger than n
Candes, E., & Tao, T. (2007) · The Annals of Statistics · doi:10.1214/009053606000001523 · Cited by 1,747
Cited by
High-Dimensional Statistics: A Non-Asymptotic Viewpoint
Wainwright, M. J. (2019) · Cambridge University Press eBooks · doi:10.1017/9781108627771 · Cited by 882
Self-citationBest subset selection via a modern optimization lens
Bertsimas, D., King, A., & Mazumder, R. (2016) · The Annals of Statistics · doi:10.1214/15-aos1388 · Cited by 655
Estimation of (near) low-rank matrices with noise and high-dimensional scaling
Negahban, S., & Wainwright, M. J. (2011) · The Annals of Statistics · doi:10.1214/10-aos850 · Cited by 537
Self-citationRestricted Eigenvalue Properties for Correlated Gaussian Designs
Raskutti, G., Wainwright, M. J., & Yu, B. (2010) · doi:10.5555/1756006.1859929 · Cited by 367
Self-citationSparse Modeling for Image and Vision Processing
Mairal, J. (2014) · now publishers, Inc. eBooks · doi:10.1561/9781680830095 · Cited by 322
A General Theory of Concave Regularization for High-Dimensional Sparse Estimation Problems
Zhang, C.-H., & Zhang, T. (2012) · Statistical Science · doi:10.1214/12-sts399 · Cited by 296
A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers
Negahban, S. N., Ravikumar, P., Wainwright, M. J., & Yu, B. (2012) · Statistical Science · doi:10.1214/12-sts400 · Cited by 287
Self-citationNoisy matrix decomposition via convex relaxation: Optimal rates in high dimensions
Agarwal, A., Negahban, S., & Wainwright, M. J. (2012) · The Annals of Statistics · doi:10.1214/12-aos1000 · Cited by 280
Self-citationDavenport, M. A., Plan, Y., van den Berg, E., & Wootters, M. (2014) · Information and Inference · doi:10.1093/imaiai/iau006 · Cited by 277
An Exact and Robust Conformal Inference Method for Counterfactual and Synthetic Controls
Chernozhukov, V., Wüthrich, K., & Zhu, Y. (2021) · Journal of the American Statistical Association · doi:10.1080/01621459.2021.1920957 · Cited by 176
Metadata
- Authors
- Raskutti, G., Wainwright, M. J., & Yu, B.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2011-10
- Volume
- 57
- Issue
- 10
- Pages
- 6976-6994
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2159700154
- Cited by
- 455
- References
- 35
- FWCI
- 29.49
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.