Overview

Coreset selection studies how to keep a small, useful subset of data while preserving the performance or statistical properties of the full dataset. Methods include geometric coverage and clustering, sensitivity and importance sampling, gradient or training-dynamics scores, and submodular, determinantal, or optimal-transport selection; newer approaches also use model representations and foundation-model embeddings. These methods support settings from image and medical annotation to language-model tuning, benchmark compression, graph learning, clustering, and memory-bounded anomaly detection. A central tension is that carefully selecting data can improve efficiency, but selection itself costs time and memory, and results depend on the learner and budget; random subsets or full-data training can still be competitive, so no method is best across settings.

Latest papers

62 papers3 papers in the last four weeks, down 67% on the four weeks before. 0.0% of all new papers.

Sep 20, 2025

Sublinear Time Quantum Sensitivity Sampling

We present a unified quantum sensitivity sampling framework that streamlines coreset construction for many classical approximation problems, significantly speeding up clustering, regression, and low-rank approximation. We assume n,d≥poly(k/ε)n,d\geq\mathrm{poly}(k/ε) and, for regression, n≥poly(d)n\geq\mathrm{poly}(d): - kk-median/kk-means: For nn points in Rd\mathbb{R}^d, we build an εε-coreset of input points of size O~(k4/3ε−2)\tilde O(k^{4/3}ε^{-2}) (resp. O~(k3/2ε−2)\tilde O(k^{3/2}ε^{-2})) in time O~(ε−1n0.5dk1.67)\tilde O(ε^{-1}n^{0.5}dk^{1.67}) (resp. O~(ε−1n0.5dk1.75)\tilde O(ε^{-1}n^{0.5}dk^{1.75})). Our better dd- and linear 1/ε1/ε-dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for d≥Ω(k7/3)d\geqΩ(k^{7/3}) (resp. Ω(k2.5)Ω(k^{2.5})). - ℓp\ell_p regression: For min⁡x∥Ax−b∥p\min_x\|Ax-b\|_p, A∈Rn×dA\in\mathbb{R}^{n\times d}, we build an εε-coreset of size O~p(dmax⁡{1,p/2}ε−2)\tilde O_p(d^{\max\{1,p/2\}}ε^{-2}) in time O~p(n0.5d1.5ε−1)\tilde O_p(n^{0.5}d^{1.5}ε^{-1}) for p≤2p\leq 2 and O~p(n0.5dp/4+1(ε−1+d0.5))\tilde O_p(n^{0.5}d^{p/4+1}(ε^{-1}+d^{0.5})) for p>2p>2, matching [Liu and Ji, ICML'26] for p≤2p\leq 2 and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all p>2p>2. - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank-kk approximation of A∈Rd×nA\in\mathbb{R}^{d\times n} free of data-dependent parameters, running in O~(n0.5dk0.5ε−0.5)\tilde O(n^{0.5}dk^{0.5}ε^{-0.5}) time with factored output (plus O~(nk2ε−2)\tilde O(nk^2ε^{-2}) to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity SS, any quantum algorithm outputting an εε-coreset of size o(nS)o(\sqrt{nS}) needs Ω(nS)Ω(\sqrt{nS}) queries, so our query complexity is optimal up to poly(ε−1,log⁡n)\mathrm{poly}(ε^{-1},\log n) and VC-dimension factors.
Jun 1, 2025

PCoreSet: Effective Active Learning through Knowledge Distillation from Vision-Language Models

Knowledge distillation (KD) is a widely used framework for training compact, task-specific models by transferring the knowledge from teacher models. However, its application to active learning (AL), which aims to minimize annotation costs through iterative sample selection, remains underexplored. This gap stems from the fact that KD typically assumes access to sufficient labeled data, whereas AL operates in data-scarce scenarios where task-specific teacher models are often unavailable. In this paper, we first introduce ActiveKD, a framework that integrates AL with KD by leveraging the zero- and few-shot capabilities of large vision-language models (VLMs). A key aspect of ActiveKD is the structured prediction bias of VLMs--i.e., their predictions form clusters in the probability space. We regard this structure as an inductive bias of the teacher model, capturing generalizable output patterns beneficial to student learning. To exploit this bias, we propose Probabilistic CoreSet (PCoreSet), a selection strategy that maximizes coverage in the probability space rather than the feature space. PCoreSet strategically selects probabilistically diverse unlabeled samples, facilitating more efficient transfer of teacher knowledge under limited annotation budgets. Extensive evaluations on 11 datasets show that ActiveKD consistently improves every selection method over the no-distillation baseline (e.g., +29.07% on ImageNet, averaged over methods). Under ActiveKD, several widely-used AL selectors underperform Random and none consistently beats it; in contrast, PCoreSet is the only selector that consistently outperforms Random across 5 students and 3 teachers, always achieving the best performance except for the first 2 AL rounds. Our code is available at https://github.com/erjui/PCoreSet.