Differential privacy enables organizations to collect accurate aggregates over sensitive data with strong, rigorous guarantees on individuals' privacy. Previous work has found that under differential privacy, computing multiple correlated aggregates as a batch, using an appropriate \emph{strategy}, may yield higher accuracy than computing each of them independently. However, finding the optimal strategy that maximizes result accuracy is non-trivial, as it involves solving a complex constrained optimization program that appears to be non-linear and non-convex. Hence, in the past much effort has been devoted in solving this non-convex optimization program. Existing approaches include various sophisticated heuristics and expensive numerical solutions. None of them, however, guarantees to find the optimal strategy. This paper points out that under ($\epsilon$, $\delta$)-differential privacy, the optimal strategy for answering an arbitrary batch of linear aggregate queries can be found, rather surprisingly, by solving a simple and elegant convex optimization program. Then, we propose an efficient algorithm based on Newton's method, which we prove to always converge to the optimal solution with linear global convergence rate and quadratic local convergence rate. Empirical evaluations demonstrate the accuracy and efficiency of the proposed solution.

通过解决凸优化问题，利用Newton方法能够找到基于（Ε，δ）差分隐私下的合适策略，以计算数据的相关聚合，从而提高结果准确度。

线性查询处理的凸优化在近似差分隐私下的应用