Gradient descent 梯度下降法

Gradient descent 梯度下降法 #

Gradient descent 是一種求函數極小值的算法 (反之，gradient ascent 是求極大值)。

convex_sample

考慮點 (x0,f(x0))(x_0, f(x_0)) ，他的微分(斜率)大於 0，此時只要往微分的反方向走 ( xx 變小)，就可以讓函數值變小。一直走到微分為 0 的地方便是極小值。所以 gradient descent 的演算法如下：

輸入：起始點x0與函數f \text{輸入：起始點}\enspace x_0 \enspace \text{與函數}\enspace f \newline While 終止條件不滿足： While \text{ 終止條件不滿足：}\newline x(n+1)=x(n)−tn⋅∇f(x(n)),fork=1,2,3,... \qquad x^{(n+1)}=x^{(n)}-t_n\cdot \nabla f(x^{(n)}), \enspace for \enspace k=1,2,3,...

起始點可以隨機給定。終止條件可以是最大迴圈數、 x(n)x^{(n)} 的變化量等等。 tnt_n 可以是一個很小的常數或是用其他方式算出來的數，gradient 決定走的方向， tnt_n 決定走的距離。

Gradient descent 是一種 first-order method，因為他只用到一階導數。

Gradient descent 的可行性 #

雖然 gradient descent 演算法可以讓函數值逐步變小看起來很直覺，不過數學上有些看起來很直覺的東西是錯的，所以依然需要證明。在這邊，我們會證明如果 gradient descnet 每次走固定步長 t≤1L t \le \frac{1}{L} ，則走 n n 步以後，跟最佳解的距離會小於等於 2∥x(0)−x∗∥22tn\frac{2\lVert x^{(0)}-x^*\rVert_2^2}{tn} 。只要 n n 夠大，就可以足夠靠近最佳解，於是我們就可以說 gradient descent 是可行的。

在證明 gradient descent 之前，我們先證明幾個引理：

Lemma 1 #

ff 可微分且 ff 為 convex，則 ∇f(y)T(x−y)≤f(x)−f(y)\nabla f(y)^T(x-y)\le f(x) - f(y)

證明：

f(tx+(1−t)y)≤tf(x)+(1−t)f(y),for0≤t≤1 兩邊除 t⇒1t(f(y+t(x−y))−f(y))≤f(x)−f(y) 取極限 t→0⇒lim⁡t→0f(y+t(x−y))−f(y)t(x−y)(x−y)=∇f(y)T(x−y)≤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 #

∇f\nabla f 是 Lipschitz continuous。意即：

存在常數 L>0 使得，對所有的 x,y 滿足∥∇f(x)−∇f(y)∥2≤L∥x−y∥2\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)≤f(y)+∇f(x)T(x−y)+L2∥x−y∥22f(x) \le f(y) + \nabla f(x)^T(x-y) + \frac{L}{2}\lVert x-y\rVert_2^2

證明：

根據泰勒展開式做一階展開，我們有 (積分項為 yy 到 xx 的積分)： f(x)=f(y)+∫01∇f(y+τ(x−y))dτ=f(y)+∇f(y)T(x−y)+∫01∇(f(y+τ(x−y))−∇f(y))T(x−y)dτ (一維的情況下很直覺，可以推廣到多維)≤f(y)+∇f(y)T(x−y)+∫01∥∇(f(y+τ(x−y))−∇f(y))∥∥(x−y)∥dτ, 根據 Lipschitz continuous 定義≤f(y)+∇f(y)T(x−y)+L∫01τ∥x−y∥22=f(y)+∇f(x)T(x−y)+L2∥x−y∥22f(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 #

ff 為 convex 且 ∇f\nabla f 是 Lipschitz continuous，則我們有：

(∇f(y)−∇f(x))T(y−x)≥1L∥∇f(x)−∇f(y)∥(\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) 根據 Lemma 1, 2≤∇f(y)T(y−z)+∇f(x)T(z−x)+L2∥z−x∥22 取 z=x−1L(∇f(x)−∇f(y))⇒f(y)−f(x)≤∇f(y)T(y−x+∇f(x)−∇f(y)L)−∇f(x)T(∇f(x)−∇f(y))L+∥∇f(x)−∇f(y)∥222L=∇f(y)T(y−x)−1L∥∇f(x)−∇f(y)∥22+12L∥∇f(x)−∇f(y)∥22=∇f(y)T(y−x)−12L∥∇f(x)−∇f(y)∥22f(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)≤∇f(y)T(y−x)−12L∥∇f(x)−∇f(y)∥22f(x)−f(y)≤∇f(x)T(x−y)−12L∥∇f(y)−∇f(x)∥22f(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≤(∇f(y)−∇f(x))T(y−x)−1L∥∇f(y)−∇f(x)∥220\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 #

∇f\nabla f 是 Lipschitz continuous，則我們有：

f(x−1L∇f(x))−f(x)≤−12L∥f(x)∥22f(x-\frac{1}{L}\nabla f(x)) - f(x) \le -\frac{1}{2L}\lVert f(x) \rVert_2^2

證明：

取 y=x−1L∇f(x)y=x-\frac{1}{L}\nabla f(x) 代入 Lipschitz continuous 的定義：

f(x−1L∇f(x))≤f(x)−1L∇f(x)T∇f(x)−L2∥1Lf(x)∥22=f(x)−12L∥f(x)∥22f(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 收斂性的證明 #

接下來可以來證明收斂性。我們有以下假設：

  1. 函數 ff 為 convex 。
  2. 函數 ff 為連續可導，即導數存在，並且為連續函數。
  3. 函數的定義域為 Rn\R^n 。
  4. 函數最小值存在， x∗=arg⁡min⁡xf(x)x^*=\arg\min_x f(x) 。
  5. ∇f\nabla f 是 Lipschitz continuous。

定理：gradient descnet 每次走固定步長 t≤1L t \le \frac{1}{L} 會滿足：

f(x(n))−f(x∗)≤2∥x(0)−x∗∥22tnf(x^{(n)})-f(x^*) \le \frac{2\lVert x^{(0)}-x^*\rVert_2^2}{tn}

證明：

∥x(k+1)−x∗∥22=∥x(k)−t∇f(x(k))−x∗∥22 代入從 k 走到 k+1=∥x(k)−x∗∥22−2t⟨x(k)−x∗,∇f(x(k))⟩+t2∥∇f(x(k))∥22≤∥x(k)−x∗∥22−t2∥∇f(x(k))∥22\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

由此可知， ∥x(k)−x∗∥22 \lVert x^{(k)}-x^* \rVert_2^2 為遞減，所以我們可以得到 ∥x(k)−x∗∥2≤∥x(0)−x∗∥2 \lVert x^{(k)}-x^*\rVert_2 \le \lVert x^{(0)}-x^*\rVert_2

由 Lemma 4 的結果，我們可以得到：

f(x(k+1))−f(x(k))≤−12L∥f(x(k))∥22≤−t2∥f(x(k))∥22⇒f(x(k+1))−f(x∗)≤f(x(k))−f(x∗)−t2∥f(x(k))∥22f(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 f 為 convex：

f(x(k))−f(x∗)≤∇f(x(k))(x(k)−x∗)≤∥∇f(x(k))∥2∥(x(k)−x∗)∥2≤∥∇f(x(k))∥2∥(x(0)−x∗)∥2f(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∗)≤f(x(k))−f(x∗)−t2(f(x(k+1))−f(x∗))2∥x(0)−x∗∥22f(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}

令 δk=f(x(k))−f(x∗),β=t2∥x(0)−x∗∥22 \delta_k= f(x^{(k)}) - f(x^*), \beta=\frac{t}{2\lVert x^{(0)} -x^* \rVert_2^2} 代入上式：

δk+1≤δk−βδk2  ⟺  1δk≤1δk+1−βδkδk+1  ⟺  βδkδk+1≤1δk+1−1δk,δk+1≤δk  ⟺  β≤1δk+1−1δk\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 k = 0, 1, 2,...,n-1 相加得到：

nβ≤1δn−1δ0≤1δn⇒δn≤1nβ  ⟺  f(x(n))−f(x∗)≤2∥x(0)−x∗∥22tnn\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 走足夠多步以後，就會足夠靠近最佳解。

參考資料：

CMU 統計系 Convex Optimization

Télécom Paris Optimization for Data Science 課堂講義