Practical Coreset Constructions for Machine Learning
read the original abstract
We investigate coresets - succinct, small summaries of large data sets - so that solutions found on the summary are provably competitive with solution found on the full data set. We provide an overview over the state-of-the-art in coreset construction for machine learning. In Section 2, we present both the intuition behind and a theoretically sound framework to construct coresets for general problems and apply it to $k$-means clustering. In Section 3 we summarize existing coreset construction algorithms for a variety of machine learning problems such as maximum likelihood estimation of mixture models, Bayesian non-parametric models, principal component analysis, regression and general empirical risk minimization.
This paper has not been read by Pith yet.
Forward citations
Cited by 10 Pith papers
-
Dataset Distillation
Dataset distillation creates a tiny synthetic training set that, when used with a fixed network initialization, produces models whose performance approximates that of models trained on the full original dataset.
-
How Much Is a Dataset Worth? Scaling Laws, the Vendi Score, and Matrix Spectral Functions
Vendi Score and scaling-law objectives belong to the class of matrix spectral functions, which are submodular, enabling efficient greedy selection of training data that outperforms random subsets in predicting held-ou...
-
Check, Please: Verifiably Fair Clustering
Proves coNP-completeness of verifying mPJR in metric clustering, defines mPJR+ with polynomial-time find-and-check algorithms, and introduces DC-mPJR+ with O(mn log n + mnk) verification that approximates mPJR+.
-
Check, Please: Verifiably Fair Clustering
DC-mPJR+ is a new proportionality concept for clustering that can be verified in O(mn log n + mnk) time and ensures that any clustering satisfying it also satisfies an approximate version of the stronger mPJR fairness...
-
Stationary MMD Points
Stationary MMD points show super-convergence in integration error over MMD for RKHS integrands, and MMD gradient flows compute them with a new non-asymptotic finite-particle error bound.
-
Data-efficient flood depth prediction through domain-aware coreset selection and tabular foundation models
Domain-aware coreset construction lets tabular foundation models predict flood depths with 0.7% of per-watershed data at R²=0.663 (98.5% of full supervised), with cross-watershed transfer.
-
Efficient Test-Time Finetuning of LLMs via Convex Reconstruction and Gradient Caching
HullFT performs test-time finetuning by sparse convex reconstruction of query embeddings followed by gradient caching on repeated examples, yielding better quality-efficiency tradeoffs than prior TTFT methods.
-
COREKG: Coreset-Guided Personalized Summarization of Knowledge Graphs
COREKG uses sensitivity-based importance sampling from coreset theory to generate personalized KG summaries that achieve higher query accuracy and structural coverage than prior methods while using only a tiny fractio...
-
Policy Gradient with Kernel Quadrature
Episodic kernel quadrature compresses batches of episodes via GP-modeled returns to enable efficient policy gradient updates without evaluating rewards on every sample.
-
ASSS: A Differentiable Adversarial Framework for Task-Aware Data Reduction
ASSS uses an adversarial selector and Gumbel-Softmax relaxation to retain 98.9% task performance with only 30% of the data by preferentially keeping boundary samples.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.