15
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Good question! I could not find anything on that, but here are PAC bounds on decision trees. Try asking again on cstheory. $\endgroup$
    – Emre
    Jun 7, 2018 at 17:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – TwinPenguins
    Jun 7, 2018 at 18:27
  • 1
    $\begingroup$ I don't have a rigourous answer to your question but here are my thoughts: Trees are step functions and those can approximate any continuous function in $R^n$ $\endgroup$
    – Smile
    Oct 19, 2020 at 17:04

1 Answer 1

Reset to default
2
$\begingroup$

Yes - create a region for each data point (i.e., memorize the training data).

Thus it is possible for gradient boosted trees fit any training data, but it would have limited generalization to new data.

Improve this answer
$\endgroup$

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.