Timezone: »

 
Scalable and Improved Algorithms for Individually Fair Clustering
Mohammadhossein Bateni · Vincent Cohen-Addad · Alessandro Epasto · Silvio Lattanzi

@
in Trustworthy and Socially Responsible Machine Learning »
Event URL: https://openreview.net/forum?id=gdPiOBu99Y »
We present scalable and improved algorithms for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al and Mahabadi et al.Given $n$ points $P$ in a metric space, let $\delta(x)$ for $x\in P$ be the radius of the smallest ball around $x$ containing at least $\nicefrac nk$ points. In this work, we present two main contributions.We first present local-search algorithms improving prior work along cost and maximum fairness violation.Then we design a fast local-search algorithmthat runs in $\tO(nk^2)$ time and obtains a bicriteria $(O(1), 6)$ approximation. Finally we show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
[ Slides]  [ Poster]  [ OpenReview]  [ Topia] 

Author Information

Mohammadhossein Bateni (Google research)
Vincent Cohen-Addad (Google research)
Alessandro Epasto (Google)
Alessandro Epasto

I am a staff research scientist at Google, New York working in the OMEGA team part of the Google Research and lead by Vahab Mirrokni. I received a Ph.D in computer science from Sapienza University of Rome, where I was advised by Professor Alessandro Panconesi and supported by the Google Europe Ph.D. Fellowship in Algorithms. I was also a post-doc at the department of computer science of Brown University in Providence (RI), USA where I was advised by Professor Eli Upfal. My research interests include algorithmic problems in machine learning and data mining, in particular in the areas of clustering, and privacy.

Silvio Lattanzi (Google Research)

More from the Same Authors