regularization on many features

Question

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?

Answer 1

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?

I don't think a general answer exists. The performance of regularization depends not just on the number of features but on how many of them are informative, how informative the informative features are, how noisy the dependent variable is, the type of model, etc. If you're curious about a specific case, why not do a simulation experiment and see what you get?