Information-Theoretic Bounds for Sparse Covariance Estimation in the Vertical-Split Distributed Model

技術要約：垂直分割分散モデルにおける疎な共分散推定のための情報理論的境界

問題定式化
本論文は、**垂直分割（特徴量分割）**設定における分散共分散行列推定（DCME）のミニマックス推定誤差を調査している。このモデルでは、$K=2$ のエージェントが、$d$ 次元の劣ガウス分布から得られた $m$ 個の独立同一分布（i.i.d.）サンプルを共通して観測するが、各エージェントは互いに素な座標の部分集合のみを観測する。具体的には、エージェント1は最初の $d_1$ 個の座標を、エージェント2は残りの $d_2$ 個の座標を観測する。

主要な推定対象は、相互共分散行列 $C_{21} = \mathbb{E}[(X_2 - \mathbb{E}X_2)(X_1 - \mathbb{E}X_1)^\top] \in \mathbb{R}^{d_2 \times d_1}$ である。対角ブロック（$C_{11}$ および $C_{22}$）は通信なしに局所的に推定可能であるため、通信コストは $C_{21}$ を推定する必要性によって決定される。エージェントは、限られたビット予算 $B_1$ および $B_2$ に基づいて局所データを圧縮し、中央サーバーに送信する。

本論文は、相互共分散行列 $C_{21}$ が $s$-疎（$s$-sparse）、すなわち高々 $s$ 個の非ゼロ要素を持つシナリオに焦点を当てている。中心的な問いは、この構造的な疎性が、平均推定において疎性が通信コストを削減しないことが以前に示された水平分割設定と比較して、通信予算およびサンプル複雑性を減少させることができるかどうかである。

手法
著者らは、下界を確立し、一致する達成可能スキームを構築するために、情報理論的フレームワークを採用している。

1. 下界（コンバース）:

   • 補助的なランダム性を伴うファノの不等式: 証明には、ファノの不等式の平均化バージョンが用いられる。相互共分散行列が符号付き部分置換行列によって摂動された仮説族が構築される。
   • 疎なパッキング: $s'$-疎な符号付き部分置換行列（ここで $s' = s \wedge d_{\min}$）のパッキング集合の構築という、主要な組合せ論的寄与がある。著者らは、部分置換制約に適応させつつ、ハミング距離において互いに分離された大きな集合の存在を証明している。
   • 条件付き強データ処理不等式 (C-SDPI): エージェント間の相関（同じ基礎となるサンプルを観測しているため）を扱うために、本論文は Rahmani et al. [2025] によって導入された C-SDPI フレームワークに依拠している。この不等式は、未知の相互共分散を状態とする状態依存チャネルを通じた情報の収縮を定量化する。著者らは、補助変数 $W$ を介してランダムなサポートパターンを平均化することで、計算可能な C-SDPI 係数が得られることを示している。
   • 仮説の分離: 仮説間の分離は、基礎となる疎な行列のハミング距離と結びついたフロベニウスノルムによって測定される。

2. 達成可能性（ダイレクト）:

   • プロトコル設計: 被覆ネット量子化（covering-net quantization）（密な部分のデータ用）と要素ごとのハード閾値処理（entry-wise hard thresholding）（疎性を活用するため）を組み合わせた分散プロトコルを提案している。
   • 手順: エージェントは局所的に自己共分散を推定し、量子化する。相互共分散については、エージェントはデータをサブサンプリングし、被覆ネットを用いてベクトルを量子化する。中央サーバーは経験的相互共分散を再構成し、小さな値をゼロに設定するハード閾値を適用する。
   • 分析: 誤差分析は、量子化ノイズと統計的ノイズへの歪みの分解を行う。決定的なことに、著者らは、相互共分散項から生じる劣指数積に関する集中不等式を利用して、統計的誤差を抑え込む。これは密なケースでは必要とされないプロセスである。

主な貢献と結果

• 垂直分割における疎性による通信の削減: 本論文は、平均推定における水平分割設定とは異なり、垂直分割における相互共分散推定においては、疎性が通信コストを削減することを証明している。
• ミニマックス下界:
  • フロベニウスノルムの下での $s$-疎な相互共分散推定において、エージェントあたりの通信予算 $B_k$ は次のようにスケールしなければならない：
    $$B_k = \Omega\left( \frac{\sigma^4 d_k s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • サンプル複雑性 $m$ は次のようにスケールしなければならない：
    $$m = \Omega\left( \frac{\sigma^4 s' \log(d_1 d_2 / s')}{\varepsilon^2} \right)$$
  • ここで、$s' = s \wedge d_{\min}$ である。1-疎（$s=1$）の場合、これは次元依存性において指数関数的な改善をもたらし、因子を $d_1 d_2$（密なレート）から $\log(d_1 d_2)$ へと減少させる。
• 一致する達成可能性: 提案されたプロトコルは、多項式対数因子を除いて導出された下界に一致しており、境界のタイトネス（緊密性）を裏付けている。
• 組合せ論的補題: 本論文は、$s'$-疎な符号付き部分置換行列に関する新しいパッキング結果を確立し、互いのハミング距離が $s'/2$ より大きい、およそ $( (2d_1 d_2)^{3/4} / (4s'^2) )^{s'}$ のサイズの集合の存在を示している。

意義と主張
本論文は、垂直分割モデルにおける疎性の影響に関する Rahmani et al. [2025] によって残された未解決の問いを解決したと主張している。著者らは、疎性が改善をもたらす構造的な理由は、垂直分割のフレームワークには、パッキング数が規定する以上の通信下界を膨張させるメカニズムが存在しないことにあると示している。仮説空間を $s'$-疎な行列に制限することで、パッキング数（およびしたがって、仮説を区別するために必要な情報量）は $\log |V| \sim d_1 d_2$ から $\log |V| \sim s' \log(d_1 d_2 / s')$ へと減少する。

この結果は、異なる生物学的特徴セットの相関（マルチオミクス研究）や、取引履歴と信用記録の連結（金融）など、相互の依存関係が本質的に疎である分散システムにおいて重要である。本論文は、密なケースでは通信が周囲の次元の積に線形に比例する必要がある一方で、疎なケースでは、通信が固有の次元 $s'$ に従ってスケールできることを指摘している。

著者らは、自身の達成可能スキームが閾値を較正するために疎性のレベル $s$ の事前知識を必要とすることを明記しており、今後の課題として、これには謙虚な姿勢を示している。$s$ を知らずに同じレートを達成できるプロトコルが存在するかどうかは、依然として未解決の問いである。同様に、他の構造的仮定（例：低ランク、バンド型、またはグループ疎性）への拡張も、将来の研究方向として特定されている。