我们介绍了一种差别的私有方法来测量遍布两个实体托管的敏感数据之间的非线性相关性。我们提供私人估算器的实用程序保障。我们是第一个非线性相关性的私人估算器，据我们在多方设置中的知识中最好。我们认为的非线性相关的重要措施是距离相关性。这项工作具有直接应用于私有功能筛选，私人独立测试，私人K样品测试，私有多方因果推断和私有数据综合，除了探索数据分析。代码访问：公开访问的链接在补充文件中提供了代码。

我们介绍了$ \ pi $ -test，这是一种用于测试跨多方数据分布的数据之间的统计独立性的隐私保护算法。我们的算法依赖于私人估计数据集之间的距离相关性，这是SZ \'ekely等人中引入的独立性的定量度量。[2007]。我们在差异私有测试的实用性上建立了加法和乘法误差界，我们相信在涉及敏感数据的各种分布式假设测试设置中，我们会发现应用程序。

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].

在本文中，我们研究了代理人（个人）具有战略性或自我利益的情况，并且在报告数据时关注其隐私。与经典环境相比，我们的目标是设计机制，这些机制既可以激励大多数代理来真实地报告他们的数据并保留个人报告的隐私，而它们的输出也应接近基础参数。在本文的第一部分中，我们考虑了协变量是次高斯的情况，并且在他们只有有限的第四瞬间的情况下进行了重尾。首先，我们是受可能性功能最大化器的固定条件的动机，我们得出了一种新颖的私人和封闭式估计量。基于估算器，我们提出了一种机制，该机制通过对几种规范模型的计算和付款方案进行一些适当的设计具有以下属性，例如线性回归，逻辑回归和泊松回归：（1）机制为$ O（1） $ - 接点差异私有（概率至少$ 1-O（1）$）; （2）这是一个$ o（\ frac {1} {n}）$ - 近似于$（1-o（1））$的代理的近似贝叶斯nash平衡，以真实地报告其数据，其中$ n $是代理人的数量； （3）输出可能会达到基础参数的$ O（1）$； （4）对于机制中的$（1-o（1））$的代理分数是个人合理的； （5）分析师运行该机制所需的付款预算为$ O（1）$。在第二部分中，我们考虑了在更通用的环境下的线性回归模型，在该设置中，协变量和响应都是重尾，只有有限的第四次矩。通过使用$ \ ell_4 $ -norm收缩运算符，我们提出了一种私人估算器和付款方案，该方案具有与次高斯案例相似的属性。

我们介绍了一个普遍的框架，用于表征差异隐私保证的统计估算问题的统计效率。我们的框架，我们呼叫高维建议 - 试验释放（HPTR），在三个重要组件上建立：指数机制，强大的统计和提议 - 试验释放机制。将所有这些粘在一起是恢复力的概念，这是强大的统计估计的核心。弹性指导算法的设计，灵敏度分析和试验步骤的成功概率分析。关键识别是，如果我们设计了一种仅通过一维鲁棒统计数据访问数据的指数机制，则可以大大减少所产生的本地灵敏度。使用弹性，我们可以提供紧密的本地敏感界限。这些紧张界限在几个案例中容易转化为近乎最佳的实用程序。我们给出了将HPTR应用于统计估计问题的给定实例的一般配方，并在平均估计，线性回归，协方差估计和主成分分析的规范问题上证明了它。我们介绍了一般的公用事业分析技术，证明了HPTR几乎在文献中研究的若干场景下实现了最佳的样本复杂性。

我们启动差异私有（DP）估计的研究，并访问少量公共数据。为了对D维高斯人进行私人估计，我们假设公共数据来自高斯人，该高斯与私人数据的基础高斯人的总变化距离可能消失了。我们表明，在纯或集中DP的约束下，D+1个公共数据样本足以从私人样本复杂性中删除对私人数据分布的范围参数的任何依赖性，而在没有公共数据的情况下，这是必不可少的。对于分离的高斯混合物，我们假设基本的公共和私人分布是相同的，我们考虑两个设置：（1）当给出独立于维度的公共数据时，可以根据多种方式改善私人样本复杂性混合组件的数量以及对分布范围参数的任何依赖性都可以在近似DP情况下去除； （2）当在维度上给出了一定数量的公共数据线性时，即使在集中的DP下，也可以独立于范围参数使私有样本复杂性使得可以对整体样本复杂性进行其他改进。

内核平均嵌入是表示和比较概率度量的有用工具。尽管具有有用性，但内核的意思是考虑无限维度的特征，在差异私有数据生成的背景下，这是具有挑战性的。最近的一项工作建议使用有限维的随机特征近似数据分布的内核平均值嵌入，从而产生可分析的敏感性。但是，所需的随机特征的数量过高，通常是一千到十万，这会使隐私准确的权衡加剧。为了改善权衡取舍，我们建议用Hermite多项式特征替换随机功能。与随机特征不同，储能多项式特征是排序的，其中低订单的特征包含的分布更多的信息比高订单处的分布更多。因此，与明显更高的随机特征相比，HERMITE多项式特征的相对较低的阶多项式特征可以更准确地近似数据分布的平均嵌入。正如在几个表格和图像数据集中所证明的那样，Hermite多项式特征似乎比随机傅立叶功能更适合私人数据生成。

差异化私有（DP）数据发布是一种有前途的技术，可以在不损害数据主体的隐私而传播数据。但是，大多数先前的工作都集中在单一方拥有所有数据的方案上。在本文中，我们专注于多方设置，其中不同的利益相关者拥有属于同一数据主体的属性集合。在线性回归的上下文中，允许各方在完全数据上训练模型，而无需推断个人的私人属性或身份，我们首先直接应用高斯机制并表明其具有小的特征值问题。我们进一步提出了我们的新方法，并证明其渐近地收敛到随着数据集大小增加的最佳（非私有）解决方案。我们通过对人工和现实世界数据集的实验来证实理论结果。

我们为高维分布的身份测试提供了改进的差异私有算法。具体来说，对于带有已知协方差$ \ sigma $的$ d $二维高斯分布，我们可以测试该分布是否来自$ \ Mathcal {n}（\ mu^*，\ sigma）$，对于某些固定$ \ mu^** $或从某个$ \ MATHCAL {n}（\ mu，\ sigma）$，总变化距离至少$ \ alpha $ from $ \ mathcal {n}（\ mu^*，\ sigma）$（\ varepsilon） ，0）$ - 微分隐私，仅使用\ [\ tilde {o} \ left（\ frac {d^{1/2}}} {\ alpha^2} + \ frac {d^{1/3}} {1/3}} { \ alpha^{4/3} \ cdot \ varepsilon^{2/3}}} + \ frac {1} {\ alpha \ cdot \ cdot \ cdot \ varepsilon} \ right）\]唯一\ [\ tilde {o} \ left（\ frac {d^{1/2}}} {\ alpha^2} + \ frac {d^{1/4}} {\ alpha \ alpha \ cdot \ cdot \ cdot \ varepsilon} \ right ）\]用于计算有效算法的样品。我们还提供了一个匹配的下限，表明我们的计算效率低下的算法具有最佳的样品复杂性。我们还将算法扩展到各种相关问题，包括对具有有限但未知协方差的高斯人的平均测试，对$ \ { - 1，1，1 \}^d $的产品分布的均匀性测试以及耐受性测试。我们的结果改善了Canonne等人的先前最佳工作。 （\ frac {\ sqrt {d}} {\ alpha^2} \ right）$在许多标准参数设置中。此外，我们的结果表明，令人惊讶的是，可以使用$ d $二维高斯的私人身份测试，可以用少于离散分布的私人身份测试尺寸$ d $ \ cite {actharyasz18}的私人身份测试来完成，以重组猜测〜\ cite {canonnekmuz20}的下限。

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

在共享数据的统计学习和分析中，在联合学习和元学习等平台上越来越广泛地采用，有两个主要问题：隐私和鲁棒性。每个参与的个人都应该能够贡献，而不会担心泄露一个人的敏感信息。与此同时，系统应该在恶意参与者的存在中插入损坏的数据。最近的算法在学习中，学习共享数据专注于这些威胁中的一个，使系统容易受到另一个威胁。我们弥合了这个差距，以获得估计意思的规范问题。样品。我们介绍了素数，这是第一算法，实现了各种分布的隐私和鲁棒性。我们通过新颖的指数时间算法进一步补充了这一结果，提高了素数的样本复杂性，实现了近最优保证并匹配（非鲁棒）私有平均估计的已知下限。这证明没有额外的统计成本同时保证隐私和稳健性。

在本文中，我们研究了非交互性局部差异隐私（NLDP）模型中估计平滑普遍线性模型（GLM）的问题。与其经典设置不同，我们的模型允许服务器访问一些其他公共但未标记的数据。在本文的第一部分中，我们专注于GLM。具体而言，我们首先考虑每个数据记录均为I.I.D.的情况。从零均值的多元高斯分布中取样。由Stein的引理动机，我们提出了GLMS的$（Epsilon，\ delta）$ -NLDP算法。此外，算法的公共数据和私人数据的示例复杂性以实现$ \ alpha $的$ \ ell_2 $ -norm估计错误（具有高概率）为$ {o}（p \ alpha^{ - 2}）$和$ \ tilde {o}（p^3 \ alpha^{ - 2} \ epsilon^{ - 2}）$，其中$ p $是特征向量的维度。这是对$ \ alpha^{ - 1} $中先前已知的指数或准过程的重大改进，或者在$ p $中的指数smack sample sample smack glms的复杂性，没有公共数据。然后，我们考虑一个更通用的设置，每个数据记录为I.I.D.从某些次高斯分布中取样，有限制的$ \ ell_1 $ -norm。基于Stein的引理的变体，我们提出了一个$（\ epsilon，\ delta）$ - NLDP算法，用于GLMS的公共和私人数据的样本复杂性，以实现$ \ ell_ \ elfty $ - infty $ -NOMM估计的$ \ alpha误差$是$ is $ {o}（p^2 \ alpha^{ - 2}）$和$ \ tilde {o}（p^2 \ alpha^{ - 2} \ epsilon^{ - 2}）$，温和的假设，如果$ \ alpha $不太小（{\ em i.e.，} $ \ alpha \ geq \ omega（\ frac {1} {\ sqrt {p}}}）$）。在本文的第二部分中，我们将我们的想法扩展到估计非线性回归的问题，并显示出与多元高斯和次高斯案例的GLMS相似的结果。最后，我们通过对合成和现实世界数据集的实验来证明算法的有效性。

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

我们给出了第一个多项式 - 时间，多项式 - 样本，差异私人估算器，用于任意高斯分发$ \ mathcal {n}（\ mu，\ sigma）$ in $ \ mathbb {r} ^ d $。所有以前的估算器都是非变性的，具有无限的运行时间，或者要求用户在参数$ \ mu $和$ \ sigma $上指定先验的绑定。我们算法中的主要新技术工具是一个新的差别私有预处理器，它从任意高斯$ \ mathcal {n}（0，\ sigma）$中采用样本，并返回矩阵$ a $，使得$ a \ sigma a ^ t$具有恒定的条件号。

我们为其非私人对准减少$（\ varepsilon，\ delta）$差异私人（dp）统计估计，提供了一个相当一般的框架。作为本框架的主要应用，我们提供多项式时间和$（\ varepsilon，\ delta）$ - DP算法用于学习（不受限制的）高斯分布在$ \ mathbb {r} ^ d $。我们学习高斯的方法的样本复杂度高斯距离总变化距离$ \ alpha $是$ \ widetilde {o} \ left（\ frac {d ^ 2} {\ alpha ^ 2} + \ frac {d ^ 2 \ sqrt {\ ln {1 / \ delta}} {\ alpha \ varepsilon} \右）$，匹配（最多为对数因子）最佳已知的信息理论（非高效）样本复杂性上限的aden-ali， Ashtiani，Kamath〜（alt'21）。在一个独立的工作中，Kamath，Mouzakis，Singhal，Steinke和Ullman〜（Arxiv：2111.04609）使用不同的方法证明了类似的结果，并以$ O（d ^ {5/2}）$样本复杂性依赖于$ d $ 。作为我们的框架的另一个应用，我们提供了第一次多项式时间$（\ varepsilon，\ delta）$-dp算法，用于鲁棒学习（不受限制的）高斯。

在许多应用程序中，多方拥有有关相同用户的私人数据，但在属性的脱节集上，服务器希望利用数据来训练模型。为了在保护数据主体的隐私时启用模型学习，我们需要垂直联合学习（VFL）技术，其中数据派对仅共享用于培训模型的信息，而不是私人数据。但是，确保共享信息在学习准确的模型的同时保持隐私是一项挑战。据我们所知，本文提出的算法是第一个实用的解决方案，用于差异化垂直联合K-均值聚类，服务器可以在其中获得具有可证明的差异隐私保证的全球中心。我们的算法假设一个不受信任的中央服务器，该服务器汇总了本地数据派对的差异私有本地中心和成员资格编码。它基于收到的信息构建加权网格作为全局数据集的概要。最终中心是通过在加权网格上运行任何K-均值算法而产生的。我们的网格重量估计方法采用了基于Flajolet-Martin草图的新颖，轻巧和差异私有的相交基数估计算法。为了提高两个以上数据方的设置中的估计准确性，我们进一步提出了权重估计算法的精致版本和参数调整策略，以减少最终的K-均值实用程序，以便在中央私人环境中接近它。我们为由我们的算法计算的群集中心提供了理论实用性分析和实验评估结果，并表明我们的方法在理论上和经验上都比基于现有技术的两个基准在理论上和经验上的表现更好。

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

Hawkes流程最近从机器学习社区中引起了人们对建模事件序列数据的多功能性的越来越多的关注。尽管它们具有丰富的历史可以追溯到几十年前，但其某些属性（例如用于学习参数的样本复杂性和释放差异化私有版本的样本复杂性）尚未得到彻底的分析。在这项工作中，我们研究了具有背景强度$ \ mu $和激发功能$ \ alpha e^{ - \ beta t} $的标准霍克斯进程。我们提供$ \ mu $和$ \ alpha $的非私人和差异私人估计器，并在两种设置中获得样本复杂性结果以量化隐私成本。我们的分析利用了霍克斯过程的强大混合特性和经典的中央限制定理的结果，结果较弱的随机变量。我们在合成数据集和真实数据集上验证了我们的理论发现。

近年来，保护隐私数据分析已成为普遍存在。在本文中，我们提出了分布式私人多数票投票机制，以解决分布式设置中的标志选择问题。为此，我们将迭代剥离应用于稳定性函数，并使用指数机制恢复符号。作为应用程序，我们研究了分布式系统中的平均估计和线性回归问题的私人标志选择。我们的方法与非私有场景一样，用最佳的信噪比恢复了支持和标志，这比私人变量选择的现代作品要好。此外，符号选择一致性具有理论保证是合理的。进行了模拟研究以证明我们提出的方法的有效性。

联合学习允许许多设备在机器学习模型的培训中进行协作。与传统的机器学习一样，越来越关注的是，接受联合学习的模型可能会对不同的人群组表现出不同的表现。现有的解决方案来衡量和确保跨小组的平等模型绩效需要访问有关小组成员的信息，但是此访问并不总是可用或可取的，尤其是在联邦学习的隐私愿望下。我们研究了衡量此类性能差异的可行性，同时保护用户组成员资格的隐私以及联合模型在用户数据上的性能。保护两者对于隐私至关重要，因为它们可能是相关的，因此学习一个可能会揭示另一个。另一方面，从公用事业的角度来看，保留隐私的数据应保持相关性，以确保能够对性能差异进行准确的测量。我们通过开发当地差异化的私人机制来实现这两个目标，从而保留小组成员和模型绩效之间的相关性。为了分析机制的有效性，我们在对给定隐私预算进行优化时估算差异时的错误，并在合成数据上验证这些界限。我们的结果表明，对于参与的客户数量的实际数量，错误迅速减少，这表明，与先前的工作相反，保护受保护属性的隐私不一定与确定联合模型性能的差异相抵触。