论文标题
快速和私人的下管和$ k $ -submodular函数最大化与矩阵约束
Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints
论文作者
论文摘要
在过去的十年中，已经深入研究了在某个约束下最大化非负单调下调函数的问题，并且已经为此问题开发了广泛的有效近似算法。许多机器学习问题，包括数据汇总和影响最大化，可以自然地建模为最大化单调次传导函数的问题。但是，当此类应用程序涉及有关个人的敏感数据时，应解决其隐私问题。在本文中，我们研究了在差异隐私框架中受到矩阵限制的最大化单调下调功能的问题。我们提供$（1- \ frac {1} {\ mathrm {e}}）$ - 近似算法，该算法在近似保证方面改善了先前的结果。这是在我们的算法中几乎数字数量的功能评估来完成的。 此外，我们研究了$ k $ - submodularity，一种自然的概括。我们给出了第一个$ \ frac {1} {2} $ - 近似算法，该算法保留了差异隐私，以最大化单调$ k $ -submodular函数，但要受矩阵约束。近似值比渐近地紧密，并通过几乎线性的函数评估获得。
The problem of maximizing nonnegative monotone submodular functions under a certain constraint has been intensively studied in the last decade, and a wide range of efficient approximation algorithms have been developed for this problem. Many machine learning problems, including data summarization and influence maximization, can be naturally modeled as the problem of maximizing monotone submodular functions. However, when such applications involve sensitive data about individuals, their privacy concerns should be addressed. In this paper, we study the problem of maximizing monotone submodular functions subject to matroid constraints in the framework of differential privacy. We provide $(1-\frac{1}{\mathrm{e}})$-approximation algorithm which improves upon the previous results in terms of approximation guarantee. This is done with an almost cubic number of function evaluations in our algorithm. Moreover, we study $k$-submodularity, a natural generalization of submodularity. We give the first $\frac{1}{2}$-approximation algorithm that preserves differential privacy for maximizing monotone $k$-submodular functions subject to matroid constraints. The approximation ratio is asymptotically tight and is obtained with an almost linear number of function evaluations.
