Differentially Private Decomposable Submodular Maximization
Differentially Private Decomposable Submodular Maximization
复制标题
DOI：
10.1609/aaai.v35i8.16860
复制
发表时间：
2020-05
期刊：
影响因子：
--
通讯作者：
Anamay Chaturvedi;Huy L. Nguyen;Lydia Zakynthinou
中科院分区：
文献类型：
--
作者：
Anamay Chaturvedi;Huy L. Nguyen;Lydia Zakynthinou
研究了可分解子模函数的微分私有约束最大化问题。一个子模函数是可分解的，如果它采取子模函数之和的形式。在基数约束下最大化单调可分解子模函数的特殊情况称为组合公共项目（CPP）问题（Papadimitriou，Schapira和Singer 2008）。Gupta等人（2010）的先前工作给出了CPP问题的差分私有算法。我们扩展这项工作的设计差分私人算法的单调和非单调可分解的子模最大化一般拟阵的约束下，具有竞争力的效用保证。我们补充我们的理论界限与实验证明改进的经验性能。
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.