Differentially Private Decomposable Submodular Maximization

Authors

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

Keywords:

Ethics -- Bias, Fairness, Transparency & Privacy

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.

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

Issue

Section

AAAI Technical Track on Machine Learning I