关于 $l_p^p$ 度量下矩阵机制的最优性
本文研究了差分隐私机制在 $d$ 个非适应性线性查询的噪音复杂度,使用几何参数给出了噪音复杂度的上下界,并根据凸几何学中的超平面猜想证明了任意线性查询的结果,提高了先前的结果,揭示了差分隐私概念与近似差分隐私概念之间的分离。
Jul, 2009
通过使用关联的高斯噪声和线性回归步骤,我们基于差分隐私机制的多项式对数组进行了矩阵突触连接和遗传差异,从而在线性查询的上下文中研究了准确性和隐私之间的权衡。
Dec, 2012
研究了通过矩阵机制方法,针对支持一组特定数量的问题而调整的合成数据集,在差分隐私下生成合成数据的方法及其对解析一组线性计数查询的困难度的影响,发现查询量的难度与行列式物理特性相关。
Feb, 2012
该研究通过指定参数 delta 来构建一个全新的下界,从而优化(epsilon,delta)差分隐私算法在高维数据库上精确回答统计查询的样本复杂度。除了新的下界之外,该研究还提出了纯粹和近似的差分隐私算法,用于回答任意统计查询,并通过对比标准拉普拉斯和高斯机制在最坏情况下精度保证方面的样本复杂度,改善了对该问题的解决方法。
Jan, 2015
本文介绍了高维矩阵机制(HDMM),它是一种用于回答谓词计数查询的差分隐私算法。HDMM 使用紧凑的隐含矩阵表示查询工作负载,并利用此表示来高效地优化差分隐私算法的子集,从而呈现出低期望误差和不偏倚结果。在实证上,HDMM 能够高效地回答查询,期望误差要比最先进的技术低,并且在某些情况下,几乎与我们考虑的机制类别的现有下限相匹配。
Jun, 2021
本文提出了单一实值查询函数的最优 ε- 差分隐私机制,其噪声概率分布类具有楼梯形状、对称性、单调递减和几何衰减,可以被视为均匀概率分布的几何混合,并将此机制自然地推广到了离散查询输出环境和更抽象的环境中。通过将最优性能与拉普拉斯机制的性能进行比较,我们得出结论,当 ε 趋近于 0 时,拉普拉斯机制是渐近最优的;而在 ε 趋近于 +∞时,最小噪声振幅和最小噪声功率分别为 Θ(Δe^-ε/2) 和 Θ(Δ^2 e^-2ε/3),而拉普拉斯机制的噪声振幅和功率期望分别为 Δ/ε 和 2Δ^2/ε^2,在低隐私保护级别下获得更明显的收益。
Dec, 2012
本文提出了第一个用于回答批量线性查询的实用差分隐私技术,即低秩机制 (LRM),它适用于确切和近似差分隐私定义,并提供对 LRM 的实用性保证,同时提供如何根据用户的实用预期设置隐私参数的指导。与差分隐私下的最新查询处理解决方案相比,这种方法在真实数据上的大规模实验中表现出了更高的准确性。
Feb, 2015
本文研究了在非交互式局部差分隐私(LDP)模型下经验风险最小化(ERM)问题,利用 Bernstein 多项式逼近方法和内积多项式逼近技术提出了两种解决高维数据下样本复杂度指数级上升的方法,最终提出了用于学习 k 维边际查询和平滑查询的(高效的)非交互式局部差分隐私算法。
Nov, 2020