Optimizing GBDT Splits: The Interview Puzzle Behind LightGBM’s Speed Trick

Interview Question

ByteDance interview asks to partition a sequence into two subsets, define a function, and compute a value with the optimal time complexity.

Solution Overview

The naive approach enumerates every possible split point, recomputing means and squared errors, leading to O(n²) time. The goal is to reduce it to O(n).

Derivation from GBDT

In Gradient Boosted Decision Trees (GBDT), when fitting a regression tree to the negative gradient, the loss is the sum of squared errors over leaf predictions. For a split of leaf j into left and right children, the loss after split can be expressed as a function of the left‑ and right‑leaf means. The optimal split maximizes the reduction ΔL, which is exactly the variance‑gain used in LightGBM.

By separating terms that are independent of the split point, the computation for each candidate split reduces to evaluating a single expression that requires only one addition/subtraction and one square operation.

Optimization Trick

This reduces the complexity from O(n²) to O(n), a key acceleration used in LightGBM implementations.

Extended Reading

LightGBM Definition 3.1 shows the split‑gain formula, which resembles XGBoost’s second‑order Taylor expansion but without the regularization term.

Review Summary

Many GBDT tutorials confuse the target loss (MSE) with the tree‑building loss (square error). The correct split criterion is the variance gain, which can be computed in linear time as shown above.

References

Ke, G. et al., “LightGBM: A Highly Efficient Gradient Boosting Decision Tree.”

Chen, T., “Introduction to Boosted Trees.”

Friedman, J. H., “Greedy function approximation: a gradient boosting machine.”