技術要約：高次元最適輸送のための凸緩和アプローチ

1. 問題設定

本論文は、高次元における最適輸送（Optimal Transport; OT）問題を解く際に内在する計算および統計上の課題に対処している。OTは幾何学的な忠実度を持って確率分布を比較するための強力な枠組みであるが、その適用は「次元の呪い」によって阻害されている。具体的には、標準的なOTソルバーの計算コストはサンプルサイズとともに急速に増大し、ワッサースタイン距離を推定するために必要なサンプル複雑度は次元 $d$ に対して指数関数的にスケールする。既存の次元削減戦略（例えば、非凸最適化のために強い理論的保証を欠くニューラルネットワークによるパラメータ化や、真の距離を近似するものの完全には復元できないスライス・ワッサースタイン距離など）は、連続的な高次元分布に対するスケーラブルで理論的根拠のある解決策を提供できないことが多い。

2. 手法

著者らは、高次元分布における相関の局所性とスパース性を利用する、一連の凸緩和アプローチを提案している。全結合の輸送計画 $\pi \in \mathcal{P}(X \times Y)$ を最適化する代わりに、低次の周辺分布とスパースなモーメント統計を用いて問題を近似する。

2.1 構造的仮定

このアプローチは、$d$ 次元の座標を $K$ 個のクラスターに分割し、相関構造をエンコードする参照グラフ $G$ を定義することに基づいている。

• クラスター分割: 座標はクラスター $z_k = (x_k, y_k)$ にグループ化される。
• 参照グラフ: クラスターを頂点とし、ペアワイズの相互作用をエッジとするグラフ $G$。本手法は、依存関係がグラフ距離とともに減衰することを前提としており、これによりスパースな近似が可能となる。

2.2 緩和フレームワーク

論文では、主に2つのレベルの緩和を導入している。

1. 周辺緩和 (Marginal Relaxation):

   • 元のOT問題は、輸送計画 $\pi$ の周辺（単一クラスター $\pi_k$ およびグラフ $G$ 内の接続されたクラスターのペア $\pi_{ij}$ に対応するもの）に対してのみ制約を課すことで緩和される。
   • 正値性: グローバルな測度の非負制約は、これらの周辺に対応するブロック行列に対する半正定値（PSD）制約へと緩和される。
   • 定式化: 著者らは3つのバリアントを定義している：
     • $(OT_{mar})$: PSD制約と非負制約の両方を含む（二重非負プログラミング）。
     • $(OT^1_{mar})$: グローバルなPSD制約を除去し、線形計画法（LP）問題とする。
     • $(OT^2_{mar})$: 非負制約を除去し、余弦分解（chordal conversion）によってさらに簡約可能な半正定値計画法（SDP）とする。

2. クラスター・モーメント緩和 (Cluster Moment Relaxation):

   • 空間的な離散化を行わずに連続分布を扱うために、周辺緩和はさらに和の平方（Sum-of-Squares; SOS）モーメント緩和を用いて近似される。
   • 測量の上で最適化を行う代わりに、変数は次数 $n$ の多項式基底から導出された有限次元のモーメント行列 ($M_k, M_{ij}$) となる。
   • 主要な革新: 全ての単項式のモーメントを次数 $n$ まで必要とする標準的なSOS階層（例：Mula and Nouy [44]）とは異なり、本手法は基底を参照グラフのローカルクラスターとエッジに限定する。
   • 複雑度: 結果として得られるSDPは、スパースなモーメントの集合のみを扱う。クラスターサイズと緩和次数が固定されている場合、グラフ $G$ が有界な木幅（tree-width）を持つならば、問題のサイズは $d$ に対して線形（具体的には $O(d)$）にスケールし、余弦分解によって解くことが可能である。

2.3 輸送写像の抽出

緩和されたSDPの双対変数は、近似的なカントロヴィッチ・ポテンシャルを提供する。これらのポテンシャルを選択された多項式基底のスペン（張る空間）内に制限することで、著者らは明示的な輸送写像 $\hat{T}(x) = x - \frac{1}{2}\nabla \hat{f}(x)$ を構築する。これは、ニューラルネットワークベースの生成モデルに代わる、解釈可能な代替案となる。

3. 主要な貢献と理論的結果

3.1 疎な精度行列を持つガウスモデル

精度行列がグラフ $G$ に関してスパースであるガウス測度 $\mu = \mathcal{N}(m_1, \Sigma_1)$ および $\nu = \mathcal{N}(m_2, \Sigma_2)$ について：

• 指数的収束: 著者らは、クラスター・モーメント緩和（特に次数1）が、参照グラフ $G_h$ の連結半径 $h$ が増加するにつれて、近似誤差において指数的な収束率を達成することを証明している。誤差境界は $C d \rho^{-h}$ の形式をとる。
• 改善されたサンプル複雑度: スパースな緩和の統計的誤差境界は $O(\sqrt{d/N} + |E(G)|/N)$ である。$|E(G)| = O(d)$ であるスパースグラフの場合、これは密な緩和の境界 $O(\sqrt{d/N} + d^2/N)$ を改善しており、スパース性を利用することで必要なサンプル数を大幅に削減できることを示している。

3.2 平均場測度の局所的摂動

平均場積測量の局所的摂動である分布について：

• 近似境界: 周辺緩和は、ワッサースタイン距離の主要な幾何学的構造（重み付き負の同次ソボレフノルムに対応）を捉えることが示されている。
• 統計的誤差: 固定された緩和次数と限定されたクラスターサイズの下で、統計的誤差は $O(d N^{-1/2})$ とスケールし、これは $O(d^2 \epsilon^{-2})$ のサンプル複雑度を意味する。これは、標準的なOT推定に見られる $d$ に対する指数関数的な依存関係と比較して、大幅な改善である。

3.3 一般的な統計的境界

一様なガウス・テイル条件を満たす一般的な分布に対し、本論文は、クラスター・モーメントSDPの統計的誤差が、周囲の次元 $d$ ではなく、ローカルブロックおよびグラフのエッジの数（$K + |E(G)|$）によって支配されることを確立している。固定された次数を持つスパースなレジームにおいて、誤差は $d$ に対して線形にスケールする。

4. 数値実験の結果

広範な実験により、以下の設定における理論的主張が検証されている：

• ガウス分布: クラスター・モーメント緩和は、連結半径 $h$ に対して指数的な収束を示す。次元 $d$ が 1000 まで増加しても、低い相対誤差と実行時間を維持しながら、標準的なOTソルバー（Sinkhorn）やICNNのベースラインを上回る性能を発揮する。
• 非ガウス積測量 (Beta分布): 本手法は、非ガウス積測量に対しても高い精度（相対誤差 $\approx 10^{-3}$）を維持する一方で、標準的なOTソルバーは次元とともに急速に劣化する。
• イジングモデル: 離散イジングモデルにおいて、周辺緩和は、厳密なLP解よりも数桁速い実行時間で、OTコストのタイトな下界を提供する。
• 生成モデリング (Ginzburg-Landau & MNIST): 抽出された輸送写像は、ターゲットの周辺分布に一致するサンプルを正常に生成する。Ginzburg-Landauモデルにおいて、本手法はスライス・ワッサースタイン距離において、ノーマライジング・フロー、ICNN、およびSinkhornベースの写像を凌駕する。MNIST（6次元のPCA空間）において、本手法は認識可能な数字のサンプルを生成する。

5. 意義と主張

本論文は、凸緩和が、高次元の最適輸送における次元削減のための有望な経路であることを主張している。

• スケーラビリティ: 局所構造とスパース性を活用することで、標準的なOTや完全なモーメント階層の指数関数的な複雑さを回避し、特定の構造的仮定の下で、誤差と実行時間の両方において次元に対して線形なスケーリングを実現している。
• 理論的保証: ニューラルネットワークのアプローチとは異なり、提案手法は、特にスパースなガウスモデルや平均場摂動モデルに対して、厳密な近似および統計的誤差の境界を提供する。
• 解釈性: 本アプローチは、多項式ポテンシャルから導出される明示的な輸送写像をもたらし、深層生成モデルに対する、より単純で解釈可能な代替手段となる。
• 堅牢性: 実験結果は、理論的保証が明示的でない非ガウスの設定においても、本手法が堅牢であることを示唆しており、従来の離散化ベースの手法が失敗する場面でも性能を維持している。

著者らは、これらの緩和手法が次元の呪いを効果的に軽減し、広範な構造化された分布に対して高次元OTを計算上および統計的に扱いやすくすることを結論づけている。