Asymptotically Optimal Best Arm Identification with Fixed-Budget under Differential Privacy
Abstractの概要
本論文では、適応的なトランスクリプト全体を保護する必要がある純粋なε-差分プライバシー下でのベルヌーイバンディットにおける固定予算最良腕識別を研究しています。推薦誤り確率の漸近的な減衰率を特徴づけるプライバシー考慮型輸送指数を導入しており、これはダイバージェンスが逆の引数順で評価されるため、固定信頼度プライベート最良腕識別の指標とは異なります。この指数に基づき、著者らはラプラス木によるプライベートな逐次推定量、ギブス分布からのチャレンジャーサンプリング、およびAdaHedgeに基づく配分更新を組み合わせた適応的アルゴリズム「AO-Pri-BAI」を提案しています。本稿では情報理論的下界とアルゴリズム的上界の双方を提供し、プライベートなベースライン手法との比較実験も報告しています。
新規性
本研究の主な新規性は、固定予算プライベート最良腕識別における新たなプライバシー考慮型輸送指数を特定した点にあり、これはKL非対称ダイバージェンスが対立仮説から真の分布の順序で現れるため固定信頼度の特徴づけとは異なります。アルゴリズム面では、この指数を標準的な非プライベートの経験的・事後分布更新ではなく、ラプラス木による継続的開示とギブスサンプリングされたチャレンジャーを用いるプライベートなミニマックス学習手順と組み合わせています。
成果
著者らは、極限配分を持ついかなる一貫したε-DP方策も提案された指数を漸近的に超えられないことを証明し、AO-Pri-BAIがトランスクリプト全体に対してε-DPを満たすことを示しています。さらに、AO-Pri-BAIが下界のベンチマークと一致する指数を持つ漸近的上界を達成し、漸近的最適性を確立することを明らかにしました。実験において、AO-Pri-BAIは中規模から大規模な予算領域でプライベートなベンチマーク手法を上回り、報告された合成インスタンスでほぼ完全な精度を達成しています。
論文の注目点
- 固定予算プライベート最良腕識別をインスタンス依存のプライバシー考慮型輸送ゲームとして定式化し、新たな下界指数を導出している。
- AO-Pri-BAIはラプラス木を用いてプライベートな逐次平均を維持し、AdaHedgeを用いた最小化・最大化学習器の相互作用を通じてサンプリング配分を適応的に学習する。
- 理論的保証として純粋なε-差分プライバシーおよび上下界の指数の一致を示し、実験では報告されたプライベートベースラインよりも大規模予算において優れた性能を発揮することを確認している。