優化算法–SGD，batch SGD

​ 優化算法的目标函數是一個基于訓練資料集的損失函數，優化的目标在于降低訓練誤差。在深度學習中主要面臨兩個挑戰：局部最小值和鞍點。

梯度下降和SGD

​ 多元梯度下降：目标函數的輸入為向量，輸出為标量。假設目标函數 f : R d → R f: \mathbb{R}^d \rightarrow \mathbb{R} f:Rd→R的輸入是一個 d d d維向量 x = [ x 1 , x 2 , … , x d ] ⊤ \boldsymbol{x} = [x_1, x_2, \ldots, x_d]^\top x=[x1​,x2​,…,xd​]⊤。目标函數 f ( x ) f(\boldsymbol{x}) f(x)有關 x \boldsymbol{x} x的梯度是一個由 d d d個偏導數組成的向量：

​ ∇ x f ( x ) = [ ∂ f ( x ) ∂ x 1 , ∂ f ( x ) ∂ x 2 , … , ∂ f ( x ) ∂ x d ] ⊤ . \nabla_{\boldsymbol{x}} f(\boldsymbol{x}) = \bigg[\frac{\partial f(\boldsymbol{x})}{\partial x_1}, \frac{\partial f(\boldsymbol{x})}{\partial x_2}, \ldots, \frac{\partial f(\boldsymbol{x})}{\partial x_d}\bigg]^\top. ∇x​f(x)=[∂x1​∂f(x)​,∂x2​∂f(x)​,…,∂xd​∂f(x)​]⊤.

​ 梯度中每個偏導數元素 ∂ f ( x ) / ∂ x i \partial f(\boldsymbol{x})/\partial x_i ∂f(x)/∂xi​代表着 f f f在 x \boldsymbol{x} x有關輸入 x i x_i xi​的變化率。通過梯度下降算法來不斷降低目标函數 f f f的值：

​ x ← x − η ∇ x f ( x ) . \boldsymbol{x} \leftarrow \boldsymbol{x} - \eta\nabla_{\boldsymbol{x}} f(\boldsymbol{x}) . x←x−η∇x​f(x).

​ 随機梯度下降（stochastic gradient descent，SGD）減少了每次疊代的計算開銷。在随機梯度下降的每次疊代中，我們随機均勻采樣的一個樣本索引 i ∈ { 1 , … , n } i\in\{1,\ldots,n\} i∈{1,…,n}，并計算梯度 ∇ f i ( x ) \nabla f_i(\boldsymbol{x}) ∇fi​(x)來疊代 x \boldsymbol{x} x：

​ x ← x − η ∇ f i ( x ) . \boldsymbol{x} \leftarrow \boldsymbol{x} - \eta \nabla f_i(\boldsymbol{x}). x←x−η∇fi​(x).

​ 可以看到每次疊代的計算開銷從梯度下降的 O ( n ) \mathcal{O}(n) O(n)降到了常數 O ( 1 ) \mathcal{O}(1) O(1)。值得強調的是，随機梯度 ∇ f i ( x ) \nabla f_i(\boldsymbol{x}) ∇fi​(x)是對梯度 ∇ f ( x ) \nabla f(\boldsymbol{x}) ∇f(x)的無偏估計：

​ E i ∇ f i ( x ) = 1 n ∑ i = 1 n ∇ f i ( x ) = ∇ f ( x ) . E_i \nabla f_i(\boldsymbol{x}) = \frac{1}{n} \sum_{i = 1}^n \nabla f_i(\boldsymbol{x}) = \nabla f(\boldsymbol{x}). Ei​∇fi​(x)=n1​i=1∑n​∇fi​(x)=∇f(x).

小批量随機梯度下降

​ 在每一次疊代中，梯度下降使用整個訓練資料集來計算梯度，是以它有時也被稱為批量梯度下降（batch gradient descent）。

​ 小批量随機梯度下降随機均勻采樣一個由訓練資料樣本索引組成的小批量 B t \mathcal{B}_t Bt​。我們可以通過重複采樣（sampling with replacement）或者不重複采樣（sampling without replacement）得到一個小批量中的各個樣本。前者允許同一個小批量中出現重複的樣本，後者則不允許如此，且更常見。對于這兩者間的任一種方式，都可以使用

g t ← ∇ f B t ( x t − 1 ) = 1 ∣ B ∣ ∑ i ∈ B t ∇ f i ( x t − 1 ) \boldsymbol{g}_t \leftarrow \nabla f_{\mathcal{B}_t}(\boldsymbol{x}_{t-1}) = \frac{1}{|\mathcal{B}|} \sum_{i \in \mathcal{B}_t}\nabla f_i(\boldsymbol{x}_{t-1}) gt​←∇fBt​​(xt−1​)=∣B∣1​i∈Bt​∑​∇fi​(xt−1​)

​ 來計算時間步 t t t的小批量 B t \mathcal{B}_t Bt​上目标函數位于 x t − 1 \boldsymbol{x}_{t-1} xt−1​處的梯度 g t \boldsymbol{g}_t gt​。這裡 ∣ B ∣ |\mathcal{B}| ∣B∣代表批量大小，即小批量中樣本的個數，是一個超參數。同随機梯度一樣，重複采樣所得的小批量随機梯度 g t \boldsymbol{g}_t gt​也是對梯度 ∇ f ( x t − 1 ) \nabla f(\boldsymbol{x}_{t-1}) ∇f(xt−1​)的無偏估計。給定學習率 η t \eta_t ηt​（取正數），小批量随機梯度下降對自變量的疊代如下：

​ x t ← x t − 1 − η t g t . \boldsymbol{x}_t \leftarrow \boldsymbol{x}_{t-1} - \eta_t \boldsymbol{g}_t. xt​←xt−1​−ηt​gt​.

​ 基于随機采樣得到的梯度的方差在疊代過程中無法減小，是以在實際中，（小批量）随機梯度下降的學習率可以在疊代過程中自我衰減或者每疊代若幹次後将學習率衰減一次。如此一來，學習率和（小批量）随機梯度乘積的方差會減小。而梯度下降在疊代過程中一直使用目标函數的真實梯度，無須自我衰減學習率。

總結

​ 當批量較小時，每次疊代中使用的樣本少，這會導緻并行處理和記憶體使用效率變低。這使得在計算同樣數目樣本的情況下比使用更大批量時所花時間更多。當批量較大時，每個小批量梯度裡可能含有更多的備援資訊。為了得到較好的解，批量較大時比批量較小時需要計算的樣本數目可能更多，例如增大疊代周期數。