Subsampling And Randomness In Gradient Boosting

Why Add Randomness to a Gradient Update?

At a boosting round, the current fitted function determines a gradient or pseudo-residual for each training observation. A common stochastic variant fits the next tree using only a randomly chosen subset of those observations. The update is then based on an incomplete view of the current loss surface. This can reduce computation and alter the variability of the fitted sequence, but it also means the update may point in a different direction from the one suggested by the full training set.

The key distinction is between gradient estimation and tree fitting. For a fixed current fit, a uniformly sampled average of per-observation gradients is unbiased for the full-data average. But a tree chosen by optimizing a sampled fitting criterion is itself random and data-dependent; its resulting direction is not generally an unbiased estimate of the full-data tree update. The calculations below make these statements precise.

Subsampling at a Fixed Boosting Round

Let the observed training data be \((x_i,y_i)\), \(i=1,\ldots,n\), and let the empirical objective for a score function \(F\) be

L_n(F)=\frac{1}{n}\sum_{i=1}^n \ell\bigl(y_i,F(x_i)\bigr).

At round \(t\), condition on the data and on all randomness used in earlier rounds. The current function \(F_{t-1}\) is then fixed. Write

g_i=\left.\frac{\partial}{\partial z}\ell(y_i,z)\right|_{z=F_{t-1}(x_i)}, \qquad \bar g=\frac{1}{n}\sum_{i=1}^n g_i.

A common subsampling scheme draws a subset \(S\) of size \(m\) uniformly from all subsets of \(\{1,\ldots,n\}\) of that size, without replacement. The sampled average gradient is \(\hat g_S=m^{-1}\sum_{i\in S}g_i\). The sampled pseudo-residuals are \(-g_i\) for \(i\in S\). This definition describes the gradient information available to the update; a tree-fitting algorithm may use that information in a more structured way than simply averaging it.

Definition: A subsampled gradient estimate at a fixed boosting round is a statistic computed from a random subset of the per-observation gradients evaluated at the current, fixed function. For a size-\(m\) uniform sample without replacement, the estimate of the full average gradient is \(\hat g_S=m^{-1}\sum_{i\in S}g_i\).

Worked Example: Variance of a Subsampled Gradient

Suppose \(n=4\), the current per-observation gradients are \((-2,-1,1,2)\), and a subset of size \(m=2\) is selected uniformly without replacement. The full average is \(\bar g=0\). The finite-population variance, using denominator \(n-1\), is

S_g^2=\frac{1}{3}\left[(-2)^2+(-1)^2+1^2+2^2\right]=\frac{10}{3}.

The variance formula derived below gives

\operatorname{Var}(\hat g_S) =\left(1-\frac{2}{4}\right)\frac{10/3}{2} =\frac{5}{6}.

This can be checked by listing the six equally likely pairs. Their sample means are \(-1.5,-0.5,0,0,0.5,1.5\). Their average is \(0\), and their average squared deviation from \(0\) is \[ \frac{2.25+0.25+0+0+0.25+2.25}{6}=\frac{5}{6}. \] The subsample gradient is unbiased here, but a typical draw does not equal the full-data gradient.

Unbiasedness and Finite-Population Variance

Theorem: Conditional on the data and the current boosting fit, if \(S\) is a uniform size-\(m\) subset sampled without replacement, then \(E[\hat g_S]=\bar g\). If \(S_g^2=(n-1)^{-1}\sum_{i=1}^n(g_i-\bar g)^2\), then \[ \operatorname{Var}(\hat g_S)=\left(1-\frac{m}{n}\right)\frac{S_g^2}{m}. \]

Proof. Let \(I_i\) be 1 if observation \(i\) is sampled and 0 otherwise. Then \(\hat g_S=m^{-1}\sum_i I_i g_i\), with \(E[I_i]=m/n\). Therefore

E[\hat g_S]=\frac{1}{m}\sum_{i=1}^n E[I_i]g_i =\frac{1}{m}\frac{m}{n}\sum_{i=1}^n g_i=\bar g.

For the variance, \(\operatorname{Var}(I_i)=(m/n)(1-m/n)\). For \(i\ne j\), the probability that both are selected is \(m(m-1)/(n(n-1))\), so \(\operatorname{Cov}(I_i,I_j)=-m(n-m)/(n^2(n-1))\). Put \(a_i=g_i-\bar g\), noting that \(\sum_i a_i=0\). Since \(\hat g_S-\bar g=m^{-1}\sum_i I_i a_i\),

\begin{aligned} \operatorname{Var}(\hat g_S) &=\frac{1}{m^2}\left[ \frac{m(n-m)}{n^2}\sum_i a_i^2 -\frac{m(n-m)}{n^2(n-1)}\sum_{i\ne j}a_i a_j \right]\\ &=\frac{1}{m^2}\frac{m(n-m)}{n^2} \left(1+\frac{1}{n-1}\right)\sum_i a_i^2\\ &=\frac{n-m}{nm}\frac{1}{n-1}\sum_i a_i^2 =\left(1-\frac{m}{n}\right)\frac{S_g^2}{m}. \end{aligned}

The second equality uses \(\sum_{i\ne j}a_i a_j=-\sum_i a_i^2\). The factor \(1-m/n\) is the finite-population correction: the variance is zero when the entire data set is used. \(\square\)

The same argument applies to a fixed direction \(h\), evaluated at the training points. The directional derivative of the empirical objective is \(n^{-1}\sum_i g_i h(x_i)\), and its sampled estimate is \(m^{-1}\sum_{i\in S}g_i h(x_i)\). The estimate is unbiased when \(h\) is fixed before the subset is drawn. This qualification matters: if the same subset is used to select \(h\), the direction and the gradient estimate are dependent.

What the Variance Says About an Update

A gradient estimate can be unbiased and still make progress less reliable. To isolate this effect, consider a differentiable objective \(Q\) on a finite-dimensional score vector \(\theta\). Suppose its gradient is \(\beta\)-Lipschitz, meaning \(\|\nabla Q(u)-\nabla Q(v)\|\leq\beta\|u-v\|\). Let \(\hat g\) be a conditionally unbiased estimate of \(g=\nabla Q(\theta)\), with covariance matrix \(\Sigma\), and take the step \(\theta^+=\theta-\eta\hat g\). The smoothness inequality yields

E[Q(\theta^+)\mid\theta] \leq Q(\theta)-\eta\|g\|^2 +\frac{\beta\eta^2}{2}\left(\|g\|^2+\operatorname{tr}(\Sigma)\right).

Indeed, Lipschitz continuity of the gradient implies \(Q(\theta+u)\leq Q(\theta)+\nabla Q(\theta)^\mathsf{T}u+\beta\|u\|^2/2\). Substitute \(u=-\eta\hat g\), take the conditional expectation, and use \(E[\hat g]=g\) and \(E[\|\hat g\|^2]=\|g\|^2+\operatorname{tr}(\Sigma)\). Thus the variance contributes a nonnegative second-order term. This is a statement about an unconstrained gradient step, not a guarantee for a tree fitted to sampled pseudo-residuals: tree approximation, splits, leaf values, and line search can all change the update.

Worked Example: Sampling Noise in a One-Dimensional Update

Consider squared loss \(Q(\theta)=\frac{1}{2n}\sum_i(\theta-y_i)^2\) with four responses \(y=(0,0,2,2)\), current value \(\theta=0\), and a size-two subsample. The full gradient is \(\theta-\bar y=-1\), where \(\bar y=1\). A sampled gradient is \(-\bar y_S\), so a step of size \(\eta\) gives \(\theta^+=\eta\bar y_S\).

The subsample mean is \(0,1,\) or \(2\), with probabilities \(1/6,4/6,\) and \(1/6\), respectively. Hence \(E[\bar y_S]=1\) and \[ \operatorname{Var}(\bar y_S)=\frac{1}{6}(0-1)^2+\frac{4}{6}(1-1)^2+\frac{1}{6}(2-1)^2=\frac{1}{3}. \] At \(\eta=1\), the full-gradient step reaches \(\theta=1\) exactly. The subsampled step instead gives \(0,1,2\) with those probabilities.

For the four training responses, \(Q(\theta)=\frac{1}{2}[(\theta-1)^2+1]\). The initial objective is \(Q(0)=1\). After the full step it is \(Q(1)=1/2\), whereas its expectation after the subsampled step is \[ E[Q(\theta^+)]=\frac{1}{2}\left[E[(\theta^+-1)^2]+1\right] =\frac{1}{2}\left[\frac{1}{3}+1\right]=\frac{2}{3}. \] The subsampled update improves the expected objective from its initial value, but not as much as the full step in this example. Unbiasedness of the gradient does not imply that each random update, or its expected objective value, matches the full-gradient update.

Tree Fitting and Rare Gradient Signals

In gradient boosting, a tree is usually fitted to the sampled pseudo-residuals, perhaps followed by leafwise optimization or a line search. The subset can affect both which observations contribute to leaf estimates and which splits are considered. Consequently, the update selected by the tree learner need not be unbiased, even though the sampled gradient average is unbiased. A further complication is selection: among many candidate splits or trees, the learner chooses one that looks good on the sample. Its sampled fit can therefore look more favorable than its full-data fit simply because the choice adapted to sampling noise.

Worked Example: A Subsample Can Miss a Rare Region

Suppose \(n=100\) observations include five in a small region where the pseudo-residuals have a strong, consistent signal. A uniform subset of \(m=20\) observations, drawn without replacement, contains none of those five with probability

P(\text{miss all five}) =\frac{\binom{95}{20}}{\binom{100}{20}} =\prod_{j=0}^{4}\frac{80-j}{100-j} \approx 0.319.

Thus, in roughly 32 percent of rounds under this setup, the sampled data contain no observation from that region. A tree trained on that subset cannot respond directly to its residual signal in that round. This does not prove that subsampling harms validation performance: other observations may support a useful split, and later rounds may include the region. It does show why a small sampling fraction can make updates unstable when important patterns are rare.

The practical effect depends on the combination of sample fraction, learning rate, tree complexity, and signal distribution. Smaller subsets typically increase gradient variability, while smaller step sizes reduce the size of the resulting score changes. These are distinct controls: reducing the learning rate does not restore information about a region absent from the subset, and increasing the subset does not by itself make a tree approximation accurate.

Reading Training and Validation Behavior

Randomness can change the path of the fitted sequence, but it is not automatically a regularizer that improves prediction. Training loss may fluctuate because each round uses a different sample; validation loss may also fluctuate, especially when the validation set is small or when the fitted trees respond to rare sampled patterns. A single favorable validation value is not evidence that subsampling has improved generalization. Compare runs or use repeated evaluations when the random variation is consequential, while keeping the validation data out of the fitting updates.

A useful diagnosis separates three sources of behavior:

Subsampling noise: which observations happened to contribute in this round.
Approximation and selection: how the tree structure and leaf values represent the sampled gradients.
Optimization choices: the learning rate, stopping rule, and any line search used for the update.

The finite-population variance result describes the first source for a fixed gradient quantity. It does not measure the full variability of a selected tree or establish a margin bound for the randomized training procedure. Such conclusions require analysis of the learner and the prediction rule, not just the gradient average.

Common Mistake

Pitfall: “The subsample gradient is unbiased, so a tree fitted on the subsample gives an unbiased version of the full-data tree update.” This does not follow. Unbiasedness applies to a fixed linear average of fixed per-observation gradients. A fitted tree is selected using the same sampled data; its split and terminal values depend on the sample. The correct claim is narrower: the subsample average gradient, and the estimated directional derivative for a direction fixed before sampling, are unbiased under uniform sampling. Tree-level behavior must be assessed separately.

Likewise, seeing lower sampled training loss after a tree update does not ensure that the full training loss or validation loss decreased. The sampled objective is only a noisy view of the full objective. The distinction is especially important when the subsample is small or the tree search considers many candidate splits.

Key takeaway: Subsampling introduces a quantifiable finite-population error into fixed gradient estimates. Its effect on the fitted boosting update is broader because the tree is adapted to the sampled observations. Treat gradient unbiasedness as a useful calculation, not as a guarantee of tree-level progress or improved validation performance.

Check Your Understanding

Use the definitions and calculations in this tutorial to answer the following.

For a uniform size-\(m\) sample without replacement, why does the variance of the sample mean vanish when \(m=n\)?
What additional condition is needed for a sampled directional derivative to be unbiased for a fixed direction?
Explain why fitting and selecting a tree on the same subsample prevents the fixed-gradient unbiasedness result from directly applying to the tree update.
In the four-response example, what are the possible subsample means and their probabilities? Why does an unbiased gradient not yield the same update as the full gradient on every draw?
Name two features of a boosting procedure, other than the finite-population gradient variance, that can affect validation behavior under subsampling.