Differentially Private Decomposable Submodular Maximization


  • Anamay Chaturvedi Northeastern University
  • Huy Lê Nguyễn Northeastern University
  • Lydia Zakynthinou Northeastern University


Ethics -- Bias, Fairness, Transparency & Privacy


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.




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. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16860



AAAI Technical Track on Machine Learning I