基于 Wishart 机制的差分隐私主成分分析
本文提出了单一实值查询函数的最优 ε- 差分隐私机制,其噪声概率分布类具有楼梯形状、对称性、单调递减和几何衰减,可以被视为均匀概率分布的几何混合,并将此机制自然地推广到了离散查询输出环境和更抽象的环境中。通过将最优性能与拉普拉斯机制的性能进行比较,我们得出结论,当 ε 趋近于 0 时,拉普拉斯机制是渐近最优的;而在 ε 趋近于 +∞时,最小噪声振幅和最小噪声功率分别为 Θ(Δe^-ε/2) 和 Θ(Δ^2 e^-2ε/3),而拉普拉斯机制的噪声振幅和功率期望分别为 Δ/ε 和 2Δ^2/ε^2,在低隐私保护级别下获得更明显的收益。
Dec, 2012
本文探讨了不同 ially private PCA 方法的理论和实证性能,并提出了一种明确优化输出效用的新方法。我们发现其样本复杂度与现有程序的不同之处在于其与数据维度的缩放,而且在实际数据中,该方法与现有方法相比具有较大的性能差距。
Jul, 2012
本文提出了一种基于差分隐私算法的,可有效从高维数据集中生成低维合成数据的方法,通过运用私有主成分分析过程并保证符合 Wasserstein 距离的实用性保障,避免了维度诅咒问题。
May, 2023
提出了一种使用后验抽样和近似采样方法相结合的算法,通过引入噪声来保持隐私性,并结合局部化步骤,在 DP-ERM 问题中实现了最佳的速率。
Oct, 2023
本文提出并研究了高斯机制的一种复杂变体,通过使用该变体输出的矩阵与 $M$ 的最佳秩 - k 近似之间的 Frobenius 范数之差被限制在大约 $\tilde {O}({\sqrt {kd}})$,这可以改善先前的工作,前者需要每对 $M$ 的前 k 个特征值之间的差异至少为 $\sqrt {d}$,而后者仅需要相邻的前 k 项的差异。
Jun, 2023
本文针对高维情况下的差分隐私数据分析算法中的高斯机制,提出了一种经过优化的高斯机制,通过解决其方差在隐私程度较高和较低的限制,直接利用高斯累积分布函数进行方差校准,采用基于自适应估计技术的后处理步骤实现抑噪,实验证明该方法相比于经典高斯机制,能减少至少三分之一的噪声方差,并且在高维情境下能够显著提高其精确性。
May, 2018
在统计分布设置中,研究了 PCA 的基本问题,介绍了一种在计算效率和估计误差方面都优于局部 ERM 解决方案的算法,通过进行简单的校正步骤来消除误差并提供一种估计器,还介绍了一种使用分布式矩阵向量乘法的迭代分布式算法,提供在广泛的参数范围内通信轮次的显着加速。
Feb, 2017
提供严格多项式时间的离散算法,用于近似分类数据集的直方图,同时保留与拉普拉斯机制相同的(纯)差分隐私保证,并基于受限离散计算模型,避免了基于实际算术的不同隐私算法攻击实现的可能性。
Sep, 2017