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

背景

• 前回: Computational Optimal Transport 精読会 記録 (#8: 3.6)は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)

• 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)
  • つまり右辺は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に開催