Journal
INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 151
Volume 151, Issue -, Pages 6387-6408Publisher
JMLR-JOURNAL MACHINE LEARNING RESEARCH
Keywords
-
Funding
- NSF CAREER [IIS-1846237]
- NSF D-ISN [2039862]
- NSF [CCF-1852352, CCF-1422569, CCF-1749864, CCF-1918749]
- NIH R01 [NLM-013039-01]
- NIST MSE [20126334]
- DARPA GARD [HR00112020007]
- DoD WHS [HQ003420F0035]
- Google Faculty Research award
- Amazon
- Direct For Social, Behav & Economic Scie
- SBE Off Of Multidisciplinary Activities [2039862] Funding Source: National Science Foundation
Ask authors/readers for more resources
This paper introduces a novel definition of individual fairness for clustering problems and answers questions regarding the combinatorial structure and Price of Fairness (PoF) behavior. Efficient and easily-implementable approximation algorithms are provided for the well-defined region of alpha, with bounded-PoF guarantees in certain cases. Extensive experiments validate the effectiveness of the theoretical results.
Clustering is a fundamental problem in unsupervised machine learning, and due to its numerous societal implications fair variants of it have recently received significant attention. In this work we introduce a novel definition of individual fairness for clustering problems. Specifically, in our model, each point j has a set of other points S-j that it perceives as similar to itself, and it feels that it is being fairly treated if the quality of service it receives in the solution is alpha-close (in a multiplicative sense, for some given alpha >= 1) to that of the points in S-j. We begin our study by answering questions regarding the combinatorial structure of the problem, namely for what values of a the problem is well-defined, and what the behavior of the Price of Fairness (PoF) for it is. For the well-defined region of alpha, we provide efficient and easily-implementable approximation algorithms for the k-center objective, which in certain cases also enjoy bounded-PoF guarantees. We finally complement our analysis by an extensive suite of experiments that validates the effectiveness of our theoretical results.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available