稳定凸松弛法私有鲁棒估计

Dec, 2021

Private Robust Estimation by Stabilizing Convex Relaxations

Pravesh K. Kothari, Pasin Manurangsi, Ameya Velingker

TL;DR提出了一种新的框架，以将鲁棒性的凸松弛算法修改为满足适当参数规范的强最坏情况稳定性保证。通过这一框架，提出了一个可以在存在恶意数据干扰下实现微分隐私的高阶矩的鲁棒估计的算法，包括均值和协方差的估计。该算法成功地应用于成族分布，并在适当参数范数下提供恢复和维度参数的从容保证。

Abstract

We give the first polynomial time and sample $(\epsilon, \delta)$-differentially private (DP) algorithm to estimate the mean, covariance and higher moments in the presence of a constant fraction of adversarial outliers. Our algorithm succeeds for families of distributions that satisfy

differential privacy robust estimation outliers semidefinite programming covariance estimation

发现论文，激发创造

近线性时间高维鲁棒均值估计

本文针对高维下平均数估计的稳健模型、对抗性污染和相应算法进行研究，提出了一种基于当前猜测值参数化的 SDP 族的自然算法，并经证明该算法在次线性时间内逼近真实平均数并达到了理论误差的信息论最优解，同时认为该算法还能进一步实现高维稳健学习问题的次线性时间算法。

Nov, 2018

重尾数据的差分隐私随机凸优化的改进速率

本文研究带有重尾数据的随机凸优化问题，并在差分隐私（DP）约束条件下进行研究。该文提出了一种新的算法用于估计重尾数据的均值，并针对凸损失函数提供了改进的上界。同时，证明了私密随机凸优化的几乎匹配下界，这表明了纯 DP 和集中 DP 之间的新分离。

Jun, 2021

更好、更简单的差分隐私统计估计下界

通过指纹技术和贝叶斯方法，我们改进了高维度隐私估计的下界。我们提出了计算高斯协方差和重尾分布均值的样本数量下界，并与先前工作的结论进行了比较。

Oct, 2023

不需要私有协方差估计的协方差感知私有均值估计

提出两种样本有效的差分隐私均值估计器，可用于具有未知协方差的 $d$ 维（子）高斯分布。这些估计器是基于一种简单通用的设计差分隐私机制的方法实现的，但需要新颖的技术步骤使其保持隐私和有效性。

Jun, 2021

学习高斯及更高模型的私有与多项式时间算法

提出了一个将差分隐私统计估计转化为无差分隐私的框架，并给出了用于学习高斯分布和鲁棒学习高斯分布的多项式时间差分隐私算法，该方法中学习高斯分布的样本复杂度和已知的信息论样本复杂度的上限相匹配，并且还证明了相似的结果，其中鲁棒学习高斯分布的样本复杂度更低。

Nov, 2021

基于平方和的异常值稳健矩估计

在存在对抗离群值的情况下，我们开发了有效的算法来估计未知分布的低阶矩。这些算法的保证在许多情况下显著优于 Diakonikolas 等人、Lai 等人和 Charikar 等人的最佳先前算法，同时我们还展示了这些算法的保证与我们考虑的分布类别的信息论下界相匹配，这些改进的保证使我们能够在存在离群值的情况下提供改进的独立成分分析和学习混合高斯的算法，我们的算法基于对下面概念简单优化问题的标准平方和松弛：在所有矩与未知分布相同的分布中，找到与对抗性污染样本的经验分布在统计距离上最接近的分布。

Nov, 2017

一种能处理无界高斯分布、隐私安全且计算高效的估算器

本文提出了一种多项式时间、多项式采样、差分隐私的算法，用于估计任意高斯分布的均值和协方差，且不需要先验参数范围。该算法的主要技术工具是一种新的差分隐私的预处理器，可以从任意的高斯分布中取样并返回一个矩阵 A，使得 A × Σ × A^T 具有固定的条件数字。

Nov, 2021

基于个体级差分隐私的私有均值估计

研究多样本时的差分隐私均值估计，在用户级别设置下，给出了人数的必要和充分条件以实现在 ε- 差分隐私（及其常见松弛条件）下在ℓ2 范数中以距离 α 估计均值的结果，并提供了近似差分隐私的高效算法（在样本复杂性上略有降低）和纯差分隐私的低效算法的计算方法和边界分析。

May, 2024

带重尾数据的差分隐私随机凸优化

本文提出了一种基于采样和聚合框架的方法和基于梯度平滑和剪枝的方案，可有效应对重尾型数据下的不规则性挑战，实现了强凸和一般凸损失函数的差分隐私，且在高概率下应达到预期的超额群体风险水平。

Oct, 2020

具有亚高斯速率的均值估计的快速谱算法

研究估计具有有界平均值和协方差的重尾随机向量均值的算法问题，提供了一种基于谱方法的算法来解决该问题，并且只需要计算近似特征向量，取得了最优的统计性能和更快的运行速度。

Aug, 2019