Minimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls

Abstract

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.