# Deterministic Coreset Construction via Adaptive Sensitivity Trimming

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 18 references that are in the map.
- First posted on arXiv 25 Aug 2025.

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

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Coresets for Clustering with Fairness Constraints](https://mlsanity.com/paper/1906.08484/) (2019)
- [New Frameworks for Offline and Streaming Coreset Constructions](https://mlsanity.com/paper/1612.00889/) (2016)
- [Fair Coresets and Streaming Algorithms for Fair k-Means Clustering](https://mlsanity.com/paper/1812.10854/) (2018)
- [Coresets for k-Means and k-Median Clustering and their Applications](https://mlsanity.com/paper/1810.12826/) (2018)

## Abstract (arXiv)

We develop a rigorous framework for deterministic coreset construction in empirical risk minimization (ERM). Our central contribution is the Adaptive Deterministic Uniform-Weight Trimming (ADUWT) algorithm, which constructs a coreset by excising points with the lowest sensitivity bounds and applying a data-dependent uniform weight to the remainder. The method yields a uniform (1±varepsilon) relative-error approximation for the ERM objective over the entire hypothesis space. We provide complete analysis, including (i) a minimax characterization proving the optimality of the adaptive weight, (ii) an instance-dependent size analysis in terms of a Sensitivity Heterogeneity Index, and (iii) tractable sensitivity oracles for kernel ridge regression, regularized logistic regression, and linear SVM. Reproducibility is supported by precise pseudocode for the algorithm, sensitivity oracles, and evaluation pipeline. Empirical results align with the theory. We conclude with open problems on instance-optimal oracles, deterministic streaming, and fairness-constrained ERM.