Split-Candidate Scaling Reveals Double Descent in Gradient Boosting Trees

The phenomenon of "double descent," where model performance first degrades and then improves with increasing capacity, is well-documented in neural networks. However, identifying an analogous single-axis capacity parameter for Gradient Boosting Decision Trees (GBDTs) has been challenging. This paper proposes that the number of split candidates serves as such a parameter for GBDTs. By increasing the budget for split candidates while keeping other training controls constant, the feature quantization grid becomes finer, and the dictionary of potential root-to-leaf paths expands. This expansion allows boosting algorithms to select more refined updates. To analyze this, the researchers developed an empirical tree-kernel diagnostic that summarizes how these candidate-induced paths group training examples. Their analysis reveals a regime where the empirical kernel rank approaches the sample size, and very small positive eigenvalues emerge, indicating sensitivity to noise. In this regime, test error peaks before declining again as the split-candidate budget further increases, confirming double descent. The study's predictions—that deeper trees reach this regime with fewer candidates, larger training sets require finer grids, and label noise accentuates the peak—were supported by experiments across XGBoost, LightGBM, and CatBoost, while random forests showed monotonic improvement.