CoChat
Sign Up
PreprintCited by 97Ethics and Social Impacts of AIPrivacy-Preserving Technologies in DataMachine Learning and Algorithms

Fairness Through Computationally-Bounded Awareness

Open access
Kim, Michael P., Reingold, Omer, Rothblum, Guy N.·2018·arXiv
DOI 10.48550/arxiv.1803.03239arXiv 1803.03239
Open this paper in CoChat — free accountOpen PDF

Abstract

We study the problem of fair classification within the versatile framework of Dwork et al. [ITCS '12], which assumes the existence of a metric that measures similarity between pairs of individuals. Unlike earlier work, we do not assume that the entire metric is known to the learning algorithm; instead, the learner can query this arbitrary metric a bounded number of times. We propose a new notion of fairness called metric multifairness and show how to achieve this notion in our setting. Metric multifairness is parameterized by a similarity metric $d$ on pairs of individuals to classify and a rich collection ${\cal C}$ of (possibly overlapping) "comparison sets" over pairs of individuals. At a high level, metric multifairness guarantees that similar subpopulations are treated similarly, as long as these subpopulations are identified within the class ${\cal C}$.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1803.03239

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • FTA requires a task-specific distance metric to measure similarity, and the difficulty or limitation is finding a proper similarity metric in a given context.

    “Importantly, a task-specific distance metric is required to measure the similarity between individuals considering human insight and domain information (Dwork et al. 2012), and similar individuals should receive a similar distribution over outcomes; hence, the difficulty or the limitation in applying this definition is finding a proper similarity metric in a given context (Kim, Reingold, and Rothb”

    From Antidiscrimination Insurance Pricing: Regulations, Fairness Criteria, and Models (2024) · cites this paper as Kim, Reingold, and Rothblum 2018

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 20

  1. [2][2] Andrej Bogdanov and Alon Rosen. Pseudorandom functions: Three decades later. In Tutorials on the Foundations of Cryptography , pages 79-158. Springer, 2017. -
  2. [3][3] Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Conference on Fairness, Accountability and Transparency , pages 77-91, 2018. -
  3. [5][5] Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq. Algorithmic decision making and the cost of fairness. KDD , 2017. -
  4. [6][6] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairness through awareness. In Innovations in Theoretical Computer Science (ITCS) , pages 214226, 2012. -
  5. [7][7] Vitaly Feldman. Distribution-specific agnostic boosting. In Proceedings of the First Symposium on Innovations in Computer Science'10 , 2010. -
  6. [8][8] Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, and Yi Wu. Agnostic learning of monomials by halfspaces is hard. SIAM Journal on Computing , 41(6):1558-1590, 2012. -
  7. [10][10] Stephen Gillen, Christopher Jung, Michael J. Kearns, and Aaron Roth. Online learning with an unknown fairness metric. arXiv preprint arXiv:1802.06936 , 2018. - · arXiv
  8. [11][11] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. In Foundations of Computer Science, 1984. 25th Annual Symposium on , pages 464-479. IEEE, 1984. -
  9. [12][12] Parikshit Gopalan, Adam Tauman Kalai, and Adam R Klivans. Agnostically learning decision trees. In Proceedings of the fortieth annual ACM symposium on Theory of computing , pages 527-536. ACM, 2008. -
  10. [13][13] Moritz Hardt, Eric Price, and Nathan Srebro. Equality of opportunity in supervised learning. In Advances in Neural Information Processing Systems , pages 3315-3323, 2016. -
  11. [14][14] Úrsula Hébert-Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Calibration for the (computationally-identifiable) masses. ICML , 2018. -
  12. [15][15] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM) , 45(6):983-1006, 1998. -
  13. [16][16] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. ICML , 2018. -
  14. [17][17] Michael J. Kearns, Robert E. Schapire, and Linda M. Sellie. Toward efficient agnostic learning. Machine Learning , 17(2-3):115-141, 1994. -
  15. [18][18] Michael P. Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box postprocessing for fairness in classification. arXiv preprint arXiv:1805.12317 , 2018. - · arXiv
  16. [20][20] Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical programming , 120(1):221-259, 2009. -
  17. [21][21] Geoff Pleiss, Manish Raghavan, Felix Wu, Jon Kleinberg, and Kilian Q. Weinberger. On fairness and calibration. NIPS , 2017. -
  18. [22][22] Guy N. Rothblum and Gal Yona. Probably approximately metric-fair learning. ICML , 2018. -
  19. [23][23] Leslie G. Valiant. A theory of the learnable. Communications of the ACM , 27(11):1134-1142, 1984. -
  20. [25][25] Blake Woodworth, Suriya Gunasekar, Mesrob I Ohannessian, and Nathan Srebro. Learning non-discriminatory predictors. COLT , 2017.

Cited by

Sorted by citations

Authors
Kim, M. P., Reingold, O., & Rothblum, G. N.
Affiliations
  • Stanford University (US)
  • Weizmann Institute of Science (IL)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2018
Volume
31
Pages
4842-4852
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1803.03239
arXiv
1803.03239
OpenAlex
W2963323630
Cited by
97
References
0
Citations by year
2025: 4 · 2024: 7 · 2023: 13 · 2022: 12 · 2021: 16 · 2020: 22 · 2019: 19 · 2018: 3 · 2017: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • neural information processing systems
Topics
  • Social Sciences › Safety Research › Ethics and Social Impacts of AI
  • Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
Keywords
algorithmic fairness, fair classification, similarity measures

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review