高维函数隐私评估新突破：输出保证落在凸包内，还改进经典采样聚合基线！
Private Evaluation of High-Dimensional Functions
📖 AI 总结
该论文研究高维任意函数的差分隐私黑盒求值问题。给定数据集S及对函数f的查询访问权限（其敏感度可能未知或无界），目标是在仅能查询S的下邻域（即从S中删除有限个元素所得子集）上f取值的限制下，隐私地输出f(S)的近似值。作者通过归约到高维隐私拟凹优化，为纯差分隐私和近似差分隐私分别设计了通用黑盒求值器，并给出几何效用保证：求值器输出以高概率落在下邻域函数值向量的凸包内。该工作将Linder等人关于实值函数求值的结果推广到高维，同时恢复了Beimel等人的隐私中心点保证并给出最大Tukey深度的显式加性近似。在用户级拟凹与凸优化应用中，该方法以加性数据开销替代了Nissim等人采样聚合基线的乘性开销。作者进一步证明高维黑盒求值与高维隐私拟凹优化在相差维度因子的意义下等价，最难的求值实例恰来自f为非隐私拟凹优化器的情形。
🔑 关键词速览
| 差分隐私 | 一种隐私保护框架，确保算法输出对数据集中单个记录的更改不敏感。 |
| 黑盒评估 | 仅通过查询访问函数值来评估函数，而不了解其内部结构。 |
| 拟凹优化 | 优化拟凹函数的问题，拟凹函数的上水平集是凸集。 |
| Tukey深度 | 一种稳健的统计深度度量，用于衡量点在高维数据分布中的中心性。 |
| 采样聚合 | 一种隐私保护技术，将数据分成子样本，对每个子样本计算统计量，然后聚合结果。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅