Does XGBoost have a max-depth hyper-parameter?

Question

According to the explanation in Complete Guide to Parameter Tuning in XGBoost, XGBoost doesn't use max_depth argument as Random Forest or GBM does. It expands the tree up to this depth and start pruning all the way up by judging if each node has a positive gain or not. But how does it split the nodes? Is it again greedy? And, if it is greedy, is it possible to have a first split yielding negative gain, and then positive gain?

Answer 1

XGBoost has multiple ways of tree construction. Excluding GPU-centric implementations, in the current XGBoost version (0.82) there are three tree_method options: exact, approx and hist.

The exact method is most likely what the authors of the linked tutorial refer at; it uses a greedy algorithm where the data are first sorted and all possible splits for continuous features are examined. Thus, yes, the split is done in a greedy manner too. As you correctly note, XGBoost does expand the tree up to max_depth and start prunes exactly because another negative split might benefit future splits. This is imporant as the minimum loss reduction required parameter is embedded in the overall loss function (see T. Chen's XGBoost presentation in page 34).

While fully informative, this exact approach can be computationally demanding and rather hard to parallelise so two additional algorithms have been suggested approx and hist. The approximate greedy algorithm uses weighted quantile of feature distribution to identify the best split. Notice that there is a argument sketch_eps that directly relates to the number of bins used - the weighting actually comes from the second order gradient statistics on the loss function; see the original XGBoost paper in page 4. The hist algorithm implements an approximate binning approach too but it is more sophisticated than the "simple" weighted quantile defined above. The github thread of the related code submission gives more information on the matter. In short, only a subset of possible split values is considered and certain binning calculations can be reused. Caveat: when the construction parameter is set to hist, the grow_policy parameter comes into play where it allows us to include new nodes in a depthwise or a lossguide manner. The lossguide manner can result to rather deep trees because we might end up repeatedly splitting the one leaf that gives the biggest gain instead of splitting until max_depth.

As you see in all tree_method options, the growth is "greedy"; what changes is the way that splits are enumerated. Finally, please note that when it comes to pruning that there is the gamma parameter; it defines a minimum loss reduction required to make a further partition on a leaf node of the tree. That can lead to even to positive split to be pruned.

To recap, yes, the nodes are split in a greedy manner up to the predefined maximum depth irrespective of their potentially negative gain at some stage.