最適輸送の収束理論 —— シンクホーンアルゴリズムとピンスカーの不等式

前章では、エントロピー正則化を導入することで、最適輸送問題が「行列スケーリング（行と列の割り算の反復）」という極めてシンプルなシンクホーンアルゴリズムに帰着することを見ました。 本章では、このアルゴリズムが「本当に最適解へ収束するのか？」そして「何回の反復で計算が終わるのか？」という問いに対し、ヒルベルト距離を用いた大域的収束性の保証と、情報理論における重要な定理「ピンスカーの不等式」を用いた厳密な計算量評価の数理を解き明かします。

1. ヒルベルト距離と縮小写像（大域的収束性）

シンクホーンアルゴリズムは、ベクトル と を交互に更新する手法でした。

この更新則が最適解 に必ず到達することを証明するために、ヒルベルト射影距離（Hilbert Projective Metric） という特殊な距離の測り方を導入します。 ヒルベルト距離の空間において、ギブスカーネル を掛けるという操作は、距離を必ず一定の割合 で縮める「縮小写像」として働くことがバーコフ（Birkhoff）の定理によって知られています。

更新を繰り返すたびに、現在のベクトル と真の最適解 との距離が係数 倍されて確実に縮んでいくため、無限回繰り返せば必ず最適解に到達する（大域的収束性）ことが数学的に保証されるのです。

2. 目的関数の変化と停止条件

では、現実の計算機でプログラムを回す際、いつ計算を「停止」すればよいでしょうか。 アルゴリズムを1ステップ進めたときの、双対目的関数 の上昇幅を計算すると、現在の輸送プランの周辺分布 と目標とする供給量 の間の KL情報量（） に比例することが分かります。

私たちが最終的に達成したい目標は、輸送プランの行の和と列の和が、それぞれ目標値 に完全に一致することです。そこで、このズレ（L1ノルムでの誤差）が許容範囲 より小さくなった時を停止条件とします。

3. ピンスカーの不等式（Pinsker's Inequality）の導出

ここで一つの問題が生じます。アルゴリズムが改善していく指標は「KL情報量」ですが、私たちが判定したい停止条件の誤差は「L1ノルム（絶対値の和）」です。 この2つを結びつける強力な定理が ピンスカーの不等式 です。

この不等式は、以下の2つの数学的テクニックを鮮やかに組み合わせることで証明されます。

① テイラー展開による2次下界

KL情報量の中に現れる関数 を考えます。この関数の2階微分は であり、下に凸です。 平均値の定理とテイラー展開を用いると、この関数は2次関数によって下から抑え込む（下界を作る）ことができます。

これをKL情報量の定義式 に適用すると、次のような不等式が得られます。

② コーシー・シュワルツの不等式

次に、求めたいL1ノルム に対して、強引に を掛けたり割ったりして、ベクトルの内積に関する コーシー・シュワルツの不等式 を適用します。

確率分布であるため となり、右辺の最初の括弧は になります。 これを①の結果と組み合わせることで、見事にピンスカーの不等式が導出されます。

（※ 対数の底の取り方等により係数は調整されますが、本質的な関係性は同じです）

4. 計算量とステップ数

ピンスカーの不等式を用いることで、「L1ノルムの誤差 は、1ステップごとの目的関数 の上昇幅によって上から抑えられる」ことが証明されました。

この関係式を全ステップにわたって足し合わせることで、許容誤差 に到達するために必要な最大反復回数 を見積もることができます。

（ はカーネル行列の最小要素などに基づく定数）

この結果は驚異的です。シンクホーンアルゴリズムは、巨大な行列の最適化でありながら、求める精度 に対して高々 のオーダーのステップ数で確実に計算が完了（停止）することが、厳密な数学的裏付けをもって保証されているのです。