论文标题
私人优化而无需违反限制
Private Optimization Without Constraint Violations
论文作者
论文摘要
当约束的右侧侧面取决于私人数据时，我们研究了差异私有优化的问题。这种类型的问题出现在许多应用程序中，尤其是资源分配。先前的研究提供了保留隐私但有时违反限制的解决方案。但是，在许多情况下，在任何情况下都不能违反限制。为了满足这一严格的要求，我们提出了一种算法，该算法释放了一个几乎最佳的解决方案，满足概率1的约束。我们还证明了一个下限，证明了算法解决方案的目标值与最佳解决方案的目标值之间的差异是紧密的，以使所有差异化私有算法之间的对数因素紧密。我们的实验结论表明，我们的算法在保留隐私时可以实现几乎最佳的性能。
We study the problem of differentially private optimization with linear constraints when the right-hand-side of the constraints depends on private data. This type of problem appears in many applications, especially resource allocation. Previous research provided solutions that retained privacy but sometimes violated the constraints. In many settings, however, the constraints cannot be violated under any circumstances. To address this hard requirement, we present an algorithm that releases a nearly-optimal solution satisfying the constraints with probability 1. We also prove a lower bound demonstrating that the difference between the objective value of our algorithm's solution and the optimal solution is tight up to logarithmic factors among all differentially private algorithms. We conclude with experiments demonstrating that our algorithm can achieve nearly optimal performance while preserving privacy.
