Timezone: »
Spotlight
Fair Clustering Through Fairlets
Flavio Chierichetti · Ravi Kumar · Silvio Lattanzi · Sergei Vassilvitskii
Wed Dec 06 05:50 PM -- 05:55 PM (PST) @ Hall A
We study the question of fair clustering under the {\em disparate impact} doctrine, where each protected class must have approximately equal representation in every cluster. We formulate the fair clustering problem under both the $k$-center and the $k$-median objectives, and show that even with two protected classes the problem is challenging, as the optimum solution violates common conventions---for instance a point may no longer be assigned to its nearest cluster center! En route we introduce the concept of fairlets, which are minimal sets that satisfy fair representation while approximately preserving the clustering objective. We show that any fair clustering problem can be decomposed into first finding appropriate fairlets, and then using existing machinery for traditional clustering algorithms. While finding good fairlets can be NP-hard, we proceed to obtain efficient approximation algorithms based on minimum cost flow. We empirically demonstrate the \emph{price of fairness} by comparing the value of fair clustering on real-world datasets with sensitive attributes.
Author Information
Flavio Chierichetti (Sapienza University)
Ravi Kumar (Google)
Silvio Lattanzi (Google)
Sergei Vassilvitskii (Google)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Poster: Fair Clustering Through Fairlets »
Thu Dec 7th 02:30 -- 06:30 AM Room Pacific Ballroom #73
More from the Same Authors
-
2020 Poster: Sliding Window Algorithms for k-Clustering Problems »
Michele Borassi · Alessandro Epasto · Silvio Lattanzi · Sergei Vassilvitskii · Morteza Zadimoghaddam -
2020 Poster: Fair Hierarchical Clustering »
Sara Ahmadian · Alessandro Epasto · Marina Knittel · Ravi Kumar · Mohammad Mahdian · Benjamin Moseley · Philip Pham · Sergei Vassilvitskii · Yuyan Wang -
2020 Poster: Online Linear Optimization with Many Hints »
Aditya Bhaskara · Ashok Cutkosky · Ravi Kumar · Manish Purohit -
2020 Poster: Differentially Private Clustering: Tight Approximation Ratios »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2020 Oral: Differentially Private Clustering: Tight Approximation Ratios »
Badih Ghazi · Ravi Kumar · Pasin Manurangsi -
2019 Poster: Differentially Private Covariance Estimation »
Kareem Amin · Travis Dick · Alex Kulesza · Andres Munoz · Sergei Vassilvitskii -
2019 Poster: Efficient Rematerialization for Deep Networks »
Ravi Kumar · Manish Purohit · Zoya Svitkina · Erik Vee · Joshua Wang -
2018 Poster: Mallows Models for Top-k Lists »
Flavio Chierichetti · Anirban Dasgupta · Shahrzad Haddadan · Ravi Kumar · Silvio Lattanzi -
2018 Poster: Maximizing Induced Cardinality Under a Determinantal Point Process »
Jennifer Gillenwater · Alex Kulesza · Sergei Vassilvitskii · Zelda Mariet -
2018 Poster: Improving Online Algorithms via ML Predictions »
Manish Purohit · Zoya Svitkina · Ravi Kumar -
2017 Poster: Revenue Optimization with Approximate Bid Predictions »
Andres Munoz · Sergei Vassilvitskii -
2017 Poster: Statistical Cost Sharing »
Eric Balkanski · Umar Syed · Sergei Vassilvitskii -
2016 Poster: On Mixtures of Markov Chains »
Rishi Gupta · Ravi Kumar · Sergei Vassilvitskii -
2011 Oral: Reconstructing Patterns of Information Diffusion from Incomplete Observations »
Flavio Chierichetti · Jon Kleinberg · David Liben-Nowell -
2011 Poster: Reconstructing Patterns of Information Diffusion from Incomplete Observations »
Flavio Chierichetti · Jon Kleinberg · David Liben-Nowell