# Coresets for Decision Trees of Signals

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 59 references that are in the map.
- First posted on arXiv 7 Oct 2021.

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

- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [CatBoost: gradient boosting with categorical features support](https://mlsanity.com/paper/1810.11363/) (2018)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering](https://mlsanity.com/paper/1807.04518/) (2018)
- [Practical Coreset Constructions for Machine Learning](https://mlsanity.com/paper/1703.06476/) (2017)
- [On Coresets for Logistic Regression](https://mlsanity.com/paper/1805.08571/) (2018)
- [Coresets and Sketches](https://mlsanity.com/paper/1601.00617/) (2016)
- [Kaggle forecasting competitions: An overlooked learning opportunity](https://mlsanity.com/paper/2009.07701/) (2020)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Training Gaussian Mixture Models at Scale via Coresets](https://mlsanity.com/paper/1703.08110/) (2017)
- [Coresets for Near-Convex Functions](https://mlsanity.com/paper/2006.05482/) (2020)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Coreset-Based Neural Network Compression](https://mlsanity.com/paper/1807.09810/) (2018)
- [Sets Clustering](https://mlsanity.com/paper/2003.04135/) (2020)
- [Robust Coreset Construction for Distributed Machine Learning](https://mlsanity.com/paper/1904.05961/) (2019)
- [Faster PAC Learning and Smaller Coresets via Smoothed Analysis](https://mlsanity.com/paper/2006.05441/) (2020)

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

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Pruning Neural Networks via Coresets and Convex Geometry: Towards No Assumptions](https://mlsanity.com/paper/2209.08554/) (2022)
- [A Unified Approach to Coreset Learning](https://mlsanity.com/paper/2111.03044/) (2021)
- [QCore: Data-Efficient, On-Device Continual Calibration for Quantized Models -- Extended Version](https://mlsanity.com/paper/2404.13990/) (2024)
- [Coresets for Data Discretization and Sine Wave Fitting](https://mlsanity.com/paper/2203.03009/) (2022)
- [Obstacle Aware Sampling for Path Planning](https://mlsanity.com/paper/2203.04075/) (2022)
- [Representative Subset Selection for Efficient Fine-Tuning in Self-Supervised Speech Recognition](https://mlsanity.com/paper/2203.09829/) (2022)
- [Improving Model Classification by Optimizing the Training Dataset](https://mlsanity.com/paper/2507.16729/) (2025)
- [Linear time small coresets for k-mean clustering of segments with applications](https://mlsanity.com/paper/2511.12564/) (2025)
- [Deterministic Coreset for Lp Subspace](https://mlsanity.com/paper/2601.00361/) (2026)

## Abstract (arXiv)

A k-decision tree t (or k-tree) is a recursive partition of a matrix (2D-signal) into k≥ 1 block matrices (axis-parallel rectangles, leaves) where each rectangle is assigned a real label. Its regression or classification loss to a given matrix D of N entries (labels) is the sum of squared differences over every label in D and its assigned label by t. Given an error parameter varepsilon∈(0,1), a (k,varepsilon)-coreset C of D is a small summarization that provably approximates this loss to every such tree, up to a multiplicative factor of 1±varepsilon. In particular, the optimal k-tree of C is a (1+varepsilon)-approximation to the optimal k-tree of D. We provide the first algorithm that outputs such a (k,varepsilon)-coreset for every such matrix D. The size |C| of the coreset is polynomial in klog(N)/varepsilon, and its construction takes O(Nk) time. This is by forging a link between decision trees from machine learning -- to partition trees in computational geometry. Experimental results on textttsklearn and textttlightGBM show that applying our coresets on real-world data-sets boosts the computation time of random forests and their parameter tuning by up to x10, while keeping similar accuracy. Full open source code is provided.