Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912644945936384 |
|---|---|
| author | Chen, Tyler Ray, Archan Seshadri, Akshay Herman, Dylan Bach, Bao Deshpande, Pranav Som, Abhishek Kumar, Niraj Pistoia, Marco |
| author_facet | Chen, Tyler Ray, Archan Seshadri, Akshay Herman, Dylan Bach, Bao Deshpande, Pranav Som, Abhishek Kumar, Niraj Pistoia, Marco |
| contents | The $k$-means algorithm (Lloyd's algorithm) is a widely used method for clustering unlabeled data. A key bottleneck of the $k$-means algorithm is that each iteration requires time linear in the number of data points, which can be expensive in big data applications. This was improved in recent works proposing quantum and quantum-inspired classical algorithms to approximate the $k$-means algorithm locally, in time depending only logarithmically on the number of data points (along with data dependent parameters) [q-means: A quantum algorithm for unsupervised machine learning, Kerenidis, Landman, Luongo, and Prakash, NeurIPS 2019; Do you know what $q$-means?, Cornelissen, Doriguello, Luongo, Tang, QTML 2025]. In this work, we describe a simple randomized mini-batch $k$-means algorithm and a quantum algorithm inspired by the classical algorithm. We demonstrate that the worst case guarantees of these algorithms can significantly improve upon the bounds for algorithms in prior work. Our improvements are due to a careful use of uniform sampling, which preserves certain symmetries of the $k$-means problem that are not preserved in previous algorithms that use data norm-based sampling. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_20982 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling Chen, Tyler Ray, Archan Seshadri, Akshay Herman, Dylan Bach, Bao Deshpande, Pranav Som, Abhishek Kumar, Niraj Pistoia, Marco Quantum Physics Data Structures and Algorithms Machine Learning The $k$-means algorithm (Lloyd's algorithm) is a widely used method for clustering unlabeled data. A key bottleneck of the $k$-means algorithm is that each iteration requires time linear in the number of data points, which can be expensive in big data applications. This was improved in recent works proposing quantum and quantum-inspired classical algorithms to approximate the $k$-means algorithm locally, in time depending only logarithmically on the number of data points (along with data dependent parameters) [q-means: A quantum algorithm for unsupervised machine learning, Kerenidis, Landman, Luongo, and Prakash, NeurIPS 2019; Do you know what $q$-means?, Cornelissen, Doriguello, Luongo, Tang, QTML 2025]. In this work, we describe a simple randomized mini-batch $k$-means algorithm and a quantum algorithm inspired by the classical algorithm. We demonstrate that the worst case guarantees of these algorithms can significantly improve upon the bounds for algorithms in prior work. Our improvements are due to a careful use of uniform sampling, which preserves certain symmetries of the $k$-means problem that are not preserved in previous algorithms that use data norm-based sampling. |
| title | Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling |
| topic | Quantum Physics Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2504.20982 |