Scalable Algorithms for Individual Preference Stable Clustering

Ron Mosenzon, Ali Vakilian
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:1108-1116, 2024.

Abstract

In this paper, we study the individual preference (IP) stability, which is an notion capturing individual fairness and stability in clustering. Within this setting, a clustering is $\alpha$-IP stable when each data point’s average distance to its cluster is no more than $\alpha$ times its average distance to any other cluster. In this paper, we study the natural local search algorithm for IP stable clustering. Our analysis confirms a $O(\log n)$-IP stability guarantee for this algorithm, where $n$ denotes the number of points in the input. Furthermore, by refining the local search approach, we show it runs in an almost linear time, $\tilde{O}(nk)$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-mosenzon24a, title = {Scalable Algorithms for Individual Preference Stable Clustering}, author = {Mosenzon, Ron and Vakilian, Ali}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {1108--1116}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/mosenzon24a/mosenzon24a.pdf}, url = {https://proceedings.mlr.press/v238/mosenzon24a.html}, abstract = {In this paper, we study the individual preference (IP) stability, which is an notion capturing individual fairness and stability in clustering. Within this setting, a clustering is $\alpha$-IP stable when each data point’s average distance to its cluster is no more than $\alpha$ times its average distance to any other cluster. In this paper, we study the natural local search algorithm for IP stable clustering. Our analysis confirms a $O(\log n)$-IP stability guarantee for this algorithm, where $n$ denotes the number of points in the input. Furthermore, by refining the local search approach, we show it runs in an almost linear time, $\tilde{O}(nk)$.} }
Endnote
%0 Conference Paper %T Scalable Algorithms for Individual Preference Stable Clustering %A Ron Mosenzon %A Ali Vakilian %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-mosenzon24a %I PMLR %P 1108--1116 %U https://proceedings.mlr.press/v238/mosenzon24a.html %V 238 %X In this paper, we study the individual preference (IP) stability, which is an notion capturing individual fairness and stability in clustering. Within this setting, a clustering is $\alpha$-IP stable when each data point’s average distance to its cluster is no more than $\alpha$ times its average distance to any other cluster. In this paper, we study the natural local search algorithm for IP stable clustering. Our analysis confirms a $O(\log n)$-IP stability guarantee for this algorithm, where $n$ denotes the number of points in the input. Furthermore, by refining the local search approach, we show it runs in an almost linear time, $\tilde{O}(nk)$.
APA
Mosenzon, R. & Vakilian, A.. (2024). Scalable Algorithms for Individual Preference Stable Clustering. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:1108-1116 Available from https://proceedings.mlr.press/v238/mosenzon24a.html.

Related Material