技術的概要：ガウスグラフィカルモデルによるプライベート適応共分散推定（PACE-GGM）

問題定義

共分散推定は、回帰、主成分分析、多変量モデルの基盤となる統計学および機械学習における基本的なタスクである。機密データを扱う状況では、個々のレコードを保護しつつ推定値を公開するために、差分プライバシー（DP）が要求される。標準的な手法であるガウス機構（または十分統計量の摂動、SSP）は、経験共分散行列のすべての $d(d+1)/2$ 個の要素にノイズを加える。この手法は、データレコードに対するグローバルな $\ell_2$ ノルム境界に依存しており、完全な行列に対して $\sqrt{2}C^2/n$ の感度をもたらす。

しかし、多くの実用的な応用（クリップまたは正規化された属性を持つ表形式データなど）では、tight なグローバルな $\ell_2$ 境界よりも、座標ごとの境界（$|x_j| \le B$）を仮定する方が自然である。$\ell_\infty$ 境界の下では、単一の要素の感度は $2B^2/n$ であるのに対し、完全な行列の感度は $\sqrt{2}dB^2/n$ となる。これにより大きな格差が生じる：同じプライバシー予算に対して、単一の要素は、完全な行列よりも $d/\sqrt{2}$ 倍小さいノイズ標準偏差で測定可能である。ここで扱われる中心的な問題は、経験共分散行列の最も情報量の多い要素のサブセットを選択的に測定し、完全な行列を再構築するアルゴリズムを設計できるかどうかであり、それによって均一な摂動よりも効率的にプライバシー予算を集中させることができるかどうかである。

手法：PACE-GGM

著者は、"select-measure-reconstruct"（選択・測定・再構築）のパラダイムに基づく反復アルゴリズムであるPACE-GGM（ガウスグラフィカルモデルによるプライベート適応共分散推定）を提案する。この手法は、ゼロ集中差分プライバシー（zCDP）の下で動作する。

1. 初期化

アルゴリズムは、プライバシー予算の一定割合（$\rho_{diag}$）を割り当て、ガウス機構を用いて共分散行列のすべての対角要素を測定することから始まる。これにより、初期推定値 $\hat{\Sigma}^{(0)}$ が形成される。

2. 反復的な選択・測定・再構築ループ

アルゴリズムはラウンドごとに進行し、ノイズを含む測定値の集合 $\{y_{jk}\}$ とそれに関連する精度 $\{\lambda_{jk}\}$ を維持する。各ラウンドでは：

• 選択： 現在の推定値によって十分に近似されていない要素 $(j, k)$ が、指数機構を用いて選択される。品質スコアは近似誤差 $|\Sigma_{jk}(X) - \hat{\Sigma}^{(t-1)}_{jk}|$ である。このステップは、どの要素が最も情報利得を提供するかを適応的に特定する。
• 測定： 選択された要素は、残りの予算の一部を用いてガウス機構で測定される。新しい測定値は、同じ要素の以前の測定値と逆分散重み付けによって結合され、精度加重平均 $y_{jk}$ と精度 $\lambda_{jk}$ が更新される。
• 再構築： 新しい完全な共分散行列 $\hat{\Sigma}^{(t)}$ は、最大エントロピー最適化問題を解くことで再構築される。目的は、観測された測定値の負の対数尤度を最小化しつつ、対数行列式（エントロピー）を最大化する正定値（PSD）行列を見つけることである。
  • 数学的には、以下を解く：
    $$\max_{\Sigma} \log |\Sigma| \quad \text{s.t.} \quad \Sigma \in \arg\min_{W \succeq 0} \sum_{(j,k) \in S} \lambda_{jk} (W_{jk} - y_{jk})^2$$
  • これは古典的な共分散選択問題（Dempster, 1972）およびガウスグラフィカルモデル（GGM）と関連している。解は、観測されていない要素（条件付き独立性）に対して精度行列 $K = \Sigma^{-1}$ がゼロとなる GGM に対応する。
  • 著者は、この問題を効率的に解くために、$\Sigma$ をそのコレスキー因子（$L$）を通じてパラメータ化する**内点法（IPM-CHOLESKY）**を提案する。これにより、ノイズに起因して問題が不適切（ill-posed）になる場合も処理可能となる。

3. 予算アニーリング

測定と再構築の間のトレードオフを管理するため、アルゴリズムは（AIM に着想を得た）予算アニーリング戦略を採用する。測定後の推定値の変化がノイズレベルに対して小さい場合、より有益な将来の測定を可能にするために、ラウンドごとの予算を増加させる。

4. プライバシー保証

アルゴリズムは $\rho$-zCDP を満たす。証明は zCDP の合成特性に依存する：

• 初期化ステップは $\rho_{diag}$-zCDP を満たす。
• 各ラウンドは、指数機構とガウス機構の適応的合成を含む。
• 再構築ステップはポスト処理操作であり、追加のプライバシーコストを伴わない。

主要な貢献

1. 適応的要素選択： PACE-GGM は、データに基づいてどの共分散要素を測定するかをプライベートかつ適応的に選択する最初の手法であり、完全な行列をプライバシー保護するか、スパース性などの固定的な構造仮定に基づいて選択する手法とは異なる。
2. 最大エントロピー再構築： 本論文は、部分的でノイズを含む観測から最大エントロピー PSD 補完を見つけることで、完全な共分散行列を復元する原理的な再構築手法を導入する。これは適応的測定をガウスグラフィカルモデルの理論と結びつける。
3. 感度分析： 著者は、座標ごとの（$\ell_\infty$）境界の下では、完全な行列を測定するよりも個々の要素を測定する方が、$d/\sqrt{2}$ 倍という因子で著しく効率的であることを厳密に示し、選択的アプローチの正当性を裏付けている。
4. ソルバーの革新： コレスキーパラメータ化の非凸性を効率的に処理し、測定グラフの連結成分を活用して計算複雑性を低減する IPM-CHOLESKY ソルバーの開発。

実験結果

この手法は、$d=6$ から $d=260$ までの次元を持つ 14 の実世界データセットで、さまざまなプライバシー予算（$\rho \in \{10^{-4}, \dots, 10\}$） across 評価された。

• 性能： PACE-GGM は、標準的なガウス機構（SSP）や AdaptiveCov、対角要素のみの推定値などの他のベースラインを一貫して上回った。
• 改善の領域： 改善は高次元の設定と低〜中程度のプライバシー予算の領域で最も顕著である。これらのシナリオでは、予算を情報量の多い要素に集中させる能力により、マハラノビス誤差とフロベニウス誤差が著しく低くなる。
• スパース性： アルゴリズムは、基礎となる共分散が密な要素に自然に測定を集中させる。高次元データセット（例：$d=260$）の場合、対角要素以外の非常に小さな割合（例：madeline データセットでは 0.1%）しか測定しないにもかかわらず、すべての要素を摂動させる手法と比較して優れた精度を達成する。
• ソルバーの堅牢性： 実験により、IPM を通じた最大エントロピー定式化は、初期値に敏感だった射影勾配降下法（PGD）よりも堅牢で安定していることが示された。

意義と主張

本論文は、PACE-GGM が差分プライバシーデータ合成および推定におけるギャップを埋めると主張している。マージナルベースの手法が離散変数または離散化された変数を対象とするのに対し、PACE-GGM は連続変数の共分散構造を正確に推定することで、連続合成データ生成の基盤を提供する。

著者は、この手法が特に、モデラーが座標ごとの境界（表形式データにおける自然な設定）を持ちながら、tight なグローバルな $\ell_2$ 境界を持たない場合に効果的であると強調している。SSP の均一なノイズ分布を回避することで、PACE-GGM はプライバシー予算が制約され、次元が高い領域において最先端の性能を達成する。この手法は、予算割り当て割合（$\alpha$ および $\beta$）の特定の選択に対して堅牢であるため、複雑なハイパーパラメータ調整を必要とせずに推定誤差を改善する、実用的でデータ適応的なルーチンとして提示されている。