背景
- 前回: Computational Optimal Transport 精読会 記録 (#16: 4.4 その2)は7/26に開催，今回は7/31に開催
- 職場でCOTを読んでおり，{自己満足,復習,将来のため}などの理由で記録をしている
前回の振り返りと今回の内容
- エントロピー正則化付き最適化問題
- 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)$
Prop 4.5の証明
- $\exp(-(f^\star_i + g^\star_j - C_{ij}) / \varepsilon) \leq 1$ より成り立つ
Prop 4.5の嬉しいところ
- (4.2)がsmooth & convexであり，最適解が求まる
- (4.2)Primalの最適解から，(4.30)Dualの最適解を復元でき，これが元の$L_C(a,b)$の下界になる
Prop 4.6
- $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}$$
Def 4.1 Sinkhorn divergences
-
(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が成り立つ
Prop 4.7
$$\mathfrak{P}^\varepsilon_C(a,b) \leq L_C(a,b) \leq \mathfrak{D}^\varepsilon_C(a, b)$$
Prop 4.7の意味
- 正則化付きの解によって，元の最適化問題の上界・下界が得られる
Prop 4.7の証明
- 式変形から成り立つ
Prop 4.7の補足
- これは収束した後にのみ成り立つので，Sinkhornを途中で止めた場合には必ずしも成り立たない
- しかしせいぜい$L$回程度計算した場合の解を利用した値であっても利用できる
- $\mathfrak{D}_C^{(L)}(a,b) := \langle f^{(L)}, a\rangle + \langle g^{(L)}, b\rangle$
Prop 4.8 L回の場合
$$\mathfrak{D}^{(L)}_C(a, b) \leq L_C(a,b)$$
Prop 4.8の証明
- 上と同じ．ここはPDFだと$\epsilon$がついているけど，たぶん間違いじゃないかなと推測．
- 以下に残りの主張を書く．
Remark 4.26
- 以前，Sinkhornの計算を補正するAltschuler et al. 2017の式を書いた
- ここで言っていることは更新のタイミングによっては$P^{(2L+1)}$のようなPrimal側の値でバウンドを考えてもダメだよ，という話
Remark 4.27
- 非凸性について
- 数値的に非凸である例がすぐ出てくるので，証明しなくてよい
- ただし，行列計算程度のものになっているので，数値微分はできる(autogradとか)(たぶんそういう意味)
Next
- §4.6を読んで，ついに§4が終わり