# A Theory of Interpretable Approximations

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 33 references that are in the map.
- First posted on arXiv 15 Jun 2024.

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

- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [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)
- [Interpreting CNNs via Decision Trees](https://mlsanity.com/paper/1802.00121/) (2018)
- [Explaining the Explainer: A First Theoretical Analysis of LIME](https://mlsanity.com/paper/2001.03447/) (2020)
- [Explainable k-Means and k-Medians Clustering](https://mlsanity.com/paper/2002.12538/) (2020)
- [A Theory of Universal Learning](https://mlsanity.com/paper/2011.04483/) (2020)
- [Sample compression schemes for VC classes](https://mlsanity.com/paper/1503.06960/) (2015)
- [Interpretability via Model Extraction](https://mlsanity.com/paper/1706.09773/) (2017)
- [Born-Again Tree Ensembles](https://mlsanity.com/paper/2003.11132/) (2020)
- [Universal Bayes consistency in metric spaces](https://mlsanity.com/paper/1906.09855/) (2019)
- [Provably efficient, succinct, and precise explanations](https://mlsanity.com/paper/2111.01576/) (2021)
- [Enforcing Interpretability and its Statistical Impacts: Trade-offs between Accuracy and Interpretability](https://mlsanity.com/paper/2010.13764/) (2020)
- [Connecting Interpretability and Robustness in Decision Trees through Separation](https://mlsanity.com/paper/2102.07048/) (2021)
- [A Learning Theoretic Perspective on Local Explainability](https://mlsanity.com/paper/2011.01205/) (2020)
- [Fine-Grained Distribution-Dependent Learning Curves](https://mlsanity.com/paper/2208.14615/) (2022)

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

- [Informative Post-Hoc Explanations Only Exist for Simple Functions](https://mlsanity.com/paper/2508.11441/) (2025)
- [Hessian-Enhanced Token Attribution (HETA): Interpreting Autoregressive LLMs](https://mlsanity.com/paper/2604.13258/) (2026)
- [How to safely discard features based on aggregate SHAP values](https://mlsanity.com/paper/2503.23111/) (2025)
- [A Classification View on Meta Learning Bandits](https://mlsanity.com/paper/2504.04505/) (2025)
- [Feature Attribution from First Principles](https://mlsanity.com/paper/2505.24729/) (2025)
- [Controlled Model Debiasing through Minimal and Interpretable Updates](https://mlsanity.com/paper/2502.21284/) (2025)
- [Fundamental Limitation in Explaining AI](https://mlsanity.com/paper/2605.24727/) (2026)

## Abstract (arXiv)

Can a deep neural network be approximated by a small decision tree based on simple features? This question and its variants are behind the growing demand for machine learning models that are *interpretable* by humans. In this work we study such questions by introducing *interpretable approximations*, a notion that captures the idea of approximating a target concept c by a small aggregation of concepts from some base class H. In particular, we consider the approximation of a binary concept c by decision trees based on a simple class H (e.g., of bounded VC dimension), and use the tree depth as a measure of complexity. Our primary contribution is the following remarkable trichotomy. For any given pair of H and c, exactly one of these cases holds: (i) c cannot be approximated by H with arbitrary accuracy; (ii) c can be approximated by H with arbitrary accuracy, but there exists no universal rate that bounds the complexity of the approximations as a function of the accuracy; or (iii) there exists a constant kappa that depends only on H and c such that, for *any* data distribution and *any* desired accuracy level, c can be approximated by H with a complexity not exceeding kappa. This taxonomy stands in stark contrast to the landscape of supervised classification, which offers a complex array of distribution-free and universally learnable scenarios. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-free) complexity. We extend our trichotomy to classes H of unbounded VC dimension and give characterizations of interpretability based on the algebra generated by H.