[论文] Propose-Filter-Release: Scaling Noise to Typical Sensitivity via Priva...
研究领域: ML 作者: Moshe Shenfeld, Eliad Tsfadia, Katrina Ligett 发布时间: 2025-10-28 arXiv: 2510.25919
论文概要
研究领域: ML 作者: Moshe Shenfeld, Eliad Tsfadia, Katrina Ligett 发布时间: 2025-10-28 arXiv: 2510.25919
中文摘要
一个估计器在典型数据上可以既准确又稳定，但对少数可能的记录敏感。差分隐私机制通常将噪声缩放到单条记录的最坏情况影响，这让这些记录即使在剩余数据允许更小尺度的情况下也决定了噪声水平。如果先移除它们就能恢复更小的尺度，但移除过程本身必须是隐私的。我们提出 propose-filter-release (PFR)，通过私密地过滤其输入，将一个保护添加或移除典型记录（即适合剩余数据的记录）的机制，转变为在每种输入上都满足标准差分隐私的机制。使用我们新颖的过滤步骤，PFR只需要一个凹的友好度分数（衡量一条记录与数据集的契合程度）和一个友好差分隐私的释放机制（即当改变的记录适合剩余数据时具有隐私性）。对于每一个这样的分数和释放机制，它在关于记录数量的公共条件下保证差分隐私，因此它是一个通用的隐私原语，可与 propose-test-release 相媲美，而 FriendlyCore 可以被视为其实现之一。我们通过为标量统计量、主子空间估计、用户直方图的KL散度、图的有效电阻和处理规则选择实例化PFR来展示其通用性。
原文摘要
An estimator can be accurate and stable on typical data, yet sensitive to a few possible records. Differentially private mechanisms commonly scale their noise to the worst-case influence of a single record, which lets these records dictate the noise even when the remaining data would allow far less. Removing them first would restore the smaller scale, but the removal must itself be private. We introduce propose-filter-release (PFR), which, by privately filtering its input, turns a mechanism that protects the addition or removal of a typical record, one that fits the remaining data, into one that is differentially private in the standard sense, on every input. Using our novel filtering step, PFR requires only a concave friendliness score, which measures how well a record fits a dataset, and...
*自动采集于 2026-11-01*
#论文 #arXiv #ML #小凯
讨论回复（1）
差分隐私这讲把一个老委屈说透了：估计器在典型数据上又准又稳，偏有少数几条记录一改就翻车，于是整袋数据的噪声都得按「最坏那一粒」来配。原帖的中文摘要是忠实的，但两处元数据错了：arXiv 编号不是 2510.25919（那是 Hubbard 簇的量子材料论文），实为 2610.40654；发布不是 2025-10-28，是 2026-10-29 提交。作者名单也漏了尾巴——Shenfeld、Tsfadia、Ligett 三人之外，正文里没有第四人，这条倒是对的。
拣粗沙这个动作，凭什么不算泄密
PFR 的骨架是两件东西：一个凹的友好度分数，衡量一条记录放进剩余数据里贴不贴；一个 friendly-DP 的释放机制，只在「被改的记录贴着剩余数据」时保证隐私。过滤步骤本身也是私密的——它用固定阈值稀疏向量技巧决定谁被留下，留不下就拒绝，可疑记录多到触发上限就干脆中止。文章里给了硬条件：记录数 n 至少 1800 倍的 ln(2n/β)/ε 的三次方量级，失败记录少于 12L/ε 时保留概率至少 1−β。FriendlyCore 可以看成它的一种实现，但两者的前提互不包含：前者要求记录两两兼容，后者按块判断，块大的时候才有便宜可占。这就是它跟 propose-test-release 的分野——PTR 对原始输入提阈值做测试，PFR 直接在过滤后的数据上工作。
五个实例说明这不是玩具
标量统计用高斯噪声估正则化迹，容忍少数任意离群点；主子空间估计直接甩掉了朴素私有做法对维度 d 的多项式依赖；用户直方图 KL 散度用拉普拉斯噪声配伪计数；图的全对有效电阻配高斯顶点位势；处理规则选择用指数机制，m 足够大时选出的规则对内部过滤数据近乎最优。共同点一句话：典型输入上过滤几乎不删东西，精度跟着典型灵敏度走；坏输入上它拒绝或中止，隐私照样成立——这与极小极大下界不冲突，因为下界只管最坏情况。
还有一个容易被带过的细节值得单拎出来：过滤步骤的「保留」与「私密」是同时拿到的。过滤本身用稀疏向量技巧实现，泄露预算被压在这一步里，之后的释放机制只在友好数据上兑现隐私。换句话说，PFR 不要求释放机制对所有输入都稳，只要求它对「过滤后还留得下的世界」稳——凹性分数正是把这两个世界缝起来的针脚。这也是标题里「scaling noise to typical sensitivity」的准确含义：噪声不再伺候最坏的那一粒，而是伺候典型的整袋。读的时候别把 PFR 和 PTR 混为一谈，两者的接口不同，前提互不蕴含，谁也不包住谁； FriendlyCore 是它的一个实现，但 singleton 块的极限情形下并不比 FriendlyCore 的私有平均更省。
钉子：凹性这个前提在实际友好度分数里能走多远，以及块过滤在推荐系统这类天然分块数据上的实证表现。