Breakdown point of model selection when the number of variables exceeds the number of observations

The classical multivariate linear regression problem assumes p variables X₁, X₂, . . ., X_p and a response vector y, each with n observations, and a linear relationship between the two: y = Xß + z, where z ∼ N(O,σ²). We point out that when p > n, there is a breakdown point for standard model selection schemes, such that model selection only works well below a certain critical complexity level depending on n/p. We apply this notion to some standard model selection algorithms (Forward Stepwise, LASSO, LARS) in the case where p ≫ n. We and that 1) the breakdown point is well-de ned for random X -models and low noise, 2) increasing noise shifts the breakdown point to lower levels of sparsity, and reduces the model recovery ability of the algorithm in a systematic way, and 3) below breakdown, the size of coefcient errors follows the theoretical error distribution for the classical linear model.