Timezone: »

 
Poster
Generalized Reductions: Making any Hierarchical Clustering Fair and Balanced with Low Cost
Marina Knittel · Max Springer · John P Dickerson · MohammadTaghi Hajiaghayi

Tue Jul 25 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #700
in Poster Session 2 »
Clustering is a fundamental building block of modern statistical analysis pipelines. Fair clustering has seen much attention from the machine learning community in recent years. We are some of the first to study fairness in the context of hierarchical clustering, after the results of Ahmadian et al. from NeurIPS in 2020. We evaluate our results using Dasgupta's cost function, perhaps one of the most prevalent theoretical metrics for hierarchical clustering evaluation. Our work vastly improves the previous $O(n^{5/6}poly\log(n))$ fair approximation for cost to a near polylogarithmic $O(n^\delta poly\log(n))$ fair approximation for any constant $\delta\in(0,1)$. This result establishes a cost fairness tradeoff and extends to broader fairness constraints than the previous work. We also show how to alter existing hierarchical clusterings to guarantee fairness and cluster balance across any level in the hierarchy.
[ PDF]  [ Poster] 

Author Information

Marina Knittel (Department of Computer Science, University of Maryland, College Park)
Max Springer (University of Maryland, College Park)

PhD student in Applied Mathematics

John P Dickerson (Arthur AI & Univ. of Maryland)
MohammadTaghi Hajiaghayi (University of Maryland, College Park)

More from the Same Authors