Deterministic Coreset Construction via Adaptive Sensitivity Trimming

Faruk Alpay, Taylan Alpay · 2025

Read Deterministic Coreset Construction via Adaptive Sensitivity Trimming by Faruk Alpay, Taylan Alpay (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-18340.txt.

Introduction

Faruk Alpay and Taylan Alpay built a fixed, repeatable way to shrink a training data set to a small core without losing what it teaches, in a 2025 paper. Such cores, called coresets, speed up model fitting. Random cores are common, but a set rule that always picks the same core is easier to audit and reuse.

Their algorithm trims away the points with the lowest sensitivity scores, then gives the rest one shared weight tuned to the data. The result tracks the full-data training goal within a tight error band across all candidate models. The authors prove the shared weight is the best possible choice in a minimax sense. They give working score tools for three standard model types and full code sketches. Tests matched the theory, and open problems close the paper.

Catalog record

CREATORFaruk Alpay, Taylan Alpay
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE13 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-18340

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Deterministic Coreset Construction via Adaptive Sensitivity Trimming Faruk Alpay, Taylan Alpay Abstract 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 ± ε ) (1\pm\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 (Table 1 ) align with the theory. We conclude with open problems on instance-optimal oracles, deterministic streaming, and fairness-constrained ERM. 1 Introduction Empirical risk minimization (ERM) is the workhorse of modern machine learning, yet its computational demands scale with the data size n . Coresets —small weighted summaries that approximate the ERM objective for all hypotheses—offer a principled route to scalability [ 7 , 1 , 10 ] . Classical coreset methods are largely randomized , most notably via sensitivity/importance sampling [ 6 , 4 ] . While such methods enjoy high-probability guarantees, a non-zero failure probability is undesirable in safety-critical settings. This motivates deterministic constructions, akin in spirit to spectral sparsification guarantees [ 2 ] . We pursue a deterministic , sensitivity-driven approach grounded in robust statistics and influence functions [ 14 , 12 ] . Our ADUWT algorithm deterministically trims the least influential points and scales the remaining loss by a data-dependent uniform factor. We prove a uniform (1\pm\varepsilon) guarantee, introduce a minimax-optimal choice of the weight, and quantify when trimming beats sampling via a Sensitivity Heterogeneity Index (SHI) . We further provide tractable oracles for popular convex ERM models and a reproducible evaluation protocol. Contributions. (i) Deterministic framework. Formalization of ADUWT (Alg. 1 ) with a uniform (1\pm\varepsilon) guarantee (Thm. 3.2 ). (ii) Minimax optimality & instance-dependence. A new minimax characterization of the adaptive weight (Thm. 3.4 ) and an instance-dependent coreset size analysis via \mathrm{SHI} (Prop. 3.6 ). (iii) Tractable oracles. Provable sensitivity upper bounds for KRR, \ell_{2} -regularized logistic regression, and linear SVM (Props. 4.2 – 4.6 ). (iv) Reproducibility. End-to-end pseudocode for ADUWT, sensitivity oracles, and the experimental protocol; explicit hyperparameters and evaluation checks. (v) Research agenda. Open problems on instance-optimal oracles, deterministic streaming, and fairness-constrained ERM [ 9 , 8 , 5 , 13 ] . 2 Preliminaries: ERM and Coresets Definition 2.1 (Empirical Risk Minimization (ERM)) . Let \mathcal{D}=\{z_{1},\dots,z_{n}\} , hypothesis class \mathcal{F} , and loss \ell:\mathcal{F}\times\mathcal{Z}\to\mathbb{R}_{\geq 0} . The empirical risk of f\in\mathcal{F} is L(f;\mathcal{D})\coloneqq\sum_{i=1}^{n}\ell(f;z_{i}) . Definition 2.2 (Coreset) . A weighted subset (S,\bm{\alpha}) with S\subseteq[n] and \bm{\alpha}=\{\alpha_{i}\}_{i\in S} is a (1\pm\varepsilon) -coreset if (1-\varepsilon)L(f;\mathcal{D})\leq\sum_{i\in S}\alpha_{i}\ell(f;z_{i})\leq(1+\varepsilon)L(f;\mathcal{D})\quad\text{for all }f\in\mathcal{F}. Definition 2.3 (Sensitivity) . s_{i}\coloneqq\sup_{f\in\mathcal{F},\ L(f;\mathcal{D})>0}\frac{\ell(f;z_{i})}{L(f;\mathcal{D})} (zero if L(f;\mathcal{D})=0 ). Let S_{\rm tot}\coloneqq\sum_{i=1}^{n}s_{i} . 3 Adaptive Deterministic Trimming (ADUWT) Algorithm 1 Adaptive Deterministic Uniform-Weight Trimming (ADUWT) 1: Dataset \mathcal{D}=\{z_{i}\}_{i=1}^{n} , loss \ell , model class \mathcal{F} , tolerance \varepsilon\in(0,1) . Sensitivity oracle returning bounds \bar{s}_{i}\geq s_{i} . 2: Coreset (S,\bm{\alpha}) with \alpha uniform on S . 3: Compute sensitivity bounds: For each i , compute \bar{s}_{i} . 4: Trim low-sensitivity tail: Sort \bar{s}_{i} nondecreasing; set \varepsilon^{\prime}\coloneqq\tfrac{2\varepsilon}{1+\varepsilon} . Take the largest m with \sum_{j=1}^{m}\bar{s}_{\pi(j)}\leq\varepsilon^{\prime} . Let U=\{\pi(1),\ldots,\pi(m)\} and S=[n]\setminus U . 5: Adaptive uniform weight: Let T_{U}\coloneqq\sum_{i\in U}\bar{s}_{i} and set \alpha\coloneqq\sqrt{\frac{1-\varepsilon^{2}}{1-T_{U}}} . 6: return (S,\{\alpha\}_{i\in S}) . Lemma 3.1 (Collective loss bound) . For any U\subseteq[n] and f\in\mathcal{F} , \sum_{i\in U}\ell(f;z_{i})\leq\big(\sum_{i\in U}s_{i}\big)L(f;\mathcal{D}) . Theorem 3.2 (ADUWT guarantee) . For \varepsilon\in(0,1) , the output of Alg. 1 is a (1\pm\varepsilon) -coreset. Proof. Let U=[n]\setminus S , T_{U}=\sum_{i\in U}\bar{s}_{i}\leq\varepsilon^{\prime} . By Lemma 3.1 , with L=L(f;\mathcal{D}) and L_{S}=\sum_{i\in S}\ell(f;z_{i}) , (1-T_{U})L\leq L_{S}\leq L. (1) With \alpha=\sqrt{(1-\varepsilon^{2})/(1-T_{U})} , the coreset loss \hat{L}=\alpha L_{S} satisfies \hat{L}\leq\alpha L\leq\sqrt{\frac{1-\varepsilon^{2}}{1-\varepsilon^{\prime}}}\,L=(1+\varepsilon)L,\quad\hat{L}\geq\alpha(1-T_{U})L\geq\sqrt{1-\varepsilon^{2}}\sqrt{1-\varepsilon^{\prime}}\,L=(1-\varepsilon)L, where \varepsilon^{\prime}=\frac{2\varepsilon}{1+\varepsilon} gives 1-\varepsilon^{\prime}=\frac{1-\varepsilon}{1+\varepsilon} . ∎ Remark 3.3 (Coreset size) . Let m be the largest index with \sum_{j=1}^{m}\bar{s}_{\pi(j)}\leq\varepsilon^{\prime} . Then |S|=n-m . The size adapts to the empirical tail of the sensitivity distribution. 3.1 Minimax optimality of the adaptive weight Theorem 3.4 (Minimax weight) . Given bounds ( 1 ) with T_{U}\in[0,\varepsilon^{\prime}] known, the choice \displaystyle\alpha^{\star}=\sqrt{\frac{1-\varepsilon^{2}}{1-T_{U}}} uniquely minimizes \sup_{x\in[1-T_{U},\,1]}\big|\alpha x-1\big| and equals the geometric mean of the feasible endpoints \frac{1-\varepsilon}{1-T_{U}} and 1+\varepsilon . Proof. Let g(\alpha)=\max\{1-\alpha(1-T_{U}),\,\alpha-1\} . The minimax solution satisfies equality of the two terms: 1-\alpha(1-T_{U})=\alpha-1 , giving \alpha=\tfrac{1}{2-T_{U}}(2-T_{U})=\sqrt{\tfrac{1-\varepsilon^{2}}{1-T_{U}}} after enforcing the outer (1\pm\varepsilon) feasibility; equivalently, pick \alpha as the geometric mean of endpoints to equalize multiplicative slack. Uniqueness follows from convexity of g . ∎ 3.2 When trimming beats sampling: a refined view Definition 3.5 (Sensitivity Heterogeneity Index) . For sensitivity bounds \{\bar{s}_{i}\} with mean \mu and standard deviation \sigma , define \mathrm{SHI}\coloneqq\sigma/\mu . Proposition 3.6 (Instance-dependent comparison) . Let \bar{S}=\sum_{i}\bar{s}_{i} . Sensitivity sampling requires k=\Theta(\bar{S}/\varepsilon^{2}) samples for a (1\pm\varepsilon) coreset [ 6 , 4 ] . ADUWT returns |S|=n-m with m the largest prefix whose \sum\bar{s}_{\pi(j)}\leq\varepsilon^{\prime} . If the empirical CDF F(t)=\frac{1}{n}|\{i:\bar{s}_{i}\leq t\}| satisfies F(t_{0})\geq\rho for a small t_{0} and large \rho , then m\geq\rho n provided \rho t_{0}n\leq\varepsilon^{\prime} , yielding |S|\leq(1-\rho)n . High \mathrm{SHI} implies such mass near 0 , thus favoring trimming over sampling in practice. 4 Tractable Sensitivity Oracles 4.1 Kernel Ridge Regression (KRR) Definition 4.1 (KRR setting) . Let f_{w}(x)=\left\langle w,\phi(x)\right\rangle_{\mathcal{H}} , \ell(w;z_{i})=(y_{i}-f_{w}(x_{i}))^{2}+\frac{\lambda}{n}\left\lVert w\right\rVert_{\mathcal{H}}^{2} , \left\lVert w\right\rVert_{\mathcal{H}}\leq B , |y_{i}|\leq Y , k(x_{i},x_{i})\leq\kappa^{2} . Proposition 4.2 (KRR sensitivity bound) . Under Def. 4.1 , for any \delta\in(0,B] , \bar{s}_{i}\;=\;\max\!\left\{\frac{y_{i}^{2}}{\sum_{j}y_{j}^{2}},\;\frac{2(Y^{2}+B^{2}\kappa^{2})+(\lambda/n)B^{2}}{\lambda\delta^{2}}\right\}. Pseudocode: KRR oracle. Algorithm 2 KRR-Sensitivity-Oracle (\{(x_{i},y_{i})\},\lambda,B,\kappa,Y,\delta) 1: for i=1 to n do 2: a_{i}\leftarrow\begin{cases}\frac{y_{i}^{2}}{\sum_{j}y_{j}^{2}},&\sum_{j}y_{j}^{2}>0\\ 0,&\text{else}\end{cases} 3: b\leftarrow\frac{2(Y^{2}+B^{2}\kappa^{2})+(\lambda/n)B^{2}}{\lambda\delta^{2}} 4: \bar{s}_{i}\leftarrow\max\{a_{i},b\} 5: end for 6: return \{\bar{s}_{i}\}_{i=1}^{n} 4.2 Regularized Logistic Regression Definition 4.3 (Logistic setting) . \ell(w;z_{i})=-\big[y_{i}\log\hat{y}_{i}+(1-y_{i})\log(1-\hat{y}_{i})\big]+(\lambda/n)\left\lVert w\right\rVert_{2}^{2} , with \hat{y}_{i}=\sigma(w^{\top}x_{i}) , \left\lVert x_{i}\right\rVert\leq R , \left\lVert w\right\rVert\leq B . Proposition 4.4 (Logistic sensitivity bound) . Under Def. 4.3 , for any \delta\in(0,B] , \bar{s}_{i}\;=\;\frac{\log(1+e^{BR})+(\lambda/n)B^{2}}{\lambda\delta^{2}}. Pseudocode: Logistic oracle. Algorithm 3 LOGISTIC-Sensitivity-Oracle (\{x_{i}\},\lambda,B,R,\delta) 1: N_{\max}\leftarrow\log(1+e^{BR})+(\lambda/n)B^{2} 2: for i=1 to n do 3: \bar{s}_{i}\leftarrow N_{\max}/(\lambda\delta^{2}) 4: end for 5: return \{\bar{s}_{i}\} 4.3 Linear SVM Definition 4.5 (Linear SVM) . \ell(w;z_{i})=\max(0,1-y_{i}w^{\top}x_{i})+(\lambda/n)\left\lVert w\right\rVert_{2}^{2} , with \left\lVert x_{i}\right\rVert\leq R , \left\lVert w\right\rVert\leq B . Proposition 4.6 (SVM sensitivity bound) . Under Def. 4.5 , for any \delta\in(0,B] , \bar{s}_{i}\;=\;\frac{1+BR+(\lambda/n)B^{2}}{\lambda\delta^{2}}. Pseudocode: SVM oracle. Algorithm 4 SVM-Sensitivity-Oracle (\{(x_{i},y_{i})\},\lambda,B,R,\delta) 1: N_{\max}\leftarrow 1+BR+(\lambda/n)B^{2} 2: for i=1 to n do 3: \bar{s}_{i}\leftarrow N_{\max}/(\lambda\delta^{2}) 4: end for 5: return \{\bar{s}_{i}\} 5 Reproducibility: End-to-end pipeline Evaluation protocol (pseudocode). Algorithm 5 ADUWT Evaluation Protocol 1: Dataset \mathcal{D} , model family \mathcal{F} , loss \ell , target \varepsilon , train/val/test split seeds \{\texttt{seed}_{r}\}_{r=1}^{R} . 2: for r=1 to R do 3: Split: Stratified split with seed r ; standardize features using train stats only. 4: Oracle: Compute \{\bar{s}_{i}\} on train set via appropriate oracle (Sec. 4 ); record (\lambda,B,R,\delta) . 5: ADUWT: Run Alg. 1 to obtain (S,\alpha) ; record T_{U},|S| . 6: Optimization: Train on full train vs. coreset; if needed, tune hyperparameters via the same validation grid and early stopping schedule. 7: Metrics: Report train/val/test losses and relative error \max_{f}\frac{|\hat{L}(f)-L(f)|}{L(f)} over a held-out hypothesis sweep; calibrate with

Read the complete text