XGBoost 2nd-Order

XGBoost is regularized second-order gradient boosting. Objective: $\mathcal{L} = \sum_{i=1}^{n} l\left(y_i, \hat{y}_i\right) + \sum_{k=1}^{K} \Omega(f_k)$ with tree regularization $\Omega(f) = \gamma T + \frac{1}{2} \lambda \Vert w \Vert^2$ ($T$ leaves, $w$ leaf weights, $\gamma$ per-leaf complexity penalty, $\lambda$ L2 shrinkage on leaf weights). Round $t$ adds $f_t$: $\hat{y}_i^{(t)} = \hat{y}_i^{(t-1)} + f_t(x_i)$; Taylor-expand the loss to second order around $\hat{y}_i^{(t-1)}$: $l\left(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)\right) \approx l\left(y_i, \hat{y}_i^{(t-1)}\right) + g_i f_t(x_i) + \frac{1}{2} h_i f_t(x_i)^2$ with first derivative $g_i = \frac{\partial l\left(y_i, \hat{y}_i^{(t-1)}\right)}{\partial \hat{y}_i^{(t-1)}}$ and second derivative $h_i = \frac{\partial^2 l\left(y_i, \hat{y}_i^{(t-1)}\right)}{\partial \left(\hat{y}_i^{(t-1)}\right)^2}$. Dropping constants, the step-$t$ objective is $\sum_{i=1}^{n} \left[ g_i w_{q(x_i)} + \frac{1}{2} h_i w_{q(x_i)}^2 \right] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2$, where $q(x)$ maps a sample to its leaf. Grouping by leaf with $I_j = \{ i \mid q(x_i) = j \}$, $G_j = \sum_{i \in I_j} g_i$, $H_j = \sum_{i \in I_j} h_i$, the objective becomes $\sum_{j=1}^{T} \left[ G_j w_j + \frac{1}{2}\left(H_j + \lambda\right) w_j^2 \right] + \gamma T$ — independent quadratics in each $w_j$, so the optimal leaf weight is $w_j^* = -\frac{G_j}{H_j + \lambda}$, giving the minimal objective $\mathcal{L}^* = -\frac{1}{2} \sum_{j=1}^{T} \frac{G_j^2}{H_j + \lambda} + \gamma T$. Splitting node $I = I_L \cup I_R$ yields the structural gain $\text{Gain} = \frac{1}{2} \left[ \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{\left(G_L + G_R\right)^2}{H_L + H_R + \lambda} \right] - \gamma$; split iff $\text{Gain} > 0$ ($\gamma$ acts as a minimum split gain, equivalent to post-pruning). Common losses: squared loss has $g_i = 2\left(\hat{y}_i - y_i\right)$, $h_i = 2$; logistic log loss has $\hat{p}_i = \sigma\left(\hat{y}_i\right)$, $g_i = \hat{p}_i - y_i$, $h_i = \hat{p}_i\left(1 - \hat{p}_i\right)$.

whiteboard-deriving XGBoost is among the most frequently asked ML hand-derivation questions in 2026 big-tech interviews — you must write the full chain objective → second-order Taylor expansion → leaf weight → structural gain; in practice XGBoost is one of the de-facto standards for tabular data.

compared with first-order GBDT, the second-order expansion is a Newton step in function space — curvature (Hessian) information gives faster convergence and a more accurate splitting criterion (distinguishing splits with identical first-order gradients but different curvature); explicit regularization $\gamma T + \frac{1}{2} \lambda \Vert w \Vert^2$ folds leaf-weight shrinkage ($\lambda$) and split penalty ($\gamma$) into the objective end-to-end; engineering-wise, column subsampling, approximate quantile histograms (candidate splits drop from $O(n)$ to $O(\text{bins})$), and sparsity-aware splitting (missing values learn a default direction) make it practical on large sparse data.

Whiteboard XGBoost: from $\sum_i l(y_i, \hat{y}_i) + \sum_k \Omega(f_k)$, Taylor-expand to second order to get $\sum_i [g_i w_{q(x_i)} + \frac{1}{2} h_i w^2] + \lambda \Vert w \Vert^2$, then derive the optimal leaf weight $w_j^* = -\frac{G_j}{H_j + \lambda}$

Whiteboard the split gain $\text{Gain} = \frac{1}{2}\left[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma$: when do we not split?

Why second-order derivatives? Convergence advantage over first-order GBDT; what are $g_i$, $h_i$ under squared loss and cross-entropy?

Roles of $\gamma$ and $\lambda$: how do they affect leaf count and leaf weights? Relationship with tree pruning?

Engineering: exact greedy vs approximate quantile histograms, sparsity-aware splits (default direction for missing), column subsampling; differences vs LightGBM