Faster DecisionTreeRegressor (numba acceleration)

[kmedved]

Hi - I've been working on creating a faster version of DecisionTreeRegressor for use with ngboost, specifically through Numba acceleration. I've got an early version of this here.

The concept is that the relative slowness of sklearn's DecisionTreeRegressor as the base learner is one of the main reasons why ngboost is slower than other boosting libraries. From some early testing, the numba compiled version linked above is between 8x-20x faster when used as the base learner for ngboost (but I am still verifying robustness across data size). When ready, I'll put together a colab notebook for benchmarking purposes.

I'm interested in thoughts on whether this makes sense generally, and if so, whether it would make sense to add into ngboost directly, or whether it makes more sense as a standalone library. Curious about thoughts generally, but especially @alejandroschuler and @ryan-wolbeck on this point?

[alejandroschuler]

Would be a welcome improvement to ngboost but agree that the tree library should be it's own thing that we'd then import as the default learner.

There are many other things we could do better too in the context of tree learners, like pre-sort the data based on outcome to make the tree searches more efficient. All the tricks in lightgbm etc. But then we're getting very specific about the learner and optimizing the library around that. The current design goes the other way and makes the package agnostic and more maintainable at the cost of losing these efficiencies.

[alejandroschuler]

A fast tree-specific reimplementation of the whole package is probably a good idea but not something I'll ever get around to.