Gradient descent 梯度下降法 #
Gradient descent 是一種求函數極小值的算法 (反之，gradient ascent 是求極大值)。
考慮點 \((x_0, f(x_0))\) ，他的微分(斜率)大於 0，此時只要往微分的反方向走 ( \(x\) 變小)，就可以讓函數值變小。一直走到微分為 0 的地方便是極小值。所以 gradient descent 的演算法如下：
\( \text{輸入：起始點}\enspace x_0 \enspace \text{與函數}\enspace f \newline\) \( While \text{ 終止條件不滿足：}\newline\) \( \qquad x^{(n+1)}=x^{(n)}-t_n\cdot \nabla f(x^{(n)}), \enspace for \enspace k=1,2,3,...\)
起始點可以隨機給定。終止條件可以是最大迴圈數、 \(x^{(n)}\) 的變化量等等。 \(t_n\) 可以是一個很小的常數或是用其他方式算出來的數，gradient 決定走的方向， \(t_n\) 決定走的距離。
Gradient descent 是一種 first-order method，因為他只用到一階導數。
Gradient descent 的可行性 #
雖然 gradient descent 演算法可以讓函數值逐步變小看起來很直覺，不過數學上有些看起來很直覺的東西是錯的，所以依然需要證明。在這邊，我們會證明如果 gradient descnet 每次走固定步長 \( t \le \frac{1}{L} \) ，則走 \( n \) 步以後，跟最佳解的距離會小於等於 \(\frac{2\lVert x^{(0)}-x^*\rVert_2^2}{tn}\) 。只要 \( n \) 夠大，就可以足夠靠近最佳解，於是我們就可以說 gradient descent 是可行的。
在證明 gradient descent 之前，我們先證明幾個引理：
Lemma 1 #
\(f\) 可微分且 \(f\) 為 convex，則 \(\nabla f(y)^T(x-y)\le f(x) - f(y)\)
證明：
\[f(tx + (1-t)y) \le tf(x) + (1-t)f(y), for\enspace 0\le t\le 1 \text{ 兩邊除 } t \newline \Rightarrow \frac{1}{t}(f(y+t(x-y))-f(y)) \le f(x) - f(y) \text{ 取極限 } t \rightarrow 0 \newline \Rightarrow \lim_{t\rightarrow 0} \frac{f(y+t(x-y))-f(y)}{t(x-y)}(x-y) =\nabla f(y)^T(x-y)\le f(x) - f(y)\]Lemma 2 #
\(\nabla f\) 是 Lipschitz continuous。意即：
\[\text{存在常數 }L \gt 0 \text{ 使得，對所有的 } x,y \text{ 滿足}\newline \lVert\nabla f(x) - \nabla f(y)\rVert_2 \le L \lVert x - y\rVert_2\]則我們有 \(f(x) \le f(y) + \nabla f(x)^T(x-y) + \frac{L}{2}\lVert x-y\rVert_2^2 \)
證明：
根據泰勒展開式做一階展開，我們有 (積分項為 \(y\) 到 \(x\) 的積分)： \[f(x) = f(y) + \int_0^1 \nabla f(y + \tau(x-y)) d\tau \newline =f(y) + \nabla f(y)^T(x-y) + \int_0^1 \nabla (f(y + \tau(x-y)) - \nabla f(y))^T(x-y) d\tau \text{ (一維的情況下很直覺，可以推廣到多維)} \newline \le f(y) + \nabla f(y)^T(x-y) + \int_0^1 \lVert\nabla (f(y + \tau(x-y)) - \nabla f(y))\rVert\lVert(x-y)\rVert d\tau \text{, 根據 Lipschitz continuous 定義} \newline \le f(y) + \nabla f(y)^T(x-y) + L\int_0^1\tau\lVert x - y\rVert_2^2 \newline =f(y) + \nabla f(x)^T(x-y) + \frac{L}{2}\lVert x-y\rVert_2^2\]
Lemma 3 #
\(f\) 為 convex 且 \(\nabla f\) 是 Lipschitz continuous，則我們有：
\[(\nabla f(y) - \nabla f(x))^T(y-x) \ge \frac{1}{L}\lVert \nabla f(x) - \nabla f(y) \rVert\]證明：
\[f(y) - f(x) = f(y) - f(z) + f(z) - f(x)\text{ 根據 Lemma 1, 2}\newline \le \nabla f(y)^T(y-z) + \nabla f(x)^T(z-x) + \frac{L}{2} \lVert z-x \rVert_2^2 \text{ 取 } z = x - \frac{1}{L}(\nabla f(x) - \nabla f(y)) \newline \Rightarrow f(y) - f(x) \le \nabla f(y)^T(y-x + \frac{\nabla f(x) - \nabla f(y)}{L})-\frac{\nabla f(x)^T(\nabla f(x) - \nabla f(y))}{L} + \frac{\lVert \nabla f(x) - \nabla f(y) \rVert_2^2}{2L} \newline =\nabla f(y)^T(y-x) - \frac{1}{L}\lVert \nabla f(x) - \nabla f(y) \rVert_2^2 + \frac{1}{2L}\lVert \nabla f(x) - \nabla f(y) \rVert_2^2 \newline =\nabla f(y)^T(y-x) - \frac{1}{2L}\lVert \nabla f(x) - \nabla f(y) \rVert_2^2\]根據上式，我們有：
\[f(y) - f(x)\le \nabla f(y)^T(y-x) - \frac{1}{2L}\lVert \nabla f(x) - \nabla f(y) \rVert_2^2 \newline f(x) - f(y)\le \nabla f(x)^T(x-y) - \frac{1}{2L}\lVert \nabla f(y) - \nabla f(x) \rVert_2^2 \]兩式相加：
\[0\le (\nabla f(y) - \nabla f(x))^T(y-x) - \frac{1}{L}\lVert \nabla f(y) - \nabla f(x) \rVert_2^2 \]移項後得證。
Lemma 4 #
\(\nabla f\) 是 Lipschitz continuous，則我們有：
\[f(x-\frac{1}{L}\nabla f(x)) - f(x) \le -\frac{1}{2L}\lVert f(x) \rVert_2^2\]證明：
取 \(y=x-\frac{1}{L}\nabla f(x)\) 代入 Lipschitz continuous 的定義：
\[f(x-\frac{1}{L}\nabla f(x)) \le f(x) - \frac{1}{L}\nabla f(x)^T\nabla f(x) -\frac{L}{2}\lVert \frac{1}{L}f(x) \rVert_2^2 \newline = f(x) - \frac{1}{2L}\lVert f(x)\rVert_2^2\]Gradient descent 收斂性的證明 #
接下來可以來證明收斂性。我們有以下假設：
- 函數 \(f\) 為 convex 。
- 函數 \(f\) 為連續可導，即導數存在，並且為連續函數。
- 函數的定義域為 \(\R^n\) 。
- 函數最小值存在， \(x^*=\arg\min_x f(x)\) 。
- \(\nabla f\) 是 Lipschitz continuous。
定理：gradient descnet 每次走固定步長 \( t \le \frac{1}{L} \) 會滿足：
\[f(x^{(n)})-f(x^*) \le \frac{2\lVert x^{(0)}-x^*\rVert_2^2}{tn}\]證明：
\[\lVert x^{(k+1)}-x^*\rVert_2^2=\lVert x^{(k)}-t\nabla f(x^{(k)})-x^*\rVert_2^2 \text{ 代入從 } k \text{ 走到 } k + 1\newline =\lVert x^{(k)}-x^*\rVert_2^2-2t\lang x^{(k)}-x^*,\nabla f(x^{(k)}) \rang+t^2\lVert\nabla f(x^{(k)})\rVert_2^2 \newline \le \lVert x^{(k)}-x^*\rVert_2^2-t^2\lVert\nabla f(x^{(k)})\rVert_2^2\]由此可知， \( \lVert x^{(k)}-x^* \rVert_2^2 \) 為遞減，所以我們可以得到 \( \lVert x^{(k)}-x^*\rVert_2 \le \lVert x^{(0)}-x^*\rVert_2 \)
由 Lemma 4 的結果，我們可以得到：
\[f(x^{(k+1)}) - f(x^{(k)}) \le -\frac{1}{2L}\lVert f(x^{(k)}) \rVert_2^2 \le -\frac{t}{2}\lVert f(x^{(k)}) \rVert_2^2 \newline \Rightarrow f(x^{(k+1)}) - f(x^*) \le f(x^{(k)}) - f(x^*) -\frac{t}{2}\lVert f(x^{(k)}) \rVert_2^2 \newline\]由於 \( f \) 為 convex：
\[f(x^{(k)}) - f(x^*) \le \nabla f(x^{(k)})(x^{(k)}-x^*) \newline \le \lVert\nabla f(x^{(k)})\rVert_2\lVert(x^{(k)}-x^*)\rVert_2 \le \lVert\nabla f(x^{(k)})\rVert_2\lVert(x^{(0)}-x^*)\rVert_2\]合併前兩式 (上一式先兩邊平方)：
\[f(x^{(k+1)}) - f(x^*) \le f(x^{(k)}) - f(x^*) - \frac{t}{2}\frac{(f(x^{(k+1)}) - f(x^*))^2}{\lVert x^{(0)} -x^* \rVert_2^2}\]令 \( \delta_k= f(x^{(k)}) - f(x^*), \beta=\frac{t}{2\lVert x^{(0)} -x^* \rVert_2^2}\) 代入上式：
\[\delta_{k+1} \le \delta_k-\beta \delta_k^2 \newline \iff \frac{1}{\delta_k} \le\frac{1}{\delta_{k+1}}-\beta\frac{\delta_k}{\delta_{k+1}} \newline \iff \beta\frac{\delta_k}{\delta_{k+1}} \le \frac{1}{\delta_{k+1}} - \frac{1}{\delta_k}, \delta_{k+1}\le\delta_k \newline \iff \beta\le \frac{1}{\delta_{k+1}} - \frac{1}{\delta_k}\]對 \( k = 0, 1, 2,...,n-1 \) 相加得到：
\[n\beta \le \frac{1}{\delta_n}-\frac{1}{\delta_0} \le \frac{1}{\delta_n} \Rightarrow \delta_n \le\frac{1}{n\beta} \newline \iff f(x^{(n)}) - f(x^*) \le \frac{2\lVert x^{(0)} -x^* \rVert_2^2}{tn}\]於是我們證明了固定步長的 gradient descnet 走足夠多步以後，就會足夠靠近最佳解。
參考資料：