English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We answer the question: "Does local progress (on batches) imply globalprogress (on the entire dataset) for mini-batch $k$-means?". Specifically, weconsider mini-batch $k$-means which terminates only when the improvement in thequality of the clustering on the sampled batch is below some threshold.  Although at first glance it appears that this algorithm might executeforever, we answer the above question in the affirmative and show that if thebatch is of size $\tilde{\Omega}((d/\epsilon)^2)$, it must terminate within$O(d/\epsilon)$ iterations with high probability, where $d$ is the dimension ofthe input, and $\epsilon$ is a threshold parameter for termination. This istrue regardless of how the centers are initialized. When the algorithm isinitialized with the $k$-means++ initialization scheme, it achieves anapproximation ratio of $O(\log k)$ (the same as the full-batch version).  Finally, we show the applicability of our results to the mini-batch $k$-meansalgorithm implemented in the scikit-learn (sklearn) python library.

Mini-batch $k$-means terminates within $O(d/\epsilon)$ iterations