Which kind of distributions can decision trees learn (well)?

Question

Suppose I have a classification task in $\mathbb{R}^d$, given by a distribution $P$ and training data $D$. The decision boundary is $$B = \{x \; : \; P(Y=1|x) = P(Y=0|x)\}$$ Assume I am learning a decision tree (not a random forest) of a given depth $k$, trying to classify the data correctly in each leaf. The loss function is the distance to the decision boundary. Of course, it depends on the geometry of $B$ on how well this task can be performed. If $B$ can be approximated by axis-aligned cuts, we can almost perfectly learn $B$ using the tree.

My question: Is there research on distributional (not so much geometric) assumptions on $P$ that give bounds on how good the optimal tree is?

Answer 1

One of the great advantages of decision trees is their relative robustness against different distributions. Because they simply make axis-parallel cuts in the data, their performance is generally considered invariant to skewness. In other words, one of the big advantages of decision trees is that they are aggressively non-parametric. I can't find any empirical research directly addressing this, but researchers commonly allude to it in there research. See here and here.

The biggest limitation seems to be a tendency to struggle with class imbalance, as I found a couple of different research papers that address this. I would note that if possible you should consider random forests as they are substantially better.