# regularization on many features

Suppose we have an nxp data matrix, with p >> n. I've read that regularization methods can help with this problem by limiting the complexity of the model. So it seems like some problems like text classification, people can just throw in hundreds of thousands of features into the model.

But what if p is VERY large relative to n? Consider a binary classification problem where y in {-1,1}. Let's say n = 100 and p = 10^(10^(10^(10^(10)))), where every predictor except one is just noise with values in {-1,1} generated from Bin(0.5). There is just one predictor z with true signal that say has a 10% correlation with y, and suppose we have a priori (based on theory) knowledge that z contains true signal.

Given we have so many features, there are almost certainly going to be several features with perfect or near perfect classification performance. Thus it seems like if we throw all the features into some model, no matter what model selection and validation method, those "noise" predictors are going to be chosen over z. So the regularized model with many features would do worse than a simple model with just one variable, z.

So is there a point at which the number of features is too large for regularization methods to handle?

• Do you have any idea how big p = 10^(10^(10^(10^(10)))) really is? You will NEVER have anything even close to that number of features! Of course, with n=100 and your p (binary predictors), with probability extremely close to 1, many predictors will be identical to the response $y$, so regularization will not help, of course. You should concentrate on some practical problem with many predictors. How many could you have, really, realistically? Sep 18, 2016 at 19:51
• Right of course p will never be anything that big, but is there a way to get an idea of at which point the size of p becomes problematic? It seems like p=1 million is not even a big deal with n = 100,000, whatabout p = 1 trillion? etc... Sep 18, 2016 at 23:06