@glouppe was very interested in the approximate splitter. I also think it would be a nice addition helping speed things up a lot... I'm also pinging @jnothman and @nelson-liu who might be interested in reviewing this...

For xgboost, all samples for a given feature will be scanned. Each sample will be used to update the impurity statistic of the node to which it belongs to (cf. here).
On the contrary in scikit-learn, only the samples for a node will be selected (cf. here or here). Therefore, it involves repetitive scans which are not necessary.

Propose a prototype of the gradient boosting modifying the samples scanning and splitting strategies. It will required a change of the decision tree algorithm (that's why we want a prototype first). This change should allow to match the performance of xgboost while using the exact method.

Can you elaborate on this?

In our case, sample_mask is only used with presorting, which we can get rid off if benchmarks show it is indeed slower than the standard implementation.

How does our standard implementation (without presorting) compare with xgboost? both in terms of algorithms and performance?

Implement an approximation splitter by binning the data

+1 for binning

I'm also a bit confused what you mean by repetitive scans. We have two different sorting mechanisms, presorting and not. Presorting works better on smaller datasets with a smaller number of features, whereas not presorting works better on larger amounts of data. XGBoost uses presorting (when I last looked at the code) and we do not, but we provide the option for allowing the user to do such.

In our case, sample_mask is only used with presorting, which we can get rid off if benchmarks show it is indeed slower than the standard implementation.

Ok, I think I understand. We could could rid of the sample_mask logic by looking for splits across all nodes in parallel -- this is what I think they do in xgboost by maintaining several Criterion-like objects.
Is that more or less what you have in mind?

@glouppe in xgboost, sample_mask would store the ID of the current node and as you said, will allow to maintain several criterions.
It allows to make one scan of sample_mask. In scikit-learn, a scan is performed for each node to be split.

@glouppe in xgboost, sample_mask would store the ID of the current node and as you said, will allow to maintain several criterions.
It allows to make one scan of sample_mask. In scikit-learn, a scan is performed for each node to be split.

Yup, looks like something promising.

+1 for both changes.

(However, to avoid never-ending PRs, please propose the changes separately, possibly with the least amount of changes to the other parts of the codebase.)

@glouppe Yep, I am gonna make separated PRs.

Can we close this as #12807 (HistGradientBoostingClassifier and HistGradientBoostingRegressor) is merged?

Yes this is done.