Differentially Private Decomposable Submodular Maximization
DOI:
https://doi.org/10.1609/aaai.v35i8.16860Keywords:
Ethics -- Bias, Fairness, Transparency & PrivacyAbstract
We study the problem of differentially private constrained maximization of decomposable submodular functions. A submodular function is decomposable if it takes the form of a sum of submodular functions. The special case of maximizing a monotone, decomposable submodular function under cardinality constraints is known as the Combinatorial Public Projects (CPP) problem (Papadimitriou, Schapira, and Singer 2008). Previous work by Gupta et al. (2010) gave a differentially private algorithm for the CPP problem. We extend this work by designing differentially private algorithms for both monotone and non-monotone decomposable submodular maximization under general matroid constraints, with competitive utility guarantees. We complement our theoretical bounds with experiments demonstrating improved empirical performance.Downloads
Published
2021-05-18
How to Cite
Chaturvedi, A., Nguyễn, H. L., & Zakynthinou, L. (2021). Differentially Private Decomposable Submodular Maximization. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8), 6984-6992. https://doi.org/10.1609/aaai.v35i8.16860
Issue
Section
AAAI Technical Track on Machine Learning I