VC dimension of a greedy decision tree vs a optimal decision tree

Take the 𝐶𝐴𝑅𝑇 binary splitting tree, for example, the practical implementation is a greedy splitting procedure.

With some fixed depth ℎ, one can fit an optimal decision tree (by trying every possible split).

The two different training procedures would hopefully result in different trees.

My question is whether the VC dimension of both trees/models are the same?

From my school memory, the VC dimension is independent of learning algorithm, can we treat greedy and optimal decision tree are only different in learning algorithms?

• There are many (many many) breeds of optimal; one of them is greedy. Did you have a particular alternative? Did you see this? link? Nov 22, 2020 at 4:06
• so I'm interested in an optimal CART. try out every binary split with different orders. and thanks for the link, I do read those before, and yet, my interest isn't really in the absolute VC dimension, as greedy is different from the optimal, whether if their VC dimension is the same is the thing I'm interested in Nov 22, 2020 at 4:10
• Optimal isn't singular. There are billions of breeds, possibly infinite families, of optimal. Optimal means you found a balance point between two competing criteria that, according to a mathematical cost formula, was the best that you could find. There are many many potential cost-formulae that you could use. Sparsity, Vastness, any of the thousands of variants of weighted error to some power "p". Energy, Force, Time. CPU heat. Whether the clock has contiguous subsequences that can be found in the first 10k digits of pi. Which optimal do you mean? Nov 23, 2020 at 14:46
• ok, so let me be strict, my goal is to compare greedy and "optimal" CART, their cost function would be the same, e.g. entropy impurity. since greedy CART would fix one binary split at a time, the "optimal" would try out different binary split combinations every time. I'm really trying to control variable here, instead of comparing two completely different model Nov 23, 2020 at 14:50