Missing Mass for Differentially Private Domain Discovery

1. 問題定義と背景

現代のデータ分析（クエリ、レビュー、購入履歴など）では、事前にドメイン（全アイテム集合）が未知であるか、実用的に巨大であることが多く、効率的な下流タスクを行うためには「ドメイン発見」が不可欠です。しかし、差分プライバシーを適用すると、個々のユーザーのデータを隠蔽する必要があるため、ドメインの特定が困難になります。

本研究では、以下の 3 つの主要な問題を扱います：

1. 集合和（Set Union）: 各ユーザーがアイテムのサブセットを持ち、それらの和集合からできるだけ多くのアイテムを DP を満たしながら出力する問題。
2. Top-k 選択: 未知のドメインから、頻出する上位 k 個のアイテムを特定する問題。
3. k-Hitting Set: 最大 k 個のアイテムの集合を出力し、それがユーザーのサブセットと交差する回数を最大化する問題（データ要約や特徴量選択に有用）。

評価指標:
従来の研究では「出力されたユニークアイテムの数（基数）」が重視されていましたが、この論文では**「欠落質量（Missing Mass）」**を主要な評価指標として採用しています。

• 欠落質量 (MM): 出力集合 $S$ に含まれないアイテムの頻度の合計比率（$\ell_1$ ノルム）。
• $\ell_\infty$ 欠落質量: 出力されなかったアイテムの中で、最も高い頻度を持つものの頻度（最大欠落質量）。
  これにより、単に「多くのアイテム」を出すだけでなく、「重要な（高頻度の）アイテムを見逃さない」ことを保証する枠組みを構築しました。

2. 手法：重み付きガウス機構（WGM）の活用

既存の DP 集合和アルゴリズムには実用的な保証が乏しいという課題に対し、著者らは単純かつスケーラブルな**重み付きガウス機構（Weighted Gaussian Mechanism: WGM）**を再評価し、その理論的保証を証明しました。

主要なアプローチ

1. WGM の再定義と理論的保証:

   • WGM は、各ユーザーのアイテム数を制限（$\Delta_0$）し、重み付きヒストグラムを作成した後、ガウスノイズを加えて閾値 $T$ を超えるアイテムを出力する仕組みです。
   • Zipf 分布に対する保証: データが Zipf 分布（$s > 1$）に従う場合、WGM は近似的に最適な $\ell_1$ 欠落質量の保証を持つことを証明（定理 3.3）。
   • 分布フリーの保証: データの分布に依存せず、$\ell_\infty$ 欠落質量に対する保証を証明（定理 3.6）。これは、最大頻度のアイテムを見逃さないことを保証します。

2. 未知ドメインアルゴリズムへの応用:

   • 既存の「既知ドメイン」アルゴリズムを「未知ドメイン」問題に適用するための前処理として WGM を使用します。
   • プライバシー予算の分割: 全体のプライバシー予算の半分を WGM（ドメイン発見）に、残りの半分を既知ドメイン用のアルゴリズム（Top-k や k-Hitting Set）に割り当てます。
   • Top-k 選択: WGM で発見されたドメイン $D$ に対して、Peeling Exponential Mechanism を適用します。
   • k-Hitting Set: WGM で発見されたドメイン $D$ に対して、私的貪欲法（User Peeling Mechanism）を適用し、サブモジュラー最大化の近似保証を得ます。

3. 主要な貢献

1. DP 集合和における絶対的な有用性保証の初提供:

   • 既存の研究（Desfontaines et al., 2022; Chen et al., 2025）は他アルゴリズムとの相対比較に留まっていましたが、本研究は DP 集合和に対する絶対的な欠落質量の理論的上界を初めて証明しました。
   • Zipf 分布における $\ell_1$ 誤差と、分布フリーな $\ell_\infty$ 誤差の両方をカバーしています。

2. 未知ドメイン問題に対する新しいアルゴリズムと保証:

   • Top-k 選択および k-Hitting Set 問題に対して、WGM をドメイン発見のプレプロセッサとして用いることで、未知ドメイン設定における最初の有用性保証（定理 4.3, 4.5）を導出しました。
   • 特に k-Hitting Set については、既知ドメイン設定での既存の近似保証（Mitrovic et al., 2017）を、ドメインサイズ $M$ に依存する形で拡張し、ドメインが巨大な場合の改善を示しました。

3. 理論的下界の証明:

   • 提案アルゴリズムの性能が本質的に最適であることを示すため、$\ell_1$ 欠落質量および Top-k 誤差に対する下界（定理 3.5, 4.4, 4.6）を証明しました。これにより、アルゴリズムのギャップを特定し、改善の余地を明確にしました。

4. 実験結果

6 つの現実世界のデータセット（Reddit, Amazon Games, Movie Reviews, Steam Games など）を用いた実験を行いました。

• 集合和（Set Union）:
  • WGM は、計算コストが非常に高い逐次的なポリシー機構（Policy Gaussian/Greedy）と比較して、欠落質量（MM）において 5% 以内の性能を示しました。
  • WGM は計算効率が高く、実用的なスケーラビリティを有しています。
• Top-k 選択:
  • 既知ドメインを仮定した既存の手法（Durfee & Rogers, 2019）と比較して、WGM ベースの手法はすべての $k$ 値において一貫して優れた性能（より小さな Top-k 欠落質量）を示しました。
  • 特に $k$ が大きくなるほど、WGM ベースの手法の優位性が増大しました。
• k-Hitting Set:
  • 未知ドメイン設定での既存の DP アルゴリズムは存在しないため、非私的貪欲法や、ドメインを公開と仮定した私的アルゴリズムと比較しました。
  • WGM ベースの手法は、ドメインを公開と仮定したアルゴリズムと同等、あるいはそれ以上の性能（ヒット数）を達成しました。これは、WGM が高品質なアイテムを含むコンパクトなドメインを生成し、2 段階目のアルゴリズムの負荷を軽減したためです。

5. 意義と結論

この論文は、差分プライバシーにおけるドメイン発見問題に対して、以下の点で重要な進展をもたらしました。

• 評価指標の転換: 「基数（数）」から「質量（頻度）」への視点の転換により、実用的なデータ分析においてより意味のある保証を提供しました。
• 実用性と理論の両立: 複雑な逐次アルゴリズムではなく、単純な WGM を活用することで、高い計算効率と堅牢な理論的保証を両立させました。
• 汎用性の高いフレームワーク: WGM をドメイン発見の汎用プリミティブとして確立し、Top-k や k-Hitting Set などの多様なタスクに拡張可能な枠組みを提示しました。

将来的には、Top-k や k-Hitting Set における上界と下界のギャップの解消、およびデータ依存型のサンプリング戦略の導入によるさらなる性能向上が期待されています。