License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FORC.2021.6
URN: urn:nbn:de:0030-drops-138748
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13874/
Diana, Emily ;
Gill, Wesley ;
Globus-Harris, Ira ;
Kearns, Michael ;
Roth, Aaron ;
Sharifi-Malvajerdi, Saeed
Lexicographically Fair Learning: Algorithms and Generalization
Abstract
We extend the notion of minimax fairness in supervised learning problems to its natural conclusion: lexicographic minimax fairness (or lexifairness for short). Informally, given a collection of demographic groups of interest, minimax fairness asks that the error of the group with the highest error be minimized. Lexifairness goes further and asks that amongst all minimax fair solutions, the error of the group with the second highest error should be minimized, and amongst all of those solutions, the error of the group with the third highest error should be minimized, and so on. Despite its naturalness, correctly defining lexifairness is considerably more subtle than minimax fairness, because of inherent sensitivity to approximation error. We give a notion of approximate lexifairness that avoids this issue, and then derive oracle-efficient algorithms for finding approximately lexifair solutions in a very general setting. When the underlying empirical risk minimization problem absent fairness constraints is convex (as it is, for example, with linear and logistic regression), our algorithms are provably efficient even in the worst case. Finally, we show generalization bounds - approximate lexifairness on the training sample implies approximate lexifairness on the true distribution with high probability. Our ability to prove generalization bounds depends on our choosing definitions that avoid the instability of naive definitions.
BibTeX - Entry
@InProceedings{diana_et_al:LIPIcs.FORC.2021.6,
author = {Diana, Emily and Gill, Wesley and Globus-Harris, Ira and Kearns, Michael and Roth, Aaron and Sharifi-Malvajerdi, Saeed},
title = {{Lexicographically Fair Learning: Algorithms and Generalization}},
booktitle = {2nd Symposium on Foundations of Responsible Computing (FORC 2021)},
pages = {6:1--6:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-187-0},
ISSN = {1868-8969},
year = {2021},
volume = {192},
editor = {Ligett, Katrina and Gupta, Swati},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13874},
URN = {urn:nbn:de:0030-drops-138748},
doi = {10.4230/LIPIcs.FORC.2021.6},
annote = {Keywords: Fair Learning, Lexicographic Fairness, Online Learning, Game Theory}
}
|
Keywords: |
|
Fair Learning, Lexicographic Fairness, Online Learning, Game Theory |
|
Collection: |
|
2nd Symposium on Foundations of Responsible Computing (FORC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
31.05.2021 |
