XGBoost: universal approximator?

Question

There are various "universal approximation theorems" for neural networks, perhaps the most famous of which is the 1989 variant by George Cybenko. Setting aside technical conditions, the universal approximation theorems say that any "decent" function can be approximated as close as is desired by a sufficiently large neural network.$^{\dagger}$

Similar results exist for other classes of functions. For instance, the Stone-Weierstrass theorem says that decent functions can be approximated by polynomials as well as is desired (again, setting aside the technical details of what constitutes a decent function). Carleson's theorem has this same flavor for approximation by Fourier series.

Does XGBoost also have a sense in which it can be a universal approximator?

$^{\dagger}$What constitutes a "decent" function is left vague as a technical detail of the specific assumptions of the various theorems.

Answer 1

Yes, it makes sense to characterise GBMs as "universal function approximators" and in particular "greedy" ones, as put forward in Friedman's (2001) (uber-classic) Greedy function approximation: A gradient boosting machine. The greediness here stemming on how we gradually/stage-wise increase the ensemble's capacity by adding units from the same family of known universal approximators (here trees). For that matter, let's remember that Boolean functions (i.e. trees) can be represented as real polynomials; a succinct (and surprisingly readable) intro on that can be found in Nisan & Szegedy (1992) On the degree of boolean functions as real polynomials. I have found Section 12.5 Universal approximation from the online blog version of the book Machine Learning Refined by Watt et al. a nice overview of how universal approximations come into play in ML, that section includes a small sub-section on tree-based universal approximators in particular too.