6
$\begingroup$

My understanding is that the curse of dimensionality implies that we need an exponential amount of data with respect to the number of features we include in our model. Is this correct?

If so, what does "we need" mean? Does it imply that we need at least that many data points to ensure we don't make a mistake?...to negate the effects of the dimensionality?..to ensure we've hit a global optimum?...something else?

Most important question(s) to me:

What specifically are the implications of the the curse of dimesionality for ordinary least squares linear regression?

If we are performing an OLS linear regression with p covariates, do we need 2^p data points?

I've read about rules of thumb for determining how many data points you need for OLS regression with respect to the number of covariates included in the model, and I know that the answer entirely depends on the properties of the data, but I'm trying to get a better understanding for how the curse of dimensionality plays a role in/affects this.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Linear regression model is a model. OLS is an estimation technique. Given this, what kind of setting are you actually interested in? $\endgroup$
    – Richard Hardy
    Oct 31, 2016 at 19:04
  • $\begingroup$ I'm trying to determine how the number of data points needed for a statistically significant estimate in the context of an ordinary least squares linear regression varies with respect to the number of covariates. I'm wondering if it increases exponentially, or if there is perhaps some other function that relates the two things. $\endgroup$
    – Kapocsi
    Oct 31, 2016 at 19:14
  • 2
    $\begingroup$ For a fixed class of models -- linear regression -- the number of parameters to be estimated equals the number of variables, plus the intercept. So the number of parameters grows one-for-one with the number of features. As long as $n>p$, the model is identified and the parameters can be estimated (but estimation precision drops as $p$ grows relative to $n$). $\endgroup$
    – Richard Hardy
    Oct 31, 2016 at 19:17
  • $\begingroup$ Adding "linear" to regression does not change anything, IMHO, as this is what we typically assume if the qualifier "linear" is omitted. So if you wanted to highlight something, what was it? $\endgroup$
    – Richard Hardy
    Oct 31, 2016 at 19:26
  • 1
    $\begingroup$ Depends on how many parameters come with an increase in $p$. By including a new feature you may add one more variable in the regression (the feature itself) or you may also add interactions will all the existing variables. Only the second case would reflect for the curse of dimensionality, IMHO. Scratch this, now after you recent edit this is irrelevant. $\endgroup$
    – Richard Hardy
    Oct 31, 2016 at 20:00

2 Answers 2

Reset to default
6
$\begingroup$

Edit: As @Richard Hardy pointed out, the linear model under squared loss and ordinary least squares (OLS) are different things. I revised my answer to discuss the linear regression model only, where we are trying to check if the curse of dimesionality (CoD) is present when solving the following optimization problem: $$ \min \|X\beta-y\|_2^2. $$

In most cases, linear regression model will not suffer from CoD. This is because the number of parameters in the OLS will NOT increase exponentially with respect to the number of features / independent variables / columns. (Unless we include all "interaction" terms for all features as mentioned in a comment.)

Suppose we have a data matrix $X$ that is $n \times p$, i.e., we have $n$ data points and $p$ features. It is possible in "machine learning context" that $n$ is on the scale of millions and $p$ is on the scale of thousands to millions. The linear model even works for $p \gg n$ as well once we add regularization.

To summarize

  • For the linear model, the number of parameters is the same as the number of features (let's assume we do not have the intercept.)

  • The CoD will happen when we have the number of parameters growing exponentially with the number of features. Here is an example: let us assume we have $p$ discrete (binary) random variables. The joint distribution table has $2^p$ rows. In this case, CoD will happen.

Improve this answer
$\endgroup$
11
  • 1
    $\begingroup$ it is very common $n$ is in the scale of millions and $p$ is in the scale of thousands to millions. No, this is not very common. Actually, there are relatively few fields where this is common (as compared with the number of fields where this is not common). Also, OLS is not a model, it is an estimation technique. It could be applied on a model suffering from the curse of dimensionality (which would normally be problematic, e.g. yield a singular $X^t X$ matrix) or it could be applied to a model that does not suffer from the curse of dimensionality. $\endgroup$
    – Richard Hardy
    Oct 31, 2016 at 19:06
  • $\begingroup$ (In your first bullet point the distinction between a model and an estimation technique is especially relevant.) $\endgroup$
    – Richard Hardy
    Oct 31, 2016 at 19:11
  • $\begingroup$ @RichardHardy the curse of dimensionality doesn't really have anything to do with whether $X'X$ is singular. $\endgroup$
    – Hong Ooi
    Oct 31, 2016 at 19:17
  • 2
    $\begingroup$ @HongOoi, I had this in mind: if you let the number of regressors grow exponentially with the number of features (e.g. incuding all interactions between features in the model), then $X'X$ quickly becomes singular as the number of parameters exceed the sample size. There you have the connection. $\endgroup$
    – Richard Hardy
    Oct 31, 2016 at 19:20
  • 1
    $\begingroup$ @RichardHardy The meaning of the curse of dimensionality is that with large p, you need very large n to get statistically reliable estimates. This is only tangentially related to getting mathematically stable estimates, which is what singularity is about. $\endgroup$
    – Hong Ooi
    Oct 31, 2016 at 19:26
4
$\begingroup$

I think that everything that hxd1011 says is correct, however if one is interested in prediction rather than description, CoD can rear it's ugly head. For example if one is using Akaike I]information Criteria to decide on model accuracy, then the value is proportional to the number ,p, of variables. Since a lower AIC is interpreted as meaning higher model quality, the number of variables used effects model quality. The same things occurs with the Bayesian information criteria, but there the BIC value depends on log(n)*p, so the effect is even more pronounced.
If these examples aren't 'exponentialish' enough, then consider a best subsets regression. Again, for prediction, it may well be that the best model doesn't contain all the variables. Best subsets looks at all the distinct models one gets by considering all the different subsets of the p variables. It then uses some criteria (frequently AIC or BIC !) to choose the 'best' model. If there are p variables there are $\binom {p}{k}$ such models using exactly k of the variables and summing over all k we get that one has to compare (via some computation) $\sum_{k=0}^{k=p} \binom {p}{k} = 2^p $ different models. There is an exponential ! One reason for the use of various regularized regression methods is that the number of models one needs to check with best subsets is exponential in p !

Originally, this was a comment, but it is too long and I don't see how editing it will be possible, so I've posted this comment as an answer.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ +1 for the idea of combinations. Noting that the OP does not necessarily seem to specify a linear (polynomial) model, another way that combinations can come up would be interaction terms (e.g. a higher order polynomial model, making terms from your subsets). This is one of the reasons why high-order polynomial models are not recommended, in fact. $\endgroup$
    – GeoMatt22
    Oct 31, 2016 at 19:44
  • $\begingroup$ @ GeoMatt22. Imagine a best subsets of an unspecified order polynomial regression :) . That would get hairy ! $\endgroup$
    – meh
    Oct 31, 2016 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.