Sample complexity of unbalanced entropic OT

技術要約：不均衡エントロピー的最適輸送のサンプル複雑性

問題提起
最適輸送（OT）は、確率測度を比較するための幾何学的枠組みを提供するが、古典的な均衡型OTには、機械学習への応用において2つの重大な制限がある。(1) 質量の保存に関する硬い制約が、質量の欠落や生成があるデータに対して不適切であること、および (2) 高次元におけるサンプル複雑性（「次元の呪い」）が悪化し、経験的な収束率が周囲の次元とともに低下することである。

エントロピー正則化および不均衡緩和（$\phi$-ダイバージェンスを用いたもの）は、これら個別の問題に対処するために開発されてきたが、不均衡エントロピー的OTに関する既存の統計的保証は、主にスカラー輸送値（目的関数）に限定されている。**最適結合（輸送プラン）**に対する高確率な有限サンプル境界に関する直接的な研究は不足している。このギャップは、生成モデリングや軌跡推論などのアプリケーションにおいて、目的となる対象が単なるコスト値ではなく、結合そのものであるため、極めて重要である。

手法
本論文は、双対問題の幾何学的特性に焦点を当てることで、不均衡エントロピー的OTの統計的解析を展開する。核心となる手法上の革新は、不均衡設定において失われるゲージ不変性を扱うための、**平行移動不変エンベロープ（translation-invariant envelope）**定式化の導入である。

1. 双対定式化とエンベロープの構築:
   均衡型OTでは、双対目的関数はカントロヴィッチ・ポテンシャルの加法的平行移動（$f \to f+\lambda, g \to g-\lambda$）に対して不変であるが、不均衡型OTでは、絶対的なポテンシャルレベルに依存する周辺ダイバージェンス・ペナルティにより、この対称性が崩れる。著者らは、平行移動不変エンベロープ $T_{\alpha, \beta}(f, g) := \inf_{\lambda \in \mathbb{R}} K_{\alpha, \beta}(f+\lambda, g-\lambda)$ を定義する。この構成は、双対関数の本質的な自由度と、偽の平行移動方向を明示的に分離する。

2. 幾何学的解析（コンパクト性と強凸性）:
   著者らは、緩やかな仮定（コンパクトな空間、リプシッツ連続なコスト）の下で、このエンベロープ関数が、ポテンシャルがソース測量に対して平均ゼロとなるように固定されたコンパクトなアンカー付き最小化領域（$P_{\alpha, \beta}^0$）を持つことを証明する。決定的なことに、この領域において、エンベロープは重み付き $L^2$ ノルムに関して一様に強凸となる。これにより、標準的な不均衡双対において失われた良好な幾何学的構造が回復される。

3. 平行移動パラメータの制御:
   エンベロープはゲージ固定の必要性を排除する一方で、平行移動パラメータ $\lambda$ に関する最適化を導入する。本論文では、ダイバージェンス生成子の緩やかなドメイン条件（仮定A2）の下で、最適な $\lambda$ が一様に有界な区間$[-R, R]$ に限定されることを確立する。これにより、双対ポテンシャルの一様 $L^\infty$ 境界が可能となる。

4. 統計的安定性:
   アンカー付きエンベロープの強凸性と平行移動パラメータの有界性を活用することで、著者らは安定性推定値を導出する。経験的双対ポテンシャルが母集団ポテンシャルに一様に収束することを示す。これらの双対収束率は、指数スケーリング関係（$d\pi/d(\alpha \otimes \beta) \propto \exp((f \oplus g - c)/\eta)$）を介して、原始的な輸送プランへと転移される。

主な貢献

• 平行移動不変な双対定式化: 本論文は、翻訳方向を商集合化することで、不均衡エントロピー的OTに対して強凸性を回復させる厳密な双対定式化を導入する。この性質は、これまでSinkhorn反復のアルゴリズム的安定性にのみ利用されていたものである。
• プランレベルのサンプル複雑性: 主な貢献は、単なる目的関数値ではなく、最適結合（輸送プラン）に関する高確率な有限サンプル境界の導出である。
• 一般的なダイバージェンスへの適用可能性: 結果は、ダイバージェンス固有の証明を必要とせず、一般的な凸性とコンパクト性の議論に依拠することで、広範なクラスの$\phi$-ダイバージェンス（KL、$\chi^2$、ヘリンジャー、イェンセン・シャノン、$\alpha$-ダイバージェンスを含む）に適用される。
• 明示的な定数: 論文は、平行移動パラメータおよび結果として得られるサンプル複雑性に関する境界の明示的な定数を提供し、エントロピーパラメータ $\eta$、コスト関数、およびダイバージェンスの特性への依存関係を明確にしている。

主な結果
$n$ 個のサンプルから導出された経験的測度 $\alpha_n, \beta_n$ に対して、経験的最適プラン $\pi_n$ と母集団プラン $\pi^\star$ の偏差は、以下の形式の高確率境界を満たすことを本論文は確立している：
$$|\langle h, \pi^\star - \pi_n \rangle| \lesssim C \cdot e^{C(M + \|c\|_\infty)/\eta} \|h\|_\infty \sqrt{\frac{m_\alpha m_\beta (\log n + t)}{n}}$$
ここで、$M$ は双対ポテンシャルの一様境界、$h$ はテスト関数であり、定数は問題の幾何学およびダイバージェンスのパラメータに依存する。注目すべき点として、サンプリング分布が周辺分布の積と一致する場合、$\log n$ の因子は除去可能である。

意義と主張
本論文は、これらの結果が、機械学習におけるOTの応用における正則化の実用的な必要性を明確にすることを主張している。具体的には：

• 次元性の緩和: 正則化は次元の呪いを和らげ、安定した輸送推定に必要なサンプル数を減少させる。
• アルゴリズムとの互換性: 得られる推定量は、スケーラブルなSinkhorn型のソルバーと互換性を保ち、統計理論と計算実践の間の溝を埋める。
• 逆問題への安定性: 提供される順方向の安定性推定は、関連研究 [1] で述べられているように、逆問題（例：サンプルからのコストの回復）の随伴解析にとって不可欠である。

著者らは、本解析が「非常に緩やかで、ほぼダイバージェンスに依存しない仮定」に基づいていることを強調しており、この理論的枠組みが実用で使用される標準的なモデルに対して堅牢であることを示している。彼らは次元の呪いそのものを解決すると主張しているのではなく、高次元の設定において、エントロピー的不均衡型OTがいかに統計的に扱いやすい代替手段を提供するかを実証している。