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.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
The Concentration of Measure Phenomenon
Ledoux, M. (2005) · Mathematical Surveys and Monographs · doi:10.1090/surv/089 · Cited by 1,700
Wainwright, M. J. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2016018 · Cited by 1,198
Self-citationLedoux, M., & Talagrand, M. (1991) · doi:10.1007/978-3-642-20212-4 · Cited by 1,160
Statistical Estimation: Asymptotic Theory
Samaniego, F. J. (2014) · Chapman & Hall/CRC eBooks · doi:10.1201/b16414-10 · Cited by 1,155
Compressed sensing and best 𝑘-term approximation
Cohen, A., Dahmen, W., & DeVore, R. (2008) · Journal of the American Mathematical Society · doi:10.1090/s0894-0347-08-00610-3 · Cited by 1,002
On Model Selection Consistency of Lasso
ZhaoPeng, & Yubin, Y. (2006) · Journal of Machine Learning Research · doi:10.5555/1248547.1248637 · Cited by 996
Adaptive estimation of a quadratic functional by model selection
Laurent, B., & Massart, P. (2000) · The Annals of Statistics · doi:10.1214/aos/1015957395 · Cited by 995
Lasso-type recovery of sparse representations for high-dimensional data
Meinshausen, N., & Yu, B. (2006) · Cited by 744
Self-citationEigenvalues of large sample covariance matrices of spiked population models
Baik, J., & Silverstein, J. W. (2006) · Journal of Multivariate Analysis · doi:10.1016/j.jmva.2005.08.003 · Cited by 701
Information-theoretic determination of minimax rates of convergence
Yang, Y., & Barron, A. (1999) · The Annals of Statistics · doi:10.1214/aos/1017939142 · Cited by 555
Empirical Processes in M-Estimation
van de Geer, S. (2000) · Cited by 530
The sparsity and bias of the Lasso selection in high-dimensional linear regression
Zhang, C.-H., & Huang, J. (2008) · The Annals of Statistics · doi:10.1214/07-aos520 · Cited by 506
Lasso-type recovery of sparse representations for high-dimensional data
Meinshausen, N., & Yu, B. (2009) · The Annals of Statistics · doi:10.1214/07-aos582 · Cited by 489
Self-citationBirgé, L., & Massart, P. (2001) · Journal of the European Mathematical Society · doi:10.1007/s100970100031 · Cited by 479
Local Operator Theory, Random Matrices and Banach Spaces
(2001) · Handbook of the Geometry of Banach Spaces · doi:10.1016/s1874-5849(01)80010-3 · Cited by 432
Restricted Eigenvalue Properties for Correlated Gaussian Designs
Raskutti, G., Wainwright, M. J., & Yu, B. (2010) · doi:10.5555/1756006.1859929 · Cited by 367
Self-citationPersistence in high-dimensional linear predictor selection and the virtue of overparametrization
Greenshtein, E., & Ritov, Y. (2004) · Bernoulli · doi:10.3150/bj/1106314846 · Cited by 362
Empirical Processes in M-Estimation
Jammalamadaka, S. R. (2001) · Journal of the American Statistical Association · doi:10.1198/jasa.2001.s399 · Cited by 345
Yu, B. (1997) · Festschrift for Lucien Le Cam · doi:10.1007/978-1-4612-1880-7_29 · Cited by 309
Self-citationAggregation for Gaussian regressionPreprint
Bunea, F., Tsybakov, A. B., & Wegkamp, M. H. (2016) · Cited by 297
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-citationMinimax risk overl p -balls forl p -error
Donoho, D. L., & Johnstone, I. M. (1994) · Probability Theory and Related Fields · doi:10.1007/bf01199026 · Cited by 218
Entropy numbers of diagonal operators between symmetric Banach spaces
Schütt, C. (1984) · Journal of Approximation Theory · doi:10.1016/0021-9045(84)90021-2 · Cited by 207
Aggregation for Gaussian regression
Bunea, F., Tsybakov, A. B., & Wegkamp, M. H. (2007) · The Annals of Statistics · doi:10.1214/009053606000001587 · Cited by 179
A Lower Estimate for Entropy Numbers
Kühn, T. (2001) · Journal of Approximation Theory · doi:10.1006/jath.2000.3554 · Cited by 99
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
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.