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.
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/ε) and, for regression, n≥poly(d): - k-median/k-means: For n points in Rd, we build an ε-coreset of input points of size O~(k4/3ε−2) (resp. O~(k3/2ε−2)) in time O~(ε−1n0.5dk1.67) (resp. O~(ε−1n0.5dk1.75)). Our better d- and linear 1/ε-dependence improve on [Xue, Chen, Li and Jiang, ICML'23] for d≥Ω(k7/3) (resp. Ω(k2.5)). - ℓp regression: For minx∥Ax−b∥p, A∈Rn×d, we build an ε-coreset of size O~p(dmax{1,p/2}ε−2) in time O~p(n0.5d1.5ε−1) for p≤2 and O~p(n0.5dp/4+1(ε−1+d0.5)) for p>2, matching [Liu and Ji, ICML'26] for p≤2 and improving on the prior best quantum sampling approach [Apers and Gribling, SICOMP'26] for all p>2. - Low-rank approximation: We give the first quantum sublinear-time algorithm for Frobenius-norm rank-k approximation of A∈Rd×n free of data-dependent parameters, running in O~(n0.5dk0.5ε−0.5) time with factored output (plus O~(nk2ε−2) to materialize them). We also give sublinear algorithms for kernel and tensor variants. - Lower bound: For generic sensitivity sampling with total sensitivity S, any quantum algorithm outputting an ε-coreset of size o(nS) needs Ω(nS) queries, so our query complexity is optimal up to poly(ε−1,logn) and VC-dimension factors.
Zhao Song, David P. Woodruff, Lichen Zhang
University of California, Berkeley. · Carnegie Mellon University. · Massachusetts Institute of Technology.
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.