Timezone: »
Clustering is a fundamental unsupervised learning problem where a dataset is partitioned into clusters that consist of nearby points in a metric space. A recent variant, fair clustering, associates a color with each point representing its group membership and requires that each color has (approximately) equal representation in each cluster to satisfy group fairness. In this model, the cost of the clustering objective increases due to enforcing fairness in the algorithm. The relative increase in the cost, the ```````''price of fairness,'' can indeed be unbounded. Therefore, in this paper we propose to treat an upper bound on the clustering objective as a constraint on the clustering problem, and to maximize equality of representation subject to it. We consider two fairness objectives: the group utilitarian objective and the group egalitarian objective, as well as the group leximin objective which generalizes the group egalitarian objective. We derive fundamental lower bounds on the approximation of the utilitarian and egalitarian objectives and introduce algorithms with provable guarantees for them. For the leximin objective we introduce an effective heuristic algorithm. We further derive impossibility results for other natural fairness objectives. We conclude with experimental results on real-world datasets that demonstrate the validity of our algorithms.
Author Information
Seyed Esmaeili (University of Maryland, College Park)
Brian Brubach (Wellesley College)
Aravind Srinivasan (University of Maryland College Park)
Aravind Srinivasan is a Professor with the Department of Computer Science and UMIACS at UMD, College Park. He received his undergraduate degree from the Indian Institute of Technology, Madras, and his Ph.D. from Cornell University. He was a postdoctoral researcher at the Institute for Advanced Study in Princeton and at DIMACS. Srinivasan's research interests are in randomized algorithms, E-commerce, public health, networking, social networks, and combinatorial optimization, as well as in the growing confluence of algorithms, networks, and randomness, in fields including the social Web, machine learning, biology, and energy. He has published more than 115 papers in these areas, in fora including Nature, Journal of the ACM, IEEE/ACM Transactions on Networking, and the SIAM Journal on Computing. He is Editor-in-Chief of the ACM Transactions on Algorithms, Managing Editor for Theory of Computing, and Associate Editor of Networks. Srinivasan is a Fellow of four professional societies: ACM, AAAS, IEEE and EATCS. He received a Distinguished Alumnus Award from his alma mater IIT Madras. He also received the Distinguished Faculty Award from the Board of Visitors of the College of Computing, Mathematical, and Natural Sciences (University of Maryland) in 2016. He received a Data Science Research Award from Adobe, Inc. in 2017.
John Dickerson (University of Maryland)
More from the Same Authors
-
2021 : It's COMPASlicated: The Messy Relationship between RAI Datasets and Algorithmic Fairness Benchmarks »
Michelle Bao · Angela Zhou · Samantha Zottola · Brian Brubach · Sarah Desmarais · Aaron Horowitz · Kristian Lum · Suresh Venkatasubramanian -
2021 : Learning Revenue-Maximizing Auctions With Differentiable Matching »
Michael Curry · Uro Lyi · Tom Goldstein · John P Dickerson -
2021 : Learning Revenue-Maximizing Auctions With Differentiable Matching »
Michael Curry · Uro Lyi · Tom Goldstein · John P Dickerson -
2021 : An mHealth Intervention for African American and Hispanic Adults: Preliminary Results from a One-Year Field Test »
Christine Herlihy · John Dickerson -
2021 : An mHealth Intervention for African American and Hispanic Adults: Preliminary Results from a One-Year Field Test »
Christine Herlihy · John Dickerson -
2022 : A Deep Dive into Dataset Imbalance and Bias in Face Identification »
Valeriia Cherepanova · Steven Reich · Samuel Dooley · Hossein Souri · John Dickerson · Micah Goldblum · Tom Goldstein -
2022 : Tensions Between the Proxies of Human Values in AI »
Daniel Nissani · Teresa Datta · John Dickerson · Max Cembalest · Akash Khanna · Haley Massa -
2022 : Characterizing Anomalies with Explainable Classifiers »
Naveen Durvasula · Valentine d Hauteville · Keegan Hines · John Dickerson -
2022 : A Deep Dive into Dataset Imbalance and Bias in Face Identification »
Valeriia Cherepanova · Steven Reich · Samuel Dooley · Hossein Souri · John Dickerson · Micah Goldblum · Tom Goldstein -
2022 : On the Importance of Architectures and Hyperparameters for Fairness in Face Recognition »
Samuel Dooley · Rhea Sukthanker · John Dickerson · Colin White · Frank Hutter · Micah Goldblum -
2022 : On the Importance of Architectures and Hyperparameters for Fairness in Face Recognition »
Samuel Dooley · Rhea Sukthanker · John Dickerson · Colin White · Frank Hutter · Micah Goldblum -
2022 : A Deep Dive into Dataset Imbalance and Bias in Face Identification »
Valeriia Cherepanova · Steven Reich · Samuel Dooley · Hossein Souri · John Dickerson · Micah Goldblum · Tom Goldstein -
2023 Poster: Doubly Constrained Fair Clustering »
John Dickerson · Seyed Esmaeili · Jamie Morgenstern · Claire Jie Zhang -
2023 Poster: Fair, Polylog-Approximate Low-Cost Hierarchical Clustering »
Marina Knittel · Max Springer · John Dickerson · MohammadTaghi Hajiaghayi -
2023 Poster: Diffused Redundancy in Pre-trained Representations »
Vedant Nanda · Till Speicher · John Dickerson · Krishna Gummadi · Soheil Feizi · Adrian Weller -
2023 Poster: Reward Scale Robustness for Proximal Policy Optimization via DreamerV3 Tricks »
Ryan Sullivan · Akarsh Kumar · Shengyi Huang · John Dickerson · Joseph Suarez -
2023 Poster: Rethinking Bias Mitigation: Fairer Architectures Make for Fairer Face Recognition »
Samuel Dooley · Rhea Sukthanker · John Dickerson · Colin White · Frank Hutter · Micah Goldblum -
2022 Workshop: Graph Learning for Industrial Applications: Finance, Crime Detection, Medicine and Social Media »
Manuela Veloso · John Dickerson · Senthil Kumar · Eren K. · Jian Tang · Jie Chen · Peter Henstock · Susan Tibbs · Ani Calinescu · Naftali Cohen · C. Bayan Bruss · Armineh Nourbakhsh -
2022 Social: Open Mic Night »
John Dickerson -
2022 Poster: Robustness Disparities in Face Detection »
Samuel Dooley · George Z Wei · Tom Goldstein · John Dickerson -
2022 Poster: On the Generalizability and Predictability of Recommender Systems »
Duncan McElfresh · Sujay Khandagale · Jonathan Valverde · John Dickerson · Colin White -
2021 Poster: VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization »
Mucong Ding · Kezhi Kong · Jingling Li · Chen Zhu · John Dickerson · Furong Huang · Tom Goldstein -
2021 Poster: Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes »
Brian Brubach · Nathaniel Grammel · Will Ma · Aravind Srinivasan -
2021 Poster: PreferenceNet: Encoding Human Preferences in Auction Design with Deep Learning »
Neehar Peri · Michael Curry · Samuel Dooley · John Dickerson -
2021 Poster: How does a Neural Network's Architecture Impact its Robustness to Noisy Labels? »
Jingling Li · Mozhi Zhang · Keyulu Xu · John Dickerson · Jimmy Ba -
2020 Workshop: Workshop on Dataset Curation and Security »
Nathalie Baracaldo · Yonatan Bisk · Avrim Blum · Michael Curry · John Dickerson · Micah Goldblum · Tom Goldstein · Bo Li · Avi Schwarzschild -
2020 Poster: Detection as Regression: Certified Object Detection with Median Smoothing »
Ping-yeh Chiang · Michael Curry · Ahmed Abdelkader · Aounon Kumar · John Dickerson · Tom Goldstein -
2020 Poster: Certifying Strategyproof Auction Networks »
Michael Curry · Ping-yeh Chiang · Tom Goldstein · John Dickerson -
2020 Poster: Improving Policy-Constrained Kidney Exchange via Pre-Screening »
Duncan McElfresh · Michael Curry · Tuomas Sandholm · John Dickerson -
2020 Poster: Probabilistic Fair Clustering »
Seyed Esmaeili · Brian Brubach · Leonidas Tsepenekas · John Dickerson -
2019 Poster: Making the Cut: A Bandit-based Approach to Tiered Interviewing »
Candice Schumann · Zhi Lang · Jeffrey Foster · John Dickerson -
2019 Poster: Adversarial training for free! »
Ali Shafahi · Mahyar Najibi · Mohammad Amin Ghiasi · Zheng Xu · John Dickerson · Christoph Studer · Larry Davis · Gavin Taylor · Tom Goldstein -
2018 Poster: Approximation algorithms for stochastic clustering »
David Harris · Shi Li · Aravind Srinivasan · Khoa Trinh · Thomas Pensyl -
2015 : Uncertainty in Dynamic Matching »
John P Dickerson