A Simple and Practical Algorithm for Differentially Private Data Release
Moritz Hardt Katrina Ligett Frank McSherry
Abstract
We present a new algorithm for differentially private data release, based on a simple combination of the Exponential Mechanism with the Multiplicative Weights update rule. Our MWEM algorithm achieves what are the best known and nearly optimal theoretical guarantees, while at the same time being simple to implement and experimentally more accurate on actual data sets than existing techniques.
中文速览
差分隐私（differential privacy）领域长期面临一个难题：现有算法要么理论保证强但实际噪声太大，要么针对特定场景设计而缺乏通用性。MWEM 算法将两个经典工具巧妙结合——用指数机制（Exponential Mechanism）挑选当前近似数据集与真实数据集差距最大的查询，再用乘法权重更新规则（Multiplicative Weights update rule）迭代修正近似数据集，从而在消耗最少隐私预算的前提下，让合成数据尽快逼近真实分布。理论上，该算法在计数查询场景下达到了已知最优且近乎紧的误差界；实验上，在范围查询、列联表发布、数据立方体发布等多个真实数据集上，精度比现有方法提升最高三个数量级。更难得的是，该算法实现简单、易于并行化，借助因子化表示可处理属性数达千量级、域大小高达 2¹⁰⁰⁰ 的大规模数据集，为隐私保护数据发布提供了兼具理论严谨性与工程实用性的新基准。
原文 arXiv:1012.4763;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1012.4763v2