【NeurIPS 2021】差分プライバシーの不確定性原理
TL;DR
差分プライバシーを満たすpoint queryとsum queryの間に不確定性関係があることを示した論文
それぞれのクエリの平均二乗誤差を定量的に評価し、片方の平均二乗誤差を小さくしようとすると、もう一方の平均二乗誤差の下界が存在することを提示
はじめに
本文
論文タイトルにもあるようにMicrodata（差分プライバシー（以下、DP）によって保護されたデータ）に対する不確定性原理を提唱している。この不確定性原理はpoint queryとsum queryの誤差を一定以下にできないという不確定性関係を示したものだ。以下で詳しくみていく。
まずpoint queryとsum queryについて述べる。本論文は著者が米国国勢調査局に所属していることもあり、例としても米国国勢調査が使われている。米国国勢調査の統計は、国勢調査細分区（census block）という地理的な最小単位に基づいて行われる。このblock単位の人口数を算出するクエリをpoint queryと呼んでいる。対して、block単位ではなくすべてのblockに対して一括でノイズ付きの人口数を得るクエリがsum queryである。
これらのクエリにはプライバシー保護のためDPのメカニズムに応じてノイズが付与されるが、point queryとsum queryの間にはノイズ付与による真値との平均二乗誤差に不確定性関係が存在するというのが本論文の内容だ。定式的には以下の表現となる
notation
$ M: ランダムアルゴリズム（ただし、出力は入力データセットを正の重み付けしたものに限る）
$ \mathcal{D}: データセット
$ q_1, \dots, q_d : 各blockに対するクエリ
$ q_*: 全blockに対するクエリ
上記notationを用いてある値$ C, Dを以下のように考える
$ E[(q_i(\mathcal{D}) - q_i(M(\mathcal{D})))^2] \leq C^2
$ E[(q_*(\mathcal{D}) - q_*(M(\mathcal{D})))^2] \leq D^2
このとき、$ Mをε-DPを満たすようにとると任意の$ k > 0に対して以下が成り立つ
$ e^{2 \epsilon (2C + k)} \geq \frac{k(d-1)}{16C+8D+4k}
上式の解釈を考える。
仮に全blockの平均二乗誤差を一定以下に抑えるため、ある定数$ \lambdaを用いて$ D^2 \leq \lambda / \epsilon^2となるようにする。このとき、$ C^2 \in \Omega(\frac{1}{\epsilon^2} log^2(d))となり、各blockの平均二乗誤差の下界が抑えられてしまう。
逆に各blockの平均二乗誤差を一定以下に抑えるため、ある定数$ \lambdaを用いて$ C^2 \leq \lambda / \epsilon^2となるようにする。このとき、$ D^2 \in \Omega(\frac{d^2}{\epsilon^2})となり、全blockの平均二乗誤差の下界が抑えられてしまう。
このようにしてpoint queryとsum query、どちらか片方の平均二乗誤差を小さくしようとすると、もう一方の平均二乗誤差の下界が存在することを提示している。今回はε-DPについて紹介したが、論文中では(ε, δ)-DP、ρ-zCDPに対する不確定性原理についても議論がなされている。
この不確定性原理はランダムアルゴリズムの出力が入力データセットに対して正の重み付けをしたものであることを前提にしており、この不確定性関係を避けるために負の重み付けを許容することも注釈されている。（文責・恩田）