Differentially Private Decomposable Submodular Maximization

No. 8: AAAI-21 Technical Tracks 8

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 35

AAAI Technical Track on Machine Learning I

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.

10.1609/aaai.v35i8.16860