# Convergence of gradient decent

## Gradient decent

### Smooth convex function

首先我們假設 object function 符合以下兩個條件：
1. $f: R^d \rightarrow R$ is convex
* 對於任何 $0 \leq \lambda \leq 1$, 不等式 $f(\lambda x + (1 - \lambda)y) \leq \lambda f(x) + (1 - \lambda)f(y)$ 成立
2. $f: R^d \rightarrow R$ is L-Lipschitz continuous gradient
* 圖
* ${||\nabla f(x) - \nabla f(y)||}_2 \leq L{||x - y||}_2$
* 這個條件雖然比一般的連續函式嚴格，但其實只是 weak constraint，大多的 regression problem 或 deep neural network 都符合。
* 以 regression 為例，當 $f(x) = \frac{1}{n}{||Ax - b||}^2 \Rightarrow \nabla f(x) = \frac{2}{n}A^T(Ax - b)$
因此 ${||\nabla f(x) - \nabla f(y)||}_2 = \frac{2}{n}{||A^TA(x - y)||}_2 \leq \frac{2}{n}{||A^TA||}_2{||x - y||}_2$
所以我們可以說 LSR 的 loss function 是一個 $\frac{2}{n}{||A^TA||}_2$ Lipschitz continuous gradient

接著我們想要證明 steep gradient decent 的收歛性，首先 steep gradient decent 的演算法為：

1. 選擇一個起始點 $x_0 \in R^d$ 以及 step size $t > 0$
2. Iteration: $x_{i + 1} = x_i -t \nabla f(x_i)$

證明其收斂相當於對於任何 $\epsilon > 0$, 存在一個 $k$，使得 $f(x_k) - f(x^*) < \epsilon$，其中 $x^*$ 為 $argmin_xf(x)$

這裡我們必須先要有兩個工具協助後續的證明：

* Claim 1.1: 對於一個 convex function $f: R^d \rightarrow R$，任意 $x, y \in R^d$ 滿足 $f(x) + \langle \nabla f(x), y - x \rangle \leq f(y)$
* 圖
* Claim 1.2: 對於一個 L-Lipschitz convex function $f: R^d \rightarrow R$，任意 $x, y \in R^d$ 滿足 $f(y) \leq f(x) + \langle \nabla f(x), y - x \rangle + \frac{L}{2} {||y - x||}^2_2$
* 首先，根據微積分 $h(1) = h(0) + \int_0^1 h'(\gamma)d\gamma$, 因此若令 $h(\gamma) = f(x + \gamma(y - x))$，我們可以得到：
$\begin{split}f(y) &= f(x) + \int_0^1 \langle \nabla f(x + \gamma(y - x)), y - x\rangle d\gamma \\
&= f(x) + \pmb{\langle \nabla f(x), y - x \rangle} + \int_0^1 \langle \nabla f(x + \gamma(y - x)), y - x\rangle - \pmb{\langle \nabla f(x), y - x \rangle} d\gamma \\
&= f(x) + \langle \nabla f(x), y - x \rangle + \int_0^1 \langle \nabla f(x + \gamma(y - x)) -f(x), y - x\rangle d\gamma \\
&\leq f(x) + \langle \nabla f(x), y - x \rangle + \int_0^1 \pmb{{|| \nabla f(x + \gamma(y - x)) - \nabla f(x)||}_2{||y - x||}_2} d\gamma \\
& (\text{因為 }|\langle u, v\rangle| \leq {||u||}_2{||v||}_2) \\
&\leq f(x) + \langle \nabla f(x), y - x \rangle + \int_0^1 \pmb{L{|| \gamma(y - x)||}_2}{||y - x||}_2 d\gamma \\
& (\text{因為 }f \text{ 是 L-Lipschitz continuous gradient}) \\
&= f(x) + \langle \nabla f(x), y - x\rangle + \frac{L}{2}{||y - x||}^2_2
\end{split}$

接下來我們就可以透過上述幾個等式不等式來證明 gradient decent 的收歛性
Again，我們想要證明對於任何 $\epsilon > 0$，存在一個 $k$，使得 $f(x_k) - f(x^*) < \epsilon$

* 首先，由 Claim 1.2：
$f(x_{i + 1}) \leq f(x_i) + \langle \nabla f(x_i), x_{i + 1} - x_i \rangle + \frac{L}{2} {||x_{i + 1} - x_i||}^2_2$

又根據 gradient decent 的演算法：$x_{i + 1} = x_i -t \nabla f(x_i)$
$\Rightarrow f(x_{i + 1}) \leq f(x_i) - t{||\nabla f(x_i)||}^2_2 + \frac{Lt^2}{2}{||\nabla f(x_i)||}^2_2 = f(x_i) - t(1 - \frac{Lt}{2}){||\nabla f(x_i)||}^2_2$

若我們取 step size $t \leq \frac{1}{L}$，則可以得到 $f(x_{i + 1}) \leq f(x_i) - \frac{t}{2}{||\nabla f(x_i)||}^2_2$

到這裡我們可以發現，function $f$ 隨著 $x$ 的迭代是**單調遞減函式 (non-decreasing)**

* 接著，因為 $f$ 為 convex function，根據 Claim 1.3：
$\Rightarrow f(x_i) \leq f(x^*) + \langle \nabla f(x_i), x_i - x^* \rangle$

合併上述兩式，可以得出：
$\begin{split}f(x_{i + 1}) &\leq f(x^*) + \langle \nabla f(x_i), x_i - x^* \rangle - \frac{t}{2}{||\nabla f(x_i)||}^2_2 \\
&= f(x^*) + \pmb{\frac{1}{2t}{||x_i - x^*||}^2_2} - \frac{1}{2t}(\pmb{{||x_i - x^*||}^2_2} - 2\langle t\nabla f(x_i), x_i - x^* \rangle + {||t\nabla f(x_i)||}^2_2) \\
&= f(x^*) + \frac{1}{2t}{||x_i - x^*||}^2_2 - \frac{1}{2t}\pmb{{||x_i - x^* - t\nabla f(x_i)||}^2_2} \\
&= f(x^*) + \frac{1}{2t}({||x_i - x^*||}^2_2 - {||\pmb{x_{i + 1}} - x^*||}^2_2) \\
& (\text{replace }x_i - t\nabla f(x_i)\text{ with }x_{i + 1})
\end{split}$

* 如果我們對 $i = 0$ 到 $i = k - 1$ 做加總，可以得出
$\sum_{i = 0}^{k - 1}(f(x_{i + 1}) - f(x^*)) \leq \frac{1}{2t}({||x_0 - x^*||}^2_2 - {||x_k - x^*||}^2_2) \leq \frac{{||x_0 - x^*||}^2_2}{2t}$

又前面我們已知 $f$ 隨著 $x$ 的迭代為單調遞減函式，因此 $\sum_{i = 0}^{k - 1}(f(x_{i + 1}) - f(x^*)) \geq k(f(x_k) - f(x^*))$
$\Rightarrow f(x_k) - f(x^*) \leq \frac{{||x_0 - x^*||}^2_2}{2tk}$

因此對於任意 $\epsilon > 0$，皆可找到 k 使得 $f(x_k) - f(x^*) \leq \frac{{||x_0 - x^*||}^2_2}{2tk} < \epsilon$

### Smooth strongly convex function

那如果是 strongly convex function 呢？

* 對於一個 strongly convex function $f: R^d \rightarrow R$，任意 $x, y \in R^d$ 滿足 $f(x) + \langle \nabla f(x), y - x \rangle < f(y)$
我們稱 function 為 $\mu$-convex，當 $f$ 滿足 $f(x) + \langle \nabla f(x), y - x \rangle + \frac{\mu}{2}{||y - x||}^2_2 \leq f(y)$

* $\begin{split}||x_{i + 1} - x^*||^2_2 &= ||\pmb{x_i - t\nabla f(x_i)} - x^*||^2_2\\
&= ||x_i - x^*||^2_2 - 2t\langle \nabla f(x_i), x_i - x^*\rangle + t^2||\nabla f(x_i)||^2_2 \\
&\leq \pmb{(1 - t\mu)||x_i - x^*||^2_2 - 2t(f(x_i) - f(x^*))} + t^2||\nabla f(x_i)||^2_2 \\
& (\text{根據 strongly convex 定義，}\langle \nabla f(x_i), x_i - x^* \rangle \geq f(x_i) - f(x^*) - \frac{\mu}{2}{||x_i - x^*||}^2_2) \\
&\leq (1 - t\mu)||x_i - x^*||^2_2 - 2t(f(x_i) - f(x^*)) + \pmb{t^2L(f(x_i) - f(x^*))} \\
& (\text{因為 }f \text{ 是 L-Lipschitz continuous gradient}) \\
&= (1 - t\mu)||x_i - x^*||^2_2 -2t(1 - tL)(f(x_i) - f(x^*)) \\
&\leq (1 - t\mu)||x_i - x^*||^2_2 \\
& (\text{因為 }\frac{t}{L} \leq \frac{\mu}{L} < 1) \\
\end{split}$

由此可推得，$||x_k - x^*||^2_2 \leq (1 - t\mu)^k||x_0 - x^*||^2_2$

### Convex vs. Strongly convex

從上面的結果可以發現，若收斂條件為 $||x_k - x^*||^2_2 < \epsilon$，則：
* Convex function 的收斂速度為 $O(\frac{1}{k})$，亦即收斂時間複雜度為 $O(\frac{1}{\epsilon})$，屬於 sub-linear convergence。
* Strongly convex function 的收斂速度為 $O(c^k)$，亦即收斂時間複雜度為 $O(log\frac{1}{\epsilon})$，屬於 linear convergence。

## Stochastic gradient decent

證明 SGD 需要多一個工具：

* Claim 2.1: 對於一個 convex function $f: R^d \rightarrow R$，任意 $y_i \in R^d$ 滿足 $f(\frac{y_1 + ... + y_k}{k}) \leq \frac{f(y_1) + ... + f(y_k)}{k}$
* 這裡可以用數學歸納法，由於 $k = 2$ 即可由定義得到，
假設 $k - 1$ 成立的情況下，令 $y = \frac{y_1 + ... + y_{k-1})}{(k - 1)}$，
則
$\begin{split}f(\frac{y_1 + ... + y_k}{k}) &= f(\frac{k - 1}{k}y + \frac{y_k}{k}) \\
&\leq \frac{k - 1}{k}f(y) + \frac{1}{k}f(y_k) \\
& (\text{by convexity applied with }\lambda = \frac{k - 1}{k}) \\
&\leq \frac{k - 1}{k}\frac{f(y_1) + ... + f(y_{k - 1})}{k - 1} + \frac{1}{k}f(y_k)) \\
&= \frac{f(y_1) + ... + f(y_k)}{k}
\end{split}$

老師證明 gradient 會收斂，這邊則是證明會接近 global minimize