Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints

Ehsan Kazemi, Morteza Zadimoghaddam, Amin Karbasi
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2544-2553, 2018.

Abstract

Can we efficiently extract useful information from a large user-generated dataset while protecting the privacy of the users and/or ensuring fairness in representation? We cast this problem as an instance of a deletion-robust submodular maximization where part of the data may be deleted or masked due to privacy concerns or fairness criteria. We propose the first memory-efficient centralized, streaming, and distributed methods with constant-factor approximation guarantees against any number of adversarial deletions. We extensively evaluate the performance of our algorithms on real-world applications, including (i) Uber-pick up locations with location privacy constraints; (ii) feature selection with fairness constraints for income prediction and crime rate prediction; and (iii) robust to deletion summarization of census data, consisting of 2,458,285 feature vectors. Our experiments show that our solution is robust against even $80%$ of data deletion.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-kazemi18a, title = {Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints}, author = {Kazemi, Ehsan and Zadimoghaddam, Morteza and Karbasi, Amin}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {2544--2553}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/kazemi18a/kazemi18a.pdf}, url = {https://proceedings.mlr.press/v80/kazemi18a.html}, abstract = {Can we efficiently extract useful information from a large user-generated dataset while protecting the privacy of the users and/or ensuring fairness in representation? We cast this problem as an instance of a deletion-robust submodular maximization where part of the data may be deleted or masked due to privacy concerns or fairness criteria. We propose the first memory-efficient centralized, streaming, and distributed methods with constant-factor approximation guarantees against any number of adversarial deletions. We extensively evaluate the performance of our algorithms on real-world applications, including (i) Uber-pick up locations with location privacy constraints; (ii) feature selection with fairness constraints for income prediction and crime rate prediction; and (iii) robust to deletion summarization of census data, consisting of 2,458,285 feature vectors. Our experiments show that our solution is robust against even $80%$ of data deletion.} }
Endnote
%0 Conference Paper %T Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints %A Ehsan Kazemi %A Morteza Zadimoghaddam %A Amin Karbasi %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-kazemi18a %I PMLR %P 2544--2553 %U https://proceedings.mlr.press/v80/kazemi18a.html %V 80 %X Can we efficiently extract useful information from a large user-generated dataset while protecting the privacy of the users and/or ensuring fairness in representation? We cast this problem as an instance of a deletion-robust submodular maximization where part of the data may be deleted or masked due to privacy concerns or fairness criteria. We propose the first memory-efficient centralized, streaming, and distributed methods with constant-factor approximation guarantees against any number of adversarial deletions. We extensively evaluate the performance of our algorithms on real-world applications, including (i) Uber-pick up locations with location privacy constraints; (ii) feature selection with fairness constraints for income prediction and crime rate prediction; and (iii) robust to deletion summarization of census data, consisting of 2,458,285 feature vectors. Our experiments show that our solution is robust against even $80%$ of data deletion.
APA
Kazemi, E., Zadimoghaddam, M. & Karbasi, A.. (2018). Scalable Deletion-Robust Submodular Maximization: Data Summarization with Privacy and Fairness Constraints. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2544-2553 Available from https://proceedings.mlr.press/v80/kazemi18a.html.

Related Material