aiqbench analysis
BalLOT introduces an optimal transport-based framework for balanced $k$-means clustering, offering theoretical guarantees on integral couplings and cluster recovery under the stochastic ball model. The method combines alternating minimization with landscape analysis to achieve fast convergence and one-step initialization for planted clusters. This work advances algorithmic optimization in machine learning by integrating information-theoretic constraints into standard clustering procedures.
BalLOT: Balanced $k$-means clustering with optimal transport
arXiv:2512.05926v2 Announce Type: replace-cross Abstract: We consider the fundamental problem of balanced $k$-means clustering. In particular, we introduce an optimal transport approach to alternating minimization called BalLOT, and we show that it delivers a fast and effective solution to this problem. We establish this with several theoretical guarantees and a variety of numerical experiments. On the theory front, we first prove that for generic data, BalLOT produces integral couplings at each step. Next, we perform a landscape analysis to provide theoretical guarantees for both exact and partial recoveries of planted clusters under the stochastic ball model. We also propose initialization schemes that achieve one-step recovery of planted clusters. To conclude, we present numerical experiments that corroborate our theoretical results.
Abstract:We consider the fundamental problem of balanced $k$-means clustering. In particular, we introduce an optimal transport approach to alternating minimization called BalLOT, and we show that it delivers a fast and effective solution to this problem. We establish this with several theoretical guarantees and a variety of numerical experiments. On the theory front, we first prove that for generic data, BalLOT produces integral couplings at each step. Next, we perform a landscape analysis to provide theoretical guarantees for both exact and partial recoveries of planted clusters under the stochastic ball model. We also propose initialization schemes that achieve one-step recovery of planted clusters. To conclude, we present numerical experiments that corroborate our theoretical results.
Machine Learning (stat.ML); Data Structures and Algorithms (cs.DS); Information Theory (cs.IT); Machine Learning (cs.LG); Optimization and Control (math.OC)
arXiv:2512.05926 [stat.ML]
(or arXiv:2512.05926v2 [stat.ML] for this version)
Full text under the publisher's open licence · 140 words
Related coverage
Scaling MoE reinforcement learning on Amazon EKS with EFA and DeepEP with 40% more throughput
AWS · Sep 25, 2026
Build a Physical AI model factory with NVIDIA Cosmos 3 on SageMaker HyperPod
AWS · Sep 4, 2026
AUP Learning Cloud: Streamlining AI Education on AMD
AMD · Aug 6, 2026
Digital States 2026: AI Moves From Experiment to Infrastructure
govtech.com · Sep 24, 2026