Every tree and boosting formula for ML interviews. Part 3: theory

July 2026. Math doesn't rot, but library details do - XGBoost version notes reflect 2.x-3.1.

The whole series:

• Part 1 - the Interview tier: trees, forests, and the ten core formulas
• Part 2 - the Practice tier: the knobs you actually turn
• Part 3 - the Theory tier: full derivations and the cheat sheets (you are here)

This is the theory tier: the full derivations behind everything stated in part 1 and part 2, plus the cheat-sheet appendices. If an interviewer ever answers your answer with "why?", this is the part that has your back. Cross-references like I.7 point to part 1, P.3 to part 2.

---

TIER 3 - [T] THEORY

Full derivations. What lets you answer any follow-up question.

---

[T.1] The regularized XGBoost objective

$$\text{Obj} = \sum_{i=1}^{n} L\big(y_i, \hat y_i\big) + \sum_{k=1}^{N} \Omega(f_k), \qquad \Omega(f) = \gamma T + \frac{1}{2}\lambda\sum_{j=1}^{T} w_j^2 + \alpha\sum_{j=1}^{T}|w_j|$$

The key difference from GBM. In classical GBM regularization is heuristic and external (cap the depth, apply shrinkage). Here the tree's complexity is an explicit term of the objective, so the algorithm itself decides, arithmetically, whether a split pays for itself.

Three components:

• $\gamma T$ - the price of leaf count => becomes the " $-\gamma$ " in Gain I.8;
• $\frac12\lambda\sum w_j^2$ - ridge on leaf weights => the $\lambda$ in the denominator of $w^\ast$ I.7;
• $\alpha\sum|w_j|$ - lasso on leaf weights => soft-thresholding T.4.

Why this is ridge/lasso "for real". In a linear model the parameters are the coefficients $\beta$ on features; in a tree the parameters are the leaf weights $w_j$ . We penalize exactly those, in exactly the same sense. Different architectures, one idea.

---

[T.2] The second-order Taylor expansion

Substitute the additive step:

$$\text{Obj}^{(t)} = \sum_{i=1}^{n} L\big(y_i, \hat y_i^{(t-1)} + f_t(x_i)\big) + \Omega(f_t) + \text{const}$$

Expand $L$ in the small increment $f_t(x_i)$ around $\hat y_i^{(t-1)}$ :

$$L\big(y_i, \hat y^{(t-1)}_i + f_t(x_i)\big) \approx L\big(y_i, \hat y^{(t-1)}_i\big) + g_i f_t(x_i) + \frac12 h_i f_t(x_i)^2$$

where

$$g_i = \left.\frac{\partial L}{\partial \hat y_i}\right|{\hat y^{(t-1)}}, \qquad h_i = \left.\frac{\partial^2 L}{\partial \hat y_i^2}\right|{\hat y^{(t-1)}}$$

Dimensions. $g, h \in \mathbb{R}^n$ (vectors, one number per sample). For multiclass - $n\times K$ .

Contrast with GBM. Classical boosting uses only $g$ (gradient descent in function space). XGBoost adds $h$ - the curvature => that's Newton's method, hence "Newton boosting".

What the second order buys.

1. An analytic optimum for the leaf weight (a closed formula instead of line search).
2. A split criterion consistent with the loss.
3. A more accurate step (curvature is taken into account).

Limitations. Requires $h_i > 0$ (otherwise the denominator breaks). For non-convex custom losses the hessian gets clipped. For MAE/quantile, where $h$ is constant, the Newton step degenerates => adaptive trees P.1.

---

[T.3] Regrouping by leaves and deriving the optimal leaf weight

Step 1. The constant $L(y_i, \hat y^{(t-1)}_i)$ doesn't depend on $f_t$ => drop it:

$$\text{Obj}^{(t)} \approx \sum_{i=1}^{n}\left[g_i f_t(x_i) + \frac12 h_i f_t(x_i)^2\right] + \gamma T + \frac12 \lambda\sum_{j=1}^{T} w_j^2$$

Step 2 (the key trick). A tree predicts a constant within a leaf: if $i \in I_j$ , then $f_t(x_i) = w_j$ . So the sum over samples can be rewritten as a sum over leaves:

$$\text{Obj}^{(t)} \approx \sum_{j=1}^{T}\left[\Big(\underbrace{\textstyle\sum_{i\in I_j} g_i}{G_j}\Big) w_j + \frac12\Big(\underbrace{\textstyle\sum{i\in I_j} h_i}_{H_j} + \lambda\Big) w_j^2\right] + \gamma T$$

This is the moment that makes the problem solvable: the leaves become independent, each optimized separately.

Step 3. Inside a leaf - an ordinary parabola:

$$\phi(w_j) = G_j w_j + \frac12 (H_j+\lambda) w_j^2$$

$$\phi'(w_j) = G_j + (H_j+\lambda)w_j = 0 \implies w_j^\ast = -\frac{G_j}{H_j+\lambda}$$

Convexity check. $\phi''(w_j) = H_j + \lambda > 0$ whenever $h_i \ge 0$ and $\lambda > 0$ => it's a minimum, not a maximum.

---

[T.4] Soft-thresholding: how the L1 case is solved

With the $\alpha|w_j|$ term, the leaf's objective is:

$$\phi(w_j) = G_j w_j + \frac12(H_j+\lambda)w_j^2 + \alpha|w_j|$$

The absolute value is non-differentiable at zero => solve via the subgradient. The result is the classic soft-thresholding, as in lasso:

$$\boxed{w_j^\ast = -\frac{\mathcal{T}\alpha(G_j)}{H_j+\lambda}}, \qquad \mathcal{T}\alpha(G) = \text{sign}(G)\cdot\max\big(|G| - \alpha, 0\big)$$

Spelled out:

Condition	$\mathcal{T}_\alpha(G)$
$G > \alpha$	$G - \alpha$
$G < -\alpha$	$G + \alpha$
$\vert G\vert \le \alpha$	$0$

Meaning. If the total gradient in a leaf is no larger than $\alpha$ in absolute value, the leaf's weight is zeroed out - the leaf predicts exactly zero and contributes nothing.

Comparing $\lambda$ and $\alpha$ :

	L2 ( $\lambda$ )	L1 ( $\alpha$ )
Where it sits	denominator	numerator (a threshold)
Effect	proportional shrinkage	shift toward zero, exact zeroing
Sparsity	no	yes (zero leaves)
Default	1	0

Why $\alpha$ is less useful in practice than in linear models. In linear regression, L1 zeroes coefficients on features - that's feature selection. In a tree the features are already selected by the structure (the splits); zeroing a leaf's weight doesn't remove a feature from the model, it merely mutes one leaf. Hence the practice: nonzero $\lambda$ , $\alpha$ usually zero.

Structure score with L1: replace $G^2$ with $[\mathcal{T}_\alpha(G)]^2$ .

Where else it shows up. Soft-thresholding is the core of ISTA / proximal gradient for lasso, and the solution of $\min_w \frac12(w-a)^2 + \alpha|w|$ in any context.

---

[T.5] The structure score

Substitute $w_j^\ast$ back into the objective (without L1, for cleanliness). The parabola's minimum is $\phi(w^\ast) = -\frac{G_j^2}{2(H_j+\lambda)}$ , hence:

$$\boxed{\text{Obj}^\ast = -\frac12 \sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda} + \gamma T}$$

What this is. A quality measure of a fixed tree structure $q$ (which splits, not which weights). The larger $\sum_j \frac{G_j^2}{H_j+\lambda}$ , the better (note the leading minus).

The philosophical moment. This is an impurity derived from the loss function, not postulated. Gini and entropy are heuristics; $\frac{G^2}{H+\lambda}$ is a consequence. That is why XGBoost doesn't use Gini.

---

[T.6] Deriving Gain from the structure score

Consider a leaf $I$ we're thinking of splitting into $I_L$ and $I_R$ .

Before the split, its contribution to $\text{Obj}^\ast$ : $-\frac12 \frac{G^2}{H+\lambda} + \gamma \cdot 1$ (one leaf).

After the split: $-\frac12\left(\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda}\right) + \gamma\cdot 2$ (two leaves).

The gain = (before) − (after), i.e. how much the objective decreased:

$$\text{Gain} = \frac12\left[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{G^2}{H+\lambda}\right] - \gamma$$

Notice: $\gamma\cdot 2 - \gamma\cdot 1 = \gamma$ - that's where the " $-\gamma$ " comes from. A global penalty $\gamma T$ produced a local rule.

Rule. Split when $\text{Gain} > 0$ .

---

[T.7] Equivalence to weighted least squares: Newton boosting ≈ IRLS

Take the post-Taylor objective and complete the square:

$$\sum_i \left[g_i f(x_i) + \frac12 h_i f(x_i)^2\right] = \sum_i \frac{h_i}{2}\left[f(x_i)^2 + \frac{2g_i}{h_i}f(x_i)\right] = \sum_i \frac{h_i}{2}\left(f(x_i) + \frac{g_i}{h_i}\right)^2 - \underbrace{\sum_i \frac{g_i^2}{2h_i}}_{\text{const}}$$

Altogether:

$$\boxed{\text{Obj}^{(t)} \equiv \sum_{i=1}^{n} \frac{1}{2} h_i \left(f_t(x_i) - \left(-\frac{g_i}{h_i}\right)\right)^2 + \text{const}}$$

What this means. Every boosting iteration is a weighted-least-squares fit of a tree to the targets $-g_i/h_i$ with weights $h_i$ .

That is literally IRLS (iteratively reweighted least squares), except the base learner is a tree instead of a linear model.

The parallel with logistic regression:

	Logistic regression	XGBoost
Method	Newton-Raphson / Fisher scoring / IRLS	Newton boosting
Gradient	$X^\top(p - y)$ , size $p\times 1$	$g_i = p_i - y_i$ , a vector $n\times 1$
Curvature	$W = \text{diag}(p_i(1-p_i))$ , $n\times n$	$h_i = p_i(1-p_i)$ , a vector $n\times 1$
Hessian	$X^\top W X$ , size $p\times p$	$H_j = \sum h_i$ (a scalar per leaf)
Step	solves weighted LS analytically	approximates weighted LS with a tree
Regularization	ridge on $\beta$	ridge on $w_j$

Three consequences you should be able to say out loud.

1. Why the quantiles are weighted by $h_i$ P.12 - because the problem is weighted LS with weights $h_i$ .
2. Why $w^\ast = -G/(H+\lambda)$ is a weighted average of the individual Newton steps $-g_i/h_i$ with weights $h_i$ :

$$w_j^\ast = \frac{\sum_{i\in I_j} h_i\left(-\frac{g_i}{h_i}\right)}{\sum_{i\in I_j} h_i + \lambda}$$

1. Why $h = p(1-p)$ in both - one and the same curvature of the logistic likelihood.

Note [T]. This is the strongest card in the whole deck. It shows that logistic regression and boosting are connected in your head.

---

[T.8] Initializing F0: what the "zeroth tree" predicts

$$\boxed{F_0 = \arg\min_{c} \sum_{i=1}^{n} L(y_i, c)}$$

The first thing is not a tree - it's a constant (a global intercept; base_score in XGBoost).

Loss	$F_0$	Comment
MSE	the mean $\bar y$	the "it's the mean" intuition is true exactly here
Log-loss	the logit of the base rate $\log\frac{\bar y}{1-\bar y}$	log-odds of the positive share
MAE	the median of $y$
Pinball ( $\tau$ )	the $\tau$ -quantile of $y$
Poisson (log link)	$\log\bar y$

Critical. $F_0$ lives in margin space (before the inverse link). For classification it's log-odds, not a probability.

The first real tree ( $f_1$ ) is trained on gradients relative to $F_0$ :

• MSE: $g_i = F_0 - y_i \Rightarrow$ the tree fits residuals from the mean. This is where "boosting fits residuals" is exact.
• Log-loss: $g_i = p_0 - y_i$ , where $p_0 = \sigma(F_0)$ is the base rate.

A historical XGBoost trap. Before version 2.0, base_score was a constant 0.5 (even for regression, where that's meaningless). And 0.5 is specified after the inverse link: for logistic tasks it's a probability that internally becomes $\log\frac{0.5}{0.5} = 0$ . Since 2.0 the intercept is estimated automatically from the target; since 3.1 it's vector-valued for multi-output models.

base_margin. A vector of per-sample starting margins (overrides base_score). Used for stacking: feed another model's raw (pre-link!) predictions so the booster learns a correction on top.

Note [T]. With enough rounds, the value of $F_0$ barely matters - the model re-learns it. It matters with few trees, aggressive early stopping, and for calibration in early iterations. For a custom loss the auto-estimation doesn't work - set it by hand.

---

[T.9] AdaBoost: the exponential loss and the logit connection

AdaBoost (Freund & Schapire, 1997) was the first boosting algorithm that worked in the wild, and it made an entrance: Breiman, not a man given to hype, called it "the best off-the-shelf classifier in the world" (the quote survives via ESL). It also earned Freund and Schapire a Gödel Prize. Worth knowing not just as history: interviewers love asking how it relates to gradient boosting, and the honest answer (it's the same forward-stagewise frame under a specific loss) is below.

The algorithm (ESL 10.1), step by step.

1. Initialize weights $w_i = 1/n$ .
2. For $m = 1..M$ :
3. - fit a classifier $G_m(x) \in \lbrace -1,+1\rbrace$ under weights $w_i$ ;
4. - compute the weighted error

$$\text{err}m = \frac{\sum{i} w_i\mathbb{I}(y_i \ne G_m(x_i))}{\sum_i w_i}$$

1. - compute the classifier's weight

$$\alpha_m = \log\frac{1 - \text{err}_m}{\text{err}_m}$$

1. - update the sample weights

$$w_i \leftarrow w_i \cdot \exp\big(\alpha_m \mathbb{I}(y_i \ne G_m(x_i))\big)$$

1. Output: $G(x) = \text{sign}\left(\sum_{m} \alpha_m G_m(x)\right)$ .

Where $\alpha_m$ comes from. AdaBoost is forward stagewise additive modeling with the exponential loss $L(y, f) = e^{-y f}$ , $y \in \lbrace -1,+1\rbrace$ . Minimizing over the coefficient gives $\beta_m = \frac12\log\frac{1-\text{err}_m}{\text{err}_m}$ ; ESL's notation takes $\alpha_m = 2\beta_m$ , which is why the $\frac12$ is absent.

The most beautiful fact - the population minimizer of the exponential loss:

$$f^\ast(x) = \arg\min_f \mathbb{E}\left[e^{-yf(x)}\middle|x\right] = \frac{1}{2}\log\frac{P(y=1\mid x)}{P(y=-1\mid x)}$$

So AdaBoost estimates half the log-odds! Hence the inverse transform $P(y=1|x) = \frac{1}{1+e^{-2f(x)}}$ - a sigmoid with a factor of two.

Where else it shows up. This is the same quantity that logistic regression predicts (log-odds), the same thing that lives in a booster's margin. The exponential and logistic losses share the same population minimizer up to a constant factor.

The difference between the losses. The exponential loss grows faster than the logistic one at large negative margins => AdaBoost is more sensitive to outliers and label noise. That is the practical reason gradient boosting on log-loss wins in production.

Note [T]. Being able to say "AdaBoost = forward stagewise + exponential loss" and "its population minimizer is half the log-odds" is very strong. Most people only know the re-weighting procedure.

---

[T.10] Multiclass: softmax, gradients, the diagonal hessian

$$p_{ik} = \frac{e^{z_{ik}}}{\sum_{c=1}^{K} e^{z_{ic}}}, \qquad L_i = -\sum_{k=1}^{K} y_{ik}\log p_{ik}$$

Dimensions. $z_i \in \mathbb{R}^K$ (per-class margins); $p_i \in \mathbb{R}^K$ ; $y_i$ - one-hot $\in \lbrace 0,1\rbrace^K$ .

Gradient:

$$g_{ik} = p_{ik} - y_{ik}$$

The full hessian (a $K\times K$ matrix per sample):

$$\frac{\partial^2 L_i}{\partial z_{ik}\partial z_{ic}} = p_{ik}(\delta_{kc} - p_{ic})$$

What XGBoost does. Uses the diagonal approximation, ignoring off-diagonal elements:

$$h_{ik} \approx 2p_{ik}(1-p_{ik})$$

(the factor 2 is an implementation detail insuring against oversized steps).

Cost. Each iteration builds $K$ trees - one per class. 100 rounds and 10 classes => 1000 trees. Cost grows linearly in the number of classes.

The alternative (XGBoost 3.1+). Vector leaf - a single tree whose leaf holds a vector of weights $w_j \in \mathbb{R}^K$ . Lets the structure capture correlations between outputs. Still work in progress.

Note [T]. Knowing that the hessian is diagonally approximated is a rare detail and an excellent marker.

---

[T.11] SHAP: Shapley values

$$\phi_i = \sum_{S \subseteq N\setminus\lbrace i\rbrace} \frac{|S|!\big(|N| - |S| - 1\big)!}{|N|!}\Big[f\big(S \cup \lbrace i\rbrace\big) - f(S)\Big]$$

Symbols. $N$ - the set of all features ( $|N| = d$ ); $S$ - a subset excluding feature $i$ ; $f(S)$ - the model's prediction with only the features in $S$ "known"; $\phi_i$ - feature $i$ 's contribution.

The meaning of the multiplier. Averaging over all possible orders of adding features: $\frac{|S|!(d-|S|-1)!}{d!}$ is the share of permutations in which feature $i$ arrives immediately after the set $S$ .

The additivity property (the main one):

$$f(x) = \phi_0 + \sum_{i=1}^{d}\phi_i$$

where $\phi_0 = \mathbb{E}[f(X)]$ is the base value. The prediction decomposes exactly into feature contributions.

The Shapley axioms (the unique solution satisfying them): efficiency (the additivity above), symmetry, dummy (a null feature => zero contribution), linearity.

Complexity. Naively $O(2^d)$ . TreeSHAP exploits the tree structure and computes exact Shapley values in polynomial time. Available in XGBoost via pred_contribs=True.

The critical limitation. SHAP explains the model, not the world. It shows what the model looks at, not the causal structure of the data. If the model learned a proxy or a confounder, SHAP will faithfully show you that proxy. Causality does not follow from SHAP.

Where else it shows up. Cooperative game theory (Shapley's original 1953 setting): dividing a coalition's payoff among players.

---

[T.12] Functional gradient descent - the general frame

Generalizing I.6, boosting is descent in a space of functions:

$$F_t = F_{t-1} - \eta \nabla_F \mathcal{L}(F)\Big|{F = F{t-1}}$$

where the "gradient" is the vector $(-g_1, ..., -g_n)$ of negative-gradient values at the training points. Since we can't move in an arbitrary direction of an infinite-dimensional space, we project onto the space of trees:

$$f_t = \arg\min_{f \in \mathcal{F}} \sum_{i=1}^{n}\big(-g_i - f(x_i)\big)^2$$

In other words: the tree that best approximates the negative gradient. That's classical GBM.

XGBoost does the same, but in the metric given by the hessian:

$$f_t = \arg\min_{f\in\mathcal{F}} \sum_{i=1}^n \frac{h_i}{2}\left(-\frac{g_i}{h_i} - f(x_i)\right)^2 + \Omega(f)$$

The projection is now curvature-weighted - which is precisely the passage from gradient descent to Newton's method T.7.

The hierarchy of generalizations (worth drawing in your head):

forward stagewise additive modeling
├── exponential loss                     => AdaBoost   **T.9**
├── any differentiable L, 1st order      => GBM        **I.6**
└── any twice-diff. L, 2nd order + Ω     => XGBoost    **T.2-T.6**

---

Appendix A. The cross-connections - "where else does this show up"

Quantity / idea	In trees	Elsewhere
$p(1-p)$	hessian of log-loss; Gini (binary, times 2)	Bernoulli variance; $W$ in $(X^\top W X)^{-1}$ of logistic regression; the IRLS weight
$-G/(H+\lambda)$	XGBoost leaf weight	the ridge solution $(X^\top X + \lambda I)^{-1}X^\top y$
Soft-thresholding	L1 on leaf weights	lasso; ISTA / proximal gradient
Weighted least squares	every XGBoost iteration	IRLS in GLMs; Fisher scoring
Log-odds	the boosting margin; $F_0$ for log-loss	the linear predictor of logistic regression; population minimizer of the exponential loss (times $\frac12$ )
$\rho\sigma^2 + \frac{1-\rho}{N}\sigma^2$	why RF decorrelates	risk of a portfolio of correlated assets
Bias-variance	bagging vs boosting	regularization in any model
"Importance ≠ effect"	feature importance, SHAP	a regression coefficient on observational data ≠ a causal effect
Base-rate shift	scale_pos_weight, undersampling	negative sampling breaks calibration; the intercept moves, not the slopes
Fisher information	$H_j$ as local curvature	$\text{SE}(\hat\beta) = \sqrt{\text{diag}(X^\top W X)^{-1}}$

---

Appendix B. What gets centered - the quick card

Computing	Center?
Impurity, Gain, $G_j$ , $H_j$	no
Features before a tree	no (invariance to monotone transformations)
$X^\top W X$ (Fisher information, logistic regression)	no (curvature, not covariance; the intercept centers implicitly)
$S_{xy} = \sum(x_i-\bar x)(y_i - \bar y)$ (CUPED, OLS)	yes, mandatory (it's a covariance)
Features before a regularized linear model	yes (the penalty depends on the scale of $\beta$ )

Mnemonic: centering belongs where a covariance of features is computed. Not where a loss curvature or sums of derivatives are.

---

Appendix C. The dimension checklist (self-test)

Expression	Dimension	Check
$X$	$n \times d$	no column of ones for a tree
$g$ , $h$	$n \times 1$	one number per sample
$G_j$ , $H_j$	scalars	sums over the leaf's samples
$w$	$T \times 1$	one number per leaf
$q(x)$	$\mathbb{R}^d \to \lbrace 1..T\rbrace$	the tree structure
Gain	scalar	compared against zero
Multiclass hessian (full)	$K\times K$ per sample	XGBoost takes the diagonal
$W$ in logistic regression	$n\times n$ diagonal	don't confuse with $H_j$ !
$X^\top W X$	$(d{+}1)\times(d{+}1)$	with the intercept
$\phi$ (SHAP)	$d \times 1$ per sample	$f(x) = \phi_0 + \sum\phi_i$

---

Appendix D. The 60-second checklist - what to say

1. A tree - low bias, high variance; greedy impurity-driven splitting; globally optimal trees are NP-hard.
2. Bagging/RF attacks variance: $\text{Var} = \rho\sigma^2 + \frac{1-\rho}{N}\sigma^2$ ; max_features lowers $\rho$ ; OOB comes for free.
3. Boosting attacks bias: an additive model, trees fit the negative gradient; it overfits => early stopping.
4. XGBoost: regularization inside the objective, second-order Taylor (Newton boosting), $w^\ast = -G/(H+\lambda)$ , Gain with $-\gamma$ , a criterion derived from the loss rather than Gini.
5. The connection: $h = p(1-p)$ = the Fisher-information weight; every iteration = weighted least squares = IRLS with trees.
6. The limits: no extrapolation; probabilities aren't calibrated out of the box; importance ≠ causal effect.

---

That's the whole file. If it saved you a tab explosion the night before an interview, a ❤️ (or a unicorn, I don't judge) is the one signal that tells me these are worth making. And if I got something wrong, say so in the comments: a reference is only useful if it's right.

If write-ups like this are your thing, I announce the best ones on my Telegram channel, FitHappensML, along with discounts and free tiers from various providers whenever I spot them. No Telegram? I'm on X and Threads too. And if you're in ML/DS or building apps yourself, I follow back.