引言
在各類優(yōu)化方法中，梯度下降法(Gradient Descent)是最為常見的策略。這里將對(duì)一些常見的梯度下降法的變種做一個(gè)梳理。方便大家更好地理解梯度下降法的應(yīng)用域。
如何理解梯度下降法
假想一個(gè)狀態(tài)，你在徒步中準(zhǔn)備下山，你該怎么走到谷底?這是一個(gè)很顯然的問題，你會(huì)順著山梯度(弧度)最大的方向向下走，而并不會(huì)選擇繞彎。
而梯度下降法其實(shí)就是建立在這種十分貪心的企圖上，即 通過找到梯度最大的方向 移動(dòng)一個(gè)固定的距離(一般稱為 Step Size )。但竟然是貪心，意味著它會(huì)有一個(gè)問題，如下圖所示：如果你正在 Starting pt 處嘗試下山，剛才的策略可能就會(huì)讓你找到一個(gè)Local minima了。這個(gè)問題是任何梯度下降法的變種都會(huì)遇到的問題。
圖片引自 https://thinkingandcomputing....
基本的梯度下降法
梯度下降法可以描述為
$$vec{x}_{n+1} = vec{x}_{n} - alpha f'(vec{x}_{n})$$
其中$f(x)$為所要優(yōu)化的函數(shù)，$alpha$為步長。
疊函數(shù)/不動(dòng)點(diǎn)理論視角下的梯度下降法
我們現(xiàn)在來看梯度下降法的適用條件(為了簡單起見，在此只討論一維的情況)。顯然，上面的遞推公式即可以轉(zhuǎn)化為一個(gè)疊函數(shù)數(shù)問題，即求：
$$gd(x) = x - alpha f'(x)$$
反復(fù)迭代后，收斂的問題。顯然，如果$gd(x)$收斂，則收斂于不動(dòng)點(diǎn)，即不動(dòng)點(diǎn)$x_0$滿足：
$$gd(x_0) = x_0 = x_0 - alpha f'(x_0)$$
化簡可得
$$f'(x_0) = 0$$
顯然，這個(gè)迭代的結(jié)果就是函數(shù)$f(x)$的極值。現(xiàn)在，我們?cè)賮硌芯刻荻认陆捣ǖ臈l件。滿足該收斂于該不動(dòng)點(diǎn)的條件是該點(diǎn)為吸引子，即滿足
$$|gd'(x)| < 1$$
化簡得
$$0 < f''(x) < frac{2}{alpha}$$
顯然，$f(x)$必須為凸函數(shù)，并在定義域上滿足$f''(x) < frac{2}{alpha}$時(shí)，梯度下降法才有效。
梯度下降法的一般難題
步長的選擇
不是凸函數(shù)
坐標(biāo)下降法
坐標(biāo)下降法( Coordinate descent )的策略相對(duì)而言是一種降低計(jì)算復(fù)雜度的方式，方法是每次只下降一個(gè)方向(坐標(biāo))的值。
圖片來自Wikipedia。
按是否設(shè)置步長可以分為兩種。
含步長的坐標(biāo)下降法
步驟：
Choose an initial parameter vector x.
Until convergence is reached, or for some fixed number of iterations:
Choose an index i from 1 to n.
Choose a step size α.
Update x_i to x_i − α * ∂F/∂x_i(x).
不含步長的坐標(biāo)下降法
此外，坐標(biāo)下降法的另一個(gè)非常好的迭代方法是，在迭代一個(gè)x_i時(shí)，可以固定其他x的前提下，只計(jì)算$f(x_i) = F(x)$。此時(shí)，計(jì)算復(fù)雜度降低，且迭代速度也可以相對(duì)加快。
步驟：
Choose an initial parameter vector x.
Until convergence is reached, or for some fixed number of iterations:
Choose an index i from 1 to n.
Update x_i to x_min, where (argmin F(x_i|x_n fixed but x_i)) = F(x_min)
坐標(biāo)下降法的限制
坐標(biāo)下降法在應(yīng)對(duì)非平滑函數(shù)時(shí)會(huì)有很大的局限，如下圖：
最后會(huì)在紅線交匯處就停止迭代了。
隨機(jī)梯度下降法/批梯度下降法
在實(shí)際 3V 大數(shù)據(jù)場景時(shí)，會(huì)遇到一個(gè)常見問題，因?yàn)闃颖緮?shù)N的數(shù)量過大，導(dǎo)致每次迭代的計(jì)算代價(jià)非常大;并且如果做一個(gè)實(shí)時(shí)的訓(xùn)練模型，顯然，每次有新數(shù)據(jù)讀入時(shí)，樣本數(shù)都會(huì)增加，每次迭代的速度也會(huì)越來越慢。
因此，一個(gè)比較好的策略就是隨機(jī)梯度下降法( Stochastic gradient descent )，即一次迭代只迭代一個(gè)樣本。這樣做的好處是顯然的，但是，無法規(guī)避的，每次迭代loss function的變異就會(huì)很大，如下圖：
