從精確梯度到梯度估計
對有下界的 L L L -光滑函數 f f f ,步長為 0 < η ≤ 1 / L 0 < \eta \le 1/L 0 < η ≤ 1/ L 的梯度下降法在每一步都令目標函數不增。下降幅度由下降引理控制:
f ( y ) ≤ f ( x ) + ⟨ ∇ f ( x ) , y − x ⟩ + L 2 ∥ y − x ∥ 2 對所有 x , y ∈ R d . f(y) \le f(x) + \langle \nabla f(x), y - x \rangle + \frac{L}{2}\lVert y - x \rVert^2 \qquad \text{對所有 } x, y \in \mathbb{R}^d. f ( y ) ≤ f ( x ) + ⟨ ∇ f ( x ) , y − x ⟩ + 2 L ∥ y − x ∥ 2 對所有 x , y ∈ R d .
同一個 Lipschitz 論證亦給出雙側形式 ∣ f ( y ) − f ( x ) − ⟨ ∇ f ( x ) , y − x ⟩ ∣ ≤ L 2 ∥ y − x ∥ 2 \lvert f(y) - f(x) - \langle \nabla f(x), y-x\rangle \rvert \le \frac{L}{2}\lVert y-x\rVert^2 ∣ f ( y ) − f ( x ) − ⟨ ∇ f ( x ) , y − x ⟩∣ ≤ 2 L ∥ y − x ∥ 2 。
在很多問題中,精確計算 ∇ f ( x ) \nabla f(x) ∇ f ( x ) 的代價太高;典型例子是目標函數為大量分量函數的平均。我們於是用隨機估計 g k g_k g k 代替它,並更新
x k + 1 = x k − η g k . x_{k+1} = x_k - \eta\, g_k . x k + 1 = x k − η g k .
這個改動使確定性論證不能原封不動地沿用。由於 g k g_k g k 是隨機的,即使真梯度為零,某一步仍可能令目標值上升。這裏的保證以期望表述,並計入估計的波動;其他形式的保證需要各自的假設與證明。以下會仔細推導,並說明所得界能夠及不能夠告訴我們甚麼。
基本假設
全文假設:
f : R d → R f:\mathbb{R}^d \to \mathbb{R} f : R d → R 可微,且對某個 L > 0 L > 0 L > 0 ,∇ f \nabla f ∇ f 在全空間為 L L L -Lipschitz。
存在有限數 f inf f_{\inf} f i n f ,使所有 x x x 都滿足 f ( x ) ≥ f inf f(x) \ge f_{\inf} f ( x ) ≥ f i n f 。
初始點 x 0 x_0 x 0 是確定的,步長固定且滿足 0 < η ≤ 1 / L 0 < \eta \le 1/L 0 < η ≤ 1/ L 。
資訊結構。 設 F 0 ⊆ F 1 ⊆ ⋯ \mathcal{F}_0 \subseteq \mathcal{F}_1 \subseteq \cdots F 0 ⊆ F 1 ⊆ ⋯ 為濾過。把 F k \mathcal{F}_k F k 理解為「抽取第 k k k 個樣本前已發生的一切」。估計 g k g_k g k 在抽樣後已知,因此是 F k + 1 \mathcal{F}_{k+1} F k + 1 -可測的。由於 x 0 x_0 x 0 確定且 x k + 1 = x k − η g k x_{k+1} = x_k - \eta g_k x k + 1 = x k − η g k ,歸納可知每個 x k x_k x k 都是 F k \mathcal{F}_k F k -可測的。直觀地說,抽取下一個樣本前,當前點已知。
定義 3.3.1
(方差界為 σ 2 \sigma^2 σ 2 的條件無偏梯度估計器)
若對每個 k k k 都有以下三點,則稱估計 ( g k ) (g_k) ( g k ) 為方差界為 σ 2 \sigma^2 σ 2 的條件無偏梯度估計器 :
g k g_k g k 平方可積,即 E ∥ g k ∥ 2 < ∞ \mathbb{E}\lVert g_k \rVert^2 < \infty E ∥ g k ∥ 2 < ∞ ;
條件無偏性: E [ g k ∣ F k ] = ∇ f ( x k ) \mathbb{E}[g_k \mid \mathcal{F}_k] = \nabla f(x_k) E [ g k ∣ F k ] = ∇ f ( x k ) 幾乎必然成立;
條件方差有界: 對某個有限常數 σ 2 ≥ 0 \sigma^2 \ge 0 σ 2 ≥ 0 ,E [ ∥ g k − ∇ f ( x k ) ∥ 2 ∣ F k ] ≤ σ 2 \mathbb{E}\big[\lVert g_k - \nabla f(x_k)\rVert^2 \mid \mathcal{F}_k\big] \le \sigma^2 E [ ∥ g k − ∇ f ( x k ) ∥ 2 ∣ F k ] ≤ σ 2 幾乎必然成立。
基本假設包括:估計滿足這個定義。
以 F k \mathcal{F}_k F k 為條件十分重要。「對所有隨機性取平均」後無偏並不足夠;因為下降引理是在當前點應用,我們需要在已知估計所用的點 時,估計仍然正確。
可積性的保證
下文使用的期望全都有限。由 ∥ x k + 1 ∥ 2 ≤ 2 ∥ x k ∥ 2 + 2 η 2 ∥ g k ∥ 2 \lVert x_{k+1}\rVert^2 \le 2\lVert x_k\rVert^2 + 2\eta^2 \lVert g_k\rVert^2 ∥ x k + 1 ∥ 2 ≤ 2 ∥ x k ∥ 2 + 2 η 2 ∥ g k ∥ 2 ,歸納可知每個 x k x_k x k 均平方可積。Lipschitz 性質給出 ∥ ∇ f ( x k ) ∥ ≤ ∥ ∇ f ( 0 ) ∥ + L ∥ x k ∥ \lVert \nabla f(x_k)\rVert \le \lVert \nabla f(0)\rVert + L\lVert x_k\rVert ∥ ∇ f ( x k )∥ ≤ ∥ ∇ f ( 0 )∥ + L ∥ x k ∥ ,故 ∇ f ( x k ) \nabla f(x_k) ∇ f ( x k ) 也平方可積。以 0 0 0 為基點的雙側下降界給出
∣ f ( x k ) ∣ ≤ ∣ f ( 0 ) ∣ + ∥ ∇ f ( 0 ) ∥ ∥ x k ∥ + L 2 ∥ x k ∥ 2 , \lvert f(x_k)\rvert \le \lvert f(0)\rvert + \lVert \nabla f(0)\rVert\,\lVert x_k\rVert + \tfrac{L}{2}\lVert x_k\rVert^2, ∣ f ( x k )∣ ≤ ∣ f ( 0 )∣ + ∥ ∇ f ( 0 )∥ ∥ x k ∥ + 2 L ∥ x k ∥ 2 ,
所以 f ( x k ) f(x_k) f ( x k ) 可積。最後,∣ ⟨ ∇ f ( x k ) , g k ⟩ ∣ ≤ 1 2 ∥ ∇ f ( x k ) ∥ 2 + 1 2 ∥ g k ∥ 2 \lvert\langle \nabla f(x_k), g_k\rangle\rvert \le \tfrac12\lVert \nabla f(x_k)\rVert^2 + \tfrac12 \lVert g_k\rVert^2 ∣⟨ ∇ f ( x k ) , g k ⟩∣ ≤ 2 1 ∥ ∇ f ( x k ) ∥ 2 + 2 1 ∥ g k ∥ 2 ,故此內積亦可積。這便確保下文各個條件期望都有意義。
單步界
關鍵代數事實是二階矩的一個精確分解。令 e k = g k − ∇ f ( x k ) e_k = g_k - \nabla f(x_k) e k = g k − ∇ f ( x k ) ,則
∥ g k ∥ 2 = ∥ ∇ f ( x k ) ∥ 2 + 2 ⟨ ∇ f ( x k ) , e k ⟩ + ∥ e k ∥ 2 . \lVert g_k\rVert^2 = \lVert \nabla f(x_k)\rVert^2 + 2\langle \nabla f(x_k), e_k\rangle + \lVert e_k\rVert^2 . ∥ g k ∥ 2 = ∥ ∇ f ( x k ) ∥ 2 + 2 ⟨ ∇ f ( x k ) , e k ⟩ + ∥ e k ∥ 2 .
由於 ∇ f ( x k ) \nabla f(x_k) ∇ f ( x k ) 是 F k \mathcal{F}_k F k -可測,可將它移出條件期望。因此 E [ ⟨ ∇ f ( x k ) , e k ⟩ ∣ F k ] = ⟨ ∇ f ( x k ) , E [ e k ∣ F k ] ⟩ = 0 \mathbb{E}[\langle \nabla f(x_k), e_k\rangle \mid \mathcal{F}_k] = \langle \nabla f(x_k), \mathbb{E}[e_k\mid\mathcal{F}_k]\rangle = 0 E [⟨ ∇ f ( x k ) , e k ⟩ ∣ F k ] = ⟨ ∇ f ( x k ) , E [ e k ∣ F k ]⟩ = 0 。交叉項完全抵消,得到
E [ ∥ g k ∥ 2 ∣ F k ] = ∥ ∇ f ( x k ) ∥ 2 + E [ ∥ g k − ∇ f ( x k ) ∥ 2 ∣ F k ] . \mathbb{E}\big[\lVert g_k\rVert^2 \mid \mathcal{F}_k\big] = \lVert \nabla f(x_k)\rVert^2 + \mathbb{E}\big[\lVert g_k - \nabla f(x_k)\rVert^2 \mid \mathcal{F}_k\big]. E [ ∥ g k ∥ 2 ∣ F k ] = ∥ ∇ f ( x k ) ∥ 2 + E [ ∥ g k − ∇ f ( x k ) ∥ 2 ∣ F k ] .
在上述基本假設下,對每個 k ≥ 0 k \ge 0 k ≥ 0 ,
E [ f ( x k + 1 ) ∣ F k ] ≤ f ( x k ) − η 2 ∥ ∇ f ( x k ) ∥ 2 + L η 2 2 σ 2 a.s. , \mathbb{E}[f(x_{k+1}) \mid \mathcal{F}_k] \le f(x_k) - \frac{\eta}{2}\lVert \nabla f(x_k)\rVert^2 + \frac{L\eta^2}{2}\sigma^2 \quad \text{a.s.}, E [ f ( x k + 1 ) ∣ F k ] ≤ f ( x k ) − 2 η ∥ ∇ f ( x k ) ∥ 2 + 2 L η 2 σ 2 a.s. , 因而
E f ( x k + 1 ) ≤ E f ( x k ) − η 2 E ∥ ∇ f ( x k ) ∥ 2 + L η 2 2 σ 2 . \mathbb{E} f(x_{k+1}) \le \mathbb{E} f(x_k) - \frac{\eta}{2}\mathbb{E}\lVert \nabla f(x_k)\rVert^2 + \frac{L\eta^2}{2}\sigma^2 . E f ( x k + 1 ) ≤ E f ( x k ) − 2 η E ∥ ∇ f ( x k ) ∥ 2 + 2 L η 2 σ 2 .
在下降引理中取 x = x k x = x_k x = x k 及 y = x k + 1 = x k − η g k y = x_{k+1} = x_k - \eta g_k y = x k + 1 = x k − η g k 。對每個隨機結果,以下不等式逐點成立:
f ( x k + 1 ) ≤ f ( x k ) − η ⟨ ∇ f ( x k ) , g k ⟩ + L η 2 2 ∥ g k ∥ 2 . f(x_{k+1}) \le f(x_k) - \eta\langle \nabla f(x_k), g_k\rangle + \frac{L\eta^2}{2}\lVert g_k\rVert^2 . f ( x k + 1 ) ≤ f ( x k ) − η ⟨ ∇ f ( x k ) , g k ⟩ + 2 L η 2 ∥ g k ∥ 2 . 各項可積,故可對 F k \mathcal{F}_k F k 取條件期望;單調性保留不等式。f ( x k ) f(x_k) f ( x k ) 是 F k \mathcal{F}_k F k -可測,故保持不變。由無偏性,E [ ⟨ ∇ f ( x k ) , g k ⟩ ∣ F k ] = ∥ ∇ f ( x k ) ∥ 2 \mathbb{E}[\langle \nabla f(x_k), g_k\rangle\mid\mathcal{F}_k] = \lVert\nabla f(x_k)\rVert^2 E [⟨ ∇ f ( x k ) , g k ⟩ ∣ F k ] = ∥ ∇ f ( x k ) ∥ 2 。由上面的分解及方差界,E [ ∥ g k ∥ 2 ∣ F k ] ≤ ∥ ∇ f ( x k ) ∥ 2 + σ 2 \mathbb{E}[\lVert g_k\rVert^2\mid\mathcal{F}_k] \le \lVert\nabla f(x_k)\rVert^2 + \sigma^2 E [∥ g k ∥ 2 ∣ F k ] ≤ ∥ ∇ f ( x k ) ∥ 2 + σ 2 。故
E [ f ( x k + 1 ) ∣ F k ] ≤ f ( x k ) − η ( 1 − L η 2 ) ∥ ∇ f ( x k ) ∥ 2 + L η 2 2 σ 2 . \mathbb{E}[f(x_{k+1})\mid\mathcal{F}_k] \le f(x_k) - \eta\Big(1 - \frac{L\eta}{2}\Big)\lVert\nabla f(x_k)\rVert^2 + \frac{L\eta^2}{2}\sigma^2 . E [ f ( x k + 1 ) ∣ F k ] ≤ f ( x k ) − η ( 1 − 2 L η ) ∥ ∇ f ( x k ) ∥ 2 + 2 L η 2 σ 2 . 由 η ≤ 1 / L \eta \le 1/L η ≤ 1/ L 可知 1 − L η / 2 ≥ 1 / 2 1 - L\eta/2 \ge 1/2 1 − L η /2 ≥ 1/2 ,得到第一個結論。再取全期望並用塔式性質 E [ E [ ⋅ ∣ F k ] ] = E [ ⋅ ] \mathbb{E}[\mathbb{E}[\,\cdot\mid\mathcal{F}_k]] = \mathbb{E}[\,\cdot\,] E [ E [ ⋅ ∣ F k ]] = E [ ⋅ ] ,便得到第二個結論。
證明透視
條件期望在單步證明中的作用 下降不等式對每個隨機結果成立,但含有兩個隨機量:⟨ ∇ f ( x k ) , g k ⟩ \langle\nabla f(x_k),g_k\rangle ⟨ ∇ f ( x k ) , g k ⟩ 與 ∥ g k ∥ 2 \lVert g_k\rVert^2 ∥ g k ∥ 2 。證明把兩者分別換成給定 F k \mathcal{F}_k F k 的條件期望,而估計器的每個假設恰好在其中一次替換時使用。條件無偏性把線性項化為 ∥ ∇ f ( x k ) ∥ 2 \lVert\nabla f(x_k)\rVert^2 ∥ ∇ f ( x k ) ∥ 2 ;它在二階矩恆等式中再用一次,消去交叉項。方差界則把 E [ ∥ e k ∥ 2 ∣ F k ] \mathbb{E}[\lVert e_k\rVert^2\mid\mathcal F_k] E [∥ e k ∥ 2 ∣ F k ] 換成 σ 2 \sigma^2 σ 2 。
兩次替換都要求 ∇ f ( x k ) \nabla f(x_k) ∇ f ( x k ) 能移出條件期望,即 x k x_k x k 是 F k \mathcal{F}_k F k -可測的。這正是要先確定資訊結構,再描述估計器的原因。
步長只在最後出現。係數為 η ( 1 − L η / 2 ) \eta(1-L\eta/2) η ( 1 − L η /2 ) 的界對每個 η > 0 \eta>0 η > 0 都成立;限制 η ≤ 1 / L \eta\le1/L η ≤ 1/ L 只是把該係數簡化為至少 η / 2 \eta/2 η /2 。
與確定性情況比較:後者沒有額外的 L η 2 2 σ 2 \frac{L\eta^2}{2}\sigma^2 2 L η 2 σ 2 ,而 f f f 單調不增。此處當 ∥ ∇ f ( x k ) ∥ 2 \lVert\nabla f(x_k)\rVert^2 ∥ ∇ f ( x k ) ∥ 2 相對 L η σ 2 L\eta\sigma^2 L η σ 2 較小時,期望目標值可能上升;雜訊項就是使用估計所付出的代價。
有限時域的駐點界
在上述基本假設下,對每個正整數 T T T ,
1 T ∑ k = 0 T − 1 E ∥ ∇ f ( x k ) ∥ 2 ≤ 2 ( f ( x 0 ) − f inf ) η T + L η σ 2 . \frac{1}{T}\sum_{k=0}^{T-1}\mathbb{E}\lVert\nabla f(x_k)\rVert^2 \le \frac{2\big(f(x_0) - f_{\inf}\big)}{\eta T} + L\eta\sigma^2 . T 1 k = 0 ∑ T − 1 E ∥ ∇ f ( x k ) ∥ 2 ≤ η T 2 ( f ( x 0 ) − f i n f ) + L η σ 2 .
重排期望單步界:
η 2 E ∥ ∇ f ( x k ) ∥ 2 ≤ E f ( x k ) − E f ( x k + 1 ) + L η 2 2 σ 2 . \frac{\eta}{2}\mathbb{E}\lVert\nabla f(x_k)\rVert^2 \le \mathbb{E}f(x_k) - \mathbb{E}f(x_{k+1}) + \frac{L\eta^2}{2}\sigma^2 . 2 η E ∥ ∇ f ( x k ) ∥ 2 ≤ E f ( x k ) − E f ( x k + 1 ) + 2 L η 2 σ 2 . 對 k = 0 , … , T − 1 k = 0, \dots, T-1 k = 0 , … , T − 1 求和,目標值望遠鏡式抵消:
η 2 ∑ k = 0 T − 1 E ∥ ∇ f ( x k ) ∥ 2 ≤ f ( x 0 ) − E f ( x T ) + T L η 2 2 σ 2 . \frac{\eta}{2}\sum_{k=0}^{T-1}\mathbb{E}\lVert\nabla f(x_k)\rVert^2 \le f(x_0) - \mathbb{E}f(x_T) + \frac{TL\eta^2}{2}\sigma^2 . 2 η k = 0 ∑ T − 1 E ∥ ∇ f ( x k ) ∥ 2 ≤ f ( x 0 ) − E f ( x T ) + 2 T L η 2 σ 2 . 因 x 0 x_0 x 0 確定,E f ( x 0 ) = f ( x 0 ) \mathbb{E}f(x_0) = f(x_0) E f ( x 0 ) = f ( x 0 ) 。又因 f ( x T ) ≥ f inf f(x_T) \ge f_{\inf} f ( x T ) ≥ f i n f 逐點成立,所以 E f ( x T ) ≥ f inf \mathbb{E}f(x_T) \ge f_{\inf} E f ( x T ) ≥ f i n f 。代入後乘以 2 / ( η T ) 2/(\eta T) 2/ ( η T ) 即得結果。
如何理解這個界
隨機選取輸出。 設 R R R 在 { 0 , … , T − 1 } \lbrace 0,\dots,T-1\rbrace { 0 , … , T − 1 } 上均勻分布,且獨立於整次運行。則
E ∥ ∇ f ( x R ) ∥ 2 = ∑ k = 0 T − 1 E [ 1 { R = k } ∥ ∇ f ( x k ) ∥ 2 ] = ∑ k = 0 T − 1 1 T E ∥ ∇ f ( x k ) ∥ 2 . \mathbb{E}\lVert\nabla f(x_R)\rVert^2 = \sum_{k=0}^{T-1}\mathbb{E}\big[\mathbf{1}_{\lbrace R = k\rbrace}\lVert\nabla f(x_k)\rVert^2\big] = \sum_{k=0}^{T-1}\frac{1}{T}\,\mathbb{E}\lVert\nabla f(x_k)\rVert^2 . E ∥ ∇ f ( x R ) ∥ 2 = k = 0 ∑ T − 1 E [ 1 { R = k } ∥ ∇ f ( x k ) ∥ 2 ] = k = 0 ∑ T − 1 T 1 E ∥ ∇ f ( x k ) ∥ 2 .
第二個等號用到 R R R 的獨立性。因此定理恰好給出 E ∥ ∇ f ( x R ) ∥ 2 \mathbb{E}\lVert\nabla f(x_R)\rVert^2 E ∥ ∇ f ( x R ) ∥ 2 的界。它亦推出 min k E ∥ ∇ f ( x k ) ∥ 2 ≤ \min\limits_k \mathbb{E}\lVert\nabla f(x_k)\rVert^2 \le k min E ∥ ∇ f ( x k ) ∥ 2 ≤ (右側的界),因為最小值不超過平均值。
三個不同的量。 不要混淆:
期望平方範數 E ∥ ∇ f ( x R ) ∥ 2 \mathbb{E}\lVert\nabla f(x_R)\rVert^2 E ∥ ∇ f ( x R ) ∥ 2 :這是定理直接控制的量。
期望範數 E ∥ ∇ f ( x R ) ∥ \mathbb{E}\lVert\nabla f(x_R)\rVert E ∥ ∇ f ( x R )∥ :Jensen 不等式給出 E ∥ ∇ f ( x R ) ∥ ≤ E ∥ ∇ f ( x R ) ∥ 2 \mathbb{E}\lVert\nabla f(x_R)\rVert \le \sqrt{\mathbb{E}\lVert\nabla f(x_R)\rVert^2} E ∥ ∇ f ( x R )∥ ≤ E ∥ ∇ f ( x R ) ∥ 2 。這是界的推論,並非同一個陳述。
樣本路徑行為 :這裏沒有說某次具體運行必定有小梯度。Markov 不等式只給概率陳述:P ( ∥ ∇ f ( x R ) ∥ 2 ≥ ε ) ≤ ε − 1 E ∥ ∇ f ( x R ) ∥ 2 \mathbb{P}(\lVert\nabla f(x_R)\rVert^2 \ge \varepsilon) \le \varepsilon^{-1}\,\mathbb{E}\lVert\nabla f(x_R)\rVert^2 P (∥ ∇ f ( x R ) ∥ 2 ≥ ε ) ≤ ε − 1 E ∥ ∇ f ( x R ) ∥ 2 。
兩項的作用。 第一項 2 ( f ( x 0 ) − f inf ) / ( η T ) 2(f(x_0)-f_{\inf})/(\eta T) 2 ( f ( x 0 ) − f i n f ) / ( η T ) 是確定性項,隨 T T T 增大而縮小;第二項 L η σ 2 L\eta\sigma^2 L η σ 2 與 T T T 無關,固定步長下運行多久仍會留在界中。定理給的是上界 ,並非說誤差永遠至少是 L η σ 2 L\eta\sigma^2 L η σ 2 。當 σ 2 = 0 \sigma^2 = 0 σ 2 = 0 ,便重得沒有雜訊下限的確定性速率。下方例子會顯示,真正有雜訊的問題確實可以出現嚴格為正的下限。
定理沒有聲稱甚麼。 此界沒有說迭代點 x k x_k x k 收斂,也沒有說它們趨向全局最小點;對非凸 f f f ,後者一般不成立。此界沒有給出最後一個迭代點 x T x_T x T 的速率,亦沒有說明不包含於 f f f 的數據上的表現。
有限和與小批次
設 f = 1 n ∑ i = 1 n f i f = \frac{1}{n}\sum\limits_{i=1}^n f_i f = n 1 i = 1 ∑ n f i ,其中各 f i : R d → R f_i:\mathbb{R}^d\to\mathbb{R} f i : R d → R 都是確定的可微函數。光滑及有下界的假設施加於 f f f 。第 k k k 步抽取與 F k \mathcal{F}_k F k 獨立、在 { 1 , … , n } \lbrace 1,\dots,n\rbrace { 1 , … , n } 上均勻分布的索引 I k I_k I k ,並令 g k = ∇ f I k ( x k ) g_k = \nabla f_{I_k}(x_k) g k = ∇ f I k ( x k ) 。
定義 V ( x ) : = n − 1 ∑ i = 1 n ∥ ∇ f i ( x ) − ∇ f ( x ) ∥ 2 V(x):=n^{-1}\sum\limits_{i=1}^n\lVert\nabla f_i(x)-\nabla f(x)\rVert^2 V ( x ) := n − 1 i = 1 ∑ n ∥ ∇ f i ( x ) − ∇ f ( x ) ∥ 2 ,並在此構造中假設所有 x x x 均滿足 V ( x ) ≤ σ 2 V(x)\le\sigma^2 V ( x ) ≤ σ 2 。從確定的 x 0 x_0 x 0 出發,歸納可知 x k x_k x k 平方可積:梯度的 Lipschitz 性質與方差界保證抽樣梯度平方可積,因此下一個迭代點亦平方可積。所以下列條件期望都有意義。由於 x k x_k x k 是 F k \mathcal{F}_k F k -可測而 I k I_k I k 與 F k \mathcal{F}_k F k 獨立,計算條件期望時可「固定」x k x_k x k ,再對索引取平均:
E [ g k ∣ F k ] = ∑ i = 1 n 1 n ∇ f i ( x k ) = ∇ f ( x k ) , \mathbb{E}[g_k\mid\mathcal{F}_k] = \sum_{i=1}^n \frac{1}{n}\nabla f_i(x_k) = \nabla f(x_k), E [ g k ∣ F k ] = i = 1 ∑ n n 1 ∇ f i ( x k ) = ∇ f ( x k ) ,
E [ ∥ g k − ∇ f ( x k ) ∥ 2 ∣ F k ] = V ( x k ) . \mathbb{E}\big[\lVert g_k - \nabla f(x_k)\rVert^2\mid\mathcal{F}_k\big] = V(x_k). E [ ∥ g k − ∇ f ( x k ) ∥ 2 ∣ F k ] = V ( x k ) .
上述全局條件充分但非必要:沿迭代點的適當界配合可積性亦已足夠。這條件不能 由 f f f 的光滑性推出。例如取 n = 2 n = 2 n = 2 、f 1 ( x ) = x 2 f_1(x) = x^2 f 1 ( x ) = x 2 及 f 2 ( x ) = − x 2 f_2(x) = -x^2 f 2 ( x ) = − x 2 。此時 f ≡ 0 f \equiv 0 f ≡ 0 光滑且有下界,但 V ( x ) = 4 x 2 V(x) = 4x^2 V ( x ) = 4 x 2 無界。因此一致有界方差是獨立假設。
一旦方差界成立,平方可積性亦隨之成立。因為 E ∥ g k ∥ 2 = E ∥ ∇ f ( x k ) ∥ 2 + E V ( x k ) \mathbb{E}\lVert g_k\rVert^2 = \mathbb{E}\lVert\nabla f(x_k)\rVert^2 + \mathbb{E}V(x_k) E ∥ g k ∥ 2 = E ∥ ∇ f ( x k ) ∥ 2 + E V ( x k ) ,第二項至多為 σ 2 \sigma^2 σ 2 ,而只要 x k x_k x k 平方可積,第一項便有限,故可積性一節中的歸納可以進行。
有放回的小批次。 現抽取 b ≥ 1 b \ge 1 b ≥ 1 個索引 I k , 1 , … , I k , b I_{k,1},\dots,I_{k,b} I k , 1 , … , I k , b ,它們各自均勻分布,彼此獨立且與 F k \mathcal{F}_k F k 獨立。所有分量梯度都在同一點 x k x_k x k 計算:
g ˉ k = 1 b ∑ j = 1 b ∇ f I k , j ( x k ) . \bar g_k = \frac{1}{b}\sum_{j=1}^b \nabla f_{I_{k,j}}(x_k). g ˉ k = b 1 j = 1 ∑ b ∇ f I k , j ( x k ) .
在有限和設定中,設所有 x x x 均滿足 V ( x ) ≤ σ 2 V(x)\le\sigma^2 V ( x ) ≤ σ 2 。令 g ˉ k \bar g_k g ˉ k 為 x k x_k x k 處 b b b 個分量梯度的平均,其索引彼此獨立、在 { 1 , … , n } \lbrace1,\dots,n\rbrace { 1 , … , n } 上均勻分布,且與 F k \mathcal F_k F k 獨立。則
E [ g ˉ k ∣ F k ] = ∇ f ( x k ) , E [ ∥ g ˉ k − ∇ f ( x k ) ∥ 2 ∣ F k ] = V ( x k ) b ≤ σ 2 b . \mathbb{E}[\bar g_k\mid\mathcal F_k]=\nabla f(x_k),\qquad
\mathbb{E}\big[\lVert\bar g_k - \nabla f(x_k)\rVert^2\mid\mathcal{F}_k\big] = \frac{V(x_k)}{b} \le \frac{\sigma^2}{b}. E [ g ˉ k ∣ F k ] = ∇ f ( x k ) , E [ ∥ g ˉ k − ∇ f ( x k ) ∥ 2 ∣ F k ] = b V ( x k ) ≤ b σ 2 .
由線性性可得無偏性。為計算方差,令 d i = ∇ f i ( x k ) − ∇ f ( x k ) d_i = \nabla f_i(x_k) - \nabla f(x_k) d i = ∇ f i ( x k ) − ∇ f ( x k ) ,於是 ∑ i d i = 0 \sum\limits_i d_i = 0 i ∑ d i = 0 ,再令 e j = d I k , j e_j = d_{I_{k,j}} e j = d I k , j 。則
∥ ∑ j = 1 b e j ∥ 2 = ∑ j ∥ e j ∥ 2 + ∑ j ≠ l ⟨ e j , e l ⟩ . \Big\lVert\sum_{j=1}^b e_j\Big\rVert^2 = \sum_{j}\lVert e_j\rVert^2 + \sum_{j\ne l}\langle e_j, e_l\rangle . j = 1 ∑ b e j 2 = j ∑ ∥ e j ∥ 2 + j = l ∑ ⟨ e j , e l ⟩ . 每個對角項的條件期望均為 V ( x k ) V(x_k) V ( x k ) 。當 j ≠ l j \ne l j = l ,索引獨立且均勻,故
E [ ⟨ e j , e l ⟩ ∣ F k ] = 1 n 2 ∑ i , m ⟨ d i , d m ⟩ = ∥ 1 n ∑ i d i ∥ 2 = 0. \mathbb{E}[\langle e_j, e_l\rangle\mid\mathcal{F}_k] = \frac{1}{n^2}\sum_{i,m}\langle d_i, d_m\rangle = \Big\lVert \frac{1}{n}\sum_i d_i\Big\rVert^2 = 0 . E [⟨ e j , e l ⟩ ∣ F k ] = n 2 1 i , m ∑ ⟨ d i , d m ⟩ = n 1 i ∑ d i 2 = 0. 交叉項全部消失。由於 g ˉ k − ∇ f ( x k ) = 1 b ∑ j e j \bar g_k-\nabla f(x_k)=\frac1b\sum\limits_j e_j g ˉ k − ∇ f ( x k ) = b 1 j ∑ e j ,除以 b 2 b^2 b 2 便得所述方差。
因此駐點定理可用 σ 2 / b \sigma^2/b σ 2 / b 代替 σ 2 \sigma^2 σ 2 ;雜訊項變為 L η σ 2 / b L\eta\sigma^2/b L η σ 2 / b ,代價是每步要計算 b b b 個分量梯度。
小批次縮小了雜訊項,於是很容易想同時放大步長,例如令步長與 b b b 成正比。這裏證明的界並不容許這樣做。證明用到 η ≤ 1 / L \eta\le1/L η ≤ 1/ L ,而 L L L 是 f f f 的性質,與估計器無關,所以對每個 b b b ,可用的步長範圍都一樣。平均 b b b 個梯度把雜訊項由 L η σ 2 L\eta\sigma^2 L η σ 2 降為 L η σ 2 / b L\eta\sigma^2/b L η σ 2 / b ;確定性項 2 ( f ( x 0 ) − f inf ) / ( η T ) 2(f(x_0)-f_{\inf})/(\eta T) 2 ( f ( x 0 ) − f i n f ) / ( η T ) 則不變。
反例模式
抽樣何時令論證失效 批次內不放回抽樣。 均勻抽取 b b b 個不同 索引,其中 2 ≤ b ≤ n 2 \le b \le n 2 ≤ b ≤ n 。每個單獨索引仍均勻分布,故 g ˉ k \bar g_k g ˉ k 仍然無偏;但交叉項不再消失。對均勻選出的不同 i ≠ m i \ne m i = m ,
E ⟨ d i , d m ⟩ = 1 n ( n − 1 ) ∑ i ≠ m ⟨ d i , d m ⟩ = ∥ ∑ i d i ∥ 2 − ∑ i ∥ d i ∥ 2 n ( n − 1 ) = − V n − 1 . \mathbb{E}\langle d_i, d_m\rangle = \frac{1}{n(n-1)}\sum_{i\ne m}\langle d_i, d_m\rangle = \frac{\lVert\sum_i d_i\rVert^2 - \sum_i\lVert d_i\rVert^2}{n(n-1)} = -\frac{V}{n-1}. E ⟨ d i , d m ⟩ = n ( n − 1 ) 1 i = m ∑ ⟨ d i , d m ⟩ = n ( n − 1 ) ∥ ∑ i d i ∥ 2 − ∑ i ∥ d i ∥ 2 = − n − 1 V . 所以 E ∥ ∑ j e j ∥ 2 = b V − b ( b − 1 ) V n − 1 = b V n − b n − 1 \mathbb{E}\lVert\sum\limits_j e_j\rVert^2 = bV - b(b-1)\frac{V}{n-1} = bV\frac{n-b}{n-1} E ∥ j ∑ e j ∥ 2 = bV − b ( b − 1 ) n − 1 V = bV n − 1 n − b ,條件方差為 V b ⋅ n − b n − 1 \frac{V}{b}\cdot\frac{n-b}{n-1} b V ⋅ n − 1 n − b 。因子 n − b n − 1 \frac{n-b}{n-1} n − 1 n − b 稱為有限總體修正。結果仍小於 V / b V/b V / b ,但推導不同。
跨步不放回抽樣。 假設索引只重新洗牌一次,然後按順序使用。取 n = 2 n = 2 n = 2 和下方例子的函數。若 I 0 = 1 I_0 = 1 I 0 = 1 ,則必有 I 1 = 2 I_1 = 2 I 1 = 2 ;給定 F 1 \mathcal{F}_1 F 1 時,g 1 = x 1 + 1 ≠ ∇ f ( x 1 ) = x 1 g_1 = x_1 + 1 \ne \nabla f(x_1) = x_1 g 1 = x 1 + 1 = ∇ f ( x 1 ) = x 1 。條件無偏性失效,所以上述定理不適用。這類方法需要另一種分析。
不重新加權的非均勻抽樣。 使用下方例子的函數,假設在 x = 0 x = 0 x = 0 時以概率 3 / 4 3/4 3/4 選取 f 1 f_1 f 1 ,以概率 1 / 4 1/4 1/4 選取 f 2 f_2 f 2 ,則
E g = 3 4 ( 0 − 1 ) + 1 4 ( 0 + 1 ) = − 1 2 ≠ 0 = ∇ f ( 0 ) . \mathbb{E}g = \tfrac34(0-1) + \tfrac14(0+1) = -\tfrac12 \ne 0 = \nabla f(0). E g = 4 3 ( 0 − 1 ) + 4 1 ( 0 + 1 ) = − 2 1 = 0 = ∇ f ( 0 ) . 從精確最小點出發,期望步伐令點移動 + η / 2 +\eta/2 + η /2 。若在每個 x x x 都使用這些概率,方法實際上是在 3 4 f 1 + 1 4 f 2 = 1 2 x 2 − 1 2 x + 1 2 \tfrac34 f_1 + \tfrac14 f_2 = \tfrac12x^2 - \tfrac12 x + \tfrac12 4 3 f 1 + 4 1 f 2 = 2 1 x 2 − 2 1 x + 2 1 上運行 SGD。該函數在 x = 1 / 2 x = 1/2 x = 1/2 達最小,是錯誤的點。補救方法是重新加權。設正概率 q i q_i q i 的和為一,且各 q i q_i q i 均為 F k \mathcal{F}_k F k -可測,並滿足 P ( I k = i ∣ F k ) = q i P(I_k=i\mid\mathcal{F}_k)=q_i P ( I k = i ∣ F k ) = q i 。若 g = ∇ f I k ( x k ) / ( n q I k ) g=\nabla f_{I_k}(x_k)/(nq_{I_k}) g = ∇ f I k ( x k ) / ( n q I k ) 可積,即使 q q q 依賴 x k x_k x k ,它仍條件無偏:∑ i q i ⋅ ∇ f i n q i = ∇ f \sum\limits_i q_i\cdot\frac{\nabla f_i}{nq_i}=\nabla f i ∑ q i ⋅ n q i ∇ f i = ∇ f 。仍須另行驗證條件方差界。
有限總體修正可以透過列舉一個小例子來核對。
取 n = 3 n=3 n = 3 ,並設在當前點的偏差 d i = ∇ f i ( x k ) − ∇ f ( x k ) d_i=\nabla f_i(x_k)-\nabla f(x_k) d i = ∇ f i ( x k ) − ∇ f ( x k ) 為純量 d 1 = − 2 d_1=-2 d 1 = − 2 、d 2 = 0 d_2=0 d 2 = 0 、d 3 = 2 d_3=2 d 3 = 2 。它們的和為零,且 V = 1 3 ( 4 + 0 + 4 ) = 8 3 V=\tfrac13(4+0+4)=\tfrac83 V = 3 1 ( 4 + 0 + 4 ) = 3 8 。
有放回,b = 2 b=2 b = 2 。 由上述命題,平均偏差的方差為 V / b = 4 3 V/b=\tfrac43 V / b = 3 4 。
不放回,b = 2 b=2 b = 2 。 三個無序對等可能,平均偏差分別為 1 2 ( d 1 + d 2 ) = − 1 \tfrac12(d_1+d_2)=-1 2 1 ( d 1 + d 2 ) = − 1 、1 2 ( d 1 + d 3 ) = 0 \tfrac12(d_1+d_3)=0 2 1 ( d 1 + d 3 ) = 0 、1 2 ( d 2 + d 3 ) = 1 \tfrac12(d_2+d_3)=1 2 1 ( d 2 + d 3 ) = 1 。其均值為 0 0 0 ,方差為 1 3 ( 1 + 0 + 1 ) = 2 3 \tfrac13(1+0+1)=\tfrac23 3 1 ( 1 + 0 + 1 ) = 3 2 。公式給出 V b ⋅ n − b n − 1 = 4 3 ⋅ 1 2 = 2 3 \tfrac{V}{b}\cdot\tfrac{n-b}{n-1}=\tfrac43\cdot\tfrac12=\tfrac23 b V ⋅ n − 1 n − b = 3 4 ⋅ 2 1 = 3 2 ,兩者一致。
邊界情形 b = n = 3 b=n=3 b = n = 3 。 不放回時批次就是整個數據集,平均偏差恆為 1 3 ( d 1 + d 2 + d 3 ) = 0 \tfrac13(d_1+d_2+d_3)=0 3 1 ( d 1 + d 2 + d 3 ) = 0 ,而因子 n − b n − 1 = 0 \tfrac{n-b}{n-1}=0 n − 1 n − b = 0 正好預測這一點。有放回時方差仍為 V / 3 = 8 9 V/3=\tfrac89 V /3 = 9 8 ,因為索引仍可能重複。
在下方例子函數的重新洗牌方案中,I 0 I_0 I 0 均勻分布,I 1 I_1 I 1 是另一個索引。誤差 e 1 = g 1 − ∇ f ( x 1 ) e_1=g_1-\nabla f(x_1) e 1 = g 1 − ∇ f ( x 1 ) 在 I 0 = 1 I_0=1 I 0 = 1 時為 + 1 +1 + 1 ,在 I 0 = 2 I_0=2 I 0 = 2 時為 − 1 -1 − 1 ,所以 E e 1 = 0 \mathbb{E}e_1=0 E e 1 = 0 :估計在平均意義下無偏。然而證明需要 E ⟨ ∇ f ( x 1 ) , e 1 ⟩ = 0 \mathbb{E}\langle\nabla f(x_1),e_1\rangle=0 E ⟨ ∇ f ( x 1 ) , e 1 ⟩ = 0 ,而 x 1 x_1 x 1 依賴 I 0 I_0 I 0 :I 0 = 1 I_0=1 I 0 = 1 時 x 1 = ( 1 − η ) x 0 + η x_1=(1-\eta)x_0+\eta x 1 = ( 1 − η ) x 0 + η ,I 0 = 2 I_0=2 I 0 = 2 時 x 1 = ( 1 − η ) x 0 − η x_1=(1-\eta)x_0-\eta x 1 = ( 1 − η ) x 0 − η 。因此
E [ x 1 e 1 ] = 1 2 [ ( 1 − η ) x 0 + η ] − 1 2 [ ( 1 − η ) x 0 − η ] = η ≠ 0. \mathbb{E}[x_1e_1]=\tfrac12\bigl[(1-\eta)x_0+\eta\bigr]-\tfrac12\bigl[(1-\eta)x_0-\eta\bigr]=\eta\ne0 . E [ x 1 e 1 ] = 2 1 [ ( 1 − η ) x 0 + η ] − 2 1 [ ( 1 − η ) x 0 − η ] = η = 0. 無條件的無偏性不能消去交叉項;給定 F k \mathcal F_k F k 的無偏性才可以。
一維計算例子
令 f 1 ( x ) = 1 2 ( x − 1 ) 2 f_1(x) = \frac12(x-1)^2 f 1 ( x ) = 2 1 ( x − 1 ) 2 及 f 2 ( x ) = 1 2 ( x + 1 ) 2 f_2(x) = \frac12(x+1)^2 f 2 ( x ) = 2 1 ( x + 1 ) 2 ,則
f ( x ) = 1 2 ( f 1 + f 2 ) = 1 2 x 2 + 1 2 , f(x) = \tfrac12(f_1 + f_2) = \tfrac12x^2 + \tfrac12, f ( x ) = 2 1 ( f 1 + f 2 ) = 2 1 x 2 + 2 1 ,
其中 ∇ f ( x ) = x \nabla f(x) = x ∇ f ( x ) = x 、L = 1 L = 1 L = 1 及 f inf = 1 2 f_{\inf} = \frac12 f i n f = 2 1 。均勻抽取單個索引時,g = x − 1 g = x - 1 g = x − 1 或 g = x + 1 g = x + 1 g = x + 1 ,概率各為 1 2 \frac12 2 1 。對每個 x x x ,其均值為 x x x ,方差為 1 2 ( 1 ) + 1 2 ( 1 ) = 1 \frac12(1) + \frac12(1) = 1 2 1 ( 1 ) + 2 1 ( 1 ) = 1 ,故一致滿足 σ 2 = 1 \sigma^2 = 1 σ 2 = 1 。
取 x 0 = 0 x_0 = 0 x 0 = 0 及 η = 1 2 \eta = \frac12 η = 2 1 。完整梯度是 ∇ f ( 0 ) = 0 \nabla f(0) = 0 ∇ f ( 0 ) = 0 ;兩種可能的步伐為
x 1 = 0 − 1 2 ( 0 ∓ 1 ) = ± 1 2 . x_1 = 0 - \tfrac12(0 \mp 1) = \pm\tfrac12 . x 1 = 0 − 2 1 ( 0 ∓ 1 ) = ± 2 1 . 兩個結果都給出 f ( ± 1 2 ) = 1 2 ⋅ 1 4 + 1 2 = 5 8 > 1 2 = f ( x 0 ) f(\pm\tfrac12) = \tfrac12\cdot\tfrac14 + \tfrac12 = \tfrac58 > \tfrac12 = f(x_0) f ( ± 2 1 ) = 2 1 ⋅ 4 1 + 2 1 = 8 5 > 2 1 = f ( x 0 ) 。實際目標值以概率一上升。單步界預測 E f ( x 1 ) ≤ 1 2 − 0 + 1 ⋅ ( 1 / 4 ) 2 ⋅ 1 = 5 8 \mathbb{E}f(x_1) \le \frac12 - 0 + \frac{1\cdot(1/4)}{2}\cdot 1 = \frac58 E f ( x 1 ) ≤ 2 1 − 0 + 2 1 ⋅ ( 1/4 ) ⋅ 1 = 8 5 ,此例中恰好取等。原因有二:f f f 是曲率恰為 L L L 的二次函數,所以下降引理取等;而 1 − L η / 2 1 - L\eta/2 1 − L η /2 與 1 2 \frac12 2 1 的差乘上的是 ∇ f ( x 0 ) = 0 \nabla f(x_0) = 0 ∇ f ( x 0 ) = 0 。
若有放回地獨立抽取 b b b 個索引,方差為 1 / b 1/b 1/ b ,期望增幅變為 1 8 b \frac{1}{8b} 8 b 1 。
寫成 g k = x k + ε k g_k = x_k + \varepsilon_k g k = x k + ε k ,其中 ε k = ± 1 \varepsilon_k = \pm1 ε k = ± 1 的概率相等,且 ε k \varepsilon_k ε k 與 F k \mathcal{F}_k F k 獨立。則
x k + 1 = ( 1 − η ) x k − η ε k , 0 < η ≤ 1. x_{k+1} = (1-\eta)x_k - \eta\varepsilon_k, \qquad 0 < \eta \le 1 . x k + 1 = ( 1 − η ) x k − η ε k , 0 < η ≤ 1. 令 a k = E x k 2 a_k = \mathbb{E}x_k^2 a k = E x k 2 。將遞歸式平方後,交叉項為 E [ x k ε k ] = E [ x k E [ ε k ∣ F k ] ] = 0 \mathbb{E}[x_k\varepsilon_k] = \mathbb{E}[x_k\,\mathbb{E}[\varepsilon_k\mid\mathcal{F}_k]] = 0 E [ x k ε k ] = E [ x k E [ ε k ∣ F k ]] = 0 ,故
a k + 1 = ( 1 − η ) 2 a k + η 2 , a 0 = 0. a_{k+1} = (1-\eta)^2a_k + \eta^2, \qquad a_0 = 0 . a k + 1 = ( 1 − η ) 2 a k + η 2 , a 0 = 0. 展開後得到等比和 a k = η 2 ∑ j = 0 k − 1 ( 1 − η ) 2 j a_k = \eta^2\sum\limits_{j=0}^{k-1}(1-\eta)^{2j} a k = η 2 j = 0 ∑ k − 1 ( 1 − η ) 2 j 。公比為 ( 1 − η ) 2 (1-\eta)^2 ( 1 − η ) 2 ,而 1 − ( 1 − η ) 2 = η ( 2 − η ) 1 - (1-\eta)^2 = \eta(2-\eta) 1 − ( 1 − η ) 2 = η ( 2 − η ) ,因此
E x k 2 = η 2 − η [ 1 − ( 1 − η ) 2 k ] ⟶ η 2 − η > 0. \mathbb{E}x_k^2 = \frac{\eta}{2-\eta}\Big[1 - (1-\eta)^{2k}\Big] \longrightarrow \frac{\eta}{2-\eta} > 0 . E x k 2 = 2 − η η [ 1 − ( 1 − η ) 2 k ] ⟶ 2 − η η > 0. 此處 ∥ ∇ f ( x k ) ∥ 2 = x k 2 \lVert\nabla f(x_k)\rVert^2 = x_k^2 ∥ ∇ f ( x k ) ∥ 2 = x k 2 。收斂數列的平均值有相同極限,故平均數 1 T ∑ k < T a k \frac1T\sum\limits_{k<T}a_k T 1 k < T ∑ a k 也趨向 η 2 − η \frac{\eta}{2-\eta} 2 − η η 。由 f ( x 0 ) = f inf f(x_0) = f_{\inf} f ( x 0 ) = f i n f ,本例定理的界為 0 + L η σ 2 = η 0 + L\eta\sigma^2 = \eta 0 + L η σ 2 = η 。當 η = 1 2 \eta = \frac12 η = 2 1 ,真正極限是 1 3 \frac13 3 1 ,界則是 1 2 \frac12 2 1 。這個下限真實且嚴格為正,而界高估的倍數為 2 − η ≤ 2 2 - \eta \le 2 2 − η ≤ 2 。
這個簡潔遞歸依賴特殊結構:雜訊 ε k \varepsilon_k ε k 在每個 x x x 的分布相同。對一般有限數據,雜訊 ∇ f I ( x ) − ∇ f ( x ) \nabla f_I(x) - \nabla f(x) ∇ f I ( x ) − ∇ f ( x ) 隨 x x x 改變;沒有進一步假設便不能得到這樣的精確公式。
練習
練習 3.3.8
(在上述例子中有放回抽取 b = 2 b = 2 b = 2 個索引。列出點 x x x 處 g ˉ \bar g g ˉ 的分布並計算其條件方差,再對兩個不同索引重做一次。)
基礎
解答 (3) 1 列舉有序索引對
四個有序索引對等可能。( 1 , 1 ) (1,1) ( 1 , 1 ) 給出 g ˉ = x − 1 \bar g = x-1 g ˉ = x − 1 ,( 2 , 2 ) (2,2) ( 2 , 2 ) 給出 x + 1 x+1 x + 1 ,而 ( 1 , 2 ) (1,2) ( 1 , 2 ) 及 ( 2 , 1 ) (2,1) ( 2 , 1 ) 均給出 x x x 。故 g ˉ \bar g g ˉ 以概率 1 4 \frac14 4 1 等於 x − 1 x-1 x − 1 ,以概率 1 2 \frac12 2 1 等於 x x x ,以概率 1 4 \frac14 4 1 等於 x + 1 x+1 x + 1 。
2 計算均值與方差
均值為 x x x 。因 V = 1 V = 1 V = 1 ,方差為
1 4 ( 1 ) 2 + 1 2 ( 0 ) 2 + 1 4 ( 1 ) 2 = 1 2 = V b . \tfrac14(1)^2 + \tfrac12(0)^2 + \tfrac14(1)^2 = \tfrac12 = \tfrac{V}{b}. 4 1 ( 1 ) 2 + 2 1 ( 0 ) 2 + 4 1 ( 1 ) 2 = 2 1 = b V . 3 不同索引
若索引不同,則恆有 g ˉ = x \bar g = x g ˉ = x ,方差為 0 0 0 ,與 V b ⋅ n − b n − 1 = 1 2 ⋅ 0 \frac{V}{b}\cdot\frac{n-b}{n-1} = \frac12\cdot 0 b V ⋅ n − 1 n − b = 2 1 ⋅ 0 一致。
看下一步 (2/3) 全部展開
練習 3.3.9
(在例子中取 η = 1 2 \eta = \frac12 η = 2 1 及 x 0 = 0 x_0 = 0 x 0 = 0 。求 x 2 x_2 x 2 的分布、E x 2 2 \mathbb{E}x_2^2 E x 2 2 和 E f ( x 2 ) \mathbb{E}f(x_2) E f ( x 2 ) ,再核對從 k = 1 k = 1 k = 1 到 k = 2 k = 2 k = 2 的單步界。)
核心
解答 (4) 1 x 2 x_2 x 2 的分布
當 η = 1 2 \eta = \frac12 η = 2 1 ,x 1 = − ε 0 / 2 x_1 = -\varepsilon_0/2 x 1 = − ε 0 /2 而 x 2 = 1 2 x 1 − 1 2 ε 1 = − ε 0 4 − ε 1 2 x_2 = \frac12x_1 - \frac12\varepsilon_1 = -\frac{\varepsilon_0}{4} - \frac{\varepsilon_1}{2} x 2 = 2 1 x 1 − 2 1 ε 1 = − 4 ε 0 − 2 ε 1 。四種符號組合給出 x 2 ∈ { ± 3 4 , ± 1 4 } x_2 \in \lbrace \pm\frac34, \pm\frac14\rbrace x 2 ∈ { ± 4 3 , ± 4 1 } ,各以概率 1 4 \frac14 4 1 出現。
2 二階矩與期望目標值
E x 2 2 = 1 2 ⋅ 9 16 + 1 2 ⋅ 1 16 = 5 16 , \mathbb{E}x_2^2 = \tfrac12\cdot\tfrac{9}{16} + \tfrac12\cdot\tfrac1{16} = \tfrac{5}{16}, E x 2 2 = 2 1 ⋅ 16 9 + 2 1 ⋅ 16 1 = 16 5 , 與公式 1 3 ( 1 − 1 16 ) = 5 16 \frac13(1 - \frac1{16}) = \frac5{16} 3 1 ( 1 − 16 1 ) = 16 5 相符。接著 E f ( x 2 ) = 1 2 ⋅ 5 16 + 1 2 = 21 32 \mathbb{E}f(x_2) = \frac12\cdot\frac5{16} + \frac12 = \frac{21}{32} E f ( x 2 ) = 2 1 ⋅ 16 5 + 2 1 = 32 21 。
3 核對單步界
E f ( x 2 ) ≤ 5 8 − 1 4 ⋅ 1 4 + 1 8 = 20 − 2 + 4 32 = 22 32 , \mathbb{E}f(x_2) \le \tfrac58 - \tfrac14\cdot\tfrac14 + \tfrac18 = \tfrac{20 - 2 + 4}{32} = \tfrac{22}{32}, E f ( x 2 ) ≤ 8 5 − 4 1 ⋅ 4 1 + 8 1 = 32 20 − 2 + 4 = 32 22 , 而確實 21 32 ≤ 22 32 \frac{21}{32} \le \frac{22}{32} 32 21 ≤ 32 22 。
依據: E f ( x 1 ) = 5 8 \mathbb{E}f(x_1)=\tfrac58 E f ( x 1 ) = 8 5 ,且 E ∥ ∇ f ( x 1 ) ∥ 2 = E x 1 2 = 1 4 \mathbb{E}\lVert\nabla f(x_1)\rVert^2=\mathbb{E}x_1^2=\tfrac14 E ∥ ∇ f ( x 1 ) ∥ 2 = E x 1 2 = 4 1 。
4 找出差距的來源
精確單步計算使用因子 η ( 1 − η / 2 ) = 3 8 \eta(1 - \eta/2) = \frac38 η ( 1 − η /2 ) = 8 3 而非 η 2 = 1 4 \frac{\eta}{2} = \frac14 2 η = 4 1 ,並給出 20 − 3 + 4 32 = 21 32 \frac{20 - 3 + 4}{32} = \frac{21}{32} 32 20 − 3 + 4 = 32 21 。差距 1 32 \frac1{32} 32 1 正是將 1 − L η / 2 1 - L\eta/2 1 − L η /2 換成 1 2 \frac12 2 1 所引入的鬆弛量。
看下一步 (2/4) 全部展開
練習 3.3.10
(假設 f ( x 0 ) − f inf = 10 f(x_0) - f_{\inf} = 10 f ( x 0 ) − f i n f = 10 、L = 4 L = 4 L = 4 、σ 2 = 9 \sigma^2 = 9 σ 2 = 9 及 T = 1000 T = 1000 T = 1000 。(a) 計算 η = 1 8 \eta = \frac18 η = 8 1 時的界。(b) 假設單索引方差一致地以 9 9 9 為界,計算有放回抽取大小為 9 9 9 的小批次時的界。(c) 求令此 T T T 對應的界最小的步長。)
核心
解答 (3) 1 (a) 計算界
步長可用,因為 1 8 ≤ 1 4 = 1 L \frac18 \le \frac14 = \frac1L 8 1 ≤ 4 1 = L 1 。界為
2 ⋅ 10 ( 1 / 8 ) ⋅ 1000 + 4 ⋅ 1 8 ⋅ 9 = 0.16 + 4.5 = 4.66. \frac{2\cdot 10}{(1/8)\cdot1000} + 4\cdot\tfrac18\cdot9 = 0.16 + 4.5 = 4.66 . ( 1/8 ) ⋅ 1000 2 ⋅ 10 + 4 ⋅ 8 1 ⋅ 9 = 0.16 + 4.5 = 4.66. 因此對均勻隨機的 R R R ,E ∥ ∇ f ( x R ) ∥ ≤ 4.66 ≈ 2.159 \mathbb{E}\lVert\nabla f(x_R)\rVert \le \sqrt{4.66} \approx 2.159 E ∥ ∇ f ( x R )∥ ≤ 4.66 ≈ 2.159 ,而 P ( ∥ ∇ f ( x R ) ∥ 2 ≥ 10 ) ≤ 0.466 \mathbb{P}(\lVert\nabla f(x_R)\rVert^2 \ge 10) \le 0.466 P (∥ ∇ f ( x R ) ∥ 2 ≥ 10 ) ≤ 0.466 。
2 (b) 大小為 9 9 9 的小批次
方差變為 9 / 9 = 1 9/9 = 1 9/9 = 1 ,故界是 0.16 + 4 ⋅ 1 8 ⋅ 1 = 0.66 0.16 + 4\cdot\frac18\cdot1 = 0.66 0.16 + 4 ⋅ 8 1 ⋅ 1 = 0.66 。這需要 9000 9000 9000 次分量梯度計算,而非 1000 1000 1000 次。
3 (c) 固定 T T T 時最優化步長
令 Δ = 10 \Delta = 10 Δ = 10 ,最小化 2 Δ η T + L η σ 2 \frac{2\Delta}{\eta T} + L\eta\sigma^2 η T 2Δ + L η σ 2 。令導數為零得
η ∗ = 2 Δ T L σ 2 = 20 36000 = 1 1800 ≈ 0.02357 ≤ 1 4 . \eta^\ast = \sqrt{\frac{2\Delta}{TL\sigma^2}} = \sqrt{\frac{20}{36000}} = \frac{1}{\sqrt{1800}} \approx 0.02357 \le \tfrac14 . η ∗ = T L σ 2 2Δ = 36000 20 = 1800 1 ≈ 0.02357 ≤ 4 1 . 在 η ∗ \eta^\ast η ∗ 處兩項均等於 36 η ∗ ≈ 0.8485 36\eta^\ast \approx 0.8485 36 η ∗ ≈ 0.8485 ,故界約為 1.697 1.697 1.697 。這個調校依賴 T T T ,並不是收斂性的陳述。
看下一步 (2/3) 全部展開
練習 3.3.11
(在例子中,獨立於過去,以概率 q 1 = 3 4 q_1 = \frac34 q 1 = 4 3 抽取 I = 1 I = 1 I = 1 ,以概率 q 2 = 1 4 q_2 = \frac14 q 2 = 4 1 抽取 I = 2 I = 2 I = 2 。使用 g = ∇ f I ( x ) / ( 2 q I ) g = \nabla f_I(x)/(2q_I) g = ∇ f I ( x ) / ( 2 q I ) 。證明 g g g 無偏,計算其條件方差,並判斷定理的方差假設在 R \mathbb{R} R 上是否成立。)
綜合
解答 (3) 1 g g g 的兩個值及其均值
若 I = 1 I = 1 I = 1 ,則 g = x − 1 3 / 2 = 2 3 ( x − 1 ) g = \frac{x-1}{3/2} = \frac23(x-1) g = 3/2 x − 1 = 3 2 ( x − 1 ) ;若 I = 2 I = 2 I = 2 ,則 g = x + 1 1 / 2 = 2 ( x + 1 ) g = \frac{x+1}{1/2} = 2(x+1) g = 1/2 x + 1 = 2 ( x + 1 ) 。均值是
3 4 ⋅ 2 3 ( x − 1 ) + 1 4 ⋅ 2 ( x + 1 ) = 1 2 ( x − 1 ) + 1 2 ( x + 1 ) = x , \tfrac34\cdot\tfrac23(x-1) + \tfrac14\cdot2(x+1) = \tfrac12(x-1) + \tfrac12(x+1) = x, 4 3 ⋅ 3 2 ( x − 1 ) + 4 1 ⋅ 2 ( x + 1 ) = 2 1 ( x − 1 ) + 2 1 ( x + 1 ) = x , 故 g g g 無偏。
2 條件方差
相對均值的偏差分別為 2 3 ( x − 1 ) − x = − x + 2 3 \frac23(x-1) - x = -\frac{x+2}{3} 3 2 ( x − 1 ) − x = − 3 x + 2 和 2 ( x + 1 ) − x = x + 2 2(x+1) - x = x+2 2 ( x + 1 ) − x = x + 2 ,故方差為
3 4 ⋅ ( x + 2 ) 2 9 + 1 4 ( x + 2 ) 2 = ( x + 2 ) 2 ( 1 12 + 3 12 ) = ( x + 2 ) 2 3 . \tfrac34\cdot\tfrac{(x+2)^2}{9} + \tfrac14(x+2)^2 = (x+2)^2\Big(\tfrac1{12} + \tfrac3{12}\Big) = \frac{(x+2)^2}{3}. 4 3 ⋅ 9 ( x + 2 ) 2 + 4 1 ( x + 2 ) 2 = ( x + 2 ) 2 ( 12 1 + 12 3 ) = 3 ( x + 2 ) 2 . 作為核對,二階矩為 1 3 ( x − 1 ) 2 + ( x + 1 ) 2 \frac13(x-1)^2 + (x+1)^2 3 1 ( x − 1 ) 2 + ( x + 1 ) 2 ,減去 x 2 x^2 x 2 得 x 2 + 4 x + 4 3 \frac{x^2 + 4x + 4}{3} 3 x 2 + 4 x + 4 。
3 判斷全局假設
在 x = 0 x = 0 x = 0 時方差是 4 3 \frac43 3 4 ,超過均勻抽樣的 1 1 1 。此外,( x + 2 ) 2 3 \frac{(x+2)^2}{3} 3 ( x + 2 ) 2 在 R \mathbb{R} R 上無界,因此沒有有限的 σ 2 \sigma^2 σ 2 能在全空間適用。重新加權恢復了無偏性,但選取不佳的 q q q 可以破壞全局方差界。僅憑這項計算不能排除某一特定迭代序列沿途存在方差界。
看下一步 (2/3) 全部展開
小結
隨機分析依賴兩個條件事實。第一,當前點的無偏性將下降引理的線性項化為 − η ∥ ∇ f ( x k ) ∥ 2 -\eta\lVert\nabla f(x_k)\rVert^2 − η ∥ ∇ f ( x k ) ∥ 2 ;第二,精確恆等式 E [ ∥ g k ∥ 2 ∣ F k ] = ∥ ∇ f ( x k ) ∥ 2 + E [ ∥ g k − ∇ f ( x k ) ∥ 2 ∣ F k ] \mathbb{E}[\lVert g_k\rVert^2\mid\mathcal F_k] = \lVert\nabla f(x_k)\rVert^2 + \mathbb{E}[\lVert g_k-\nabla f(x_k)\rVert^2\mid\mathcal F_k] E [∥ g k ∥ 2 ∣ F k ] = ∥ ∇ f ( x k ) ∥ 2 + E [∥ g k − ∇ f ( x k ) ∥ 2 ∣ F k ] 把雜訊分離出來。接著望遠鏡求和以一個 1 / ( η T ) 1/(\eta T) 1/ ( η T ) 階的項,加上一個固定步長雜訊項 L η σ 2 L\eta\sigma^2 L η σ 2 ,控制平均期望梯度平方範數。
獨立小批次將該雜訊項除以 b b b 。其他抽樣方法如不放回抽樣、重新洗牌或非均勻抽樣,須分別核查無偏性及方差後才可使用定理。