Document Open Access Logo

Lexicographically Fair Learning: Algorithms and Generalization

Authors Emily Diana, Wesley Gill, Ira Globus-Harris, Michael Kearns, Aaron Roth, Saeed Sharifi-Malvajerdi

PDF
Thumbnail PDF

File

LIPIcs.FORC.2021.6.pdf
  • Filesize: 0.78 MB
  • 23 pages

Document Identifiers

Author Details

Emily Diana
  • University of Pennsylvania, Philadelphia, PA, USA
Wesley Gill
  • University of Pennsylvania, Philadelphia, PA, USA
Ira Globus-Harris
  • University of Pennsylvania, Philadelphia, PA, USA
Michael Kearns
  • University of Pennsylvania, Philadelphia, PA, USA
Aaron Roth
  • University of Pennsylvania, Philadelphia, PA, USA
Saeed Sharifi-Malvajerdi
  • University of Pennsylvania, Philadelphia, PA, USA

Funding

Supported in part by the Warren Center for Network and Data Sciences, NSF grant CCF-1763307 and the Simons Collaboration on the Theory of Algorithmic Fairness.

Cite AsGet BibTex

Emily Diana, Wesley Gill, Ira Globus-Harris, Michael Kearns, Aaron Roth, and Saeed Sharifi-Malvajerdi. Lexicographically Fair Learning: Algorithms and Generalization. In 2nd Symposium on Foundations of Responsible Computing (FORC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 192, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FORC.2021.6

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.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Machine learning
Keywords
  • Fair Learning
  • Lexicographic Fairness
  • Online Learning
  • Game Theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach. A reductions approach to fair classification. In Proceedings of the 35th International Conference on Machine Learning, 2018. Google Scholar
  2. M. Allalouf and Y. Shavitt. Centralized and distributed algorithms for routing and weighted max-min fair bandwidth allocation. IEEE/ACM Transactions on Networking, 16(5):1015-1024, 2008. URL: https://doi.org/10.1109/TNET.2007.905605.
  3. Arash Asadpour and Amin Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. SIAM Journal on Computing, 39(7):2970-2989, 2010. Google Scholar
  4. Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth. Fairness in criminal justice risk assessments: The state of the art. Sociological Methods & Research, page 0049124118782533, 2018. Google Scholar
  5. Robert S. Chen, Brendan Lucier, Yaron Singer, and Vasilis Syrgkanis. Robust optimization for non-convex objectives. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30, pages 4705-4714. Curran Associates, Inc., 2017. URL: https://proceedings.neurips.cc/paper/2017/file/10c66082c124f8afe3df4886f5e516e0-Paper.pdf.
  6. Andrew Cotter, Heinrich Jiang, and Karthik Sridharan. Two-player games for efficient non-convex constrained optimization. In Aurélien Garivier and Satyen Kale, editors, Proceedings of the 30th International Conference on Algorithmic Learning Theory, volume 98 of Proceedings of Machine Learning Research, pages 300-332, Chicago, Illinois, 22-24 March 2019. PMLR. URL: http://proceedings.mlr.press/v98/cotter19a.html.
  7. Emilie Danna, Avinatan Hassidim, Haim Kaplan, Alok Kumar, Yishay Mansour, Danny Raz, and Michal Segalov. Upward max-min fairness. J. ACM, 64(1), 2017. URL: https://doi.org/10.1145/3011282.
  8. Emily Diana, Wesley Gill, Ira Globus-Harris, Michael Kearns, Aaron Roth, and Saeed Sharifi-Malvajerdi. Lexicographically fair learning: Algorithms and generalization. arXiv preprint, 2021. URL: http://arxiv.org/abs/2102.08454.
  9. Emily Diana, Wesley Gill, Michael Kearns, Krishnaram Kenthapadi, and Aaron Roth. Convergent algorithms for (relaxed) minimax fairness. arXiv preprint, 2020. URL: http://arxiv.org/abs/2011.03108.
  10. Dongliang Xie, Xin Wang, and Linhui Ma. Lexicographical order max-min fair source quota allocation in mobile delay-tolerant networks. In 2016 IEEE/ACM 24th International Symposium on Quality of Service (IWQoS), pages 1-6, 2016. URL: https://doi.org/10.1109/IWQoS.2016.7590424.
  11. Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, and Max Leiserson. Decoupled classifiers for group-fair and efficient machine learning. In Conference on Fairness, Accountability and Transparency, pages 119-133, 2018. Google Scholar
  12. Yoav Freund and Robert E. Schapire. Game theory, on-line prediction and boosting. In Proceedings of the Ninth Annual Conference on Computational Learning Theory, COLT '96, page 325–332, New York, NY, USA, 1996. Association for Computing Machinery. URL: https://doi.org/10.1145/238061.238163.
  13. Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M Pai, and Aaron Roth. Online multivalid learning: Means, moments, and prediction intervals. arXiv preprint, 2021. URL: http://arxiv.org/abs/2101.01739.
  14. Ellen L. Hahne. Round-robin scheduling for max-min fairness in data networks. IEEE Journal on Selected Areas in communications, 9(7):1024-1039, 1991. Google Scholar
  15. Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the (computationally-identifiable) masses. In International Conference on Machine Learning, pages 1939-1948. PMLR, 2018. Google Scholar
  16. C. Jung, S. Neel, A. Roth, L. Stapleton, and S. Wu. An algorithmic framework for fairness elicitation. Preprint, 2020. Google Scholar
  17. Christopher Jung, Changhwa Lee, Mallesh M Pai, Aaron Roth, and Rakesh Vohra. Moment multicalibration for uncertainty estimation. arXiv preprint, 2020. URL: http://arxiv.org/abs/2008.08037.
  18. Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-307, 2005. Learning Theory 2003. URL: https://doi.org/10.1016/j.jcss.2004.10.016.
  19. Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In International Conference on Machine Learning, pages 2564-2572. PMLR, 2018. Google Scholar
  20. Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. An empirical study of rich subgroup fairness for machine learning. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pages 100-109, 2019. Google Scholar
  21. Michael P Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, pages 247-254, 2019. Google Scholar
  22. Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed H. Chi. Fairness without demographics through adversarially reweighted learning, 2020. URL: http://arxiv.org/abs/2006.13114.
  23. Natalie Martinez, Martin Bertran, and Guillermo Sapiro. Minimax Pareto fairness: A multi objective perspective. In Proceedings of the 37th International Conference on Machine Learning. Vienna, Austria, PMLR 119, 2020. Google Scholar
  24. Shira Mitchell, Eric Potash, Solon Barocas, Alexander D’Amour, and Kristian Lum. Algorithmic fairness: Choices, assumptions, and definitions. Annual Review of Statistics and Its Application, 8, 2020. Google Scholar
  25. D. Nace and M. Pióro. Max-min fairness and its applications to routing and load-balancing in communication networks: a tutorial. IEEE Communications Surveys and Tutorials, 10, 2008. Google Scholar
  26. W. Ogryczak and Warsaw. Lexicographic max-min optimization for efficient and fair bandwidth allocation. International network optimization conference (INOC), January 2007. Google Scholar
  27. Wlodzimierz Ogryczak, Hanan Luss, Dritan Nace, and Michał Pióro. Fair Optimization and Networks: Models, Algorithms, and Applications. Journal of Applied Mathematics, September 2014. URL: https://doi.org/10.1155/2014/340913.
  28. B. Radunovic and J. Le Boudec. A unified framework for max-min and min-max fairness with applications. IEEE/ACM Transactions on Networking, 15(5):1073-1083, 2007. URL: https://doi.org/10.1109/TNET.2007.896231.
  29. Samira Samadi, Uthaipon Tantipongpipat, Jamie H Morgenstern, Mohit Singh, and Santosh Vempala. The price of fair PCA: One extra dimension. In Advances in Neural Information Processing Systems, pages 10976-10987, 2018. Google Scholar
  30. Saeed Sharifi-Malvajerdi, Michael Kearns, and Aaron Roth. Average individual fairness: Algorithms, generalization and experiments. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dquotesingle Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL: https://proceedings.neurips.cc/paper/2019/file/0e1feae55e360ff05fef58199b3fa521-Paper.pdf.
  31. Berk Ustun, Yang Liu, and David Parkes. Fairness without harm: Decoupled classifiers with preference guarantees. In International Conference on Machine Learning, pages 6373-6382, 2019. Google Scholar
  32. X. Wang, K. Kar, and J. Pang. Lexicographic max-min fair rate allocation in random access wireless networks. In Proceedings of the 45th IEEE Conference on Decision and Control, pages 1294-1300, 2006. URL: https://doi.org/10.1109/CDC.2006.377233.
  33. Congzhou Zhou and N. F. Maxemchuk. Scalable max-min fairness in wireless ad hoc networks. In Jun Zheng, Shiwen Mao, Scott F. Midkiff, and Hua Zhu, editors, Ad Hoc Networks, pages 79-93, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  34. Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML'03, page 928–935. AAAI Press, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact