Every tree and boosting formula for ML interviews. Part 1: the core ten

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

The whole series:

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

I've been preparing for ML interviews, and the formulas for trees and boosting are scattered across ESL chapters, the XGBoost paper, documentation and a hundred blog posts, each with its own notation, each explaining the part the author happened to care about. At some point I gave up looking for one complete reference and made it myself.

While collecting I noticed my notes kept mixing three different kinds of "know", so I sorted everything into three tiers. For myself, originally, but the split turned out to be the most useful part:

• [I] Interview - what I want to reproduce cold, at a whiteboard, mid-stress.
• [P] Practice - the knobs I actually turn, and the places I've been burned.
• [T] Theory - full derivations and cross-connections, for when a paper or an interviewer goes one level deeper.

Every formula follows the same template: symbols and dimensions => where it comes from => step by step => does anything get centered => where else this shows up => a note. The "where else" parts are, to me, the most valuable: the same three or four quantities keep reappearing across trees, logistic regression and statistics, and once you see that, the whole thing stops being a pile of facts.

The file came out so long that dev.to's editor waved a white flag, so it's a three-part series now. Cross-references like T.7 are section codes; I. sections live in this part, P. in part 2, T. in part 3, and every section carries its label in the heading, so Ctrl-F jumps you there. And it took a real amount of time to put together, so if you find it useful, leave a reaction: it genuinely raises the motivation to write more of these.

---

Section 0. Notation and conventions used throughout

0.1 Basic symbols and dimensions

Symbol	What it is	Dimension
$n$	number of samples	scalar
$d$	number of features	scalar
$K$	number of classes	scalar
$X$	design matrix	$n \times d$
$x_i$	features of sample $i$	column vector $d \times 1$
$y_i$	target of sample $i$	scalar (or $K$ -vector for multiclass)
$\hat y_i$ , $F(x_i)$	model prediction (in margin space, before the link)	scalar
$p_i$	predicted probability (after the sigmoid)	scalar in $(0,1)$
$g_i$	gradient of the loss w.r.t. the prediction	scalar; vector $g \in \mathbb{R}^n$
$h_i$	hessian of the loss w.r.t. the prediction	scalar; vector $h \in \mathbb{R}^n$
$T$	number of leaves in a tree	scalar
$w_j$	weight (prediction) of leaf $j$	scalar; vector $w \in \mathbb{R}^T$
$q(\cdot)$	tree structure: sample => leaf index	$\mathbb{R}^d \to \lbrace 1..T\rbrace$
$I_j$	set of samples in leaf $j$	subset of $\lbrace 1..n\rbrace$
$G_j = \sum_{i \in I_j} g_i$	sum of gradients in a leaf	scalar
$H_j = \sum_{i \in I_j} h_i$	sum of hessians in a leaf	scalar
$\eta$	learning rate / shrinkage	scalar
$\lambda, \alpha, \gamma$	L2, L1, per-leaf penalty	scalars
$N$	number of trees in the ensemble	scalar

Do not confuse. $T$ is the number of leaves, not the depth and not the number of nodes. $H_j$ is the sum of hessians, not the number of samples - they coincide only for MSE, where $h_i = 1$ .

0.2 What gets centered and what doesn't - the once-and-for-all answer

A frequent source of confusion, because formulas from different models look alike.

Object	Centered?	Why
Features for a tree	No	A tree is invariant to any monotone transformation: the split "x < t" doesn't change under shift/scale. Centering, standardizing, logging - useless (numerical trivia aside)
Features for RF / GBM / XGBoost	No	Same reason. Hence "trees don't need feature scaling"
$G_j, H_j$ in XGBoost	No	These are sums of gradients and hessians, not moments of a distribution
$X^\top W X$ (Fisher information in logistic regression)	No	This is the curvature of the log-likelihood, not a covariance of features; the intercept column centers implicitly
$S_{xy} = \sum (x_i - \bar x)(y_i - \bar y)$ (CUPED / OLS scatter)	Yes, mandatory	This is an actual covariance; without centering it stops being one

Mnemonic: centering belongs where you compute a covariance/variance of features. Where you compute loss curvature or sums of gradients, centering is beside the point.

One more difference from linear models: the design matrix for a tree needs no column of ones - a tree has no intercept; its role is played by $F_0$ (see T.8).

---

TIER 1 - [I] INTERVIEW

The ten I keep coming back to. Everything else here is built on top of them.

First, the thirty-second version of what a decision tree even is, so the formulas have something to sit on. A tree is a stack of if-else questions about features: is age < 34, is income < 52k. Each question splits the data in two, and the tree picks the question that makes the two halves as pure as possible, as close to single-class as it can manage. It grows greedily, one best question at a time, top to bottom. That's the entire machine. Everything below is just making "as pure as possible" precise, and then fixing the problems that greed creates.

The purity measures come first, and they have a surprisingly good pedigree: one is borrowed from a 1912 Italian statistician, the other from Claude Shannon.

---

[I.1] Impurity: Gini and entropy

$$\text{Gini}(t) = 1 - \sum_{k=1}^{K} p_k^2, \qquad \text{Entropy}(t) = -\sum_{k=1}^{K} p_k \log p_k$$

The absolute classic: the first thing anyone learns about trees, and still the first thing interviewers reach for. These are the two standard answers to "how mixed is this node": the tree plugs one of them into information gain I.2 to score every split it ever makes.

Symbols. $t$ - a tree node; $p_k$ - the share of class- $k$ samples in node $t$ (scalar, $\sum_k p_k = 1$ ). Both quantities are scalars.

Where they come from.

• Gini - the probability of mislabeling a sample if you assign it a class drawn at random from the node's own distribution: $\sum_k p_k (1 - p_k) = 1 - \sum_k p_k^2$ . And yes, it's named after that Gini (Corrado Gini of income-inequality fame), though it's not the inequality coefficient (that one is the Lorenz-curve construction). It's a categorical cousin from the same 1912 work, later reborn in ecology as the Gini-Simpson diversity index; both ask how likely two random draws are to disagree. For a 0/1 label the kinship becomes exact: the mean absolute difference between two random draws is $2p(1-p)$ , literally the binary impurity below.
• Entropy - Shannon, 1948: the average number of bits (with $\log_2$ ) needed to encode the class. So the other half of the tree runs on information theory. XGBoost and sklearn default to the natural log where one is needed.

Extremes. Both are zero in a pure node (single class). Maximum at the uniform distribution: Gini $= 1 - 1/K$ , entropy $= \log K$ .

Binary case (worth memorizing).

$$\text{Gini} = 2p(1-p), \qquad \text{Entropy} = -p\log p - (1-p)\log(1-p)$$

Centering. Not applicable - these are functions of class shares.

Where else it shows up. $p(1-p)$ inside Gini is the Bernoulli variance - the same quantity as the hessian of the logistic loss I.10 and the weight in the Fisher information matrix $W$ of logistic regression. Not a coincidence: both measure "uncertainty" at a point.

Note [I] - why they're basically the same thing. Take entropy, $\sum_k p_k(-\ln p_k)$ , and replace the log with its first-order approximation $-\ln p \approx 1-p$ . You get $\sum_k p_k(1-p_k)$ , which is exactly Gini. Gini is entropy with the logarithm linearized: same shape (zero on pure nodes, maximal at uniform, both concave), just a hair less sharp near uniform distributions and cheaper to compute, because no log. Which is also the honest answer to the classic trap question "which one is better?": on real data the chosen splits almost never differ, and sklearn defaults to Gini for the boring reason: speed.

---

[I.2] Information Gain - the CART split criterion

$$\text{IG} = I(\text{parent}) - \left[ \frac{n_L}{n} I(\text{left}) + \frac{n_R}{n} I(\text{right}) \right]$$

CART is Classification and Regression Trees - Breiman, Friedman, Olshen and Stone, 1984, and it arrived as a book, not a paper. It's one of the two family lines behind every modern tree: Quinlan's ID3/C4.5 line preferred entropy and multiway splits; the CART line preferred Gini and strictly binary splits. What's in sklearn and every boosting library today is essentially CART with forty years of engineering on top.

Symbols. $I(\cdot)$ - any impurity (Gini, entropy, MSE); $n_L, n_R$ - sample counts in the left and right child; $n = n_L + n_R$ . All scalars.

Where it comes from. "How much did heterogeneity drop after the split." The weights $n_L/n$ and $n_R/n$ exist because a child's impurity must be weighted by its size: a split that carves off a single sample into a pure leaf should not count as good.

Step by step (how CART picks a split).

1. For each feature $j = 1..d$ , sort the values $x_{ij}$ .
2. For each candidate threshold $t$ (usually midpoints between adjacent unique values), partition into $L = \lbrace i : x_{ij} < t\rbrace$ and $R$ , compute IG.
3. Pick the pair $(j^\ast, t^\ast)$ with maximal IG.
4. Recurse into the children.

Complexity. $O(nd)$ per node after sorting (or $O(nd \log n)$ including the sort; XGBoost amortizes sorting via column blocks).

For regression. $I = \text{MSE} = \frac{1}{n_t}\sum_{i \in t}(y_i - \bar y_t)^2$ , and maximizing IG is equivalent to maximizing the reduction in the sum of squares.

Centering. Not needed: thresholds are compared within a feature, and monotone transformations don't change the ordering.

Where else it shows up. The XGBoost Gain formula I.8 is the exact same pattern - "left score + right score − parent score" - except the score is derived from the loss function instead of postulated.

Note [I]. The algorithm is greedy - locally best split, never revisited. Finding the globally optimal tree is NP-hard. Say this out loud at the interview. Second: the criterion is biased toward features with many unique values (more candidate thresholds => more chances to stumble on a good one). This is where the MDI bias in feature importance P.8 comes from.

---

Before the next formula - the one-paragraph version of Random Forest. A single deep tree is a great memorizer and a poor generalizer: nudge the training data and you get a completely different tree (that's high variance, I.9). Leo Breiman's fix was blunt: grow a lot of deep trees on bootstrap copies of the data (bagging, 1996), also force every split to choose from a random subset of features (random forests, 2001), and average the whole thing. He did this in his seventies, after a career as a probability theorist and years of freelance consulting. And "Random Forests" is, delightfully, a registered trademark he and Adele Cutler licensed out. The next formula is the entire mathematical justification for all that averaging.

[I.3] Variance of a mean of correlated variables - why RF decorrelates

$$\boxed{\text{Var}\left(\frac{1}{N}\sum_{i=1}^{N} X_i\right) = \rho\sigma^2 + \frac{1-\rho}{N}\sigma^2}$$

Symbols. $N$ - number of trees; $\sigma^2$ - variance of a single tree's prediction; $\rho$ - pairwise correlation of tree predictions. All scalars.

Where it comes from. Direct computation:

$$\text{Var}\left(\frac{1}{N}\sum X_i\right) = \frac{1}{N^2}\left[\sum_i \text{Var}(X_i) + \sum_{i\neq j}\text{Cov}(X_i,X_j)\right] = \frac{1}{N^2}\left[N\sigma^2 + N(N-1)\rho\sigma^2\right]$$

$$= \frac{\sigma^2}{N} + \frac{N-1}{N}\rho\sigma^2 = \rho\sigma^2 + \frac{1-\rho}{N}\sigma^2$$

How to read it (this is the point). Two terms:

• $\frac{1-\rho}{N}\sigma^2$ => goes to zero as trees are added. Averaging kills it.
• $\rho\sigma^2$ => a floor that no amount of extra trees gets you below.

This is all of Random Forest. Since the floor is set by $\rho$ , you must reduce correlation between trees. Bootstrap gives part of the decorrelation; random feature selection at each split (max_features, mtry) gives most of it. If the data has one dominant feature, then without feature subsampling every tree picks it for the first split and the trees become nearly identical ( $\rho \to 1$ ) - and averaging buys almost nothing.

Centering. Not applicable.

Where else it shows up. The same formula is the foundation of any ensembling and of portfolio diversification in finance (risk of a portfolio of $N$ correlated assets). Literally one piece of math.

Note [I]. The single most important formula about random forests. If you can derive it and explain that max_features targets specifically the first term (the $\rho$ ), you're already above the median candidate who says "the forest adds randomness for diversity". It also answers why a forest doesn't overfit with more trees: growing $N$ only shrinks the second term; there's nothing for it to hurt.

---

[I.4] Bootstrap: the out-of-bag fraction

$$P(\text{sample not drawn into the bootstrap}) = \left(1 - \frac{1}{n}\right)^{n} \xrightarrow[n\to\infty]{} e^{-1} \approx 0.368$$

Symbols. $n$ - training set size, which is also the bootstrap sample size (sampling with replacement, same size).

Where it comes from. The probability of not picking a given sample in one draw is $1 - 1/n$ . There are exactly $n$ independent draws => $(1-1/n)^n$ . The limit is the classic $e$ limit.

Consequences.

• A bootstrap contains about 63.2 percent unique samples ( $1 - e^{-1}$ ); the rest are duplicates.
• About 36.8 percent of samples are out-of-bag (OOB) for a given tree.

How the ensemble's OOB estimate is computed (step by step).

1. For sample $i$ , find all trees whose bootstrap did not include it (about $0.368N$ of them).
2. Predict $i$ by averaging/voting over those trees only.
3. Repeat for all $i$ ; compare with true labels => OOB error.

The key point. OOB is not an estimate for a single tree. Each sample is predicted by its own "honest sub-forest" that never saw it. That's why OOB ≈ cross-validation, for free.

OOB bias. You're evaluating a forest of roughly $0.368N$ trees, not $N$ , so OOB is slightly pessimistic. With large $N$ (hundreds) the difference vanishes. With small $N$ (dozens) OOB is noisy and noticeably low - use regular CV there.

Where else it shows up. Bootstrap as an uncertainty tool (bootstrap CIs), and the ".632 rule" in bootstrap error estimates (the .632 and .632+ estimators).

Note [I]. OOB does not work for boosting - trees there are sequential and dependent; an "honest sub-ensemble that never saw the sample" doesn't exist. For boosting: a held-out set and early stopping. This makes an excellent bagging-vs-boosting comprehension check.

---

And now boosting: the other way to combine trees, and for tabular data the one that ate the world. Instead of averaging many independent deep trees, you build shallow ones sequentially, each correcting what the ensemble so far gets wrong. The XGBoost paper contains my favorite measure of how completely this took over: of the 29 winning Kaggle solutions published in 2015, 17 used XGBoost. A decade later, gradient-boosted trees still routinely beat deep learning on tabular benchmarks: an awkward fact for a deep-learning decade, and the reason this half of the file is the longer one.

[I.5] The additive model of boosting (forward stagewise)

$$\hat y_i^{(t)} = \hat y_i^{(t-1)} + \eta f_t(x_i), \qquad \hat y_i^{(0)} = F_0$$

The final model:

$$\hat y_i = F_0 + \eta \sum_{k=1}^{N} f_k(x_i)$$

Symbols. $f_t$ - the tree built at step $t$ (a map $\mathbb{R}^d \to \mathbb{R}$ ); $\eta$ - learning rate; $F_0$ - the constant intercept (see T.8).

The key property - forward stagewise. At step $t$ we freeze everything built so far and do not re-optimize earlier trees. This is what distinguishes boosting from a neural net, where all weights move together.

What a tree predicts. Not the target - a correction to the ensemble's current prediction. Everything follows from this: that a leaf's value is a learned parameter (not "the average of y"), and that it can therefore be regularized.

A tree as a map into leaf weights.

$$f_t(x) = w_{q(x)}, \qquad q: \mathbb{R}^d \to \lbrace 1..T\rbrace, \quad w \in \mathbb{R}^{T}$$

where $q$ is the structure (which features, which thresholds) and $w$ is the vector of leaf weights.

Centering. Not applicable.

Where else it shows up. Forward stagewise additive modeling is the general frame: AdaBoost falls out of it under the exponential loss T.9, gradient boosting under an arbitrary differentiable one.

Note [I]. It follows that boosting cannot be parallelized across trees - they are sequential by construction. Parallelism lives inside the construction of a single tree (across features, across histogram bins). A frequent question.

---

[I.6] Pseudo-residuals: gradient boosting as descent in function space

$$r_{it} = -\left[\frac{\partial L\big(y_i, F(x_i)\big)}{\partial F(x_i)}\right]{F = F{t-1}} = -g_i$$

Symbols. $L$ - the loss; $F_{t-1}$ - the current ensemble; $r_{it}$ - the pseudo-residual of sample $i$ at step $t$ . A vector $r \in \mathbb{R}^n$ .

Where it comes from. Friedman's idea: we want to move in the direction that decreases the loss, but our parameters are not numbers - they're functions. Then the "steepest descent direction" in function space is the negative gradient of the loss with respect to the function's values at the training points. The tree is trained to approximate that negative gradient.

Sanity check on MSE. $L = \frac12 (y - F)^2 \Rightarrow \frac{\partial L}{\partial F} = F - y \Rightarrow r_i = y_i - F_{t-1}(x_i)$ - ordinary residuals.

This is where the popular phrase "boosting fits the residuals" comes from. It is exact only for the squared loss; for every other loss, residuals are replaced by the negative gradient.

Sanity check on log-loss. $g_i = p_i - y_i \Rightarrow r_i = y_i - p_i$ - the gap between the label and the predicted probability.

Centering. Not applicable (gradients are already "deviations").

Where else it shows up. Direct analogy with ordinary gradient descent $\theta \leftarrow \theta - \eta \nabla_\theta L$ ; here it's $F \leftarrow F + \eta \cdot (\text{tree approximating } -\nabla_F L)$ .

Note [I]. The sentence "gradient boosting is gradient descent in function space" is mandatory vocabulary. The next level of depth: XGBoost adds the second Taylor term and turns this into Newton's method T.2.

---

[I.7] XGBoost: the optimal leaf weight

$$\boxed{w_j^\ast = -\frac{G_j}{H_j + \lambda}}$$

(out loud: "minus the sum of gradients over the leaf's samples, divided by the sum of their hessians plus lambda")

Symbols and dimensions. $G_j = \sum_{i \in I_j} g_i$ - scalar; $H_j = \sum_{i \in I_j} h_i$ - scalar; $\lambda$ - the L2 coefficient (reg_lambda, default 1); $w_j^\ast$ - scalar, the prediction of leaf $j$ (in margin space!).

Where it comes from (short version; full derivation in **T.3).** Second-order Taylor => regroup the sum by leaves => inside a leaf you get a parabola $G_j w + \frac12 (H_j+\lambda) w^2$ => take the minimum the high-school way.

Three interpretations (be able to say all three).

1. Naive. Numerator - "how much error has accumulated in this leaf"; denominator - "how confidently we may correct it" (curvature) plus regularization.

2. Newtonian. A single sample's individual Newton step is $-g_i/h_i$ . Then

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

That is a weighted average of individual Newton steps with weights $h_i$ , shrunk by $\lambda$ . The leaf trusts the samples with the most curvature.

1. Weighted least squares. See T.7.

Sanity check on MSE. $g_i = \hat y_i - y_i$ , $h_i = 1$ , $\lambda = 0$ :

$$w_j^\ast = -\frac{\sum(\hat y_i - y_i)}{|I_j|} = \text{mean of the residuals in the leaf}$$

The mean of residuals! So the intuition "a leaf's value is computed automatically" is a special case. It breaks the moment the loss isn't MSE or $\lambda > 0$ .

How the L2 works. $\lambda$ sits in the denominator => the weight is pulled toward zero. And since the denominator can't drop below $\lambda$ , the small leaves get strangled hardest (where $H_j \ll \lambda$ ) - exactly where the overfitting risk is highest. Large leaves ( $H_j \gg \lambda$ ) are barely touched.

Centering. No. $G, H$ are sums of derivatives, not moments.

Where else it shows up. Ridge regression: $\hat\beta = (X^\top X + \lambda I)^{-1}X^\top y$ - the same "regularizer in the denominator" structure. In logistic-regression IRLS the update for $\beta$ contains $(X^\top W X + \lambda I)^{-1}$ .

Note [I]. Classic question: "how can L2 penalize a tree if a tree has no coefficients?" Answer: the tree's parameters are the leaf weights $w_j$ (learned constant corrections); ridge penalizes exactly those.

---

[I.8] XGBoost: the Gain formula (split value)

$$\boxed{\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}$$

(out loud: "one half of left-leaf score plus right-leaf score minus parent score, minus gamma")

Symbols. $G_L, H_L$ - sums of gradients and hessians in the left child; same for $R$ . Parent: $G = G_L + G_R$ , $H = H_L + H_R$ . $\gamma$ - gamma / min_split_loss.

Where it comes from. From the structure score T.5: the quality of a structure is $\text{Obj}^\ast = -\frac12\sum_j \frac{G_j^2}{H_j+\lambda} + \gamma T$ . Gain is (quality before) minus (quality after), accounting for the fact that a split adds exactly one leaf ( $\Delta T = +1$ ), i.e. we pay $\gamma$ .

The three terms in the bracket. Left child's score + right child's score − parent's score. The same pattern as Information Gain I.2, but the score is derived from the loss, not postulated.

Split rule. Split if $\text{Gain} > 0$ . So $\gamma$ is a break-even threshold.

How $\gamma$ went from a global penalty to a local rule. In the objective the penalty is $\gamma T$ (global, per whole tree). Since every split adds $\Delta T = +1$ , the local price of any split is $\gamma \cdot 1 = \gamma$ . Hence the " $-\gamma$ " in the formula. This is a genuinely beautiful moment and it lands great at interviews.

How $\lambda$ influences split selection. A larger $\lambda$ suppresses the contribution of leaves with small $H$ => splits that produce small/uncertain leaves become less profitable => the tree grows more slowly. So L2 acts twice: it shrinks weights I.7 and it suppresses splits.

Sanity check on MSE. $h_i = 1$ , $\lambda = 0$ , $\gamma = 0$ : the bracket becomes $\frac{G_L^2}{n_L} + \frac{G_R^2}{n_R} - \frac{G^2}{n}$ - exactly the reduction in the sum of squares, the classical CART criterion for regression. A special case, again.

Computational trick. To evaluate Gain at any threshold, you only need $G_L, H_L$ (the parent's $G, H$ are known). So walking left to right along the sorted feature and accumulating prefix sums covers all thresholds in a single pass.

With L1. Replace $G$ with $\mathcal{T}_\alpha(G)$ - soft-thresholding T.4.

Note [I]. The pair I.7+I.8 is the core of XGBoost. If you can derive both in two minutes, XGBoost questions are closed.

---

[I.9] The bias-variance decomposition

$$\mathbb{E}\left[\big(y - \hat f(x)\big)^2\right] = \underbrace{\sigma^2}{\text{irreducible noise}} + \underbrace{\big(\mathbb{E}[\hat f(x)] - f(x)\big)^2}{\text{Bias}^2} + \underbrace{\mathbb{E}\left[\big(\hat f(x) - \mathbb{E}[\hat f(x)]\big)^2\right]}_{\text{Variance}}$$

Symbols. $f(x)$ - the true function; $\hat f(x)$ - the trained model (random through the randomness of the training set); $\sigma^2 = \text{Var}(\varepsilon)$ - noise variance. Expectations are over training sets.

Where it comes from. Add and subtract $\mathbb{E}[\hat f]$ inside the square, expand; the cross term vanishes.

How it maps onto trees.

Model	Bias	Variance	Treatment
A single deep tree	low	very high	ensembles
Bagging / Random Forest	low (unchanged)	reduced by averaging	more trees, lower $\rho$ I.3
Boosting	reduced sequentially	grows with the number of trees	early stopping, shrinkage, regularization

The key contrast (say it explicitly).

• Bagging attacks variance => trees are deep (low bias), unpruned, averaged. Extra trees don't hurt.
• Boosting attacks bias => trees are shallow (weak learners), added sequentially. Extra trees overfit.

Centering. Not applicable.

Where else it shows up. Regularization in any model is "add bias, remove variance". L1/L2 in linear models, $\lambda$ in XGBoost, dropout in neural nets.

Note [I]. Extra depth: in deep networks the classic U-shaped picture breaks (double descent) - fine to mention, carefully, without derailing the conversation.

---

[I.10] The sigmoid, log-loss, and g, h for the logistic loss

$$p = \sigma(z) = \frac{1}{1+e^{-z}}, \qquad \sigma'(z) = \sigma(z)\big(1-\sigma(z)\big) = p(1-p)$$

$$L(y, z) = -\big[y\log p + (1-y)\log(1-p)\big]$$

$$\boxed{g_i = \frac{\partial L}{\partial z_i} = p_i - y_i, \qquad h_i = \frac{\partial^2 L}{\partial z_i^2} = p_i(1-p_i)}$$

Symbols. $z_i$ - the raw prediction (margin, log-odds); $p_i = \sigma(z_i)$ ; $y_i \in \lbrace 0,1\rbrace$ .

Where it comes from (step by step).

1. $\frac{\partial L}{\partial p} = -\frac{y}{p} + \frac{1-y}{1-p} = \frac{p - y}{p(1-p)}$
2. $\frac{\partial p}{\partial z} = p(1-p)$
3. Chain rule: $\frac{\partial L}{\partial z} = \frac{p-y}{p(1-p)} \cdot p(1-p) = p - y$ . Everything cancels - this cancellation is exactly why the logit parametrization is so convenient.
4. $\frac{\partial^2 L}{\partial z^2} = \frac{\partial (p-y)}{\partial z} = p(1-p)$ .

The meaning of $h_i = p(1-p)$ . It's the Bernoulli variance - "how unsure the model is". Maximum $0.25$ at $p = 0.5$ (at the decision boundary), tending to zero as $p \to 0$ or $1$ . So samples near the boundary weigh more - they're the ones carrying information about where to move the boundary.

Technical nuance. As $p \to 0,1$ the hessian $\to 0$ => division blowup in $-G/(H+\lambda)$ . XGBoost clips the hessian from below by a constant around $10^{-16}$ ; additionally max_delta_step bounds $|w_j|$ .

Centering. Not applicable.

Where else it shows up - the most important connection in this file. The same quantity $p(1-p)$ is:

• the Bernoulli variance in statistics;
• Gini impurity (binary case $= 2p(1-p)$ ) I.1;
• the diagonal of the matrix $W$ in the Fisher information of logistic regression: $\widehat{\text{Cov}}(\hat\beta) = (X^\top W X)^{-1}$ , with $W = \text{diag}(p_i(1-p_i))$ ; dimensions: $X$ is $n\times p$ , $W$ is $n\times n$ , the result is $p\times p$ ;
• the hessian in XGBoost.

It is one and the same curvature of the logistic likelihood. See T.7 on Newton boosting ≈ IRLS.

Note [I]. Dropping this connection at an interview instantly shows that the models in your head are connected, not filed in separate boxes. One of the strongest cards you can play.

A plug, but an on-topic one, since half of Tier 1 just turned out to be statistics in disguise: I built a statistics exam app, Stat Exam Pro. The main focus is medical statistics, but if you're prepping for DS interviews it's worth a look anyway: the topics overlap more than you'd expect, and seeing the same ideas from another field's angle is weirdly refreshing. Everything is in test format with thoroughly worked answers. The section I'm proudest of is Paradoxes & Intuition Traps - start there ;)

---

Next up, part 2: the knobs you actually turn, and where they bite - Part 2 - the Practice tier: the knobs you actually turn