Why gradient boosting uses sampling without replacement?

Question

In Random Forest each tree is built selecting a sample with replacement (bootstrap). And I assumed that Gradient Boosting's trees were selected with the same sampling technique. (@BenReiniger corrected me). Here there are the sampling techniques implemented for Catboost

My questions:

• Why is Gradient Boosting sampling done without replacement?
• Why would it be worst to sample with replacement?
• Are there any sampling techniques used in GB that are with replacement?

I quote a paper for SGB:

Stochastic Gradient Boosting is a randomized version of standard Gradient Boosting algorithm... adding randomness into the tree building procedure by using a subsampling of the full dataset. For each iteration of the boosting process, the sampling algorithm of SGB selects random s·N objects without replacement and uniformly

Answer 1

Why is Gradient Boosting sampling done without replacement?

Your first question seems to suggest that the base classifier will always have a subsampling mechanism but this is not necessarily true.

Notice that in the Catboost documentation it is mentioned "Stochastic Gradient Boosting" not "Gradient Boosting". Stochastic Gradient Boosting is a variation of Gradient Boosting that is precisely based on building the boosting process using a subset of the data at each iteration. Therefore each base model does not see the whole train data, it sees only a subset (or minibatch) of the data.

You might want to do this for 2 main reasons: Faster train time, Regularization effect.

Why would it be worst to sample with replacement?

As long as you do sampling in your base classifier the speed benefit should be quite similar. If your base classifier does not do any sampling then the Stochastich Gradient Boosting algorithm will converge much faster. Just like a Mini Batch version of a Neural network converges much faster than a Full Batch version.

Are there any sampling techniques used in GB that are with replacement?

Standard Gradient Boosting uses all the data to build the gradient at each step of the boosting process.

If you do full batch learning but your base classifier has a "subsample" parameter then you are essentially doing sampling with replacement at every step of the boosting process.