Computational Optimal Transport 精読会 記録 (#9: 3.7)

# 背景


- 前回: [Computational Optimal Transport 精読会 記録 (#8: 3.6)](https://qiita.com/takilog/items/10cd50382c6f2471653a)はGW後の5/8に開催，今回は一週間あいて5/23に開催
- 職場でCOTを読んでおり，{自己満足,復習,将来のため}などの理由で記録をしている


# 今回の範囲の内容

- Sinkhornあたりと関係があるらしいオークションアルゴリズムによる計算


# アンチョコ

- Kantorovich problem: $L_C(\mathbf{a,b}) = \min_{\mathrm{P}\in U(\mathbf{a, b})} \langle C, P \rangle$, $U(a, b) = \\{\mathrm{P}\in \mathbb{R}_+^{n\times m}\mid \mathrm{P} \mathbb{1}\_m = \mathbf{a}, \mathbf{P}^T \mathbb{1}\_n = \mathbf{b} \\}$

- Dual problem $L_C(\mathbf{a,b}) = \max_{(\mathbf{f, g})\in R(C)} \langle \mathbf{f, a}\rangle + \langle \mathbf{g, b}\rangle$, $R(C) = \\{(\mathbf{f,g})\in\mathbb{R}^n\times \mathbb{R}^m \mid \mathbf{f \oplus g} \leq C\\}$

- $G({\bf P})$は輸送が存在する山の間に辺をはった二部グラフ

- *complementary*: もし${\bf P}\_{i,j} > 0$ (輸送する)ならば，$C_{i,j} = {\bf f}_i + {\bf g}_j$であること

- *feasible*: $\mathbf{f} \oplus \mathbf{g} \leq \mathbf{C}$であること


# §3.7 Auction Algorithm

- イマイチ何がオークションなのかよくわからないがこのタイトル（本来はより一般的な枠組みらしい）
- ここではKantrovichでもなく割当$\sigma$の最適化に関する議論からオークションアルゴリズムを学ぶ

- 最適割当 $\sigma^\star$ が分かっている場合，complementary slacknessが成立
    - このときのdual側の最適解が$\mathbf{f}^\star, \mathbf{g}^\star$
    - CS性: $\mathbf{f^\star\_i} + \mathbf{g^\star\_{\sigma^\star\_i}} = C\_{i,\sigma^\star\_i}$

- 以前使ったC-Transformを思い出す: [参考 Computational Optimal Transport 精読会 記録 (#5: 3.1-3.2)](https://qiita.com/takilog/items/078e716757389525fa9f)
- C-Transformを利用することで$\mathbf{f}^\star = \mathbf{g^\star}^{\bar{C}}$にできる
    - 補足: C-Transformで解が改善するが，ここでは最適解なので一致する
    - C-Transformの定義より次が成り立つ: $C\_{i,\sigma^\star\_i} - \mathbf{g^\star\_{\sigma^\star\_i}} = \min\_{j} C\_{i,j} - \mathbf{g^\star\_j}$
- これは逆も成り立つ
    - 証明: Prop 3.3より成り立つ
    - [参考 Prop 3.3はここで出てきた: Computational Optimal Transport 精読会 記録 (#6: 3.3-3.4)](https://qiita.com/takilog/items/94be71f5ddfbee8c4b11)
    - つまり右辺はC-Transformなので，これを使うとfeasibleでありComplementaryであることが示せ，最適となる


## オークションアルゴリズムのやること

- オークションアルゴリズムは部分解 $S, \xi, \mathbf{g}$ を計算していく
    - $S$はすでに割当が計算されている箇所の集合
    - $\xi$は部分割当
    - $\mathbf{g}$はdual vector

- 計算は$S=\emptyset$から初めて，以下の(a)-(c)を常に満たした状態で計算を行う
    - (a) 任意の$i$について，$\epsilon$-CSが満たされる: $C\_{i,\xi\_i} - \mathbf{g}\_{\xi\_i} \leq \epsilon + \min\_{j} C\_{i,j} - \mathbf{g\_j}$: CS性の条件を小さな正の数$\epsilon$で緩めた
    - (b) $S$が必ず大きくなっていく
    - (c) $\mathbf{g}\_i$が最小でも$\epsilon$減少するような$i$が存在すること


- 処理1: 2nd bestを選んで値を更新
    - $j\_i^1 \in \arg\min\_{j} C_{i, j} - \mathbf{g}\_j$
    - $j\_i^2 \in \arg\min\_{j, j\neq j\_i^1} C_{i, j} - \mathbf{g}\_j$
    - ここで得られた2つのインデクスを利用して，最小の位置を更新
        - $\mathbf{g}\_{j\_i^1} \leftarrow \mathbf{g}\_{j\_i^1} - \left( (C\_{i,j\_{i}^2} - \mathbf{g}\_{j\_i^2}) - (C\_{i,j\_{i}^1} - \mathbf{g}\_{j\_i^1}) + \epsilon \right) = C\_{i,j\_i^1} - (C_{i,j\_i^2} - \mathbf{g}\_{j\_i^2}) - \epsilon$


- 処理2: 更新に利用した2つのインデクスを確認して部分割当$\xi$を更新
    - もし$i'\in S$について$\xi\_{i'}=j\_i^1$ （すでに使われていた）
        - $S$から$i'$を取り除き，$j\_i^1$に置き換え，今の処理1で固定している$i$を$S$に加える
    - そうでないとき，$\xi$は大きくならないが，どこかの値が減少している

## Prop 3.7

- 主張: 更新によって$\epsilon$-CS性が崩れない
- 式展開から自然と成り立つ（ここは式展開が丁寧なので分かる）


## Prop 3.8

- 計算量(更新回数)に関する主張
- よく分からなかったので教えてもらった

- (メモ)
    - もし止まってないとする
    - このときdual vector $\mathbf{g}\_j=0$となっている(まだ計算されていないので初期値のまま)
    - そしてこのとき**仮定として**，$n > ||C||\_\infty/\epsilon$とする（ここから背理法）
        - 式展開から，更新したときに$\epsilon$-CSが満たされなくなってしまう
        - しかしアルゴリズムは$\epsilon$-CSを保存することが確認されていたのでおかしく，仮定が間違っている
    - よって更新回数が抑えられる


## Prop 3.9

- オークションアルゴリズムの解の質について，$n\epsilon$-suboptimalである
- 式展開から分かる（ここも式展開が丁寧なのでそのまま）


# Next

- 5/28に開催