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

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

Answer 1

I would say that there are two main reasons for the use of sampling without replacement for most implementations of stochastic variants of Gradient Boosting.

The first one is simply historic: In 1999 both Breiman and Friedman published papers that went in the similar direction of trying reduce both Bias and Variance for ensemble estimators. Breiman published Adaptive Bagging, which was more based on Random Forests and used sampling with replacement. Friedman (who had also authored the first paper on Gradient Boosting) published instead Stochastic Gradient Boosting, which used sampling without replacement. In general, the work of Friedman in this field has been much more successful, as his work on Gradient Boosting is at the base of all modern implementations, which therefore use sampling without replacement as the standard.

The second reason is that sampling without replacement is more flexible: the goal of Stochastic Gradient Boosting is not only to introduce randomness, but also to make boosting iterations faster.
Quoting from the original paper:

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.