EMS Coreset: An Efficient Expectation-Maximization Algorithm for Sinkhorn Coreset
2026-08-17 • Machine Learning
Machine Learning
AI summaryⓘ
The authors came up with a way to pick small representative parts of big datasets more quickly by improving a mathematical method called Optimal Transport. Their approach lets them update these small sets in a simpler way that works like a soft version of the popular k-means clustering. They proved their method is both accurate and reliable when the data changes a bit. Tests on different data showed it can be faster and just as good or better than older methods, especially with very large datasets.
CoresetsOptimal TransportSinkhorn algorithmEntropic regularizationk-means clusteringWasserstein distanceData summarizationAsymptotic consistencyLipschitz stabilityMachine learning scalability
Authors
Haoyun Yin, Chuanhui Liu, Xiao Wang
Abstract
Coresets distill large datasets into small, representative subsets for efficient downstream learning. Yet Optimal Transport (OT)-based selection typically requires intensive computation of transport plans, limiting scalability. We introduce a scalable Sinkhorn coreset method that permits closed-form updates of the entropically regularized OT coupling by allowing non-uniform coreset weights. This produces centroids that generalize k-means via soft assignments. We establish asymptotic consistency of the selected measure and Lipschitz stability to data perturbations, providing accuracy and robustness guarantees. Across synthetic and real-world benchmarks, the proposed method achieves competitive or improved approximation quality while substantially reducing runtime compared to Wasserstein- and standard Sinkhorn-based coreset selection, especially at large scale.