在数据库查询结果中添加随机噪声是实现隐私的重要工具。一个挑战是最大程度地减少这种噪音，同时仍然满足隐私要求。最近，出版了$（\ epsilon，\ delta）$的足够和必要的条件 - 高斯噪声的差异隐私。这种情况允许计算此分布的最小隐私量表。我们扩展了这项工作，并为$（\ epsilon，\ delta）$ - 差分隐私提供了足够和必要的条件，用于所有对称和对象concove噪声密度。我们的结果允许将噪声分布的细粒度调整为查询结果的维度。我们证明，与当前使用的Laplace和Gaussian机制相同的$ \ epsilon $和$ \ delta $发生的Laplace和Gaussian机制所产生的均方误差明显低得多。

我们呈现渐近最优的$（\ epsilon，\ delta）$差异私有机制，用于回答多个，自适应的$ \ delta $ -sursitive查询，解决Steinke和Ullman的猜想[2020]。我们的算法具有显着的优点，即它向每个查询增加独立的有界噪声，从而提供绝对误差。此外，我们在自适应数据分析中应用了我们的算法，获得了使用有限样本对某些基础分布的多个查询的改进保证。数值计算表明，界限噪声机制在许多标准设置中优于高斯机制。

Concentrated differential privacy" was recently introduced by Dwork and Rothblum as a relaxation of differential privacy, which permits sharper analyses of many privacy-preserving computations. We present an alternative formulation of the concept of concentrated differential privacy in terms of the Rényi divergence between the distributions obtained by running an algorithm on neighboring inputs. With this reformulation in hand, we prove sharper quantitative results, establish lower bounds, and raise a few new questions. We also unify this approach with approximate differential privacy by giving an appropriate definition of "approximate concentrated differential privacy."

我们介绍了一种基于约翰逊·林登斯特劳斯引理的统计查询的新方法，以释放具有差异隐私的统计查询的答案。关键的想法是随机投影查询答案，以较低的维空间，以便将可行的查询答案的任何两个向量之间的距离保留到添加性错误。然后，我们使用简单的噪声机制回答投影的查询，并将答案提升到原始维度。使用这种方法，我们首次给出了纯粹的私人机制，具有最佳情况下的最佳情况样本复杂性，在平均错误下，以回答$ n $ $ n $的宇宙的$ k $ Queries的工作量。作为其他应用，我们给出了具有最佳样品复杂性的第一个纯私人有效机制，用于计算有限的高维分布的协方差，并用于回答2向边缘查询。我们还表明，直到对错误的依赖性，我们机制的变体对于每个给定的查询工作负载几乎是最佳的。

特征在于构图的隐私劣化，即隐私会计，是差异隐私（DP）的基本话题，许多应用于差异私有机器学习和联合学习。我们提出了近期进步（Renyi DP，Privacy Compiles，$-D $ -dp和Pld形式主义）的统一，通过\ emph {phi $ \ phi $ -function）{占主导地位}隐私损失随机变量。我们展示了我们的方法允许\ emph {natural}自适应组成等renyi dp，提供\ emph {完全紧张}隐私会计，如pld，并且可以（通常是\ memph {docklyly}）转换为隐私权概况和$ f $ -dp ，从而提供$（\ epsilon，\ delta）$ - DP保证和可解释的权衡职能。算法，我们提出了一个\ xper {分析傅里叶会计师}，它象征性地表示$ \ phi $ -functions的\ icph {complex}对数，并使用高斯正交进行数值计算。在几个受欢迎的DP机制及其撤销的对应物上，我们展示了我们在理论和实验中的方法的灵活性和紧张性。

最大信息系数（MIC）是一个强大的统计量，可以识别变量之间的依赖性。但是，它可以应用于敏感数据，并且发布可能会泄漏私人信息。作为解决方案，我们提出算法以提供差异隐私的方式近似麦克风。我们表明，经典拉普拉斯机制的自然应用产生的精度不足。因此，我们介绍了MICT统计量，这是一种新的MIC近似值，与差异隐私更加兼容。我们证明MICS是麦克风的一致估计器，我们提供了两个差异性私有版本。我们对各种真实和合成数据集进行实验。结果表明，私人微统计数据极大地超过了拉普拉斯机制的直接应用。此外，对现实世界数据集的实验显示出准确性，当样本量至少适中时可用。

Differentially private algorithms for common metric aggregation tasks, such as clustering or averaging, often have limited practicality due to their complexity or to the large number of data points that is required for accurate results. We propose a simple and practical tool, $\mathsf{FriendlyCore}$, that takes a set of points ${\cal D}$ from an unrestricted (pseudo) metric space as input. When ${\cal D}$ has effective diameter $r$, $\mathsf{FriendlyCore}$ returns a "stable" subset ${\cal C} \subseteq {\cal D}$ that includes all points, except possibly few outliers, and is {\em certified} to have diameter $r$. $\mathsf{FriendlyCore}$ can be used to preprocess the input before privately aggregating it, potentially simplifying the aggregation or boosting its accuracy. Surprisingly, $\mathsf{FriendlyCore}$ is light-weight with no dependence on the dimension. We empirically demonstrate its advantages in boosting the accuracy of mean estimation and clustering tasks such as $k$-means and $k$-GMM, outperforming tailored methods.

We construct a universally Bayes consistent learning rule that satisfies differential privacy (DP). We first handle the setting of binary classification and then extend our rule to the more general setting of density estimation (with respect to the total variation metric). The existence of a universally consistent DP learner reveals a stark difference with the distribution-free PAC model. Indeed, in the latter DP learning is extremely limited: even one-dimensional linear classifiers are not privately learnable in this stringent model. Our result thus demonstrates that by allowing the learning rate to depend on the target distribution, one can circumvent the above-mentioned impossibility result and in fact, learn \emph{arbitrary} distributions by a single DP algorithm. As an application, we prove that any VC class can be privately learned in a semi-supervised setting with a near-optimal \emph{labeled} sample complexity of $\tilde{O}(d/\varepsilon)$ labeled examples (and with an unlabeled sample complexity that can depend on the target distribution).

除了近年来数据收集和分析技术的快速开发外，还越来越强调需要解决与此类数据使用相关的信息泄漏。为此，隐私文献中的许多工作都致力于保护个人用户和数据贡献者。但是，某些情况需要不同的数据机密性概念，涉及数据集记录的全局属性。这样的信息保护概念尤其适用于业务和组织数据，在这些数据中，全球财产可能反映商业秘密或人口统计数据，如果不当行为可能是有害的。最新关于财产推断攻击的工作还显示了数据分析算法如何容易泄漏数据的这些全局性能，从而强调了开发可以保护此类信息的机制的重要性。在这项工作中，我们演示了如何应用分发隐私框架来形式化保护数据集的全球属性的问题。鉴于此框架，我们研究了一些提供数据机密性概念的机制及其权衡。我们分析了这些机制在各种数据假设下提供的理论保护保证，然后对几个数据分析任务进行实施并经验评估这些机制。我们的实验结果表明，我们的机制确实可以降低实用性推理攻击的有效性，同时提供的实用性大大超过了原油差异的隐私基线。因此，我们的工作为保护数据集的全球性质的理论支持机制提供了基础。

研究人员和从业人员如何处理隐私 - 实用性权衡之间存在脱节。研究人员主要是从隐私的第一角度运作，设定严格的隐私要求并最大程度地限制受这些约束的风险。从业者通常希望获得准确的第一视角，可能会对他们可能获得足够小的错误的最大隐私感到满意。 Ligett等。已经引入了一种“降噪”算法来解决后一种观点。作者表明，通过添加相关的拉普拉斯噪声并逐步减少其需求，可以产生一系列越来越准确的私人参数估计值，而仅以最低噪声介绍的方式支付隐私成本。在这项工作中，我们将降噪概括为高斯噪声的设置，并引入了布朗机制。布朗机制首先添加与模拟布朗运动的最后点相对应的高方差的高斯噪声。然后，根据从业人员的酌情决定权，通过沿着布朗的路径追溯到较早的时间来逐渐降低噪音。我们的机制更自然地适用于有限的$ \ ell_2 $ - 敏感性的共同设置，从经验上优于公共统计任务上的现有工作，并在与从业者的整个交互中提供了对隐私损失的可自定义控制。我们通过简化的Brownian机制来补充我们的布朗机制，这是对提供自适应隐私保证的经典座位算法的概括。总体而言，我们的结果表明，人们可以达到公用事业的限制，同时仍保持强大的隐私水平。

差异隐私通常使用比理论更大的隐私参数应用于理想的理想。已经提出了宽大隐私参数的各种非正式理由。在这项工作中，我们考虑了部分差异隐私（DP），该隐私允许以每个属性为基础量化隐私保证。在此框架中，我们研究了几个基本数据分析和学习任务，并设计了其每个属性隐私参数的算法，其较小的人（即所有属性）的最佳隐私参数比最佳的隐私参数。

We continue a line of research initiated in [10,11] on privacypreserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query function f mapping databases to reals, the so-called true answer is the result of applying f to the database. To protect privacy, the true answer is perturbed by the addition of random noise generated according to a carefully chosen distribution, and this response, the true answer plus noise, is returned to the user.Previous work focused on the case of noisy sums, in which f = i g(xi), where xi denotes the ith row of the database and g maps database rows to [0, 1]. We extend the study to general functions f , proving that privacy can be preserved by calibrating the standard deviation of the noise according to the sensitivity of the function f . Roughly speaking, this is the amount that any single argument to f can change its output. The new analysis shows that for several particular applications substantially less noise is needed than was previously understood to be the case.The first step is a very clean characterization of privacy in terms of indistinguishability of transcripts. Additionally, we obtain separation results showing the increased value of interactive sanitization mechanisms over non-interactive.Supported by the Louis L. and Anita M. Perlman Postdoctoral Fellowship.

聚类是数据分析中的一个根本问题。在差别私有聚类中，目标是识别$ k $群集中心，而不披露各个数据点的信息。尽管研究进展显着，但问题抵制了实际解决方案。在这项工作中，我们的目的是提供简单的可实现的差异私有聚类算法，当数据“简单”时，提供实用程序，例如，当簇之间存在显着的分离时。我们提出了一个框架，允许我们将非私有聚类算法应用于简单的实例，并私下结合结果。在高斯混合的某些情况下，我们能够改善样本复杂性界限，并获得$ k $ -means。我们与合成数据的实证评估补充了我们的理论分析。

The ''Propose-Test-Release'' (PTR) framework is a classic recipe for designing differentially private (DP) algorithms that are data-adaptive, i.e. those that add less noise when the input dataset is nice. We extend PTR to a more general setting by privately testing data-dependent privacy losses rather than local sensitivity, hence making it applicable beyond the standard noise-adding mechanisms, e.g. to queries with unbounded or undefined sensitivity. We demonstrate the versatility of generalized PTR using private linear regression as a case study. Additionally, we apply our algorithm to solve an open problem from ''Private Aggregation of Teacher Ensembles (PATE)'' -- privately releasing the entire model with a delicate data-dependent analysis.

构建差异私有（DP）估计器需要得出观察结果的最大影响，如果在输入数据或估计器上没有外源性界限，这可能很困难，尤其是在高维度设置中。本文表明，在这方面，统计深度（即半空间深度和回归深度）的标准概念在这方面尤其有利，这在于单个观察值的最大影响很容易分析，并且该值通常很低。这用于使用这两个统计深度概念的最大值来激励新的近似DP位置和回归估计器。还提供了近似DP回归估计器的更高效的变体。此外，为了避免要求用户对估计和/或观察结果指定先验界限，描述了这些DP机制的变体，即满足随机差异隐私（RDP），这是Hall，Wasserman和Wasserman和Wasserman和Wasserman提供的差异隐私的放松Rinaldo（2013）。我们还提供了此处提出的两种DP回归方法的模拟。当样本量至少为100-200或隐私性损失预算足够高时，提出的估计器似乎相对于现有的DP回归方法表现出色。

在本文中，我们研究了非平滑凸函数的私人优化问题$ f（x）= \ mathbb {e} _i f_i（x）$ on $ \ mathbb {r}^d $。我们表明，通过将$ \ ell_2^2 $正规器添加到$ f（x）$并从$ \ pi（x）\ propto \ exp（-k（f（x）+\ mu \ \ | | x \ | _2^2/2））$恢复已知的最佳经验风险和$（\ epsilon，\ delta）$ - dp的已知最佳经验风险和人口损失。此外，我们将展示如何使用$ \ widetilde {o}（n \ min（d，n））$ QUERIES $ QUERIES $ f_i（x）$用于DP-SCO，其中$ n $是示例数/用户和$ d $是环境维度。我们还在评估查询的数量上给出了一个（几乎）匹配的下限$ \ widetilde {\ omega}（n \ min（d，n））$。我们的结果利用以下具有独立感兴趣的工具：（1）如果损失函数强烈凸出并且扰动是Lipschitz，则证明指数机制的高斯差异隐私（GDP）。我们的隐私约束是\ emph {optimal}，因为它包括高斯机制的隐私性，并使用等仪不等式证明了强烈的对数concove措施。 （2）我们展示如何从$ \ exp（-f（x） - \ mu \ | x \ | |^2_2/2）$ g $ -lipschitz $ f $带有$ \ eta $的总变化中的错误（电视）使用$ \ widetilde {o}（（g^2/\ mu）\ log^2（d/\ eta））$无偏查询到$ f（x）$。这是第一个在dimension $ d $和精度$ \ eta $上具有\ emph {polylogarithmic依赖的查询复杂性的采样器。

我们给出了第一个多项式算法来估计$ d $ -variate概率分布的平均值，从$ \ tilde {o}（d）$独立的样本受到纯粹的差异隐私的界限。此问题的现有算法无论是呈指数运行时间，需要$ \ OMEGA（D ^ {1.5}）$样本，或仅满足较弱的集中或近似差分隐私条件。特别地，所有先前的多项式算法都需要$ d ^ {1+ \ omega（1）} $ samples，以保证“加密”高概率，1-2 ^ { - d ^ {\ omega（1） $，虽然我们的算法保留$ \ tilde {o}（d）$ SAMPS复杂性即使在此严格设置中也是如此。我们的主要技术是使用强大的方块方法（SOS）来设计差异私有算法的新方法。算法的证据是在高维算法统计数据中的许多近期作品中的一个关键主题 - 显然需要指数运行时间，但可以通过低度方块证明可以捕获其分析可以自动变成多项式 - 时间算法具有相同的可证明担保。我们展示了私有算法的类似证据现象：工作型指数机制的实例显然需要指数时间，但可以用低度SOS样张分析的指数时间，可以自动转换为多项式差异私有算法。我们证明了捕获这种现象的元定理，我们希望在私人算法设计中广泛使用。我们的技术还在高维度之间绘制了差异私有和强大统计数据之间的新连接。特别是通过我们的校验算法镜头来看，几次研究的SOS证明在近期作品中的算法稳健统计中直接产生了我们差异私有平均估计算法的关键组成部分。

隐私保护数据分析研究了在隐私约束下的统计方法。这是现代统计数据中的一个不断提高的挑战，因为机密性保证的实现通常是通过数据扰动而发生的，这可能会决定数据的统计实用性损失。在本文中，我们考虑对频率表中的拟合优点进行隐私测试，这可以说是释放数据的最常见形式，并对私人可能性比率（LR）的大样本行为进行了严格的分析（LR）测试。在$（\ varepsilon，\ delta）$ - 差异隐私的框架下，我们的主要贡献是私人LR测试的功率分析，该测试的特征是通过差异隐私参数测量的机密性之间的权衡取舍（$）（ \ varepsilon，\ delta）$和统计实用程序，通过测试功率测量。这是通过bahadur-rao大偏差扩展获得的，用于私人LR测试的功率，从样本量，表和$（\ varepsilon，\ delta）$，这决定了测试功能的损失。然后，将这样的结果应用于与参数$（\ varepsilon，\ delta）$相关的样本量和表尺寸的影响，对私人LR测试的功率损失。特别是，我们确定$（样本）成本（\ varepsilon，\ delta）$ - 私人LR测试中的差异隐私，即在没有缺少多项式LR测试的功率所需的附加样本量扰动。我们的功率分析依赖于LR的非标准大偏差分析，以及用于I.I.D的新颖（尖锐）大偏差原理的发展。随机矢量，具有独立感兴趣。

In this work, we give efficient algorithms for privately estimating a Gaussian distribution in both pure and approximate differential privacy (DP) models with optimal dependence on the dimension in the sample complexity. In the pure DP setting, we give an efficient algorithm that estimates an unknown $d$-dimensional Gaussian distribution up to an arbitrary tiny total variation error using $\widetilde{O}(d^2 \log \kappa)$ samples while tolerating a constant fraction of adversarial outliers. Here, $\kappa$ is the condition number of the target covariance matrix. The sample bound matches best non-private estimators in the dependence on the dimension (up to a polylogarithmic factor). We prove a new lower bound on differentially private covariance estimation to show that the dependence on the condition number $\kappa$ in the above sample bound is also tight. Prior to our work, only identifiability results (yielding inefficient super-polynomial time algorithms) were known for the problem. In the approximate DP setting, we give an efficient algorithm to estimate an unknown Gaussian distribution up to an arbitrarily tiny total variation error using $\widetilde{O}(d^2)$ samples while tolerating a constant fraction of adversarial outliers. Prior to our work, all efficient approximate DP algorithms incurred a super-quadratic sample cost or were not outlier-robust. For the special case of mean estimation, our algorithm achieves the optimal sample complexity of $\widetilde O(d)$, improving on a $\widetilde O(d^{1.5})$ bound from prior work. Our pure DP algorithm relies on a recursive private preconditioning subroutine that utilizes the recent work on private mean estimation [Hopkins et al., 2022]. Our approximate DP algorithms are based on a substantial upgrade of the method of stabilizing convex relaxations introduced in [Kothari et al., 2022].

我们提出并分析了算法，以解决用户级差分隐私约束下的一系列学习任务。用户级DP仅保证只保证个人样本的隐私，而是保护用户的整个贡献（$ M \ GE 1 $ Samples），而不是对信息泄漏提供更严格但更现实的保护。我们表明，对于高维平均估计，具有平稳损失，随机凸优化和学习假设类别的经验风险最小化，具有有限度量熵，隐私成本随着用户提供的$ O（1 / \ SQRT {M}）$减少更多样本。相比之下，在增加用户数量$ N $时，隐私成本以较快的价格降低（1 / n）$率。我们将这些结果与下界相提并论，显示了我们算法的最低限度估计和随机凸优化的算法。我们的算法依赖于私有平均估计的新颖技术，其任意维度与误差缩放为浓度半径$ \ tai $的分布而不是整个范围。