| Abstract |
XGBoost is one of the most successful machine learning methods in practice, yet its theoretical foundations remain poorly understood. In particular, despite its widespread use, there is currently no rigorous characterization of the function class that XGBoost is capable of learning. In this talk, I will present a theoretical framework that addresses this question.
I will introduce an infinite-dimensional function class that extends finite ensembles of bounded-depth regression trees, together with a complexity measure that generalizes the regularization penalty used by XGBoost. I will show that every minimizer of the XGBoost objective is a minimizer of an equivalent penalized regression problem over this larger function class, thereby revealing the function class that XGBoost implicitly targets.
I will also discuss a smoothness-based characterization of this function class, connecting XGBoost to classical smoothness-based methods in nonparametric regression. Finally, I will present statistical guarantees showing that least squares estimation over this class achieves nearly minimax-optimal rates of convergence without suffering from the curse of dimensionality. These results provide a theoretical explanation for why XGBoost performs well in practice. |
