Detailed Instructions: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
Problem:<lb>We analyze online [6] and mini-batch [20] k-means variants. Both<lb>scale up the widely used Lloyd's algorithm via stochastic approximation,<lb>and have become popular for large-scale clustering and unsupervised<lb>feature learning. We show, for the first time, that they have global<lb>convergence towards "local optima" at rate<lb>O(1t ) under general condi-<lb>tions. In addition, we show if the dataset is clusterable, with suitable<lb>initialization, mini-batch k-means converges to an optimal k-means<lb>solution at rate<lb>O(1t ) with high probability. The k-means objective is<lb>non-convex and non-differentiable: we exploit ideas from non-convex<lb>gradient-based optimization by providing a novel characterization of the<lb>trajectory of k-means algorithm on its solution space, and circumvent<lb>its non-differentiability via geometric insights about k-means update.
Solution:
Convergence rate of stochastic k-means