Feb, 2018

Hadamard Response：高效、低通信、隐私保护的分布估计

PDF
TL;DR该论文提出了一种名为 Hadamard Response 的本地隐私保护方案，可在高隐私水平下使用，并在所有 ε 下具有最优的样本复杂度，通信不超过每个用户的 log k + 2 位，并且具有几乎线性的运行时间，该方案的编码和解码基于 Hadamard 矩阵，其统计性能依赖于编码理论方面的因素。
local differential privacyhadamard responsesample complexitycoding theoryfast walsh-hadamard transform
发现论文，激发创造
  • 局部隐私分布估计和重要元素中的通信复杂度

    本文研究在保障隐私和通讯限制下分布估计和重头分估计的问题，提出了使用局部差分隐私的样本最优方案，并表明 Hadamard 反应方案可以用于重头分估计。

    May, 2019

  • 局部差分隐私下的离散分布估计最优方案

    本文研究在隐私限制下，离散分布的 Minimax 估计问题。通过将保密方案分别应用于每个原始样本，我们需要从保密样本中估计原始样本的分布。对于给定的 ε，我们考虑构造具有 ε- 隐私级别、即能够最小化最坏情况下的预期估计损失的最优保密方案问题。本文提出了一种新的保密方案族，它在中等隐私度量 ε 的情况下显著提高了现有方案的性能。

    Feb, 2017

  • 打破通信 - 隐私 - 准确性三难题

    该研究提出了一种基于 Kashin 表示和随机抽样的方案以及利用 Walsh-Hadamard 矩阵的递归结构来实现隐私和通信效率的联合优化编码和解码机制，对平均值估计和频率估计等问题进行了研究。

    Jul, 2020

  • 局部隐私条件下的离散分布估计

    本文探讨了在隐私保护下进行离散分布估计的机制，提出了一种新的哈希 K-ary 随机响应（KRR）机制，并证明其与已有机制相比，在所有隐私级别上都可以实现更优的效果。同时，本文还探究了 KRR 和已有的 RAPPOR 机制在不同隐私保护级别下的效果与顺序最优性。

    Feb, 2016

  • 来自匿名消息的私人计数：凭借消失通信开销的接近最优准确性

    本文介绍了中心模型、本地 DP 模型和洗牌 DP 模型，并提出了在洗牌 DP 模型下用于机器学习的两种基本聚合方法，其精度接近中心 DP 算法，而通信效率与不加隐私约束的通信需求基本匹配。

    Jun, 2021

  • 基于通信复杂度的局部隐私估计的下限

    本文为研究局部隐私约束下的估计方案制定下限，推导出了私有估计和受通信限制的估计问题之间的等价性，适用于任意交互的隐私机制，并且得出了所有不同隐私保护级别的尖锐下限。作者作为对研究结果的一个重要推论，证明了有界或高斯随机向量的均值估计的最小最大均方误差按比例缩放的结论为 $d/n * d/min (ε,ε^2)$ 。

    Feb, 2019

  • 私人和通信高效的熵估计算法

    本文提供了针对现代统计估计的改进的隐私保护算法和通信效率算法，包括用于估计分布熵的算法和用于通信效率估计基尼熵的算法，并基于现有最佳算法推广了一种用于碰撞熵估计的算法，满足局部差分隐私。

    May, 2023

  • 无信任测试：最优的本地隐私分布测试

    本研究针对分布测试问题，考虑使用本地差分隐私机制时的样本，并着重研究离散分布的两个代表性测试问题：完全匹配性检验和独立性检验。我们提出了基于 RAPTOR 和 RAPPOR 等机制的测试，并分析了它们的样本复杂度，我们的算法利用的是公共硬币且样本最优。

    Aug, 2018

  • 本地化隐私高斯估计

    研究局部差分隐私在高斯分布参数估计中的应用，并给出了自适应的两轮解决方案和非自适应的一轮解决方案，并通过信息理论下界证明了准确性保证的紧密性。

    Nov, 2018

  • 私有假设选择

    提出一种差分隐私算法，用于假设选择和生成学习算法，可处理各种自然分布类，包括高斯分布、分布乘积、独立随机变量的和、分段多项式和混合类，这种算法的样本复杂度最优。

    May, 2019