Minimax Rates of Estimation for High-Dimensional Linear Regression Over q -Balls

By Garvesh Raskutti, Martin J. Wainwright, Bin Yu. 2009

596 citations recorded by the source corpus.

Consider the high-dimensional linear regression model y = X β* + w, where y ∈ \BBRn is an observation vector, X ∈ \BBRn × d is a design matrix with d >; n, β* ∈ \BBRd is an unknown regression vector, and w ~ N(0, σ2I) is additive Gaussian noise. This paper studies the minimax rates of convergence for estimating β* in either l2-loss and l2-prediction loss, assuming that β* belongs to an lq -ball \BBBq(Rq) for some q ∈ [0,1]. It is shown that under suitable regularity conditions on the design matrix X, the minimax optimal rate in l2-loss and l2-prediction loss scales as Θ(Rq ([(logd)/(n)])1-q/2). The analysis in this paper reveals that conditions on the design matrix X enter into the rates for l2-error and l2-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 over lq-balls. For the special case q=0, corresponding to models with an exact sparsity constraint, our results show that although computationally efficient l1-based methods can achieve the minimax rates up to constant factors, they require slightly stronger assumptions on the design matrix X than optimal algorithms involving least-squares over the l0-ball.

Subfields: Computational Mathematics, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Best Subset Selection via a Modern Optimization Lens (2015, background): “, p ≤ 30) and theoretical evidence, see for example, [46, 58, 38, 31, 56, 48] and the references therein.”
The geometry of differential privacy: the sparse and approximate cases (2012, methodology): “Both algorithms rely on recursively computing an orthonormal basis for R d , based on the minimum volume enclosing ellipsoid of the columns of the query matrix A .”
Hypothesis Testing in High-Dimensional Regression Under the Gaussian Random Design Model: Asymptotic Theory (2013, background): “[22, 18, 23]; (3) The model selection (or support recovery) properties typically by bounding P{supp(θ̂) 6= supp(θ0)}, see e.”
Using Non-invertible Data Transformations to Build Adversarial-Robust Neural Networks (2016, background): “According to Theorem 1 in [28], under certain assumption, we can obtain a lower bound of the reconstruction error, which is the L 2 norm of the difference between X and ˆ X as shown in (7): where s denotes the sparsity of X . κ 0 is a constant whose value depends closely on the data set.”
Lower bounds on the performance of polynomial-time algorithms for sparse linear regression (2014, methodology): “The RE condition (10) and related quantities have been studied extensively in past work on basis pursuit and the Lasso (e.g. Bickel et al., 2009; Meinshausen and Yu, 2009; Raskutti et al., 2011); see the paper (Van De Geer and Bühlmann, 2009) for an overview of the different types of RE parameters.”
High-Dimensional Gaussian Process Bandits (2013, background): “This idea has been also at the root of nonparametric regression approaches [4, 5, 6, 7].”
Restricted Eigenvalue Properties for Correlated Gaussian Designs (2010, methodology): “Moreover, this ℓ 2 -convergence rate is known to be minimax optimal (Raskutti et al., 2009) in the regime k/p → 0.”
Differentially Private Feature Selection via Stability Arguments, and the Robustness of the Lasso (2013, methodology): “Differentially private algorithms for sparse regression were first considered in our recent work (Kifer et al. [13]).”
Estimation of (near) low-rank matrices with noise and high-dimensional scaling (2009, methodology): “[45] for details), this lower bound implies the claim (25).”
Linear Hypothesis Testing in Dense High-Dimensional Linear Models (2016, background): “There are several articles showing that the regularized procedures have non-vanishing estimation errors in such settings (Donoho and Johnstone, 1994; Raskutti et al., 2011; Cai and Guo, 2016).”
High-dimensional regression with unknown variance (2011, background): “The minimax lower bound (6) has been first proved in [61, 62, 79] while (7) is stated in [77].”
On the Fundamental Limits of Adaptive Sensing (2011, background): “The crux of our argument is thus to show that it is not possible to choose sensing vectors adaptively in such a way that the support of the signal may be estimated accurately.”
Exponential Screening and optimal rates of sparse estimation (2010, background): “The minimax rates on the ℓ 0 and ℓ 1 balls obtained in Raskutti et al. (2009, Theorem 3) are similar to (5.24) and (5.25) but, because of the speciﬁc asymptotics, some eﬀects are wiped out there.”