技術要約：ナップサック制約付き差分プライバシー準劣モジュラ最大化

1. 問題定義

本論文は、**差分プライバシー（DP）の枠組みにおけるナップサック制約付き準劣モジュラ最大化（SMK）**問題を取り扱う。

• SMKの文脈: $n$ 個の要素からなる基底集合 $N$、準劣モジュラ目的関数 $f: 2^N \to \mathbb{R}$、コスト関数 $c: N \to \mathbb{R}_{>0}$、および予算 $B$ が与えられるとき、目標は $\sum_{v \in S} c(v) \leq B$ を満たし、$f(S)$ を最大化する部分集合 $S \subseteq N$ を見つけることである。この問題はNP困難であり、特徴量選択、データ要約、影響力最大化などの機械学習アプリケーションにおいて遍在している。
• プライバシー設定: 目的関数 $f_D$ は機密データセット $D$ に依存する。アルゴリズムは、$(\epsilon, \delta)$-差分プライバシーを満たすように解 $S$ を出力しなければならない。これは、データ $D$ 内の個人のデータが変更されたとしても、出力分布の変化が無視できる程度であることを保証するものである。
• 範囲: 本研究では、**単調（monotone）な目的関数と非単調（non-monotone）**な目的関数の両方を対象とする。

2. 手法と技術的課題

著者らは、標準的なDP準劣モジュラ最大化の手法（多くの場合、濃度制約向けに設計されている）が、ナップサック制約においては以下の2つの主要な課題により最適ではないことを指摘している。

1. 密度スコアの感度の変動: ナップサックの設定では、アルゴリズムは通常、「密度」（限界利得をコストで除したもの）に基づいて要素を選択する。濃度制約では感度が一様であるが、密度スコア $f(u|S)/c(u)$ の感度は、要素のコスト $c(u)$ に反比例して依存する。標準的な選択メカニズム（指数メカニズムなど）を素朴に適用すると、$\Delta f \cdot (B/c_{\min})$ に比例する加法的誤差が生じ、最大実行可能解のサイズ $k$ に対する依存関係が最適ではなくなる。

   • 解決策: 著者らは Generalized Report Noisy Max (GRNM) メカニズム（Raskhodiana & Smith, 2016）を採用している。このメカニズムは、個々の候補の感度に適応し、加法的誤差がワーストケースの境界ではなく、選択された候補の特定の感度に応じてスケールするようにしている。

2. 合成のボトルネック: 単調なSMKに対する最先端の非プライベートアルゴリズム（例：Two-Guess-Greedy）は、最適な要素を推測するために $O(n^2)$ 回の反復を必要とする。標準的な高度な合成定理を適用すると、エラー項が $n$ に対して多項式的にスケールしてしまい、プライバシーの恩恵を打ち消してしまう。

   • 解決策: 著者らは Generalized Private Selection フレームワーク（Cohen et al., 2023）を活用している。各列挙ステップが呼び出される回数をランダム化することで、プライバシー損失を総サブ関数の数から切り離し、$n$ に対する多項式ではなく、対数的な依存関係を持つ加法的誤差を実現している。

3. 主要な貢献とアルゴリズム

A. 単調な目的関数

本論文では、単調なケースに対して2つのアルゴリズムを提案している。

1. DP-2GG (Algorithm 2): 「Two-Guess-Greedy」アルゴリズム（Feldman et al., 2023）の差分プライベートな適応版。

   • メカニズム: サイズが最大2のすべての部分集合 $Y \subseteq N$ について反復処理を行う。各 $Y$ に対して、残差インスタンスに対してプライベートな密度・グリーディ・サブルーチン（Algorithm 1）を実行する。最終的な解は、これらサブルーチンのノイズを含む出力から選択される。
   • 保証: 最適な $(1 - 1/e)$-近似 を達成する。
   • 計算量: $O(\beta^{-1} n^3 k)$ オラクルクエリ。
   • 誤差: 加法的誤差は $O(\frac{\Delta k^{1.5}}{\epsilon} \sqrt{\log n} \dots)$ となり、以前の研究と比較して $n$ および $1/c_{\min}$ への多項式依存性を排除することで改善されている。

2. DP-DG+ (Algorithm 7): Density-Greedy+ に基づく、より高速なシングルパス・アルゴリズム。

   • メカニズム: プライベートな密度・グリーディ・パスを一度実行し、部分解およびそれらの単一要素拡張の中から、Report Noisy Max を用いて最良の解を選択する。
   • 保証: $1/2$-近似 を達成する。
   • 計算量: $O(nk)$ オラクルクエリ。
   • 誤差: 単調なケースと同等の改善された加法的誤差。

B. 非単調な目的関数

本論文は、非単調なSMKに対して証明可能な保証を持つ最初の差分プライベート・アルゴリズムを導入している。

• アルゴリズム: DP-SDG (Algorithm 3)。これは、非プライベートな SmkRan アルゴリズム（Han et al., 2021）のプライベートな適応版である。
• メカニズム: GRNM を用いて密度ベースの選択を行う。選択された要素は、非単調性を処理するために確率 $1/2$ で解に追加される（ランダムな破棄）。決定的なのは、限界利得が（ノイズにより）負になったとしても反復を継続し、すべての部分解とその拡張の中から最良の観測解を選択するために RNM を使用することである。
• プライバシー分析: 選択ステップの数の不確実性を扱うため、著者らは、総反復回数が $O(k)$ の周りに集中する幾何分布の和によって確率的に支配されることを示す集中不等式を導出した。
• 保証: 期待値として $1/4$-近似 を達成する。
• 計算量: $O(nk)$ オラクルクエリ。
• 誤差: 単調なケースと同等の加法的誤差。

4. 結果と実証的評価

理論的結果

著者らは、表1において、先行研究（特に Sadeghi & Fazel, 2021）と比較を行っている。主な改善点は以下の通りである：

• 近似比: 最良の既知の非プライベートな比率（単調な場合は $(1-1/e)$、非単調な場合は $1/4$）に一致している。
• 加法的誤差: 基底集合のサイズ $n$ に対する依存関係（多項式から対数へ）および、最大実行可能解のサイズ $k$ に対する依存関係（$k$ またはそれ以下から $k^{1.5}$ へ）が大幅に改善されている。
• クエリ複雑性: 先行研究の単調SMKが多項式時間のアルゴリズムのために $O(2^n)$ クエリを必要としていたのに対し、本研究は $n$ と $k$ の多項式となっている。

実証的結果

アルゴリズムは、マンハッタンにおける100,000件のUberピックアップ場所のデータセットを用いたライドシェアリング最適化タスクで評価された。

• 有用性: $\epsilon \geq 0.1$ において、DPアルゴリズム（DP-2GG, DP-DG+, DP-SDG）は、非プライベートな対応物（2GG, DG+, SmkRan）と同等の効用を実現しており、ランダムなベースラインを大幅に上回っている。$\epsilon=0.2$ において、DP-2GG は非プライベートな 2GG の 2% 以内の誤差に収まっている。
• スケーラビリティ: DP-DG+ と DP-SDG は、基底集合のサイズ $n$ に対してオラクルクエリが線形に増加することを示しており、よりクエリ集約的な DP-2GG と比較して、実用的な効率性を裏付けている。

5. 重要性と主張

本論文は、差分プライベートな組合せ最適化に関する文献における重要なギャップを埋めることを主張している。

1. 初の証明可能な非単調SMK: 差分プライバシー下での非単調SMKに対する最初の証明可能な保証を確立した。
2. 改善された単調バウンド: 単調SMKアルゴリズムの有用性（加法的誤差）とクエリ複雑性の両方を改善し、以前のアプローチの指数関数的なクエリ複雑性から脱却した。
3. ナップサック制約の処理: 汎用的な選択メカニズムと集中不等式を用いることで、ナップサック制約特有の課題（変動する感度と合成のボトルネック）を克服し、濃度制約の設定と同等の効率性を達成できることを示した。

著者らは、加法的誤差の $k$ への依存関係が、有界な感度の下での多項式時間アルゴリズムにおける最良の既知のケースと一致しているものの、より良い $k$ への依存関係が可能かどうかという問いは未解決であると述べている。また、これらの手法を、ナップサック制約とマトロイド制約を組み合わせたものへ拡張することを今後の研究方向として示唆している。