BalLOT: Balanced k-means clustering with optimal transport

2025/12/05 by Dustin G. Mixon, Luo, Wenyan, Mixon, Dustin G.
Business, Management and Accounting · Computer Science · #Advanced Clustering Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Facility Location and Emergency Management #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2512.05926

openalex publication_date 2025/12/05 · openalex created_date 2025/12/09 · openalex updated_date 2026/07/28

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 a variety of numerical experiments before proving several theoretical guarantees. First, we 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. Finally, we propose initialization schemes that achieve one-step recovery of planted clusters.

Citations

• 60 years of cyclic monotonicity: a survey
• K-median: exact recovery in the extended stochastic ball model
• A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics
• Hidden Integrality and Semi-random Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm
• Clustering Semi-Random Mixtures of Gaussians
• When Do Birds of a Feather Flock Together? k-Means, Proximity, and Conic Programming
• Balanced power diagrams for redistricting
• Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants
• Clustering subgaussian mixtures by semidefinite programming
• Probably certifiably correct k-means clustering
• Relax, no need to round: integrality of clustering formulations
• On semidefinite relaxations for the block model
• Recovery guarantees for exemplar-based clustering

Related

• Probably certifiably correct k-means clustering
• Clustering subgaussian mixtures by semidefinite programming
• Relax, no need to round: integrality of clustering formulations
• Fixed-sized clusters k-Means
• Further heuristics for k-means: The merge-and-split heuristic and the (k,l)-means