Better Approximation Algorithms for Individually Fair Clustering
Dec 6, 2021
Speakers
Deeparnab Chakrabarty
Speaker · 0 followers
Maryam Negahbani
Speaker · 1 follower
About
We study data clustering problems with ℓ_p-norm objectives (e.g. k-Median and k-Means) in the context of individual fairness. The dataset consists of n points, and we want to find k centers such that (a) the objective is minimized, while (b) respecting the individual fairness constraint that every point v has a center within a distance at most r(v), where r(v) is v's distance to its (n/k)th nearest point. Jung, Kannan, and Lutz [FORC 2020] introduced this concept and designed a clustering algorithm with provable (approximate) fairness and objective guarantees for the ℓ_∞ or k-Center objective. Mahabadi and Vakilian [ICML 2020] revisited this problem to give a local-search algorithm for all ℓ_p-norms. Empirically, their algorithms outperform Jung et. al.'s by a large margin in terms of cost (for k-Median and k-Means), but they incur a reasonable loss in fairness. In this paper, our main contribution is to use Linear Programming (LP) techniques to obtain better algorithms for this problem, both in theory and in practice. We prove that by modifying known LP rounding techniques, one gets a worst-case guarantee on the objective which is much better than in MV20, and empirically, this objective is extremely close to the optimal. Furthermore, our theoretical fairness guarantees are comparable with MV20 in theory, and empirically, we obtain noticeably fairer solutions.Although solving the LP exactly might be prohibitive, we demonstrate that in practice, a simple sparsification technique drastically improves the run-time of our algorithm.We study data clustering problems with ℓ_p-norm objectives (e.g. k-Median and k-Means) in the context of individual fairness. The dataset consists of n points, and we want to find k centers such that (a) the objective is minimized, while (b) respecting the individual fairness constraint that every point v has a center within a distance at most r(v), where r(v) is v's distance to its (n/k)th nearest point. Jung, Kannan, and Lutz [FORC 2020] introduced this concept and designed a clustering algori…
Organizer
NeurIPS 2021
Account · 1.9k followers
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Best Paper Awards and Closing Remarks
Watch later
Total of 1 viewers voted for saving the presentation to eternal vault which is 0.1%
Workshop on Deep Learning and Inverse Problems
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Non-Euclidean Differentially Private Stochastic Convex Optimization
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
The role of study design, data science, and machine learning when estimating causal effects in non-experimental studies
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Backdoor Attack with Imperceptible Input and Latent Modification
Watch later
Khoa D. Doan, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Cross Modality 3D Navigation Using Reinforcement Learning and Neural Style Transfer
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%