Estimating Numerical Distributions under Local Differential Privacy

[ShuntaIshihara]

• 論文タイトル Estimating Numerical Distributions under Local Differential Privacy
• 著者（所属） Zitao Li(PurdueUniversity), Tianhao Wang(PurdueUniversity), Milan Lopuhaa ̈-Zwakenberg(EindhovenUniversityofTechnology), Boris Skoric(EindhovenUniversityofTechnology), Ninghui Li(PurdueUniversity)
• 論文PDF／ランディングページへのリンク https://arxiv.org/pdf/1912.01051.pdf

• 論文まとめ（落合フォーマット準拠）

  • どんなもの？
    • LDP（ローカル差分プライバシー）の下で数値ドメインの分布を再構築する問題を調査し，提案手法である矩形波メカニズム（SW）と期待値最大化法，平滑化法（EMS）を組み合わせた手法が幅広いメトリックにおいて高いパフォーマンスを発揮することを示す．
    • 先行研究の改良版であるHH-ADMMという手法も提案する．
  • 先行研究と比べてどこがすごい？ 既存手法では，カテゴリカルドメインにフォーカスを当てた手法がほとんどであり，数値ドメインに対応させるためには離散化を適用してからカテゴリカルドメインと同様の手法を使うというやり方が考えられる．しかし，プライバシーパラメータとデータ分布に依存する最適なビンの数を見つけるのが大変．そこで，複数の粒度を同時に利用する階層型ヒストグラムを適用して，異なる粒度での推定値の間の自然な一貫性関係を利用することで改善する手法がある．しかし，LDPの大きなノイズのため推定値が負になるものがあり，これらの手法はこれをそのまま利用するので適切ではない．
  • 先行研究と比べてどこがすごい？
    • HH-ADMMでは，階層ヒストグラムベースの手法を改善したもの．これは全ての推定値が負ではなく，合計すると１になるという制約を利用して，階層ヒストグラムをを改善するために，交互方向乗数法（ADMM）を適用することを提案している．
    • 研究課題は、ドメインの順序付けられた性質を直接利用し，より良い推定を生成するプロトコルを設計できるかどうか．この論文では，これを肯定的に答えている．矩形波レポートメカニズムと呼ばれるものを，期待値の最大化と平滑化を使用する後処理と組み合わせるアプローチを提案している．
  • どうやって有効だと検証した？
    • 矩形波以外の一般的な波のメカニズムのさまざまな波形について定義して調査し，矩形波が最も有用であると結論付けた． また，重要なパラメータb，つまり波の幅を決定する方法についても検討した．入力変数と出力変数の間の相互情報量の上限を最大化するようにbを選択することを提案し，プライバシーパラメータεが与えられたときにbを計算できる．
    • 提案手法を最先端の手法と比較して、広範な実験的評価を実施したところ，EMSとHH-ADMMを備えたSWが既存の方法を大幅に上回っていることを示した．さらに，EMSを備えたSWは一般に，幅広いメトリックの下で高いパフォーマンスを発揮し，HH-ADMMは，急激に上昇する分布（スパイク）でSW-EMSよりも優れたパフォーマンスを発揮している．
  • 議論はある？
    • 一次元データのみを対象としている印象なので，二次元，三次元データに応用できるのかどうか
    • 時系列データにはどうなのであろうか

  • 次に読むべき論文は？

    • J.Acharya,Z.Sun,andH.Zhang.Hadamardresponse:Estimatingdis- tributions privately, efficiently, and with little communication. arXiv preprint arXiv:1802.04705, 2018.

    • R. Bassily and A. D. Smith. Local, private, efficient protocols for succinct histograms. In STOC, 2015.

    • U.Erlingsson, V.Pihur, and A.Korolova. RAPPOR : randomize daggre-gatable privacy-preserving ordinal response. In CCS, 2014.

    • T. Wang, J. Blocki, N. Li, and S. Jha. Locally differentially private protocols for frequency estimation. In USENIX Security, 2017.

    • M.YeandA.Barg.Optimal schemes for discreted istribution estimation under locally differential privacy. IEEE Transactions on Information Theory, 2018.

    • T. Kulkarni, G. Cormode, and D. Srivastava. Answering range queries under local differential privacy. PVLDB, 2019.

    • M.Hay, V.Rastogi, G.Miklau,and D.Suciu. Boosting the accuracy of differentially private histograms through consistency. PVLDB, 3(1), 2010.

    • W.H.Qardaji,W.Yang,andN.Li.Understandinghierarchicalmethods for differentially private histograms. PVLDB, 6(14), 2013.

    • X. Xiao, G. Wang, and J. Gehrke. Differential privacy via wavelet transforms. In ICDE, 2010.

    • LDPの開発について

      • A.D.P.Team.Learningwithprivacyatscale,2017.
      • U. Erlingsson, V.Pihur, and A.Korolova. RAPPOR: randomize daggre-gatable privacy-preserving ordinal response. In CCS, 2014.
      • B.Ding, J.Kulkarni, and S.Yekhanin. Collecting telemetry data privately. In NIPS, 2017.