Convergence rate of stochastic k-means

2016-10-16 · Cheng Tang, Claire Monteleoni

We analyze online and mini-batch k-means variants. Both scale up the widely used Lloyd 's algorithm via stochastic approximation, and have become popular for large-scale clustering and unsupervised feature learning. We show, for the first time, that they have global convergence towards local optima at $O(\frac{1}{t})$ rate under general conditions. In addition, we show if the dataset is clusterable, with suitable initialization, mini-batch k-means converges to an optimal k-means solution with $O(\frac{1}{t})$ convergence rate with high probability. The k-means objective is non-convex and non-differentiable: we exploit ideas from non-convex gradient-based optimization by providing a novel characterization of the trajectory of k-means algorithm on its solution space, and circumvent its non-differentiability via geometric insights about k-means update.

📄 PDF Abstract BibTeX arXiv:1610.04900

Code (0)

등록된 구현이 없습니다.

Tasks

Clustering

Convergence of online $k$-means

2022-02-22 · Sanjoy Dasgupta, Gaurav Mahajan, Geelon So

We prove asymptotic convergence for a general class of $k$-means algorithms performed over streaming data from a distribution: the centers asymptotically converge to the set of stationary points of the $k$-means cost fun…

Weighted K-Harmonic Means Clustering: Convergence Analysis and Applications to Wireless Communications

2025-12-18 · Gourab Ghatak arxiv

We propose the \emph{weighted K-harmonic means} (WKHM) clustering algorithm, a regularized variant of K-harmonic means designed to ensure numerical stability while enabling soft assignments through inverse-distance weigh…

Robust Clustering on High-Dimensional Data with Stochastic Quantization

2024-09-03 · Anton Kozyriev, Vladimir Norkin

This paper addresses the limitations of conventional vector quantization algorithms, particularly K-Means and its variant K-Means++, and investigates the Stochastic Quantization (SQ) algorithm as a scalable alternative f…

Clustering Computational Efficiency image-classification Image Classification+2