This paper introduces the first provably accurate algorithms for
differentially private, top-down decision tree learning in the distributed
setting (Balcan et al., 2012). We propose DP-TopDown, a general privacy
preserving decision tree learning algorithm, and present two distributed
implementations. Our first method NoisyCounts naturally extends the single
machine algorithm by using the Laplace mechanism. Our second method LocalRNM
significantly reduces communication and added noise by performing local
optimization at each data holder. We provide the first utility guarantees for
differentially private top-down decision tree learning in both the single
machine and distributed settings. These guarantees show that the error of the
privately-learned decision tree quickly goes to zero provided that the dataset
is sufficiently large. Our extensive experiments on real datasets illustrate
the trade-offs of privacy, accuracy and generalization when learning private
decision trees in the distributed setting.

本文提出了分布式环境下差分隐私保护决策树学习的第一个证明准确的算法: DP-TopDown，并介绍了两种分布式实现方法。这些研究成果提供了差分隐私保护下的顶部 - 向下决策树学习的效用保证，并揭示了在隐私、精度和概括性之间学习私有决策树的权衡。

分布式差分隐私决策树学习的可扩展和可证明精确性算法

Scalable and Provably Accurate Algorithms for Differentially Private  Distributed Decision Tree Learning

Privacy preserving data publishing has attracted considerable research
interest in recent years. Among the existing solutions, {\em
$\epsilon$-differential privacy} provides one of the strongest privacy
guarantees. Existing data publishing methods that achieve
$\epsilon$-differential privacy, however, offer little data utility. In
particular, if the output dataset is used to answer count queries, the noise in
the query answers can be proportional to the number of tuples in the data,
which renders the results useless.
In this paper, we develop a data publishing technique that ensures
$\epsilon$-differential privacy while providing accurate answers for {\em
range-count queries}, i.e., count queries where the predicate on each attribute
is a range. The core of our solution is a framework that applies {\em wavelet
transforms} on the data before adding noise to it. We present instantiations of
the proposed framework for both ordinal and nominal data, and we provide a
theoretical analysis on their privacy and utility guarantees. In an extensive
experimental study on both real and synthetic data, we show the effectiveness
and efficiency of our solution.

本文提出一种数据出版技术，通过将数据进行小波变换并添加噪音，在保证 ε- 差分隐私的同时，为区间计数查询提供准确的答案，并在真实数据和合成数据上进行了广泛的实验，展示了该解决方案的有效性和效率。

小波变换实现差分隐私

Differential Privacy via Wavelet Transforms

A mechanism for releasing information about a statistical database with
sensitive data must resolve a trade-off between utility and privacy. Privacy
can be rigorously quantified using the framework of {\em differential privacy},
which requires that a mechanism's output distribution is nearly the same
whether or not a given database row is included or excluded. The goal of this
paper is strong and general utility guarantees, subject to differential
privacy.
We pursue mechanisms that guarantee near-optimal utility to every potential
user, independent of its side information (modeled as a prior distribution over
query results) and preferences (modeled via a loss function).
Our main result is: for each fixed count query and differential privacy
level, there is a {\em geometric mechanism} $M^*$ -- a discrete variant of the
simple and well-studied Laplace mechanism -- that is {\em simultaneously
expected loss-minimizing} for every possible user, subject to the differential
privacy constraint. This is an extremely strong utility guarantee: {\em every}
potential user $u$, no matter what its side information and preferences,
derives as much utility from $M^*$ as from interacting with a differentially
private mechanism $M_u$ that is optimally tailored to $u$.

本文提出了一种基于差分隐私的机制，以保证数据查询的数据隐私和查询效用之间的平衡。机制包含了每个可能的用户的期望最小化的代价函数，并且针对每个固定数量的查询和差分隐私级别，存在一种几何机制可以同时保证每个可能用户的最佳实用性，这是一种极强的实用性保障。