Corollary 6.3.2（Rockafellar 1970）

定理

もし $C$ が $\mathbb{R}^n$ の凸集合であるならば、$\operatorname{cl}C$ と交わる任意の開集合は、$\operatorname{ri}C$ とも交わる。

証明

　任意の開集合を$A$として、$\operatorname{cl} C \cap A \neq \emptyset \Rightarrow \operatorname{ri}C \cap A \neq \emptyset$を示せば良い。 $\exists \epsilon > 0, \quad \exists x \in \operatorname{cl} C \cap A \quad\text{s.t.} \quad x + \epsilon B \in A, \quad x + \epsilon B \in \operatorname{cl}C$となる。 Theorem 6.2（Rockafellar 1970）およびTheorem 6.3（Rockafellar 1970）より、

となり、$x \in \operatorname{ri}C \cap A$となる$x$は存在する。よって示された。

参考文献

Tyrrell Rockafellar, R, 1970 p46

Corollary 6.3.1（Rockafellar 1970）

定理

$\mathbb{R}^n$ 内の凸集合 $C_1$ と $C_2$ に対して、$\operatorname{cl} C_1 = \operatorname{cl} C_2$ であることは $\operatorname{ri} C_1 = \operatorname{ri} C_2$ であることと同値である。これらの条件は $\operatorname{ri} C_1 \subset C_2 \subset \operatorname{cl} C_1$ という条件に等しい。

証明

(「$\operatorname{cl}C_1 = \operatorname{cl}C_2 \Rightarrow \operatorname{ri}C_1 = \operatorname{ri}C_2$」の証明)
　仮定およびTheorem 6.2（Rockafellar 1970）より、$\operatorname{aff}(\operatorname{cl}C_1) = \operatorname{aff}C_1 = \operatorname{aff}C_2 = \operatorname{aff}(\operatorname{cl}C_2)$となる。また、$C_1 \subset \operatorname{cl}C_1 =\operatorname{cl}C_2$となる。

　よって、$\forall x \in \operatorname{ri}C_1 = \lbrace x \in \operatorname{aff}C_1 \mid \exists \epsilon > 0, (x + \epsilon B)\cap \operatorname{aff}C_1 \subset C_1 \rbrace$は、$x \in \lbrace x \in \operatorname{aff}(\operatorname{cl})C_2 \mid \exists \epsilon > 0, (x + \epsilon B)\cap \operatorname{aff}(\operatorname{cl})C_2 \subset \operatorname{cl}C_2 \rbrace = \operatorname{ri}(\operatorname{cl}C_2)$となる。Theorem 6.3（Rockafellar 1970）より、$\operatorname{ri}(\operatorname{cl}C_2) = \operatorname{ri}C_2$となるため、$\operatorname{ri}C_1 \subset \operatorname{ri}C_2$が示される。$\operatorname{ri}C_1 \supset \operatorname{ri}C_2$についても同様に示される。

(「$\operatorname{cl}C_1 = \operatorname{cl}C_2 \Leftarrow \operatorname{ri}C_1 = \operatorname{ri}C_2$」の証明)

となり、示された。

(「$\operatorname{cl}C_1 = \operatorname{cl}C_2 \Rightarrow \operatorname{ri}C_1 \subset C_2 \subset \operatorname{cl}C_1$」の証明)
　仮定より$\operatorname{cl}C_1 = \operatorname{cl}C_2 \supset C_2$となる。また、$C_2 \supset \operatorname{ri}C_2 = \operatorname{ri}C_1$が成立する。よって、示された。

(「$\operatorname{cl}C_1 = \operatorname{cl}C_2 \Leftarrow \operatorname{ri}C_1 \subset C_2 \subset \operatorname{cl}C_1$」の証明)

となる。また、$\operatorname{ri}C_1 \subset C_2$より$\operatorname{cl}(\operatorname{ri}C_1) \subset \operatorname{cl}C_2$となり、Theorem 6.3（Rockafellar 1970）から$\operatorname{cl}C_1 \subset \operatorname{cl} C_2$となる。よって示された。

参考文献

Tyrrell Rockafellar, R, 1970 p46

【備忘】A Distributional Interpretation of Robust Optimization

論文の概要

　本論文は、決定変数と不確実性を表す分布の台が同じ空間に属するとき、ある条件の下Robust Optimization（RO）の最適解がDistributionally Robust Stochastic Programming（DRSP）の最適解と漸近的に一致することを示したものである。
　詳細な問題設定としては、最適化対象の関数$f(\cdot, \cdot) : \mathbb{R}^{n} \times \mathbb{R}^{m} \mapsto \mathbb{R} \cup \lbrace -\infty \rbrace$は可測関数であり、データ$\lbrace x_n \rbrace$は確率分布$h^{*}$からiidで観測されたとする。また$f$は有限でかつ同程度連続であるとする、つまり$\max_{x, v} | f(v,x) | \le Const$、かつ$d(\epsilon) := \max_{x, v, | \delta |_{\infty} \le \epsilon} | f(v, x + \delta) - f(v,x) | \rightarrow 0$である。
　このとき、次のROの最適解$v_{(n)}$はDRSPの解となる。
つまり、$v_{(n)} := \arg\max_v \frac{1}{n} \sum_{i=1}^{n} \inf_{|\delta_i|_\infty \le \epsilon(n)} f(v, x_i + \delta_i)$に対して、

が成立する。

不明点

　詳細は割愛するが、本論文のTheorem１、２の証明において不明な箇所があった。
-（Theorem１）：$f( \hat{x}_{i} )$の定義において、$\inf$ではなく$\max$が使用されている点
-（Theorem１）：$\sum_{k=1}^{n} \alpha_k f( \hat{x}_{k} ) \ge \sum_{k=1}^{n} c_k f( \hat{x}_{k} )$が成立する理由
-（Theorem２）：$\frac{| S |}{n}$が導出できる箇所。（$2^{m}$や$\epsilon(n)^{m}$などが消去できた理由）
-（Theorem２）：最後、$\lim_n \int_{\mathbb{R}^{m}} f(v_{(n)},\mathbf{x}) h^{*} (\mathbf{x}) d\mathbf{x} = \lim_n \inf_{\tilde{\mu} \in \mathcal{P}_n} \int_{\mathbb{R}^{m}} f(v_{(n)}, \mathbf{x}) d\tilde{\mu}$より、Theorem２の式を導出できる理由

参考文献

Xu, Huan, Constantine Caramanis, and Shie Mannor. "A distributional interpretation of robust optimization." Mathematics of Operations Research 37.1 (2012): 95-110.

Theorem 6.3（Rockafellar 1970）

定理

$\mathbb{R}^n$ 内の任意の凸集合 $C$ に対して、$\text{cl} (\text{ri} C) = \text{cl } C$ かつ $\text{ri} (\text{cl } C) = \text{ri } C$ が成り立つ。

証明

($\text{cl} (\text{ri } C) = \text{cl} C$ の証明)
　$\text{ri } C \subset C$より$\text{cl} (\text{ri } C) \subset \text{cl} C$が成立する。
　次に$\text{cl} (\text{ri } C) \supset \text{cl} C$を示す。$\forall x \in \operatorname{cl}C$について$x \in \operatorname{cl}(\operatorname{ri}C)$を示せば良い。Proposition 1.3.2（Bertsekas 2009）より$C$が非空であれば$\operatorname{ri}C$は非空となるため、$y \in \operatorname{C}$となる$y$が存在する。ここでTheorem 6.1（Rockafellar 1970）より$x$と$y$を繋ぐ線分の内、$x$以外は$\operatorname{ri}C$に含まれる。その閉包をとることで、定義より$x \in \operatorname{cl}(\operatorname{ri}C)$が導かれ、示された。

($\text{ri} (\text{cl } C) = \text{ri } C$の証明)
　$\operatorname{cl} C \supset C$は成立する。Theorem 6.2（Rockafellar 1970）より、それぞれのアフィン包は一致することから、相対的内部の定義より$\operatorname{ri}(\operatorname{cl}C) \supset \operatorname{ri}C$となる。
　次に$\text{ri} (\text{cl} C) \subset \text{ri} C$を示す。$\forall x \in \operatorname{ri}(\operatorname{cl} C)$について$x \in \operatorname{ri}C$を示せば良い。
$\forall y \in \operatorname{ri}C$と、十分小さい$\epsilon > 0$を用いて定義される$\lambda (0 \le \lambda - 1 \le \epsilon)$とから定義される$x,y$の外分点点$z$を考える。 $$ z = \lambda x + (1-\lambda)y = x + (\lambda - 1)(x - y) = x + \epsilon (x-y) $$ と記述できる。この点は$x$に十分近い外分点であるため、$z\in \operatorname{cl}(\operatorname{ri}\operatorname{cl}C) = \operatorname{cl}(\operatorname{cl}C) = \operatorname{cl}C$となる。
　この外分点$z$の式を整理すると、$(1 - \frac{1}{\lambda})y + \frac{1}{\lambda}z = x$と記述でき、$0 < \frac{1}{1+\epsilon} \le \frac{1}{\lambda} \le 1$より、Theorem 6.1（Rockafellar 1970）から$x \in \operatorname{ri}C$となる。よって示された。

参考文献

Tyrrell Rockafellar, R, 1970 p46

Theorem 6.2（Rockafellar 1970）

定理

任意の凸集合 $C \subset \mathbb{R}^n$ に対し、$\operatorname{cl} C$ および $\operatorname{ri} C$ は同じアフィン包を持ち、それぞれ$C$と同じ次元を持つ。（特に、$C \neq \emptyset$ ならば $\operatorname{ri} C \neq \emptyset$ である。）

証明

　Theorem 3.1（Rockafellar 1970）より、$\forall \epsilon$に対して$C + \epsilon B$ は凸集合となる。よって、Theorem 2.1（Rockafellar 1970）より、$\operatorname{cl}C = \bigcap_{\epsilon > 0} (C + \epsilon B)$は凸集合となる。同様に、$\operatorname{aff}C$が凸集合であることから$\operatorname{ri}C$も凸集合となる。（Theorem 6.1（Rockafellar 1970）において、$y \in \operatorname{ri}C$として証明）

　それぞれが同じアフィン包を持つことを証明する。
まず$\operatorname{aff}\operatorname{cl}C = \operatorname{aff}C$であることを確認する。
$\operatorname{cl}C \supset C$より、$\operatorname{aff}(\operatorname{cl}C) \supset \operatorname{aff}C$となる。 また。$\operatorname{cl}C \subset \operatorname{cl}(\operatorname{aff}C) = \operatorname{aff}C$より、$\operatorname{aff}(\operatorname{cl}C) = \operatorname{aff}C$となる。
　よって、２つの集合は等しいことがわかる。

　次に$\operatorname{aff}(\operatorname{ri}C) = \operatorname{aff}C$であること及び$\operatorname{ri}C \neq \emptyset$は、Proposition 1.3.2（Bertsekas 2009）にて示される。
　よって、$\operatorname{cl}C, \operatorname{ri}C$はそれぞれ同じアフィン包をもつ。

　それぞれの次元はTheorem 2.4（Rockafellar 1970）より、それぞれに含まれる最大の単体の次元、つまりアフィン包の次元と等しい。それぞれのアフィン包は$\operatorname{aff}C$であるため、$C$の次元と等しい。

参考文献

Tyrrell Rockafellar, R, 1970 p45

【備忘】GraphKAN: Enhancing Feature Extraction with Graph Kolmogorov Arnold Networks

論文の概要

　本論文は、Graph Neural Network（GNN）の非線形変換器をMultilayer Perceptron（MLP）からKolmogorov-Arnold Networks（KAN）に変更したもので、類似研究（KAGNNs：論文、備忘録）と同じ内容である。本論文で提案しているモデルGraphKANは、類似研究で提案されているKANGCNと同等の構造を持ったモデルである。
　本論文と類似研究とで主張している内容に違いはあまりない。強いて違いをあげるなら、グラフノードの複雑な構造を捉えるのにReluの様な活性化関数では不適切と言及した点、また性能評価において表現能力を確認するにあたりKANの特徴表現をT-SNEで確認している点がある。類似研究の方が性能評価はしっかりしていた。

参考文献

Zhang, Fan, and Xin Zhang. "GraphKAN: Enhancing Feature Extraction with Graph Kolmogorov Arnold Networks." arXiv preprint arXiv:2406.13597 (2024).

【備忘】KAGNNs: Kolmogorov-Arnold Networks meet Graph Learning

論文の概要

　本論文は、Graph Neural Network（以下、GNN）で用いられる特徴変換器をMultilayer Perceptron（以下、MLP）を、Kolmogorov-Arnold Networks（以下、KAN）に置き換えて、その有効性を確認した論文である。
　GNNにおいてMLPは広く用いられているが、その非凸性により収束性や解釈性に難がある。一方KANは、関数の近似精度や解釈性がMLPよりも優れているため、GNNに組み込むことで、従来のGNNよりも優れた性能を発揮すると考えられる。そこで、GNNの構造であるGCN/GINのMLP部分をKANに置き換えた、KANGCN/KANGINを提案した。これらの有効性の確認にあたり、各種データセットを用いてノード分類、グラフ分類、グラフ回帰を行った。
　結果として、ノード分類においては種々のデータセットにおいてKANを用いた方が性能が良い場合が多く、またグラフ回帰においては顕著に性能が良く、その有効性は示唆された。しかし、グラフ分類においては、KANを用いた方が優れた結果が得られることは多いものの、その差はほとんどなかった。また連続値を取り扱うデータセットにおいては、それらの差と比較して大きく性能は劣る結果が得られた。このことから、KAN/MLPを用いたGNNはのグラフ識別能力は同等であると考えられる。またKANは連続値の特徴量を扱うのには適していな可能性があると言える。

提案手法

　詳細な記法を割愛して、KANGINおよびKANGCNの構造を示す。

KANGCN

　ノード$v$の$l$回目の埋め込み後の特徴量$h_{v}^{l}$は次のように定義される。

　ここで、$\phi^{l}$は一層からなるKANである。従来のGNNでは$\phi^{l}$の箇所が活性化関数であった。このモデルはノード分類問題でのみ性能評価を実施している。 　

KANGIN

　KANGCNと同様に、$h_{v}^{l}$は、

と記述できる。MLPを用いたGINでは、$\operatorname{KAN}^{l}$の箇所が$\operatorname{MLP}^{l}$となっている。KANGINは本論文において全てのタスクで性能評価されている。

参考文献

Bresson, Roman, et al. "Kagnns: Kolmogorov-arnold networks meet graph learning." arXiv preprint arXiv:2406.18380 (2024).

以上。