Stochastic Gradient Descent

# はじめに
今回は機械学習の学習の基本的なアルゴリズムであるStochastic gradient descentのアルゴリズムの理論を紹介します. 具体的には学習の収束が保証されることについての証明を見ていきます.

# ニュートン法の改良

$g(x^*) = 0$となる

$x^*$ を探す最適化アルゴリズムを考えます.

この問題を解くのに一番よく知られているアルゴリズムはニュートン法です. ニュートン法は$x^*$付近に$x_0$をとり、漸化式
```math
x_{n+1} = x_n-\frac{g(x_n)}{g'(x_n)}
```

によって$x^*$に収束する数列を作ることによって近似的に解を探します.
ニュートン法は$g$が明らかで決定的である場合には用いることができます. しかし, 例えば入力$x$に対して出力$g(x)$にノイズ$\epsilon$が入る場合はどうでしょう? ニュートン法では収束を保証することはできません.

# Stochastic Gradient Descent

Stochastic gradient descentは以下のように定式化されます.
```math
\begin{align}
x_{n+1}=x_n-\alpha_ny_n
\end{align}
```
ここで${\lbrace\alpha_n\rbrace}^\infty_{n=0}$は以下の条件を満たします.
```math 
\begin{align}
\sum_n\alpha_n = \infty \\
\sum_n\alpha_n^2 < \infty
\end{align}
```
このアルゴリズムが適切な仮定のもとで収束することをこれから示します.

# 準備1 優マルチンゲール(必要なところだけ) [^1]

[^1]: 今回は優マルチンゲールのみを使うのですがマルチンゲール, 劣マルチンゲールもあり, 定義2にある3つ目の性質の部分の不等号が違う場合の定義となります. 定理として述べている優マルチンゲールの収束定理はマルチンゲールや劣マルチンゲールでも成り立つ主張です.

この部分は飛ばしても一応読めるようにはします.

$(\Omega, \mathcal{F}, P)$を確率空間とします.

**定義1**
- 各$\mathcal{F}_n$は$\mathcal{F}$の部分$\sigma$-加法族で
- $\mathcal{F}_1 \subset \mathcal{F}_2 \subset \cdots$

を満たすとき,$(\mathcal{F}_n)$を情報系という.

**定義2**
確率過程$(X_n)$が情報系$(\mathcal{F}_n)$に関して優マルチンゲールとは
- $(\mathcal{F}_n)$-適合性: $\forall n \in \mathbb{N}, X_n$は$\mathcal{F}_n$-可測
- 可積分性: $\forall n \in \mathcal{N}, \mathbb{E}[|X_n|] < \infty$
- 確率1で$\forall n \in \mathbb{N}, \mathbb{E}[X_{n+1}|\mathcal{F}_n] \leq X_n$

が成り立っていることを言う.

**定理 優マルチンゲールの収束定理**
$(X_n)$を優マルチンゲールとし, $\sup_n \mathbb{E}[|X_n|] < \infty$が成り立っているとする. この時確率1で$X = \lim_{n \to \infty} X_n$.

証明は省略します.

# 準備2 Robbins-Siegmundの定理

準備としてRobbins-Siegmundの定理を証明します.

**主張**
$Z_n, a_n, b_n, c_n$を正の適合的確率変数[^2]で確率1で

[^2]: 確率変数列を0から順番に作っていく時に自分の添え字より小さい時点では値が決定しない変数のことです.

```math 
\begin{align}
\sum_n a_n = \infty, \sum_n b_n < \infty, \sum_n c_n < \infty
\end{align}
```
が成り立っているとします.

```math
\begin{equation}
\mathbb{E}[Z_{n+1}|\mathcal{F}_n] \lt (1-a_n+b_n)Z_n+c_n \tag{1} \\
\end{equation}
```
を満たす時,$ \lim_{n \to \infty} z_n = 0$.

**証明**
まず$\forall n, b_n = 0$の時で成り立つことを示せれば十分であることを確かめます.
(1)の両辺を$\prod_{m=0}^n(1-b_m)$で割ると
```math
\begin{align}
\mathbb{E}[Z_{n+1}'|\mathcal{F}_n] \leq (1-a_n')Z_n'+c_n'
\end{align}
```
となるように書き直すことができます.ここで
```math 
\begin{align}
a_n' = a_n / (1+b_n) \\
c_n' = c_n / \prod_{m=0}^n(1+b_m) \\
Z_n' = Z_n / \prod_{m=0}^n(1+b_m)
\end{align}
```
とします. ここで$\sum b_n < \infty$より$\prod (1+b_n) \leq \prod e^{b_n} = e^{\sum b_n} < \infty$.
よって$\sum_n a_n' = \infty, \sum_n c_n' < \infty, a_n',c_n', Z_n' > 0$となるので$b=0$の時のみを考えれば良いことがわかります.
ここで$Y_n=Z_n'+\sum_{k=0}^{n-1}a_k'Z_k'-\sum_{k=0}^{n-1}c_k'$とすると$Y_n \geq \mathbb{E}[Y_{n+1}|\mathcal{F}_n]$であることに注意します.

$(\because)$
$(1-a_n)Z_n'+c_n \geq \mathbb{E}[Z_{n+1}'|\mathcal{F}_n]$より
```math
\begin{align}
(1-a_n)Z_n'+\sum_{k=0}^{n-1}a_k'Z_k'-\sum_{k=0}^{n-1}c_k'+c_n &\geq \mathbb{E}[Z_{n+1}'|\mathcal{F}_n]+\sum_{k=0}^{n-1}a_k'Z_k'-\sum_{k=0}^{n-1}c_k' \\
Z_n'+\sum_{k=0}^{n-1}a_k'Z_k'-\sum_{k=0}^{n-1}c_k' &\geq \mathbb{E}[Z_{n+1}'|\mathcal{F}_n] + \sum_{k=0}^n a_k' Z_k' - \sum_{k=0}^n c_k' \\
Y_n &\geq \mathbb{E}[Z_{n+1}'|\mathcal{F}_n] + \mathbb{E}[\sum_{k=0}^n a_k' Z_k' - \sum_{k=0}^n c_k'|\mathcal{F}_n] \\
Y_n &\geq \mathbb{E}[Z_{n+1}' + \sum_{k=0}^n a_k' Z_k' - \sum_{k=0}^n c_k'|\mathcal{F}_n] \\
Y_n &\geq \mathbb{E}[Y_{n+1}|\mathcal{F}_n]
\end{align}
```
$\tau_C = \inf\lbrace n \geq 0: \sum_{k=0}^n c_k' > C\rbrace$とします [^3]. また$\tau \land \sigma := \min \lbrace \tau, \sigma \rbrace$とします.すると,

[^3]: マルコフ時刻

```math
\begin{align}
Y_{n\land\tau_C}&=Z_n'+\sum_{k=0}^{n\land \tau_C-1}a_k'Z_k'-\sum_{k=0}^{n\land\tau_C-1}c_k' \\
&\geq - \sum_{k=0}^{n\land \tau_C-1}c_k' \\
&\geq -C
\end{align}
```
$Y_{n\land \tau_C}$は優マルチンゲールで$-C$以上となることから優マルチンゲールの収束定理より任意の$c$について, $\lim_{n\to\infty}Y_{n\land\tau_C}$が存在します.・・・(2)

ここで$\sum c_k'<\infty$から$\exists C, \forall n, \sum_{k=1}^n c_k' < C$であることから,$\exists C, \tau_C=\infty$.
そのような$C$をとってくると$Y_{n\land \tau_C} = Y_n$となるので(2)と合わせて,$\lim_{n\to\infty}Y_n$が存在します.
$Y$の定義より
```math 
\begin{align}
\sum_{k=1}^n c_k'-\sum_{k=1}^na_k'Z_k'=Z_{n+1}'-Y_{n+1}\leq -Y_{n+1}
\end{align}
```
$\lim Y_n$と$\sum c_k'$が存在することから$\sum a_k' Z_k'$は収束します.
$Z_{n+1}' = Y_{n+1}+\sum_{k=1}^nc_k'+\sum_{k=1}a_k'Z_k'$より$\lim Z_n$が存在します.
さらに, $\sum_k a_k' =\infty, \sum_{k=1}^\infty a_k' Z_k' < \infty$であったことを思い出すと,$Z_k'$は$0$に収束します.

# Stochastic Gradient Descent
ノイズが入る時の最適化問題を定式化します.
$F:\mathbb{R}^p\to\mathbb{R}$を$F(\theta)=\mathbb{E}_X[f(X;\theta)]$と定義し$(\theta \in \mathbb{R}^p)$,最小化することを考えます.
ここで$f(X;\theta)$とその勾配$g(\theta;X)$は既知とし,$\mathbb{E}[g(\theta,X)]=G(\theta)$とします. ここで$G(\theta)$は$F(\theta)$の勾配となっています. また$X$の分布は未知であるがサンプル$X_1,\cdots$は知ることができるとします. ここで先ほど述べたStochastic Gradient Descentの枠組みを使って$F(\theta)$を最小化することを考えます. 書き直すと
```math
\begin{align}
\theta_{n+1}&=\theta_n - \alpha_n g_n(\theta_n) \\
&= \theta_n-\alpha_nG(\theta_n)+\alpha_n\epsilon_n \\
\end{align}
```
ここで$g_n(\theta)=g(\theta; X_n), \epsilon_n=G(\theta)-g_n(\theta)$です.
また, $\lbrace\alpha_n\rbrace$に対する仮定として$\sum_n \alpha_n = \infty, \sum_n \alpha_n^2 < \infty$をおきます.
この更新方法が適切な仮定のもとで収束することを確かめます.

**定理**
$\theta^*=\arg\min_\theta F(\theta)$とする. 以下の3つの条件を満たしている時

$\lim_{n\to\infty} \theta_n = \theta^*$.
```math
\begin{align}
\exists \theta^*\forall \theta, G(\theta)\cdot(\theta-\theta^*)\geq \mu||\theta-\theta^*||_2^2 \tag{1} \\
||G(\theta_n)||_2^2 \leq A+B||\theta_n||^2_2 \\
\mathbb{E}[||\epsilon_n||_2^2|\mathcal{F}_n] \leq K \\
\end{align}
```
(1)は$\theta$を$\theta^*$に近づけると常に$F(\theta)$は減少する(狭義凸関数)であることを意味しています.

**証明**
```math
\begin{align}
&||\theta_{n+1}-\theta^*||_2^2-||\theta_n-\theta^*||_2^2 \\
= &||(\theta_n-\theta^*)+(-\alpha_nG(\theta_n)+\alpha_n\epsilon_n)||_2^2-||\theta_n-\theta^*||_2^2 \\
= &(\theta_n-\theta^*)\cdot(-\alpha_nG(\theta_n)+\alpha_n\epsilon_n)+||-\alpha_nG(\theta_n)+\alpha_n\epsilon_n||_2^2 \\
= &-\alpha_nG(\theta_n)(\theta_n-\theta^*)+\alpha_n\epsilon_n(\theta_n-\theta^*)-2\alpha_n^2G(\theta_n)\epsilon_n+\alpha_n^2||\epsilon_n||^2_2+\alpha_n^2||G(\theta_n)||_2^2
\end{align}
```
よって
```math 
\begin{align}
&\mathbb{E}[||\theta_{n+1}-\theta^*||_2^2-||\theta_n-\theta^*||_2^2|\mathcal{F}_n] \\
= &-\alpha_nG(\theta_n)(\theta_n-\theta^*)+\alpha_n^2\mathbb{E}[||\epsilon_n||_2^2|\mathcal{F}_n]+\alpha_n^2||G(\theta_n)||_2^2 \\
\leq &-\alpha_n\mu||\theta_n-\theta^*||_2^2+\alpha_n^2K+\alpha_n^2(A+B||\theta_n-\theta^*||_2^2)
\end{align}
```
つまり
```math
\begin{align}
\mathbb{E}[||\theta_{n+1}-\theta^*||_2^2|\mathcal{F}_n] \leq (1-\alpha_n\mu+\alpha_n^2\beta)||\theta_n-\theta^*||_2^2+\alpha_n^2(K+A)
\end{align}
```
よってRobbins-Siegmundの定理より, $\lim_{n\to\infty}||\theta_n-\theta^*||_2^2 = 0$となる. 

このことから, $\lim_{n\to\infty}\theta_n\to \theta^*$. よって示された.

# 参考文献

[Robbins-Monro](https://appliedprobability.blog/2019/01/26/robbins-munro-2/)
[マルチンゲール](https://www.asakura.co.jp/detail.php?book_code=11600&srsltid=AfmBOorN8y5693aozPW8mJ7bLUluWRJyANDpVgcw-F8GKDFzF8EeWlpE)