Categorical boosting (CatBoost) [1]} focuses on categorical features by using minimal variance sampling (MVS) which is a weighted sampling method at the tree-level. Unlike LightGBM, CatBoost grows balanced trees which makes this method less prone to overfitting, and uses combinations of categorical
features as additional categorical features to capture high-order dependencies. As it is infeasible to process all of the possible combinations, CatBoost solves the exponential growth of the features combination by constructing the combinations in a greedy way.
