確率的勾配降下法の理論入門（証明編）

こんにちは．[U-TOKYO AP Advent Calendar 2018](https://qiita.com/advent-calendar/2018/ut_ap) 10日目の担当のsnowhorkです．
この記事は，[確率的勾配降下法の理論入門](https://qiita.com/snowhork/items/db4abb114d3343a49539)の定理証明編です．

# 証明する定理
パラメーター$w$におけるデータ$(x_i, y_i)$に関する**損失関数**を$l_i(w)$とします．
損失関数のデータの分布に関する期待値$L(w)=\mathbb{E}_{x_i, y_i}(l_i(w))$を**汎化誤差**といいます．
$l_i(w)$が$a-$平滑な凸関数で，非負な損失関数である時，

```math
\mathbb{E}[L(\overline{w})]\leq \frac{1}{1-\eta a}(L(w^*) + \frac{{w^*}^2}{2\eta T})　\tag{1}
```

が成り立ちます．

この定理はSGDによって得られるパラメーター$\overline{w}$による汎化誤差と，最も良いパラメーターを用いた汎化誤差とのずれについての評価です．$\frac{1}{1-\eta a}$倍のずれで$O(1/T)$で収束していくということがわかります．

本項ではこれを証明したいと思います．

# 準備
あらためて凸関数や平滑関数の定義を紹介して，性質を紹介したいと思います．

## 凸関数
凸関数とは，グラフ上の２点で線分を引くと，それより下にグラフがくるような関数です．
凸関数の例
![image.png](https://qiita-image-store.s3.amazonaws.com/0/151852/01926fb2-7558-9654-3ff2-c15d7c471483.png)

上の例では，グラフ上の２点で緑の線分を引くと，青のグラフが必ず下にきます．
### 凸関数の定義

```math
関数fが凸関数であるとは，

f上の２点(x,f(x)),　(y, f(y))と，\\
それらの間の点(tx + (1-t)y), f(tx + (1-t)y)) について，\\
f(tx + (1-t)y) \leq tf(x) + (1-t)f(y) が成立することです．
```

### 凸関数の性質１
$f$が微分可能な凸関数の時，その勾配$f'(w)$について，全ての$w^*$について，

```math
f(w) - f(w^*) \leq f'(w)（w-w^*） \tag{2}
```
が成り立ちます．

（*証明*）
微分と平均変化率の定義からわかります．
![image.png](https://qiita-image-store.s3.amazonaws.com/0/151852/1cacb4cf-f056-1064-a0c2-e3a17d6867b8.png)

凸関数の場合，勾配は単調増加するので，

```math
\frac{f(w) - f(w^*)}{w-w^*} \leq f'(w) \ \ \  (w^* < w のとき)
```
が成り立ちます．$(w^* > w)$の場合も同様です．


### 凸関数の性質2
損失関数$l_i$が凸関数の時，$w_i$ と$\overline{w} = \frac{\sum_{i=1}^T w_i}{T}$について，

```math
L(\overline{w}) \leq  \frac{1}{T}\sum_i{L(w_i)} 　\tag{3}
```
が成り立ちます．

（*証明*）
$l_i$が凸関数なので，

```math
l_i(\overline{w}) \leq  \frac{1}{T}\sum_i{l_i(w_i)}
```
が成り立ちます．両辺を$x_i,y_i$について期待値を取れば，目的の式が得られます．（*証明終*）

この式を見れば，SGDにおいて各$w_i$を用いるよりは平均した$\overline{w}$を用いる方が期待値の意味で良いということがわかります．

## 平滑関数
今回考えている二乗損失の関数は平滑性があり，良い性質が成り立ちます．

### 平滑関数の定義
```math
微分可能な関数f(w)がa-平滑関数であるとは， 　\\
|f'(w) - f'(u)|\leq a|w-u| \ が成立することです．
```

### 平滑関数の性質
微分可能な関数f(w)がa-平滑関数であるとき，

```math
f(v)\leq f(w) + (v-w)f'(w) + \frac{a}{2} (v-w)^2
```

が成り立ちます．

（*証明*）
平滑関数の性質を用いるために，$f'(w+t(v-w))-f'(w)$を評価します．ただし，$t\in[0,1]$です．

```math
f'(w+t(v-w))-f'(w) \leq |f'(w+t(v-w))-f'(w)| \\
\leq a|w+t(v-w))-w| = at|v-w|
```

１行目から2行目において，平滑関数の性質を用いました．
両辺を$t$について[0,1]で積分します．

```math
\int_{[0,1]}(f'(w+t(v-w))-f'(w))dt \leq \int_{[0,1]} at|v-w|dt
```
まず右辺は，

```math
\int_{[0,1]}at|v-w| dt = \frac{a}{2}|v-w|
```
となります．次に左辺は，

```math
\int_{[0,1]}(f'(w+t(v-w))-f'(w)) dt = \frac{f(v) - f(w)}{v-w}-f'(w)
```

これらを代入すると，

```math
\frac{f(v) - f(w)}{v-w}-f'(w) \leq \frac{a}{2}|v-w|
```

$v>w$の時と，$v<w$の場合で場合分けが必要ですが，移項をすると目的の式が得られます．（*証明終*）

### 非負平滑関数の性質
$f$が非負であるとします．上の式で$v = w - \frac{1}{a}f'(w)$ ととることで，

```math
f(v)\leq f(w) + (- \frac{1}{a}f'(w))f'(w) + \frac{a}{2} (- \frac{1}{a}f'(w))^2　\\
= f(w) - \frac{1}{2a} (f'(w))^2 \\
```

```math
(f'(w))^2 \leq 2a(f(w) - f(v)) \leq 2af(w) \tag{4}
```

が成り立ちます．最後の不等式で$f$が非負であることを使いました．


## SGD
SGDのアルゴリズムを再掲します．

* $\eta$ を設定
* $w_1=0$ で初期化
* ステップ$i=1,2,\dots,T$で以下を繰り返す
    * $(x_i, y_i)$ をサンプル
    * $w_{i+1} = w_i - \eta l_i'{(w_i)}$ で更新
* $\overline{w} = \frac{\sum_i w_i}{T}$ を出力

### SGDの性質
(SGDに限らず），次のようにパラメーターを更新するとします．

```math
w_1=0, w_{i+1} = w_{i} - \eta v_{i}
```

このとき，全ての$w^*$について，

```math
\sum_{i=1}^T (w_i-w^*)i_t \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |v_i|^2 
```

が成り立ちます．特に，SGDの場合は，$v_i = l'(w_i)$なので，

```math
\sum_{i=1}^T (w_i-w^*)l'(w_i) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |l'(w_i)|^2 \tag{5}
```

が成り立ちます．

(*証明*)
今のステップと前のステップとの二乗差$(w_{i+1}-w^\*)^2-(w_i-w^*)^2$を比較するところが証明のポイントです．
更新式$w_{i+1} = w_i - \eta v_{i}$を使うことができます．

```math
(w_{i+1}-w^*)^2-(w_i-w^*)^2 = (w_i - \eta v_{i}-w^*)^2-(w_i-w^*)^2 \\
= -2\eta v_{i}(w_i-w^*) + (\eta v_{i})^2 
```

両辺について$i$に関して和を取ります．

```math
(w_{T+1}-w^*)^2-(w_1-w^*)^2 = -2\eta \sum_{i=1}^T v_{i}(w_i-w^*) + \sum_{i=1}^T (\eta v_{i})^2 
```

移項して評価すると，

```math
2\eta \sum_{i=1}^T v_{i}(w_i-w^*) \leq -(w_{T+1}-w^*)^2+(w_1-w^*)^2 + \sum_{i=1}^T (\eta v_{i})^2 \\
\leq (w_1-w^*)^2 + \sum_{i=1}^T (\eta v_{i})^2 \\
\leq (w^*)^2 + \sum_{i=1}^T (\eta v_{i})^2 
```

最後に$w_1=0$を代入しました．両辺を$2\eta$で割ると，目的の式が得られます．(*証明終*)

# 定理の証明
ここまででてきた凸関数の性質，平滑関数の性質，SGDの性質を全て組み合わせていくと目的の式(1)を証明することができます．

(*(1)の証明*)
まずはSGDの性質$(5)$を用います．

```math
\sum_{i=1}^T (w_i-w^*)l'(w_i) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |l'(w_i)|^2 \tag{5}
```

左辺の$(w_i-w^*)l'(w_i)$に注目して，凸関数の性質$(2)$を適用します．

```math
\sum_{i=1}^T (l_i(w_i)-l_i(w^*)) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T |l'(w_i)|^2 
```

右辺の$|l'(w_i)|^2$に注目して，非負平滑関数の性質$(4)$を適用します．

```math
\sum_{i=1}^T (l_i(w_i)-l_i(w^*)) \leq \frac{|w^*|^2}{2\eta} + \frac\eta 2 \sum_{i=1}^T (2a)l(w_i)  \\
= \frac{|w^*|^2}{2\eta} + \eta a \sum_{i=1}^T l(w_i)
```

移項して整理します．

```math
(1-\eta a)\sum_{i=1}^T l_i(w_i) \leq 
\sum_{i=1}^T l_i(w^*) + \frac{|w^*|^2}{2\eta}
```

両辺を$T$で割ります．

```math
(1-\eta a)\frac{\sum_{i=1}^T l_i(w_i)}{T} \leq 
\frac{\sum_{i=1}^T l_i(w^*)}{ T } + \frac{|w^*|^2}{2\eta T}
```

両辺の期待値を取ります．$\sum_{i=1}^T l_i(w^\*)=TL(w^*)$となります．

```math
(1-\eta a)\frac{\sum_{i=1}^T L(w_i)}{T} \leq 
\frac{TL(w^*)}{ T } + \frac{|w^*|^2}{2\eta T} = L(w^*) + \frac{|w^*|^2}{2\eta T}
```

最後に，凸関数の性質$(3)　L(\overline{w}) \leq  \frac{1}{T}\sum_i{L(w_i)}$を左辺に適用します．

```math
(1-\eta a)L(\overline{w}) \leq L(w^*) + \frac{|w^*|^2}{2\eta T}
```

両辺を$1- \eta a$でわると，目的の式が得られます．お疲れ様でした！ :tada: :tada: 

# まとめ
確率的勾配法は深い理論があり，その有効性が今でも研究されています．（最も簡単な例でも結構大変ですね...）
今回は簡単のためパラメーター$w$は1次元としましたが，多次元のパラメーターの場合でも全く同様に成立します．

最後に参考文献を挙げておきます．

[鈴木大慈 『確率的最適化』](https://www.amazon.co.jp/dp/B018K6C98G/ref=dp-kindle-redirect?_encoding=UTF8&btkr=1)
和書ですが，やや一般的・形式的な書き方がされているため，初学者には難しいかもしれません．

[S. Shalev-Shwartz, S. Ben-David 『Understanding Machine Learning: From Theory to Algorithms』](https://www.amazon.com/Understanding-Machine-Learning-Theory-Algorithms-ebook/dp/B00J8LQU8I)
洋書ですが，内容自体は初学者にもわかりやすいです．

U-TOKYO AP Advent Calendar 2018 はまだまだ続きます！