を読んだ。

問題設定

データセットと学習アルゴリズムを固定したときに、入力に対する予測の誤差の期待値を抑えるのではなく、その期待値と、有限個の入力での誤差の平均の差(Generalization Error)を抑える。

→何個ぐらいからなるデータセットを用意すればいいかがわかる

Single Layer GCNNを考える。フィルターは $f(X, \Theta) = \sigma(g(L)X\Theta)$ の形をしている
固定されたグラフ上でのSemi-supervisedという設定
つまり、データセット内の $z_i=(x_i, y_i)$ （頂点属性）のペアは未知の分布に従う $\mathcal{D}$ からサンプルされたものだとする
SGDで学習しているとする
activation function $\sigma$ はリプシッツ連続かつリプシッツスムーズ
loss関数もリプシッツ連続かつリプシッツスムーズ

証明の重要ポイント

データセットの一要素が変わった場合を考える。このとき影響を受けるのは $\Theta$ のみ。 $\Theta$ の差分による寄与と、その他の係数に分ける。

やばい点

f:id:xuzijian629:20191110160939p:plain で $\lambda_G^{\mathrm{max}}$ のオーダー表記が正しいのは、最大固有値が1より大きい場合であるがこれは一般に成り立たない。さらに悪いことには $g(L) = A+ I$ のときには1以下なので困る。