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

• URL: http://arxiv.org/abs/2608.16101v1
• Date: Mon, 17 Aug 2026 04:46:34 GMT
• Title: EMS Coreset: An Efficient Expectation-Maximization Algorithm for Sinkhorn Coreset
• Abstract summary: Coresets distill large datasets into small, representative subsets for efficient downstream learning.<n>We introduce a scalable Sinkhorn coreset method that permits closed-form updates of the entropically regularized OT coupling by allowing non-uniform coreset weights.<n>We establish consistency of the selected measure and Lipschitz stability to data perturbations, providing accuracy and robustness guarantees.
• Score: 4.297295761793895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization [50.59470683896735]
  min-max optimization has attracted increasing attention due to its applications in modern machine learning.<n>We provide a comprehensive theoretical of gradient descent (SGDA)<n>We develop new clipping-free algorithms, i.e., Stoc-GDAM and Stoc-TRmax, and they both can achieve the optimal dependence on the target accuracy without using gradient clipping.
  arXiv  Detail & Related papers  (2026-09-05T12:49:28Z)
• Scalable Lindblad Noise Learning via Stochastic Tensor-Network Simulation [48.887627688666974]
  Learning dissipation rates in large-scale open quantum systems is a major obstacle for near-term quantum technologies.<n>Here, we propose a scalable noise-learning framework for Lindblad dissipation rates that combines a simulation method, the Jump Method (TJM)<n>We demonstrate the approach on two noise models in the Ising model, in which independent dissipation rates are learned for each site up to $N_mathrmsite=16$.<n>This combination of scalable numerics and rigorous theoretical guarantees positions TJM-based noise learning as a practical foundation for characterizing dissipation in large quantum devices.
  arXiv  Detail & Related papers  (2026-08-25T15:07:11Z)
• From Atoms to Entropy: Optimal Noise Allocation for Diffusion Training in the Convex Regime [52.459513910242485]
  We develop a general statistical framework for studying optimal noise-level allocation in diffusion training.<n>We show that the optimized training schedule admits an atomic minimizer, concentrated on finitely many noise levels.<n>We then evaluate the entropic schedule in larger-scale experiments, where full schedule optimization is currently intractable.
  arXiv  Detail & Related papers  (2026-07-10T20:59:06Z)
• Towards The Implicit Bias on Multiclass Separable Data Under Norm Constraints [3.421126849736858]
  We introduce NucGD, a geometry-aware geometry designed to enforce low rank structures through nuclear norm constraints.<n>To enable scalable training, we derive an efficient SVD-free update rule via asynchronous power iteration.<n>We empirically dissect the impact of gradient optimization dynamics, characterizing how varying levels of gradient noise induced by mini-batch sampling and momentum modulate the convergence toward the expected maximum margin solutions.
  arXiv  Detail & Related papers  (2026-03-24T05:51:50Z)
• FAST: Topology-Aware Frequency-Domain Distribution Matching for Coreset Selection [19.148841575715746]
  Coreset selection compresses datasets into compact, representative subsets, reducing the energy and computational burden of training deep neural networks.<n>We propose FAST, the first DNN-free distribution-matching coreset selection framework.<n>FAST significantly outperforms state-of-the-art coreset selection methods across all evaluated benchmarks, achieving an average accuracy gain of 9.12%.
  arXiv  Detail & Related papers  (2025-11-22T09:24:57Z)
• Deterministic Coreset Construction via Adaptive Sensitivity Trimming [0.2864713389096699]
  We develop a framework for deterministic coreset construction in empirical risk minimization.<n>Our central contribution is the Adaptive Deterministic Uniform-Weight Trimming (ADUWT) algorithm.<n>We conclude with open problems on instance-optimal oracles, deterministic streaming, and fairness-constrained ERM.
  arXiv  Detail & Related papers  (2025-08-25T17:19:13Z)
• Coreset selection for the Sinkhorn divergence and generic smooth divergences [0.8594140167290099]
  CO2 is an efficient algorithm to produce convexly-weighted coresets with respect to generic smooth divergences.<n>We show a local equivalence between sufficiently regular losses and their second order approximations, reducing the coreset selection problem to maximum mean discrepancy minimization.<n>We apply CO2 to the Sinkhorn divergence, providing a novel sampling procedure that requires poly-logarithmically many data points to match the approximation guarantees of random sampling.
  arXiv  Detail & Related papers  (2025-04-28T18:54:53Z)
• SeWA: Selective Weight Average via Probabilistic Masking [51.015724517293236]
  We show that only a few points are needed to achieve better and faster convergence.<n>We transform the discrete selection problem into a continuous subset optimization framework.<n>We derive the SeWA's stability bounds, which are sharper than that under both convex image checkpoints.
  arXiv  Detail & Related papers  (2025-02-14T12:35:21Z)
• Tuning-Free Coreset Markov Chain Monte Carlo via Hot DoG [14.360996967498]
  We propose a learning-rate-free gradient optimization procedure, Hot-start Distance over Gradient (Hot DoG)<n>We provide a theoretical analysis of the convergence of the coreset weights produced by Hot DoG.<n>We also provide empirical results demonstrate that Hot DoG provides higher quality posterior approximations than other learning-rate-free gradient methods.
  arXiv  Detail & Related papers  (2024-10-24T17:59:23Z)
• Refined Coreset Selection: Towards Minimal Coreset Size under Model Performance Constraints [69.27190330994635]
  Coreset selection is powerful in reducing computational costs and accelerating data processing for deep learning algorithms. We propose an innovative method, which maintains optimization priority order over the model performance and coreset size. Empirically, extensive experiments confirm its superiority, often yielding better model performance with smaller coreset sizes.
  arXiv  Detail & Related papers  (2023-11-15T03:43:04Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
  arXiv  Detail & Related papers  (2021-11-01T15:43:36Z)
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization [85.84019017587477]
  Distributionally robust supervised learning is emerging as a key paradigm for building reliable machine learning systems for real-world applications. Existing algorithms for solving Wasserstein DRSL involve solving complex subproblems or fail to make use of gradients. We revisit Wasserstein DRSL through the lens of min-max optimization and derive scalable and efficiently implementable extra-gradient algorithms.
  arXiv  Detail & Related papers  (2021-04-27T16:56:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.