差分プライバシー下における最適なベストアームの識別

この研究では、データが敏感なアプリケーションにおけるベストアーム識別（BAI）アルゴリズムを、特にグローバルな差分プライバシー（DP）のもとで最適化する問題を考察しています。従来の最適なBAIアルゴリズムはプライバシーに配慮されていない設定では数多く存在しますが、グローバルDP設定では最良の下限と上限の間に大きなギャップがあります。本研究は、任意のプライバシーバジェットεに対してこのギャップを小さな定数に縮小します。まず、確率的なサンプル複雑度のタイトな下限を提供し、次に新たな停止ルールと、アーム依存の幾何学的バッチ処理を用いたプライベート推定器を導入します。最後に、期待サンプル複雑度に対する漸近的な上限を示し、既存の他のBAIアルゴリズムを上回る性能を示します。