Connect the Dots:差分プライバシーのより効率的なプライバシーコスト推定(2/2)

１．Connect the Dots:差分プライバシーのより効率的なプライバシーコスト推定(2/2)まとめ

・Connect-the-Dotsは離散化して戻す事で効率的な計算を行うアルゴリズム
・Connect-the-Dotsは先行実装に比べてより厳密に速く見積もる事ができる
・ライブラリは現在悲観的推定版のみをサポートしているが楽観的版も対応予定

２．Connect the Dotsの性能

以下、ai.googleblog.comより「Differential Privacy Accounting by Connecting the Dots」の意訳です。元記事の投稿は2022年12月20日、Pritish KamathさんとPasin Manurangsiさんによる投稿です。

アイキャッチ画像はstable diffusionの生成

Connect-the-Dots:新しいアルゴリズム

私達の新しいConnect-the-Dotsアルゴリズムは、ホッケースティックダイバージェンスの推定を目的としたPLDの離散化のためにより良い方法を提供します。この方法は、まずホッケースティックダイバージェンス関数を離散化し、それを等間隔に配置された離散PLDにマッピングし直すことで間接的に機能します。

Connect-the-Dotsのアルゴリズムの概要図

このアプローチは「支配的PLD(dominating PLD)」の概念に依存しています。

すなわち、「\(PLD_{P’||Q’}\)が\(PLD_{P||Q}\)より支配的」とは、すべてのεの値について前者のホッケースティック発散が後者のホッケースティック発散より大きいか等しい場合です。

支配的PLDの重要な特性は、合成後も支配的であり続けることです。したがって、プライバシー会計を目的とするのであれば、支配的なPLDについて作業すれば十分であり、正確なプライバシーコストの上界を与えます。

Connect-the-Dotsの背後にある私達の主な洞察は、離散PLDの特徴付けです。

すなわち、PLDは与えられた有限のε値の集合にサポートされますが、これは、もし、\(e^ε\)の関数として対応するホッケースティックダイバージェンスが連続する\(e^ε\)値の間で線形である場合にのみ成り立ちます。

これにより、与えられた\(e^ε\)値におけるホッケースティックダイバージェンス関数に正確に等しい区分的線形関数を得るために、単に点を結ぶことによってホッケースティックダイバージェンスを離散化することができます。アルゴリズムの詳細な説明はyoutubeの解説動画をご覧ください。

ホッケースティックダイバージェンスの離散化におけるConnect-the-DotsとPrivacy Bucketsの比較

実験による評価

DP-SGDアルゴリズムには、各勾配ステップで追加されるノイズの大きさを制御するノイズ乗数パラメータと、各ミニバッチに含まれるサンプルの数を制御するサンプリング確率が含まれています。

ノイズ乗数=0.5、\(サンプリング確率 = 0.2×10^{-4}\)、\(δ=10^{-8}\)に設定したプライバシー会計DP-SGDのタスクで、Connect-the-Dotsと以下に示すアルゴリズムを比較します。

・Renyi DP
DP-SGDのプライバシーアカウンティングに使用される独自の手法です。この手法はGoogle-DPライブラリでもサポートされています

・Privacy Buckets
Google-DPライブラリで使用されているPLDベースのアプローチで、離散化点間の確率質量を丸めています。

・Microsoft PRV Accountant
PLDの平均値を保持した離散化により、Privacy Bucketsを改良したアプローチです。

各アルゴリズムで計算されたεの値を合成ステップ数に対してグラフ化し、さらに、各実装の実行時間をグラフ化しました。

以下のグラフに示すように、Renyi DPを用いたプライバシー会計は、プライバシー損失を大まかに推定する事ができます。しかし、PLDを用いたアプローチを比較すると、この例では、Connect-the-Dotsの実装が、Microsoft PRV Accountantよりも5倍速く、Google-DPライブラリのPrivacy Bucketsの以前のアプローチよりも200倍以上速く、プライバシー損失のより厳密な見積もりを達成していることが分かります。

左：DP-SGDのステップ数を変化させた場合のアルゴリズムによるプライバシーパラメータεの上界(\(δ=10^{-8}\)固定)
右：各アルゴリズムの実行時間

まとめと今後の方向性

本研究では、異なるアルゴリズムの組み合わせに対して最適なプライバシーパラメータを計算する新しいアルゴリズム、Connect-the-Dotsを提案します。DP-SGDタスクで評価したところ、このアルゴリズムは、プライバシー損失に対してより厳しい推定値を与え、実行時間が大幅に短縮されることがわかりました。

これまでのところ、ライブラリはConnect-the-Dotsアルゴリズムの悲観的推定版のみをサポートしており、DP-アルゴリズムのプライバシー損失の上界を与えることができます。しかし、この論文では、PLDの「楽観的」な推定を行うアルゴリズムの亜種も紹介しており、これを用いてDP-アルゴリズムのプライバシーコストの下界を導くことができます。(「最悪の場合」のPLDを認めることが条件です)。現在、このライブラリはPrivacy Bucketsアルゴリズムによる楽観的な推定をサポートしており、Connect-the-Dotsバージョンも取り入れたいと考えています。

謝辞

この研究は、Vadym Doroshenko、Badih Ghazi、Ravi Kumarとの共同作業で行われました。Galen Andrew, Stan Bashtavenko, Steve Chien, Christoph Dibak, Miguel Guevara, Peter Kairouz, Sasha Kulankhina, Stefan Mellem, Jodi Spacek, Yurii Sushko そして Andreas Terzisに感謝します。