论文标题
差异化私有分解次生体最大化
Differentially Private Decomposable Submodular Maximization
论文作者
论文摘要
我们研究了可分解的下义功能的差异私有约束最大化的问题。如果以下函数的形式可以分解，则可以分解。在基数限制下最大化单调，可分解的下义功能的特殊情况称为组合公共项目（CPP）问题[Papadimitriou等，2008]。 Gupta等人的先前工作。 [2010]给出了CPP问题的私有算法。我们通过设计差异化私有算法在一般的Matroid限制下设计差异性私有算法，并具有竞争力保证。我们通过证明经验表现的实验来补充理论界限，该实验改进了差异私有算法的总体最大化情况，并且接近非私有算法的性能。
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 et al., 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 empirical performance, which improves over the differentially private algorithms for the general case of submodular maximization and is close to the performance of non-private algorithms.
