# Scalable Rule Lists Learning with Sampling

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 41 references that are in the map.
- First posted on arXiv 18 Jun 2024.

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

- [All Models are Wrong, but Many are Useful: Learning a Variable's Importance by Studying an Entire Class of Prediction Models Simultaneously](https://mlsanity.com/paper/1801.01489/) (2018)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [On the Existence of Simpler Machine Learning Models](https://mlsanity.com/paper/1908.01755/) (2019)
- [Exploring the Whole Rashomon Set of Sparse Decision Trees](https://mlsanity.com/paper/2209.08040/) (2022)
- [Scalable Bayesian Rule Lists](https://mlsanity.com/paper/1602.08610/) (2016)
- [Interpretable multiclass classification by MDL-based rule lists](https://mlsanity.com/paper/1905.00328/) (2019)
- [Efficient learning of large sets of locally optimal classification rules](https://mlsanity.com/paper/2301.09936/) (2023)
- [MCRapper: Monte-Carlo Rademacher Averages for Poset Families and Approximate Pattern Mining](https://mlsanity.com/paper/2006.09085/) (2020)
- [Efficient Centrality Maximization with Rademacher Averages](https://mlsanity.com/paper/2306.03651/) (2023)
- [Concise and interpretable multi-label rule sets](https://mlsanity.com/paper/2210.01533/) (2022)

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

- [Mixtures of Transparent Local Models](https://mlsanity.com/paper/2601.10541/) (2026)
- [Evidential Rule Learning for Interpretable Classification with Abstention](https://mlsanity.com/paper/2608.05859/) (2026)
- [Learning Auditable Classifier Models: Source-Disjoint Tree Ensembles](https://mlsanity.com/paper/2608.15725/) (2026)
- [Regional Explanations via Causal Sufficiency and Necessity](https://mlsanity.com/paper/2609.18049/) (2026)

## Abstract (arXiv)

Learning interpretable models has become a major focus of machine learning research, given the increasing prominence of machine learning in socially important decision-making. Among interpretable models, rule lists are among the best-known and easily interpretable ones. However, finding optimal rule lists is computationally challenging, and current approaches are impractical for large datasets. We present a novel and scalable approach to learn nearly optimal rule lists from large datasets. Our algorithm uses sampling to efficiently obtain an approximation of the optimal rule list with rigorous guarantees on the quality of the approximation. In particular, our algorithm guarantees to find a rule list with accuracy very close to the optimal rule list when a rule list with high accuracy exists. Our algorithm builds on the VC-dimension of rule lists, for which we prove novel upper and lower bounds. Our experimental evaluation on large datasets shows that our algorithm identifies nearly optimal rule lists with a speed-up up to two orders of magnitude over state-of-the-art exact approaches. Moreover, our algorithm is as fast as, and sometimes faster than, recent heuristic approaches, while reporting higher quality rule lists. In addition, the rules reported by our algorithm are more similar to the rules in the optimal rule list than the rules from heuristic approaches.