2016/11/16 by Cheng Tang, Tang, Cheng, Claire Monteleoni +1
Computer Science · Engineering · #Advanced Neural Network Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1611.05132
openalex publication_date 2016/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We analyze online \citeBottouBengio and mini-batch \citeSculley k-means variants. Both scale up the widely used k-means algorithm via stochastic approximation, and have become popular for large-scale clustering and unsupervised feature learning. We show, for the first time, that starting with any initial solution, they converge to a "local optimum" at rate O((1)/(t)) (in terms of the k-means objective) under general conditions. In addition, we show if the dataset is clusterable, when initialized with a simple and scalable seeding algorithm, mini-batch k-means converges to an optimal k-means solution at rate O((1)/(t)) with high probability. The k-means objective is non-convex and non-differentiable: we exploit ideas from recent work on stochastic gradient descent for non-convex problems \citege:sgdtensor, balsubramani13 by providing a novel characterization of the trajectory of k-means algorithm on its solution space, and circumvent the non-differentiability problem via geometric insights about k-means update.