Fairness in Streaming Submodular Maximization over a Matroid Constraint

Marwa El Halabi, Federico Fusco, Ashkan Norouzi-Fard, Jakab Tardos, Jakub Tarnawski
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:9150-9171, 2023.

Abstract

Streaming submodular maximization is a natural model for the task of selecting a representative subset from a large-scale dataset. If datapoints have sensitive attributes such as gender or race, it becomes important to enforce fairness to avoid bias and discrimination. This has spurred significant interest in developing fair machine learning algorithms. Recently, such algorithms have been developed for monotone submodular maximization under a cardinality constraint. In this paper, we study the natural generalization of this problem to a matroid constraint. We give streaming algorithms as well as impossibility results that provide trade-offs between efficiency, quality and fairness. We validate our findings empirically on a range of well-known real-world applications: exemplar-based clustering, movie recommendation, and maximum coverage in social networks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-el-halabi23a, title = {Fairness in Streaming Submodular Maximization over a Matroid Constraint}, author = {El Halabi, Marwa and Fusco, Federico and Norouzi-Fard, Ashkan and Tardos, Jakab and Tarnawski, Jakub}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {9150--9171}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/el-halabi23a/el-halabi23a.pdf}, url = {https://proceedings.mlr.press/v202/el-halabi23a.html}, abstract = {Streaming submodular maximization is a natural model for the task of selecting a representative subset from a large-scale dataset. If datapoints have sensitive attributes such as gender or race, it becomes important to enforce fairness to avoid bias and discrimination. This has spurred significant interest in developing fair machine learning algorithms. Recently, such algorithms have been developed for monotone submodular maximization under a cardinality constraint. In this paper, we study the natural generalization of this problem to a matroid constraint. We give streaming algorithms as well as impossibility results that provide trade-offs between efficiency, quality and fairness. We validate our findings empirically on a range of well-known real-world applications: exemplar-based clustering, movie recommendation, and maximum coverage in social networks.} }
Endnote
%0 Conference Paper %T Fairness in Streaming Submodular Maximization over a Matroid Constraint %A Marwa El Halabi %A Federico Fusco %A Ashkan Norouzi-Fard %A Jakab Tardos %A Jakub Tarnawski %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-el-halabi23a %I PMLR %P 9150--9171 %U https://proceedings.mlr.press/v202/el-halabi23a.html %V 202 %X Streaming submodular maximization is a natural model for the task of selecting a representative subset from a large-scale dataset. If datapoints have sensitive attributes such as gender or race, it becomes important to enforce fairness to avoid bias and discrimination. This has spurred significant interest in developing fair machine learning algorithms. Recently, such algorithms have been developed for monotone submodular maximization under a cardinality constraint. In this paper, we study the natural generalization of this problem to a matroid constraint. We give streaming algorithms as well as impossibility results that provide trade-offs between efficiency, quality and fairness. We validate our findings empirically on a range of well-known real-world applications: exemplar-based clustering, movie recommendation, and maximum coverage in social networks.
APA
El Halabi, M., Fusco, F., Norouzi-Fard, A., Tardos, J. & Tarnawski, J.. (2023). Fairness in Streaming Submodular Maximization over a Matroid Constraint. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:9150-9171 Available from https://proceedings.mlr.press/v202/el-halabi23a.html.

Related Material