I assume that MIN_CAT_SUPPORT is one reason why native categorical support is not strictly equivalent to OHE (tree depth is another). In this case, giving the user control over this is desirable. Maybe a future PR.

It is very hard to find any explaining documentation for this.

Looking into lightgbm and googling, is this a form of additive smoothing?
If so, I do not fully understand the formula for cat_infos[n_used_bins].value, i.e. why do we add MIN_CAT_SUPPORT to every sum_hessians_bin?

MIN_CAT_SUPPORT is used as a cut-off and seems to play at the same time a role similar to self.l2_regularization.

I couldn't find doc on this either.

I just see it as some form of shrinkage. sum_hessian_bin is basically n_samples_bins

After a long walk, I'd be in favor of excluding this functionality here and introduce it in a separate PR showing its usefulness.

Would that be OK to keep it with the option to remove it in the future depending on empirical results?

While I don't have a specific ref for the specific case of categorical splits in GBDTs, this kind of shrinkage is quite common (ref below). Also, "LightGBM does it" has been a pretty strong argument for this part of the code so far lol.

Categories are ordered by their mean y, and the main idea is that we don't want to trust too much a mean that is computed with too few samples. So we add this small constant in the denominator to "shrink" it and limit its strength (in other words, we regularize).

Such shrinkage is often used in an RS context as a form of regularization of similarities: in this paper they shrink similarities that don't have enough support, and they justify from a Bayesian point of view.
(There's also the original ref "Regression Shrinkage and Selection via the Lasso" from Tibshirani...)

Hmm...
We already have min_samples_leaf to control too little samples and l2_regularization for some regularization. I' still prefer to take this out and to do it later properly.

What I'm missing in the implemented formula is that smoothing should be size dependent: the more samples we have the more should we trust the empirical averages. Something like:

prior_mean = 0
n = samples of category
penalty = 10
alpha = n / (n + penalty)
value = alpha * sum_gradients_bin / sum_hessians_bin + (1-alpha) * prior_mean

There would even be theory in how to choose an optimal penalty or an empirical estimation of prior_mean, cf. credibility theory or linear mixed models with random intercept.

Conclusion: As HGBT is still experimental, I'll also approve this PR without removal of MIN_CAT_SUPPORT. In this case, I plead for the responsibility of the implementors of this PR to investigate this in a future PR. 🙏

We already have min_samples_leaf to control too little samples and l2_regularization for some regularization

This is similar, but unrelated. min_sample_leaf controls tree tree size, l2_reg is used for the leaves values. The shrinkage here only affects the values by which we will sort the categories.

What I'm missing in the implemented formula is that smoothing should be size dependent: the more samples we have the more should we trust the empirical averages

This is what happens here I believe. The denominator is n_samples + CAT_SMOOTH. When n_samples is small, CAT_SMOOTH takes over and the final value is shrinked,. When it's high, CAT_SMOOTH has almost no effect.

For ref this is briefly discussed in microsoft/LightGBM#699 (comment) . They didn't published benchmarks, but this yielded the best performance according to the comments.