EMS Coreset: An Efficient Expectation-Maximization Algorithm for Sinkhorn Coreset

Haoyun Yin; Chuanhui Liu; Xiao Wang

stat.MLAug 17, 2026

EMS Coreset: An Efficient Expectation-Maximization Algorithm for Sinkhorn Coreset

Authors: Haoyun Yin, Chuanhui Liu, Xiao Wang

Organizations: Department of Statistics, Purdue University West Lafayette, IN 47906, USA

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.

Figures & tables

Figure 1: Comparison on 2D manifold datasets. All optimal-transport coresets capture the global geometry. EMS (Ours) spreads smoothly and preserves low-density tails, while gradient-based WCSL can be over-smoothed.

Panel of Figure 2 — Figure 2: Synthetic Gaussian mixture datasets where each component has unit variance with its mean located at distance R from the origin.

Dataset	Coreset size	Random	K-means	WCSL	EMS
				$\lambda=10^{-2}$	$\lambda=0$	$\lambda=10^{-3}$	$\lambda=10^{-2}$	$\lambda=10^{-1}$
		dist / time	dist / time	dist / time	dist / time	dist / time	dist / time	dist / time
Gaussian	$k=10$	18.28 / -	10.87 / 0.09	10.85 / 14.9	10.87 / 0.08	10.86 / 0.15	10.87 / 0.15	10.87 / 0.12
	$k=20$	16.05 / -	10.14 / 0.14	10.11 / 24.4	10.14 / 0.09	10.14 / 0.10	10.14 / 0.17	10.12 / 0.22
	$k=50$	14.31 / -	9.25 / 0.08	9.19 / 56.9	9.24 / 0.07	9.24 / 0.11	9.23 / 0.18	9.20 / 0.39
	$k=100$	12.92 / -	8.69 / 0.06	8.53 / 92.5	8.63 / 0.06	8.63 / 0.08	8.61 / 0.14	8.56 / 0.54

Table 1: Distributional accuracy and total runtime (distance / time). Lower distance is better; bold indicates the best distance for each

k

. Statistics averaged over five runs. dist / time stands for distance / time.

Panel of Figure 3 — Figure 3: Pairwise entropic Wasserstein distances across $10$ random initializations for Gaussian mixture dataset with $R=2$ (top) and $R=5$ (bottom).

Varying	Setup	WCSL	EMS
		$\lambda=10^{-2}$	$\lambda=0$	$\lambda=10^{-3}$	$\lambda=10^{-2}$	$\lambda=10^{-1}$
		distance / time	distance / time	distance / time	distance / time	distance / time
Data size $n$	$10^{4}$	$5.203/9.749$	$3.697/\mathbf{0.028}$	$3.709/0.031$	$3.691/0.052$	$\mathbf{3.670}/0.129$
	$10^{5}$	$\mathbf{3.634}/161.777$	$3.764/\mathbf{0.452}$	$3.765/0.524$	$3.756/0.723$	$3.755/0.971$
	$10^{6}$	$0.154/2{,}006.306$	$0.152/\mathbf{7.368}$	$0.152/9.051$	$0.151/7.957$	$\mathbf{0.151}/9.653$
Dimension $d$	$1$	$0.00791/2.450$	$\mathbf{0.00171}/0.020$	$0.00199/0.024$	$0.00244/0.024$	$0.00543/\mathbf{0.020}$

Table 2: Wasserstein distance and runtime in seconds. Lower is better. Means over 10 runs. Default setup is

n=10^{4},d=10,k=100

Census ( $n=6{,}513$ )
Method	MeanAE	MaxAE	BVE
EMS( $\lambda=0.01$ )	$\mathbf{5.07\times 10^{-3}}$	$5.40\times 10^{-2}$	$3.31\times 10^{-2}$
EMS( $\lambda=0$ )	$8.10\times 10^{-3}$	$8.87\times 10^{-2}$	$3.73\times 10^{-2}$
K-means	$5.76\times 10^{-3}$	$\mathbf{4.34\times 10^{-2}}$	$4.33\times 10^{-2}$
WCSL	$5.52\times 10^{-3}$	$4.92\times 10^{-2}$	$\mathbf{1.01\times 10^{-2}}$
Diabetes ( $n=89$ )

Table 3: Shapley reconstruction error on two test datasets (lower is better; best in bold). Results average over five runs.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Dataset	$k$	Random	K-means	WCSL	EMS
				$\lambda=10^{-2}$	$\lambda=0$	$\lambda=10^{-3}$	$\lambda=10^{-2}$	$\lambda=10^{-1}$
		distance / time	distance / time	distance / time	distance / time	distance / time	distance / time	distance / time
Transactions	20	74.47 / –	46.47 / 1.43	46.45 / 76.57	46.47 / 1.37	46.48 / 1.66	46.48 / 1.45	46.47 / 1.85
	50	68.85 / –	44.88 / 1.63	44.82 / 148.02	44.88 / 2.08	44.87 / 1.95	44.87 / 2.26	44.84 / 2.20
	100	65.65 / –	43.67 / 1.76	43.56 / 203.11	43.66 / 2.24	43.65 / 2.81	43.65 / 3.00	43.61 / 3.00
	200	63.13 / –	42.48 / 3.15	42.26 / 307.59	42.42 / 2.86	42.42 / 3.65	42.40 / 6.36	42.34 / 6.46

Appendix

Table 4: Performance comparison on real-world datasets. Each entry reports distance / runtime (seconds).

Coreset Selection

Coreset selection chooses compact subsets that preserve a dataset’s learning, evaluation, or optimization value while reducing cost.

See all 57 papers

SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport
Aug 28, 2026Ian Hsieh, Soumya Snigdha Kundu, Tom Vercauteren +1Optimal Transport Entropy Regularization
Sorbonne Université, Institut du Cerveau - Paris Brain Institute - ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, 75013 Paris, France · King’s College London, UK
Efficient Coreset Selection via K-Nearest Neighbor Graphs
Aug 17, 2026Yingfan Liu, Leiyu Zhang, Jiadong Xie +3Coreset Selection Training Data Selection
Xidian University Xi’an, China · Hangzhou Institute, Xidian University Hangzhou, China · The Chinese University of Hong Kong Hong Kong SAR, China +2
Low-Budget Active Learning through Entropic Optimal Transport
Oct 1, 2026Rim Hajal, Mathieu Besançon, Jérôme MalickActive Learning Coreset Selection
Univ. Grenoble Alpes, CNRS, Inria, LIG, LJK · Univ. Grenoble Alpes, Inria, CNRS, LIG · Univ. Grenoble Alpes, CNRS, LJK

Aug 28, 2026J/K move · Enter open · S save

SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport

Ian Hsieh, Soumya Snigdha Kundu, Tom Vercauteren, Reuben Dorent

Sorbonne Université, Institut du Cerveau - Paris Brain Institute - ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de la Pitié Salpêtrière, 75013 Paris, France · King’s College London, UK

Optimal Transport Entropy Regularization

Open paper AskPDF arXiv

Entropic optimal transport (EOT) has been shown to offer a computationally tractable approximation to exact optimal transport. However, the standard Sinkhorn-Knopp algorithm has two main limitations. First, given discrete measures with

N

points, each iteration requires

O(N^2)

operations, which restricts its use on large-scale datasets (e.g.

N\geq10^4

). Second, it uses the independent coupling as a reference measure for regularisation. This assigns mass to high-cost transport edges at moderate regularisation strengths. We propose SinkSLOT, which addresses both limitations by putting forth the expected sliced lifted transport plan as a natural way to sparsify the Gibbs kernel with a non-independent prior coupling. We prove that: 1) SinkSLOT converges; 2) with

L

slices, each resulting sparse Sinkhorn iteration costs

O(LN)

; and 3) the resulting objective is a divergence requiring no debiasing. Experiments on synthetic benchmarks show that SinkSLOT delivers substantial speedups over state-of-the-art dense and sparse EOT methods. We also demonstrate the applicability of the proposed divergence in a gradient flow experiment. The code is publicly available at https://github.com/cai4cai/SinkSLOT.

Abstract

Coreset Selection

Explore similar work

SinkSLOT: Sinkhorn via Sparse Lifted Optimal Transport

Efficient Coreset Selection via K-Nearest Neighbor Graphs

Low-Budget Active Learning through Entropic Optimal Transport