背景

エントロピー正則化付き最適化問題
- Primal (4.2) $L^\varepsilon_C({\bf a}, {\bf b}) = \min_{{\bf P}\in U({\bf a},{\bf b})} \langle {\bf P}, C\rangle - \varepsilon H({\bf P})$
- Dual (4.30) $L_C^\varepsilon(a,b) = \max_{f, g} \langle f, a\rangle + \langle g, b\rangle - \varepsilon \langle \exp(f/\varepsilon), K\exp(g/\varepsilon)\rangle$
Sinkhornアルゴリズム最高 → ちゃんと収束するし，高速化できるよ．安定化するためにはLogドメインが必須だよ．
- $\mathbf{u}^{(l+1)} = \frac{\mathbf{a}}{\mathbf{Kv}^{(l)}}$, $\mathbf{v}^{(l+1)} = \frac{\mathbf{b}}{\mathbf{K}^T\mathbf{u}^{(l + 1)}}$
今回: 近似性能とかについて知りたい

Prop 4.5 エントロピー正則化付きdual問題の解は，正則化なし問題の解の下界になる

(4.30)の最適解$f^\star, g^\star$は，元の問題のfeasibleなdual$(f^\star, g^\star)\in R(C)$になっている
結果として下界になる
- $\langle f^\star, a\rangle + \langle g^\star, b\rangle \leq L_C(a, b)$

$L_C^\varepsilon(a,b)$が$a, b$のjointly convex functionであり，勾配方向を作れる
- この$f^\star, g^\star$を使っている（理由はよくわからない）

$$\nabla L_C^\varepsilon (a, b) = \begin{pmatrix} f^\star \\ g^\star \end{pmatrix}$$

(4.2)と(4.30)の最適解を$P^\star, f^\star, g^\star$とし，以下の値を計算する
- $\mathfrak{P}^\varepsilon_C(a,b) := \langle C, P^\star\rangle$
- $\mathfrak{D}^\varepsilon_C(a,b) := \langle f^\star, a\rangle + \langle g^\star, b\rangle$ ← これはProp 4.5の左辺
次のProp 4.7が成り立つ

$$\mathfrak{P}^\varepsilon_C(a,b) \leq L_C(a,b) \leq \mathfrak{D}^\varepsilon_C(a, b)$$

これは収束した後にのみ成り立つので，Sinkhornを途中で止めた場合には必ずしも成り立たない
しかしせいぜい$L$回程度計算した場合の解を利用した値であっても利用できる
- $\mathfrak{D}_C^{(L)}(a,b) := \langle f^{(L)}, a\rangle + \langle g^{(L)}, b\rangle$

$$\mathfrak{D}^{(L)}_C(a, b) \leq L_C(a,b)$$