{"ID":2832658,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.05926","arxiv_id":"2512.05926","title":"BalLOT: Balanced $k$-means clustering with optimal transport","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.","short_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...","url_abs":"https://arxiv.org/abs/2512.05926","url_pdf":"https://arxiv.org/pdf/2512.05926v1","authors":"[\"Wenyan Luo\",\"Dustin G. Mixon\"]","published":"2025-12-05T18:04:35Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.DS\",\"cs.IT\",\"cs.LG\",\"math.OC\"]","methods":"[]","has_code":false}