Tutorials › Exam SRM - Statistics for Risk Modeling › Stochastic Gradient Boosting By Subsampling

Home  /  Tutorials  /  Exam SRM / Boosting Methods

Exam SRM · Boosting Methods · Tutorial 655 of 926

Stochastic Gradient Boosting By Subsampling

See how observation subsampling changes gradient-boosting updates, and work through its effects on fitted trees, computational effort, and training loss.

Advanced 10 min read

What You'll Learn

  • Define the subsampling rate and distinguish observation subsampling from feature selection.
  • Compute pseudo-residuals and fit a tree using only the selected observations.
  • Explain why the fitted tree is applied to predictions for all observations.
  • Derive the mean and variance of a simple random subsample gradient average.
  • Assess how subsampling affects computation, randomness, and generalization.
  • Avoid confusing stochastic gradient boosting with bootstrap sampling or a guaranteed reduction in test error.

Why Subsample During Boosting?

Gradient boosting builds a prediction in stages. At each stage, it computes how the current predictions should change to reduce the chosen loss, fits a small tree to those directions, and adds a shrunken version of the tree to the current model. Fitting every tree to every training observation can be computationally expensive, and successive trees can respond repeatedly to the same details of the data.

Stochastic gradient boosting changes the fitting step: at each iteration, it selects a random subset of the training observations and fits the new tree using that subset. The tree is still added to the ensemble, and its predictions can update the model for every observation. Subsampling introduces additional randomness; it can reduce computation and sometimes improve generalization, but neither improvement is guaranteed.

Definition: Suppose a training set has \(N\) observations. At boosting iteration \(m\), stochastic gradient boosting selects \(s\) observations, usually by simple random sampling without replacement, and fits the next tree using their pseudo-residuals. The subsampling rate is \(q=s/N\), where \(0<q\leq 1\). When \(q=1\), every observation is used and the fitting step is ordinary, full-sample gradient boosting.

The random subset is a subset of observations, not a subset of predictors. In the usual version described here, the observations within a single iteration are sampled without replacement, while a fresh subset is drawn at the next iteration. Thus, an observation may be selected again in a later iteration. This is not the same as fitting each tree to a bootstrap sample drawn with replacement.

What Changes in a Boosting Iteration?

Let \(F_{m-1}(x_i)\) be the current score for observation \(i\), and let \(\ell(y_i,F_{m-1}(x_i))\) be its loss. The negative derivative of the loss with respect to the current score is the pseudo-residual:

$$ r_{im} = -\left. \frac{\partial \ell(y_i,F(x_i))}{\partial F(x_i)} \right|_{F=F_{m-1}}. $$

In stochastic gradient boosting, the algorithm computes or uses these pseudo-residuals for the selected observations, fits a tree to those selected cases, and adds the tree's shrunken predictions to the current model. With learning rate \(\nu\), a common update is

$$ F_m(x)=F_{m-1}(x)+\nu h_m(x), $$

where \(h_m\) is the fitted tree. For squared-error loss, fitting the tree means approximating the residuals; for other losses, the tree approximates the negative loss gradients. The exact leaf-value procedure depends on the boosting algorithm and loss. The examples below state their fitting rule explicitly.

Important distinction: The tree is fitted using only the selected observations, but once fitted, \(h_m(x)\) can be evaluated at any predictor vector \(x\). The update is therefore ordinarily applied to the ensemble's predictions for all observations, including cases not selected for that iteration.

Worked Example: A Subsampled Squared-Error Update

Worked Example: A Subsampled Squared-Error Update

A hypothetical severity model has four training observations with predictor values \(x=1,2,3,4\) and outcomes \(y=2,3,5,6\). Use half-squared-error loss, \( \ell(y,F)=\frac12(y-F)^2 \), initialize with the mean outcome, and use learning rate \(\nu=0.4\). At the first iteration, the selected observations are those with \(x=1,2,4\). Fit a stump with split \(x\leq 2\) versus \(x>2\), using the mean pseudo-residual in each leaf. Compute the updated predictions and compare the total squared error before and after the update.

Method and initialization. For half-squared-error loss, the negative derivative with respect to \(F\) is \(y-F\). The initial constant prediction is the outcome mean:

$$ F_0=\frac{2+3+5+6}{4}=4. $$

The four pseudo-residuals are \(2-4=-2\), \(3-4=-1\), \(5-4=1\), and \(6-4=2\). The selected cases have \(x=1,2,4\), so the left leaf contains residuals \(-2,-1\), and the right leaf contains residual \(2\).

Fit the leaves. The left-leaf value is \((-2-1)/2=-1.5\). The right-leaf value is \(2\). Thus \(h_1(x)=-1.5\) for \(x\leq2\), and \(h_1(x)=2\) for \(x>2\).

Update all four predictions. The tree is evaluated at every predictor value. For \(x=1,2\), the updated score is \(4+0.4(-1.5)=3.4\). For \(x=3,4\), it is \(4+0.4(2)=4.8\). In particular, the observation at \(x=3\), which was not selected, receives the right-leaf update.

Check the error. Before the update, the squared errors are \(4,1,1,4\), for a total of \(10\). After the update, they are \((2-3.4)^2=1.96\), \((3-3.4)^2=0.16\), \((5-4.8)^2=0.04\), and \((6-4.8)^2=1.44\). Their sum is \(1.96+0.16+0.04+1.44=3.60\). The total squared error decreases from \(10\) to \(3.60\) on this training set.

Common mistake avoided: Updating only the selected observations would leave the score at \(4\) for \(x=3\). That is not the stated tree-boosting update: the fitted tree assigns a value to \(x=3\), so its score becomes \(4.8\).

Why the Subsample Gradient Average Is Informative

For a fixed set of \(N\) gradient values, a simple random sample without replacement gives an unbiased sample mean. This explains one useful feature of observation subsampling, but it does not mean that the entire tree fit is unbiased: deciding which split to make is a data-dependent, nonlinear operation.

Theorem: Suppose \(N>1\) fixed values \(z_1,\ldots,z_N\) have population mean \(\bar z\) and sample variance \(S^2=\sum_{i=1}^N(z_i-\bar z)^2/(N-1)\). If \(s\) values are selected by simple random sampling without replacement, where \(1\leq s\leq N\), their mean \(\bar z_s\) satisfies $$ E[\bar z_s]=\bar z,\qquad \operatorname{Var}(\bar z_s)=\left(1-\frac{s}{N}\right)\frac{S^2}{s}. $$

To justify the mean result, let \(I_i\) equal 1 if value \(z_i\) is selected and 0 otherwise. Every value has selection probability \(s/N\), so

$$ E[\bar z_s] = E\left[\frac{1}{s}\sum_{i=1}^N I_i z_i\right] = \frac{1}{s}\sum_{i=1}^N\frac{s}{N}z_i = \bar z. $$

For the variance, define \(a_i=z_i-\bar z\), so that \(\sum_i a_i=0\), and write \(\bar z_s-\bar z=(1/s)\sum_i I_i a_i\). Under sampling without replacement, \(E[I_i]=s/N\), \(\operatorname{Var}(I_i)=s(N-s)/N^2\), and for distinct \(i,j\), \(\operatorname{Cov}(I_i,I_j)=-s(N-s)/N^2(N-1)\). Therefore,

$$ \begin{aligned} \operatorname{Var}(\bar z_s) &=\frac{1}{s^2}\operatorname{Var}\left(\sum_i I_i a_i\right)\\ &=\frac{1}{s^2}\left[ \frac{s(N-s)}{N^2}\sum_i a_i^2 -\frac{s(N-s)}{N^2(N-1)}\sum_{i\ne j}a_i a_j \right]. \end{aligned} $$

Since \(\sum_{i\ne j}a_i a_j=(\sum_i a_i)^2-\sum_i a_i^2=-\sum_i a_i^2\), the bracket becomes \(\frac{s(N-s)}{N(N-1)}\sum_i a_i^2\). Substituting \(\sum_i a_i^2=(N-1)S^2\) gives the stated variance. When \(s=N\), it is zero, as the sample is the whole set.

Worked Example: Quantifying Subsample Variability

At a boosting iteration, suppose four fixed pseudo-residuals are \(-2,-1,1,2\), and two are selected uniformly without replacement. Find the expected selected mean and its variance. Then verify the variance by listing the possible selected means.

Method. The full-set mean is \((-2-1+1+2)/4=0\). The sample variance of these four values is

$$ S^2=\frac{(-2)^2+(-1)^2+1^2+2^2}{4-1}=\frac{10}{3}. $$

Here \(N=4>1\) and \(s=2\), so the theorem gives \(E[\bar z_s]=0\) and

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

There are six equally likely pairs. Their means are \(-1.5,-0.5,0,0,0.5,1.5\). Their average is zero, and the average squared deviation from zero is \((2.25+0.25+0+0+0.25+2.25)/6=5/6\), confirming the result.

Common mistake avoided: The variance formula uses \(S^2\) with denominator \(N-1\), not the population variance with denominator \(N\). Also, the stated result requires \(N>1\); for \(N=1\), that sample variance is undefined.

Worked Example: Subsampling With Logistic Loss

Worked Example: Subsampling With Logistic Loss

Consider a hypothetical binary outcome data set with ordered predictor values \(x=1,2,3,4\) and outcomes \(y=1,1,0,0\). Use logistic loss \(\ell(y,F)=\log(1+e^F)-yF\), start with scores \(F_0=0\), select \(x=1,2,3\), and fit the stump split at \(x\leq2\). Fit each leaf to the mean negative gradient among selected cases and use learning rate \(\nu=0.2\). Calculate the updated probabilities for all observations and the mean logistic loss before and after.

Compute the negative gradients. The probability corresponding to score \(F\) is \(p=1/(1+e^{-F})\), and the negative gradient is \(y-p\). Initially every probability is \(0.5\). The selected cases therefore have negative gradients \(0.5,0.5,-0.5\).

Fit the stump and update. The left leaf mean is \((0.5+0.5)/2=0.5\); the right leaf mean is \(-0.5\). The shrunken updates are \(0.2(0.5)=0.1\) on the left and \(0.2(-0.5)=-0.1\) on the right. Applying the tree to all cases gives scores \(0.1,0.1,-0.1,-0.1\). Thus the probabilities are \(1/(1+e^{-0.1})\approx0.5250\) for \(x=1,2\), and \(1/(1+e^{0.1})\approx0.4750\) for \(x=3,4\).

Check the loss. Initially each case has loss \(\log 2\approx0.6931\), so the mean loss is approximately \(0.6931\). After the update, each case has loss \(\log(1+e^{-0.1})\approx0.6444\): the positive outcomes have score \(0.1\), and the negative outcomes have score \(-0.1\). The mean loss is therefore approximately \(0.6444\), lower than before. Probabilities and losses are rounded to four decimal places.

Common mistake avoided: For logistic loss, the negative gradient is \(y-p\), not the raw difference \(y-F\). The score is on the logit scale; it is converted to a probability with the logistic function.

Effects on Computation, Variability, and Generalization

If building a tree costs roughly proportionally to the number of cases it examines, using a fraction \(q\) of the data can reduce the per-iteration case-level work. The actual time savings depend on implementation, tree depth, and other overhead, so a subsampling rate of one-half does not necessarily make the full algorithm exactly twice as fast. Across many iterations, a smaller subset also means fewer case-level gradient values are used to choose each tree.

A different subset at each iteration makes the fitted sequence of trees more variable than a sequence based on identical full-sample fitting. That randomness can keep a tree from repeatedly tracking the same sample-specific fluctuations. In some data settings, this reduces overfitting and improves predictions on new data. But an overly small subset can make the fitted directions noisy, and a particular random sequence can perform worse. Subsampling is therefore a regularizing choice, not a guarantee of lower test error.

A useful distinction is between two claims:

  • The mean of sampled fixed gradients is unbiased for the full-data mean under simple random sampling.
  • The tree selected from those gradients, including its split and leaf values, need not be an unbiased estimate of the full-sample tree. Tree construction is adaptive to the selected cases.

The finite-population variance result also shows that using more observations reduces the variability of the sampled mean, with variance zero at \(s=N\). It does not prescribe an optimal subsampling rate. The appropriate rate depends on the data, the computational budget, and how stable the resulting predictions are.

Worked Example: Translating a Subsampling Rate Into Work

Worked Example: Translating a Subsampling Rate Into Work

A hypothetical training set contains \(N=1{,}200\) policy records. A boosting procedure draws a new simple random sample without replacement of size \(s=360\) at every iteration. It runs for \(M=50\) iterations. Find the subsampling rate, the number of record-iteration pairs used for tree fitting, and the expected number of times a given record is selected over the 50 iterations.

Rate and work. The rate is \(q=360/1{,}200=0.30\). Tree fitting uses \(360\) records per iteration, or \(50(360)=18{,}000\) record-iteration pairs. Fitting on all records at every iteration would use \(50(1{,}200)=60{,}000\) such pairs. This is a 70% reduction in record-iteration pairs, though it need not translate into exactly 70% less elapsed time.

Selection frequency. A given record has probability \(0.30\) of being selected in any one iteration. Its expected number of selections over 50 iterations is \(50(0.30)=15\). This is an expectation, not a guarantee that every record appears exactly 15 times.

Check. The selected fraction is \(18{,}000/60{,}000=0.30\), consistent with the per-iteration subsampling rate. The record-iteration work reduction is \((60{,}000-18{,}000)/60{,}000=0.70\), or 70%.

Common mistake avoided: A 30% subsampling rate means that 30% of records are used in each iteration, not that only 30% of the original records are ever used across the entire fit.

Practical Interpretation and Exam Traps

When interpreting a stochastic boosting procedure, identify the sampling unit and the sampling rule before making claims about it. Here the unit is an observation; within an iteration, selection is without replacement. The rate \(q\) determines the number of cases used per tree, while the learning rate \(\nu\) determines how much the fitted tree changes the current score. They are different controls and should not be confused.

Keep these points in view:

  • A sampled tree is fitted from the selected cases, but its predictions generally update the ensemble for all cases.
  • Subsampling observations is not random feature selection; it does not, by itself, discard predictors.
  • Sampling without replacement within one iteration is not bootstrap sampling with replacement.
  • An unbiased sampled mean does not imply that a data-adaptive tree or the final ensemble is unbiased.
  • Less per-iteration fitting work and added randomness may help, but improved generalization is an empirical possibility rather than a theorem.

These distinctions are aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus: the key is to connect the sampling mechanism to the gradient-fitting step and then state carefully what follows—and what does not.

Check Your Understanding

Work through each problem before checking the answer shown at its end.

  1. A stochastic boosting fit has \(N=800\) training cases and uses \(q=0.25\). How many cases are selected for one tree? (Answer: 200 cases.)
  2. Four fixed pseudo-residuals are \(-3,-1,1,3\). A sample of \(s=2\) is drawn without replacement. Find the expected sample mean and its variance. (Answer: \(E[\bar z_s]=0\), \(\operatorname{Var}(\bar z_s)=5/3\).)
  3. A fitted tree has value \(0.8\) in a leaf, the current score for a case is \(1.2\), and the learning rate is \(0.25\). The case was not selected when the tree was fitted but falls in that leaf. What is its updated score? (Answer: \(1.2+0.25(0.8)=1.4\).)
  4. For one binary observation, the outcome is \(y=0\) and the current logistic probability is \(p=0.7\). What negative gradient is used as the pseudo-residual? (Answer: \(y-p=-0.7\).)
  5. A data set has 50 cases, the subsampling rate is \(0.60\), and 4 independent iterations draw new subsets. What is the expected number of times one specified case is selected, and the probability it is never selected? (Answer: Expected selections \(=4(0.60)=2.4\); probability never selected \(=(1-0.60)^4=0.0256\).)

Previous

Next

Back to Tutorials
Clinical Biostats