# Why gradient boosting uses sampling without replacement?

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

This question is crossposted at Data Science Stack Exchange, since I didn't got any answers i am posting it here

• The last option (Poisson) actually uses replacement, and it's more like a classic bootstrap Feb 10, 2020 at 16:21
• Yes! I see that there is one sampling that is done with replacement, but in the original (and most sampling techniques) it is done with out, and I am curious why this Feb 10, 2020 at 17:04

Using $$\tilde{N} = N$$ introduces no randomness and causes Algorithm 2 (SGB, e.n.) to return the same result as Algorithm 1 (GB, e.n.). The smaller the fraction $$f=\tilde{N}/N$$, the more samples used in successive iterations will differ, thereby introducing more overall randomness into the procedure. Using the value $$f=1/2$$ is roughly equivalent to drawing bootstrap samples at each iteration. Using $$\tilde{N} = f \cdot N$$ also reduces computation by a factor of $$f$$.
This means that we could indeed use sampling with replacement instead (also sampling a lower fraction $$f$$), but the computation factor would be much higher for an equivalent amount of "randomness" added to the iterations.