Curse of dimensionality using trees

Question

The curse of dimensionality refers to the fact when a model tries to fit the data in a very high dimensional space (and there is not enough training data). In my mind, I believe that this curse happens for all machine learning models. However, someone told me that trees (for instance xgboost and lgbm) are not affected by this curse and this family of models will learn to ignore some dimensions on their own. How true is this statement and why?

There is already an answer in this post, but can I have a more in depth answer?

Answer 1

Yeah I wouldn't say that trees are not affected by it but that they are 'generally' more robust than most other methods like a linear model. This is due to how they handle features by assessing each and accessing only one at a time to generate a split (assuming we are talking about CART). So you could have 100 features for 50 observations but a tree may only use 3 of those features to generate a prediction, they do not 'ignore' the other features but they do not use them for fitting.

This is in stark contrast to a linear regression which would generate a coefficient for each feature or a neural net that would generate a ton of parameters for each.

It's that overparameterization that can get us into trouble and trees are just better at handling it, although there are specific implementations of NNs and LRs which are better than the standard methods.

So, in short (this is a generalization of course):

If you are in the situation where you have way more features than observations then all methods benefit from doing analysis to eliminate less-than-useful features, trees just don't benefit as much as most other methods...generally