行列を出力するクエリで差分プライバシーを実現するMVGメカニズム
TL;DR
差分プライバシーを満たしつつ、行列を出力するクエリに対する行列変量正規分布ノイズの扱いを定式化
差分プライバシーを満たす条件がrowとcolumnの共分散行列の固有値のみに依存することを示す
はじめに
差分プライバシーで扱うクエリは出力にスカラー値を取るものを扱うことが多く、メカニズムとしてもLaplaceメカニズムやGaussianメカニズムが伝統的だ。クエリの出力を複数にしたい場合には、値域の各次元に対して加えるノイズは独立同分布（以下、i.i.d.）とすることが多く、この方法を取ることでベクトルの出力を扱うことができる。
本文
メカニズムの分類
データ分割と統合
adaptive queries
メカニズムのカテゴライズ
basic mechanisms
例）
Laplace Mechanism
Gaussian Mechanism
Johnson-Lindenstrauss Transform
Exponential Mechanism
derived mechanisms
revised mechanismsとも
basic mechanismにcomposition theremsやpost-processing propertyを適用して、応用したもの
目的
Sensitivityの制御
worst-case sensitivityを避けるもの
例）
smooth sensitivity
elastic sensitivity
データの分割と統合
データ（columnやrow）の重み付け
Matrix-Variate Gaussian (MVG) メカニズム
行列変量正規分布を使ってノイズを加える
$ p_{\chi}(\bm{X}) = \frac{\mathrm{exp\{-\frac{1}{2} \mathrm{tr}[\bm{\Psi}^{-1}(\bm{X}-\bm{M})^T\Sigma^{-1}(\bm{X}-\bm{M})] \}}}{(2 \pi)^{mn/2} |\bm{\Psi}|^{m/2} |\Sigma|^{n/2}}
ここで
dataset: $ \bm{X} \in \mathbb{R}^{M\times N}
mean: $ \bm{M} \in \mathbb{R}^{M\times N}
row-wise covariance: $ \Sigma \in \mathbb{R}^{m\times m}
column-wise covariance: $ \bm{\Psi} \in \mathbb{R}^{n\times n}
m=2, n=2に対して、matrix-valued query function: $ f(\bm{X}) \in \mathbb{R}^{m\times n}に対してノイズを加える例は以下の通り
https://gyazo.com/381c0ba89279ccc849b53e17c6551b30
（論文中より引用）
このとき、L2-sensitivityを以下のように定義することができる
$ s_2 (f) = \underset{d(X_1, X_2)=1}{\mathrm{sup}}|| f(X_1) - f(X_2) ||_F
ここで$ ||\cdot||_FはFrobenius normで$ a_{ij}成分を持つ行列Aでは以下のように計算できる
$ ||A||_F = \sqrt{ \sum_i \sum_j |a_{ij}|^2 }
ここで以下表のような表記を導入する
https://gyazo.com/9fc8fee204e9eb6859a0b8532a7e28c7
（論文中より引用）
上記表の表記を用いて、MVGメカニズムが(ε, δ)-差分プライバシーを満たす条件は以下のようになる
$ || \bm{\sigma}(\Sigma^{-1}) ||_2 || \bm{\sigma(\Psi^{-1}}) ||_2 \leq \frac{(-\beta + \sqrt{\beta^2+8\alpha \epsilon} )^2}{4 \alpha^2}
ここで
$ \alpha = [H_r + H_{r, 1/2}]\gamma^2 + 2 H_r \gamma s_2(f)
$ \beta = 2(mn)^{1/4} H_r s_2(f) \xi(\delta)
ここで重要な点がprivacy保証が$ \Sigmaと$ \bm{\Psi}の固有値にのみ依存しているという点（不等式の左辺）だ。これによってrow、columnの固有ベクトルを基底に取ったときのノイズを独立して考えることが可能になる。また固有ベクトル方向に独立であるが、元の空間ではrow方向にもcolumn方向にも相関した柔軟なクエリを表現できていることになる。
https://gyazo.com/4636b1ad71e7ecbb08e62c4e28112b56
（論文中より引用）
実験
本論文では3つのデータセットに対して、回帰、第一主成分、共分散推定の実験を行っている。評価は以下表の Eval. metric に記載の指標を用いて行っている。またε=1、δ=1/Nとして実験している。
https://gyazo.com/ddb64e4c91368eac4191a5589ef0834b
（論文中より引用）
ここではExp. Iの結果のみを紹介する（残り2つも類似の結果となっている）。Laplace、Exponentialに対しては1.5倍程度RMSEが小さくできている。またGaussianやJL transformに対しても優れた結果となっている。
https://gyazo.com/f825a27715349cc3b56f7e026bed2d6d
（論文中より引用）
終わりに
行列変量正規分布を用いたノイズを加えることで柔軟なクエリを実現できる点は非常に興味深い。また(ε, δ)-差分プライバシーを満たす条件がrowとcolumnの共分散行列の固有値にのみ依存しており、この条件は各固有値の逆数（= precision）の2乗和で表現できることについても触れられていた。これは各次元に対してどの程度のprecision budgetを割り当てるか、次元ごとに独立して考えられることを示しており、その点でも興味深い内容だ。