# Can gradient boosted trees fit any function?

For neural networks we have the universal approximation theorem which states that neural networks can approximate any continuous function on a compact subset of $R^n$.

Is there a similar result for gradient boosted trees? It seems reasonable since you can keep adding more branches, but I cannot find any formal discussion of the subject.

EDIT: My question seems very similar to Can regression trees predict continuously?, though maybe not asking exactly the same thing. But see that question for relevant discussion.

• Good question! I could not find anything on that, but here are PAC bounds on decision trees. Try asking again on cstheory. – Emre Jun 7 '18 at 17:25
• See here: projecteuclid.org/download/pdf_1/euclid.aos/1013203451. It is an old read. I believe it has what you are looking for. As far as I understand, in principle, they can. Let me know what you think of it. – TwinPenguins Jun 7 '18 at 18:27