2009/10/11 by Garvesh Raskutti, Martin J. Wainwright, Raskutti, Garvesh +3 · 6 citations
Engineering · Decision Sciences · Mathematics · #Sparse and Compressive Sensing Techniques #Probabilistic and Robust Engineering Design #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.0910.2042
Consider the standard linear regression model \y = \Xmat \betastar + w, where \y ∈ \real^\numobs is an observation vector, \Xmat ∈ \real\numobs × \pdim is a design matrix, \betastar ∈ \real^\pdim is the unknown regression vector, and w ∼ N(0, σ2 I) is additive Gaussian noise. This paper studies the minimax rates of convergence for estimation of \betastar for ℓ_\rpar-losses and in the ℓ2-prediction loss, assuming that \betastar belongs to an ℓ\qpar-ball \Ballq(\myrad) for some \qpar ∈ [0,1]. We show that under suitable regularity conditions on the design matrix \Xmat, the minimax error in ℓ2-loss and ℓ2-prediction loss scales as \Rq ((log \pdim)/(n))1-(\qpar)/(2). In addition, we provide lower bounds on minimax risks in ℓ\rpar-norms, for all \rpar ∈ [1, +∞], \rpar ≠ \qpar. 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 \Ballq(\myrad), whereas our proofs of the upper bounds are direct and constructive, involving direct analysis of least-squares over ℓ\qpar-balls. For the special case q = 0, a comparison with ℓ2-risks achieved by computationally efficient ℓ1-relaxations reveals that although such methods can achieve the minimax rates up to constant factors, they require slightly stronger assumptions on the design matrix \Xmat than algorithms involving least-squares over the ℓ0-ball.