# Better Short than Greedy: Interpretable Models through Optimal Rule Boosting

arXiv: https://arxiv.org/abs/2101.08380 · HTML: https://mlsanity.com/paper/2101.08380/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 23 references that are in the map.
- First posted on arXiv 21 Jan 2021.

## Builds on (most cited first, 5 of 5)

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [Learning Certifiably Optimal Rule Lists for Categorical Data](https://mlsanity.com/paper/1704.01701/) (2017)
- [Diverse Rule Sets](https://mlsanity.com/paper/2006.09890/) (2020)
- [Identifying Consistent Statements about Numerical Data with Dispersion-Corrected Subgroup Discovery](https://mlsanity.com/paper/1701.07696/) (2017)
- [Rectangular Bounding Process](https://mlsanity.com/paper/1903.03906/) (2019)

## Built on by (most cited first, 6 of 6)

- [Efficient learning of large sets of locally optimal classification rules](https://mlsanity.com/paper/2301.09936/) (2023)
- [Robust subgroup discovery](https://mlsanity.com/paper/2103.13686/) (2021)
- [Orthogonal Gradient Boosting for Simpler Additive Rule Ensembles](https://mlsanity.com/paper/2402.15691/) (2024)
- [Concise and interpretable multi-label rule sets](https://mlsanity.com/paper/2210.01533/) (2022)
- [Interpretable Representation Learning for Additive Rule Ensembles](https://mlsanity.com/paper/2506.20927/) (2025)
- [Sparse Oblique Rule Boosting for Simpler Additive Rule Ensembles](https://mlsanity.com/paper/2609.06426/) (2026)

## Abstract (arXiv)

Rule ensembles are designed to provide a useful trade-off between predictive accuracy and model interpretability. However, the myopic and random search components of current rule ensemble methods can compromise this goal: they often need more rules than necessary to reach a certain accuracy level or can even outright fail to accurately model a distribution that can actually be described well with a few rules. Here, we present a novel approach aiming to fit rule ensembles of maximal predictive power for a given ensemble size (and thus model comprehensibility). In particular, we present an efficient branch-and-bound algorithm that optimally solves the per-rule objective function of the popular second-order gradient boosting framework. Our main insight is that the boosting objective can be tightly bounded in linear time of the number of covered data points. Along with an additional novel pruning technique related to rule redundancy, this leads to a computationally feasible approach for boosting optimal rules that, as we demonstrate on a wide range of common benchmark problems, consistently outperforms the predictive performance of boosting greedy rules.