在共享数据的统计学习和分析中,在联合学习和元学习等平台上越来越广泛地采用,有两个主要问题:隐私和鲁棒性。每个参与的个人都应该能够贡献,而不会担心泄露一个人的敏感信息。与此同时,系统应该在恶意参与者的存在中插入损坏的数据。最近的算法在学习中,学习共享数据专注于这些威胁中的一个,使系统容易受到另一个威胁。我们弥合了这个差距,以获得估计意思的规范问题。样品。我们介绍了素数,这是第一算法,实现了各种分布的隐私和鲁棒性。我们通过新颖的指数时间算法进一步补充了这一结果,提高了素数的样本复杂性,实现了近最优保证并匹配(非鲁棒)私有平均估计的已知下限。这证明没有额外的统计成本同时保证隐私和稳健性。
translated by 谷歌翻译
我们介绍了一个普遍的框架,用于表征差异隐私保证的统计估算问题的统计效率。我们的框架,我们呼叫高维建议 - 试验释放(HPTR),在三个重要组件上建立:指数机制,强大的统计和提议 - 试验释放机制。将所有这些粘在一起是恢复力的概念,这是强大的统计估计的核心。弹性指导算法的设计,灵敏度分析和试验步骤的成功概率分析。关键识别是,如果我们设计了一种仅通过一维鲁棒统计数据访问数据的指数机制,则可以大大减少所产生的本地灵敏度。使用弹性,我们可以提供紧密的本地敏感界限。这些紧张界限在几个案例中容易转化为近乎最佳的实用程序。我们给出了将HPTR应用于统计估计问题的给定实例的一般配方,并在平均估计,线性回归,协方差估计和主成分分析的规范问题上证明了它。我们介绍了一般的公用事业分析技术,证明了HPTR几乎在文献中研究的若干场景下实现了最佳的样本复杂性。
translated by 谷歌翻译
We establish a simple connection between robust and differentially-private algorithms: private mechanisms which perform well with very high probability are automatically robust in the sense that they retain accuracy even if a constant fraction of the samples they receive are adversarially corrupted. Since optimal mechanisms typically achieve these high success probabilities, our results imply that optimal private mechanisms for many basic statistics problems are robust. We investigate the consequences of this observation for both algorithms and computational complexity across different statistical problems. Assuming the Brennan-Bresler secret-leakage planted clique conjecture, we demonstrate a fundamental tradeoff between computational efficiency, privacy leakage, and success probability for sparse mean estimation. Private algorithms which match this tradeoff are not yet known -- we achieve that (up to polylogarithmic factors) in a polynomially-large range of parameters via the Sum-of-Squares method. To establish an information-computation gap for private sparse mean estimation, we also design new (exponential-time) mechanisms using fewer samples than efficient algorithms must use. Finally, we give evidence for privacy-induced information-computation gaps for several other statistics and learning problems, including PAC learning parity functions and estimation of the mean of a multivariate Gaussian.
translated by 谷歌翻译
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].
translated by 谷歌翻译
我们给出了第一个多项式算法来估计$ 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证明在近期作品中的算法稳健统计中直接产生了我们差异私有平均估计算法的关键组成部分。
translated by 谷歌翻译
We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a constant fraction of adversarially-corrupted samples.
translated by 谷歌翻译
我们启动差异私有(DP)估计的研究,并访问少量公共数据。为了对D维高斯人进行私人估计,我们假设公共数据来自高斯人,该高斯与私人数据的基础高斯人的总变化距离可能消失了。我们表明,在纯或集中DP的约束下,D+1个公共数据样本足以从私人样本复杂性中删除对私人数据分布的范围参数的任何依赖性,而在没有公共数据的情况下,这是必不可少的。对于分离的高斯混合物,我们假设基本的公共和私人分布是相同的,我们考虑两个设置:(1)当给出独立于维度的公共数据时,可以根据多种方式改善私人样本复杂性混合组件的数量以及对分布范围参数的任何依赖性都可以在近似DP情况下去除; (2)当在维度上给出了一定数量的公共数据线性时,即使在集中的DP下,也可以独立于范围参数使私有样本复杂性使得可以对整体样本复杂性进行其他改进。
translated by 谷歌翻译
我们给出了第一个多项式时间和样本$(\ epsilon,\ delta)$ - 差异私有(DP)算法,以估计存在恒定的对抗性异常分数的平均值,协方差和更高的时刻。我们的算法成功用于分布的分布系列,以便在经济估计上满足两个学习的良好性质:定向时刻的可证明的子销售,以及2度多项式的可证式超分子。我们的恢复保证持有“右仿射效率规范”:Mahalanobis距离的平均值,乘法谱和相对Frobenius距离保证,适用于更高时刻的协方差和注射规范。先前的作品获得了私有稳健算法,用于界限协方差的子静脉分布的平均估计。对于协方差估算,我们的是第一算法(即使在没有异常值的情况下也是在没有任何条件号的假设的情况下成功的。我们的算法从一个新的框架出现,该框架提供了一种用于修改凸面放宽的一般蓝图,以便在算法在其运行中产生正确的正确性的证人,以满足适当的参数规范中的强烈最坏情况稳定性。我们验证了用于修改标准的平方(SOS)SEMIDEFINITE编程放松的担保,以实现鲁棒估算。我们的隐私保障是通过将稳定性保证与新的“估计依赖性”噪声注入机制相结合来获得,其中噪声比例与估计的协方差的特征值。我们认为,此框架更加有用,以获得强大的估算器的DP对应者。独立于我们的工作,Ashtiani和Liaw [Al21]还获得了高斯分布的多项式时间和样本私有鲁棒估计算法。
translated by 谷歌翻译
我们给出了第一个多项式 - 时间,多项式 - 样本,差异私人估算器,用于任意高斯分发$ \ mathcal {n}(\ mu,\ sigma)$ in $ \ mathbb {r} ^ d $。所有以前的估算器都是非变性的,具有无限的运行时间,或者要求用户在参数$ \ mu $和$ \ sigma $上指定先验的绑定。我们算法中的主要新技术工具是一个新的差别私有预处理器,它从任意高斯$ \ mathcal {n}(0,\ sigma)$中采用样本,并返回矩阵$ a $,使得$ a \ sigma a ^ t$具有恒定的条件号。
translated by 谷歌翻译
We study the fundamental task of outlier-robust mean estimation for heavy-tailed distributions in the presence of sparsity. Specifically, given a small number of corrupted samples from a high-dimensional heavy-tailed distribution whose mean $\mu$ is guaranteed to be sparse, the goal is to efficiently compute a hypothesis that accurately approximates $\mu$ with high probability. Prior work had obtained efficient algorithms for robust sparse mean estimation of light-tailed distributions. In this work, we give the first sample-efficient and polynomial-time robust sparse mean estimator for heavy-tailed distributions under mild moment assumptions. Our algorithm achieves the optimal asymptotic error using a number of samples scaling logarithmically with the ambient dimension. Importantly, the sample complexity of our method is optimal as a function of the failure probability $\tau$, having an additive $\log(1/\tau)$ dependence. Our algorithm leverages the stability-based approach from the algorithmic robust statistics literature, with crucial (and necessary) adaptations required in our setting. Our analysis may be of independent interest, involving the delicate design of a (non-spectral) decomposition for positive semi-definite matrices satisfying certain sparsity properties.
translated by 谷歌翻译
在这项工作中,我们在用户级差异隐私下研究高维平均值估计,并设计$(\ varepsilon,\ delta)$ - 使用尽可能少的用户差异化私人机制。特别是,即使用户数量低至$ o(\ frac {1} {\ varepsilon } \ log \ frac {1} {\ delta})$。有趣的是,这对\ emph {users}的数量绑定到独立于维度(尽管\ emph {samples aper users}的数量被允许以多项式依赖于尺寸),这与先前需要用户数量的工作数量不同。在多项式上依赖于维度。这解决了Amin等人首先提出的问题。此外,我们的机制可抵抗高达$ 49 \%用户的损坏。最后,我们的结果还适用于与少数用户私下学习离散分布的最佳算法,回答Liu等人的问题,以及更广泛的问题,例如随机凸优化和通过差异化的随机梯度优化和随机梯度下降的变体私人平均估计。
translated by 谷歌翻译
我们研究了在存在$ \ epsilon $ - 对抗异常值的高维稀疏平均值估计的问题。先前的工作为此任务获得了该任务的样本和计算有效算法,用于辅助性Subgaussian分布。在这项工作中,我们开发了第一个有效的算法,用于强大的稀疏平均值估计,而没有对协方差的先验知识。对于$ \ Mathbb r^d $上的分布,带有“认证有限”的$ t $ tum-矩和足够轻的尾巴,我们的算法达到了$ o(\ epsilon^{1-1/t})$带有样品复杂性$的错误(\ epsilon^{1-1/t}) m =(k \ log(d))^{o(t)}/\ epsilon^{2-2/t} $。对于高斯分布的特殊情况,我们的算法达到了$ \ tilde o(\ epsilon)$的接近最佳错误,带有样品复杂性$ m = o(k^4 \ mathrm {polylog}(d)(d))/\ epsilon^^ 2 $。我们的算法遵循基于方形的总和,对算法方法的证明。我们通过统计查询和低度多项式测试的下限来补充上限,提供了证据,表明我们算法实现的样本时间 - 错误权衡在质量上是最好的。
translated by 谷歌翻译
我们为其非私人对准减少$(\ 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算法,用于鲁棒学习(不受限制的)高斯。
translated by 谷歌翻译
我们研究了差异私有线性回归的问题,其中每个数据点都是从固定的下高斯样式分布中采样的。我们提出和分析了一个单次迷你批次随机梯度下降法(DP-AMBSSGD),其中每次迭代中的点都在没有替换的情况下进行采样。为DP添加了噪声,但噪声标准偏差是在线估计的。与现有$(\ epsilon,\ delta)$ - 具有子最佳错误界限的DP技术相比,DP-AMBSSGD能够在关键参数(如多维参数)(如多维参数)等方面提供几乎最佳的错误范围$,以及观测值的噪声的标准偏差$ \ sigma $。例如,当对$ d $二维的协变量进行采样时。从正常分布中,然后由于隐私而引起的DP-AMBSSGD的多余误差为$ \ frac {\ sigma^2 d} {n} {n}(1+ \ frac {d} {\ epsilon^2 n})$,即当样本数量$ n = \ omega(d \ log d)$,这是线性回归的标准操作制度时,错误是有意义的。相比之下,在此设置中现有有效方法的错误范围为:$ \ mathcal {o} \ big(\ frac {d^3} {\ epsilon^2 n^2} \ big)$,即使是$ \ sigma = 0 $。也就是说,对于常量的$ \ epsilon $,现有技术需要$ n = \ omega(d \ sqrt {d})$才能提供非平凡的结果。
translated by 谷歌翻译
我们研究了清单可解放的平均估计问题,而对手可能会破坏大多数数据集。具体来说,我们在$ \ mathbb {r} ^ $和参数$ 0 <\ alpha <\ frac 1 2 $中给出了一个$ $ n $ points的$ t $ points。$ \ alpha $ -flaction的点$ t $是iid来自乖巧的分发$ \ Mathcal {D} $的样本,剩余的$(1- \ alpha)$ - 分数是任意的。目标是输出小型的vectors列表,其中至少一个接近$ \ mathcal {d} $的均值。我们开发新的算法,用于列出可解码的平均值估计,实现几乎最佳的统计保证,运行时间$ O(n ^ {1 + \ epsilon_0} d)$,适用于任何固定$ \ epsilon_0> 0 $。所有先前的此问题算法都有额外的多项式因素在$ \ frac 1 \ alpha $。我们与额外技术一起利用此结果,以获得用于聚类混合物的第一个近几个线性时间算法,用于分开的良好表现良好的分布,几乎匹配谱方法的统计保证。先前的聚类算法本身依赖于$ k $ -pca的应用程序,从而产生$ \ omega(n d k)$的运行时。这标志着近二十年来这个基本统计问题的第一次运行时间改进。我们的方法的起点是基于单次矩阵乘法权重激发电位减少的$ \ Alpha \至1 $制度中的新颖和更简单的近线性时间较强的估计算法。在Diakonikolas等人的迭代多滤波技术的背景下,我们迫切地利用了这种新的算法框架。 '18,'20,提供一种使用一维投影的同时群集和下群点的方法 - 因此,绕过先前算法所需的$ k $ -pca子程序。
translated by 谷歌翻译
我们提出并分析了算法,以解决用户级差分隐私约束下的一系列学习任务。用户级DP仅保证只保证个人样本的隐私,而是保护用户的整个贡献($ M \ GE 1 $ Samples),而不是对信息泄漏提供更严格但更现实的保护。我们表明,对于高维平均估计,具有平稳损失,随机凸优化和学习假设类别的经验风险最小化,具有有限度量熵,隐私成本随着用户提供的$ O(1 / \ SQRT {M})$减少更多样本。相比之下,在增加用户数量$ N $时,隐私成本以较快的价格降低(1 / n)$率。我们将这些结果与下界相提并论,显示了我们算法的最低限度估计和随机凸优化的算法。我们的算法依赖于私有平均估计的新颖技术,其任意维度与误差缩放为浓度半径$ \ tai $的分布而不是整个范围。
translated by 谷歌翻译
我们介绍了一种基于约翰逊·林登斯特劳斯引理的统计查询的新方法,以释放具有差异隐私的统计查询的答案。关键的想法是随机投影查询答案,以较低的维空间,以便将可行的查询答案的任何两个向量之间的距离保留到添加性错误。然后,我们使用简单的噪声机制回答投影的查询,并将答案提升到原始维度。使用这种方法,我们首次给出了纯粹的私人机制,具有最佳情况下的最佳情况样本复杂性,在平均错误下,以回答$ n $ $ n $的宇宙的$ k $ Queries的工作量。作为其他应用,我们给出了具有最佳样品复杂性的第一个纯私人有效机制,用于计算有限的高维分布的协方差,并用于回答2向边缘查询。我们还表明,直到对错误的依赖性,我们机制的变体对于每个给定的查询工作负载几乎是最佳的。
translated by 谷歌翻译
我们在差分隐私(DP)的约束下,用重型数据研究随机凸优化。大多数关于此问题的事先工作仅限于损耗功能是Lipschitz的情况。相反,正如王,肖,德拉达斯和徐\ Cite {wangxdx20}所引入的那样,假设渐变的分布已涉及$ k $ --th时刻,我们研究了一般凸损失功能。我们在集中DP下提供了改善的上限,用于凸起的凸起和强凸损失功能。一路上,我们在纯粹和集中的DP下获得了私人平均估计的私有平均估计的新算法。最后,我们证明了私有随机凸性优化的近乎匹配的下限,具有强凸损失和平均估计,显示纯净和浓缩的DP之间的新分离。
translated by 谷歌翻译
在本文中,我们研究了代理人(个人)具有战略性或自我利益的情况,并且在报告数据时关注其隐私。与经典环境相比,我们的目标是设计机制,这些机制既可以激励大多数代理来真实地报告他们的数据并保留个人报告的隐私,而它们的输出也应接近基础参数。在本文的第一部分中,我们考虑了协变量是次高斯的情况,并且在他们只有有限的第四瞬间的情况下进行了重尾。首先,我们是受可能性功能最大化器的固定条件的动机,我们得出了一种新颖的私人和封闭式估计量。基于估算器,我们提出了一种机制,该机制通过对几种规范模型的计算和付款方案进行一些适当的设计具有以下属性,例如线性回归,逻辑回归和泊松回归:(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收缩运算符,我们提出了一种私人估算器和付款方案,该方案具有与次高斯案例相似的属性。
translated by 谷歌翻译
我们给出了\ emph {list-codobable协方差估计}的第一个多项式时间算法。对于任何$ \ alpha> 0 $,我们的算法获取输入样本$ y \ subseteq \ subseteq \ mathbb {r}^d $ size $ n \ geq d^{\ mathsf {poly}(1/\ alpha)} $获得通过对抗损坏I.I.D的$(1- \ alpha)n $点。从高斯分布中的样本$ x $ size $ n $,其未知平均值$ \ mu _*$和协方差$ \ sigma _*$。在$ n^{\ mathsf {poly}(1/\ alpha)} $ time中,它输出$ k = k(\ alpha)=(1/\ alpha)^{\ mathsf {poly}的常数大小列表(1/\ alpha)} $候选参数,具有高概率,包含$(\ hat {\ mu},\ hat {\ sigma})$,使得总变化距离$ tv(\ Mathcal {n}(n})(n}(n})( \ mu _*,\ sigma _*),\ Mathcal {n}(\ hat {\ mu},\ hat {\ sigma}))<1-o _ {\ alpha}(1)$。这是距离的统计上最强的概念,意味着具有独立尺寸误差的参数的乘法光谱和相对Frobenius距离近似。我们的算法更普遍地适用于$(1- \ alpha)$ - 任何具有低度平方总和证书的分布$ d $的损坏,这是两个自然分析属性的:1)一维边际和抗浓度2)2度多项式的超收缩率。在我们工作之前,估计可定性设置的协方差的唯一已知结果是针对Karmarkar,Klivans和Kothari(2019),Raghavendra和Yau(2019和2019和2019和2019和2019年)的特殊情况。 2020年)和巴克西(Bakshi)和科塔里(Kothari)(2020年)。这些结果需要超级物理时间,以在基础维度中获得任何子构误差。我们的结果意味着第一个多项式\ emph {extcect}算法,用于列表可解码的线性回归和子空间恢复,尤其允许获得$ 2^{ - \ Mathsf { - \ Mathsf {poly}(d)} $多项式时间错误。我们的结果还意味着改进了用于聚类非球体混合物的算法。
translated by 谷歌翻译