Differentially Private Decomposable Submodular Maximization

Anamay Chaturvedi, Huy Le Nguyen, Lydia Zakynthinou

AAAI 2021 pp. 6984-6992

doi:10.1609/AAAI.V35I8.16860 /aaai/2021/chaturvedi2021aaai-differentially/

Abstract

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.

PDF AAAI Semantic Scholar

Cite

Text

Chaturvedi et al. "Differentially Private Decomposable Submodular Maximization." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I8.16860

Markdown

[Chaturvedi et al. "Differentially Private Decomposable Submodular Maximization." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/chaturvedi2021aaai-differentially/) doi:10.1609/AAAI.V35I8.16860

BibTeX

@inproceedings{chaturvedi2021aaai-differentially,
  title     = {{Differentially Private Decomposable Submodular Maximization}},
  author    = {Chaturvedi, Anamay and Le Nguyen, Huy and Zakynthinou, Lydia},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2021},
  pages     = {6984-6992},
  doi       = {10.1609/AAAI.V35I8.16860},
  url       = {https://mlanthology.org/aaai/2021/chaturvedi2021aaai-differentially/}
}