NeurIPS 2021に採択されたプライバシー関連論文を概観する(前編)
TL;DR
NeurIPS 2021に採択されたプライバシー論文を概観
大まかな論文の類型
既存の機械学習タスク(連合学習、多腕バンディット問題、n-gram抽出)にDPを適用
SGDなどの勾配アルゴリズムの更新におけるDP保証の改善
高次元出力も加味したprivacyとaccuracyのトレードオフの最適化
はじめに
NeurIPS 2021の採択論文が発表された。今回は本会議に採択された論文のうち、差分プライバシー(Differential Privacy: 以下DP)に関連する論文のabstractを一通り眺め、トップ会議に採択される論文の潮流を眺めたい。 対象論文は全部で48本のため、3回に分けて紹介する
本文
Jinshuo Dong, Weijie Su, Linjun Zhang
数値クエリへのノイズ付与にあたり、answer vectorが高次元な場合、ノイズ分布がprivacyとaccuracyをどのように最適化するか
高次元での中心極限定理現象を提示し、クラメール・ラオの限界によって不確定性原理型の結果(privacyパラメタとl2-lossの積の下界)を導く
Hilal Asi, Daniel Levy, John Duchi
特定の最適化対象関数の困難さに適応するプライベート確率的凸最適化アルゴリズムの開発
既存研究では任意の凸関数のworst-caseの boundsを対象としていたが、より小さいクラスでより速いレートにできる
Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, Chris Waites
学習済みモデルからのデータ削除を、再学習するよりも安価に行いたい
DPと最大情報量への接続を利用して、adaptive sequenceからnoo-adaptive sequenceへの削除保証を低減を示す
John Abowd, Robert Ashmead, Ryan Cumings-Menon, Simson Garfinkel, Daniel Kifer, Philip Leclerc, William Sexton, Ashley Simpson, Christine Task, Pavel Zhuravlev
差分プライバシーを満たすpoint queryとsum queryの間に不確定性関係があることを示した論文
それぞれのクエリの平均二乗誤差を定量的に評価し、片方の平均二乗誤差を小さくしようとすると、もう一方の平均二乗誤差の下界が存在することを提示
Mani Malek Esmaeili, Ilya Mironov, Karthik Prasad, Igor Shilov, Florian Tramer
学習済みモデルが教師データのラベルに対してDPを満たさなければならない問題が対象
LaplaceメカニズムとPATEによる2つのアプローチを提案
Adaptive Laplaceノイズとベイズ推定の組み合わせが、典型的なMLタスクに適していることを主張
Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, Lydia Zakynthinou
共分散が未知な劣ガウス分布に対して、2つのsample-efficient DP 平均推定量を示す
指数メカニズムを用いて近似最大テューキー深度を持つ点をサンプルして推定
経験的共分散に適合したノイズのあるデータセットを用いた経験的平均として推定
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, Chiyuan Zhang
ランダムレスポンスと同等のプライバシー保証でありながら、より正確な結果を提供できるRandomized Response qith Priorを提案
LabelDPを使用したニューラルネットワークの学習で、ラベル保護のみであれば最新の研究を凌駕することを示す
事前情報を取得する方法も種々検討し、RRWithPriorではprivate modelとnon-private modelsの間のprivacy-accuracyギャップが改善
Rishav Chourasia, Jiayuan Ye, Reza Shokri
アルゴリズムの内部状態がプライベートな場合の反復ランダムアルゴリズムの情報リークや、モデルを介した情報リークに関してノイズ付き勾配降下アロゴリズムを研究
学習プロセス全体でRényi-DP損失のダイナミクスをモデル化
プライバシー損失が、滑らかな強凸な損失関数に対して指数関数的に収束することを証明(合成定理で加算するよりも優れた上限を算出)
Cuong Tran, My Dinh, Ferdinando Fioretto
最近の研究で、DP学習システムが個人グループのbiasやunfairnessを助長することが示された
DPの経験的リスク最小化(出力摂動法、DP-SGD)によって発生する影響の原因を調査
Zhongxiang Dai, Bryan Kian Hsiang Low, Patrick Jaillet
federated Thompson sampling (FTS) アルゴリズムによって、ベイス最適化が連合学習に拡張されたが、DP保証が具備されていない
DPをFTSに統合し、user-level privacyを保護する
distributed exploration (DE) を通じて、DP-FTS-DEアルゴリズムを開発
Galen Andrew, Om Thakkar, Swaroop Ramaswamy, Brendan McMahan
連合学習にDPを適用する既存アプローチは、モデル更新の寄与を一定にclippingして対処している
一方、タスクや学習でclippingの基準を事前に設定することはできない
更新ノルム分布の分位数でclippingする方式を提案
中央値更新ノルムへのadaptive clippingが現実的な連合学習でうまく機能することを提示(ハイパラ調整なしに、最良の固定clipingを上回る)
Prateek Jain, John Rush, Adam Smith, Shuang Song, Abhradeep Guha Thakurta
user-level DPを使用した教師あり学習のパーソナライズ
Almost-No-Inner-Loopメソッドなど、このドメインで一般的なnon-privateアプローチを使用しつつ、プライバシー保証を提供
Jay Tenenbaum, Haim Kaplan, Yishay Mansour, Uri Stemmer
shuffle modelにおける多腕バンディット問題のアルゴリズムに(ε, δ)-DP保証を提供
Kunho Kim, Sivakanth Gopi, Janardhan Kulkarni, Sergey Yekhanin
n-gram抽出にDPを適用
private text dataのコーパスが与えられたとき、user-level DPを保持しながら可能な限り多くのn-gramをリリースする問題
同様の問題はsequence miningでも見られ、DP set union (DPSU) の一般化として捉えることができる
Matthew Reimherr, Karthik Bharath, Carlos Soto
リーマン多様体上のDP統計サマリのリリース問題を扱う
Lplaceメカニズム、K-norm メカニズムを拡張
データのFréchet平均について詳細に検討
多様体構造を無視するとサニタイズされたサマリの有用性がどのように低下するか提示
Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith, Marika Swanberg
未知の分布Pからサンプリングされたn個の観測値から、Pに全変動距離が最も近い分布から観測値を出力する問題
終わりに
今回は前編として全48本のDPのうち、16本を紹介した。大まかな傾向として感じられたのは以下。
既存の機械学習タスク(連合学習、多腕バンディット問題、n-gram抽出)にDPを適用
SGDなどの勾配アルゴリズムの更新におけるDP保証の改善
高次元出力も加味したprivacyとaccuracyのトレードオフの最適化
この他にも類型があるのか、中編・後編でも紹介を続けたい。(文責・恩田)