AISTATS 2022poster6 citations
Convergence of online k-means
Geelon So, Gaurav Mahajan, Sanjoy Dasgupta
Abstract
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 objective function. To do so, we show that online k-means over a distribution can be interpreted as stochastic gradient descent with a stochastic learning rate schedule. Then, we prove convergence by extending techniques used in optimization literature to handle settings where center-specific learning rates may depend on the past trajectory of the centers.
BibTeX
@InProceedings{pmlr-v151-so22a,
title = { Convergence of online k-means },
author = {So, Geelon and Mahajan, Gaurav and Dasgupta, Sanjoy},
booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics},
pages = {8534--8569},
year = {2022},
editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel},
volume = {151},
series = {Proceedings of Machine Learning Research},
month = {28--30 Mar},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v151/so22a/so22a.pdf},
url = {https://proceedings.mlr.press/v151/so22a.html},
abstract = { 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 objective function. To do so, we show that online k-means over a distribution can be interpreted as stochastic gradient descent with a stochastic learning rate schedule. Then, we prove convergence by extending techniques used in optimization literature to handle settings where center-specific learning rates may depend on the past trajectory of the centers. }
}