从精确梯度到梯度估计
设 f f f 是下有界的 L L L -光滑函数。梯度下降取步长 0 < η ≤ 1 / L 0<\eta\le 1/L 0 < η ≤ 1/ L 时,每一步都使目标值不增。依据是下降引理:对所有 x , y ∈ R d x,y\in\mathbb R^d x , y ∈ R d ,
f ( y ) ≤ f ( x ) + ⟨ ∇ f ( x ) , y − x ⟩ + L 2 ∥ y − x ∥ 2 . f(y)\le f(x)+\langle\nabla f(x),y-x\rangle+\frac L2\lVert y-x\rVert^2. f ( y ) ≤ f ( x ) + ⟨ ∇ f ( x ) , y − x ⟩ + 2 L ∥ y − x ∥ 2 .
同一 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 L2\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 .
随机性改变了原来的论证:即使真实梯度为零,单步仍可能向上走。这里的保证用期望表述,并计入估计的波动;其他形式的保证需要各自的假设与证明。下文推导这样的保证,也说明它的局限。
基本假设
全文假设:
f : R d → R f:\mathbb R^d\to\mathbb R f : R d → R 可微,且 ∇ f \nabla f ∇ f 全局 L L L -Lipschitz,其中 L > 0 L>0 L > 0 。
存在有限的 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 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\ge0 σ 2 ≥ 0 ,使得 E [ ∥ g k − ∇ f ( x k ) ∥ 2 ∣ F k ] ≤ σ 2 \mathbb E[\lVert g_k-\nabla f(x_k)\rVert^2\mid\mathcal F_k]\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\le2\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 ∥ ,所以梯度也平方可积。以 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 L2\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\frac12\lVert\nabla f(x_k)\rVert^2+\frac12\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 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[\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 ] .
在上述假设下,对每个 k ≥ 0 k\ge0 k ≥ 0 ,几乎处处有
E [ f ( x k + 1 ) ∣ F k ] ≤ f ( x k ) − η 2 ∥ ∇ f ( x k ) ∥ 2 + L η 2 2 σ 2 , \mathbb E[f(x_{k+1})\mid\mathcal F_k]\le f(x_k)-\frac\eta2\lVert\nabla f(x_k)\rVert^2+\frac{L\eta^2}{2}\sigma^2, E [ f ( x k + 1 ) ∣ F k ] ≤ f ( x k ) − 2 η ∥ ∇ f ( x k ) ∥ 2 + 2 L η 2 σ 2 , 因而
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\eta2\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 − η g k y=x_k-\eta g_k y = 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 ( x k ) ∥ 2 \lVert\nabla f(x_k)\rVert^2 ∥ ∇ f ( x k ) ∥ 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\le1/L η ≤ 1/ L 知 1 − L η / 2 ≥ 1 / 2 1-L\eta/2\ge1/2 1 − L η /2 ≥ 1/2 ,得到第一式。再取全期望并应用塔式性质,便得到第二式。
证明透视
条件期望在单步证明中的作用 下降不等式对每个样本结果成立,但其中有两个随机量:⟨ ∇ 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 L\eta^2\sigma^2/2 L η 2 σ 2 /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 . \frac1T\sum_{k=0}^{T-1}\mathbb E\lVert\nabla f(x_k)\rVert^2\le\frac{2(f(x_0)-f_{\inf})}{\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\eta2\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,\ldots,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\eta2\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 ) 。逐点下界给出 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 } \lbrace0,\ldots,T-1\rbrace { 0 , … , T − 1 } 上均匀分布,且与整个运行过程独立,则
E ∥ ∇ f ( x R ) ∥ 2 = ∑ k = 0 T − 1 E [ 1 { R = k } ∥ ∇ f ( x k ) ∥ 2 ] = 1 T ∑ k = 0 T − 1 E ∥ ∇ f ( x k ) ∥ 2 . \mathbb E\lVert\nabla f(x_R)\rVert^2=\sum_{k=0}^{T-1}\mathbb E[\mathbf1_{\lbrace R=k\rbrace}\lVert\nabla f(x_k)\rVert^2]=\frac1T\sum_{k=0}^{T-1}\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 ] = T 1 k = 0 ∑ T − 1 E ∥ ∇ f ( x k ) ∥ 2 .
第二个等号用到了独立性。定理因此恰好控制随机输出的期望梯度平方;由于最小值不超过平均值,也有 min k E ∥ ∇ f ( x k ) ∥ 2 \min\limits_k\mathbb E\lVert\nabla f(x_k)\rVert^2 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 。由 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 (ε > 0 \varepsilon>0 ε > 0 )。
两项的含义。 第一项 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 消失。这是一个上界 ,并非声称误差总至少为该值。σ 2 = 0 \sigma^2=0 σ 2 = 0 时恢复没有噪声项的确定性速率;后面的例子则表明真正有噪声时确实可能出现严格正的极限。
没有得到什么? 这里没有证明迭代点 x k x_k x k 收敛,也没有证明它们趋向全局最小点(对非凸函数一般不成立);没有给出最后迭代点 x T x_T x T 的速率,也没有保证未包含在 f f f 中的数据上的表现。
有限和与小批量
设 f = n − 1 ∑ i = 1 n f i f=n^{-1}\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 } \lbrace1,\ldots,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 出发归纳:梯度的 Lipschitz 性及方差界使抽样梯度平方可积,故下一迭代点也平方可积。因此下面的条件期望有定义。条件于历史时可以固定 x k x_k x k ,只对指标平均:
E [ g k ∣ F k ] = 1 n ∑ i = 1 n ∇ f i ( x k ) = ∇ f ( x k ) , \mathbb E[g_k\mid\mathcal F_k]=\frac1n\sum_{i=1}^n\nabla f_i(x_k)=\nabla f(x_k), E [ g k ∣ F k ] = n 1 i = 1 ∑ n ∇ f i ( x k ) = ∇ f ( x k ) ,
E [ ∥ g k − ∇ f ( x k ) ∥ 2 ∣ F k ] = V ( x k ) . \mathbb E[\lVert g_k-\nabla f(x_k)\rVert^2\mid\mathcal F_k]=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\equiv0 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 EV(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\ge1 b ≥ 1 个指标 I k , 1 , … , I k , b I_{k,1},\ldots,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=\frac1b\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,\ldots,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[\lVert\bar g_k-\nabla f(x_k)\rVert^2\mid\mathcal F_k]=\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]=\frac1{n^2}\sum_{i,m}\langle d_i,d_m\rangle=\Big\lVert\frac1n\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 \sigma^2 σ 2 换成 σ 2 / b \sigma^2/b σ 2 / b ,噪声项变成 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 。单个指标仍均匀,因此估计仍无偏,但交叉项不再为零。给定历史,对均匀选取的不同 i , m i,m i , m ,记 V = V ( x k ) V=V(x_k) V = V ( x k ) ,则
E ⟨ 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{\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 ) ∥ ∑ 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)V/(n-1)=bV(n-b)/(n-1) E ∥ j ∑ e j ∥ 2 = bV − b ( b − 1 ) V / ( n − 1 ) = bV ( n − b ) / ( n − 1 ) ,条件方差为 V b n − b n − 1 \frac Vb\frac{n-b}{n-1} b V 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 Eg=\tfrac34(0-1)+\tfrac14(0+1)=-\tfrac12\ne0=\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 \frac34f_1+\frac14f_2=\frac12x^2-\frac12x+\frac12 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 。可通过重加权修正:令 g = ∇ f I ( x k ) / ( n q I ) g=\nabla f_I(x_k)/(nq_I) g = ∇ f I ( x k ) / ( n q I ) ,其中 q i > 0 q_i>0 q i > 0 、∑ i q i = 1 \sum\limits_iq_i=1 i ∑ q i = 1 ,各 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 g g 可积,即使 q q q 依赖于 x k x_k x k ,仍有 ∑ i q i ∇ f i / ( n q i ) = ∇ f \sum\limits_iq_i\nabla f_i/(nq_i)=\nabla f i ∑ q i ∇ f i / ( n q 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 Ee_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}=1/2 f i n f = 1/2 。均匀单次抽样分别以概率 1 / 2 1/2 1/2 给出 g = x − 1 g=x-1 g = x − 1 或 x + 1 x+1 x + 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=1/2 η = 1/2 ,完整梯度为零,但两种可能的更新是
x 1 = 0 − 1 2 ( 0 ∓ 1 ) = ± 1 2 . x_1=0-\tfrac12(0\mp1)=\pm\tfrac12. x 1 = 0 − 2 1 ( 0 ∓ 1 ) = ± 2 1 . 两种结果都满足 f ( ± 1 / 2 ) = 5 / 8 > 1 / 2 = f ( x 0 ) f(\pm1/2)=5/8>1/2=f(x_0) f ( ± 1/2 ) = 5/8 > 1/2 = f ( x 0 ) ,实际目标值以概率一上升。单步界预测 E f ( x 1 ) ≤ 1 2 + 1 ⋅ ( 1 / 4 ) 2 = 5 / 8 \mathbb Ef(x_1)\le\frac12+\frac{1\cdot(1/4)}2=5/8 E f ( x 1 ) ≤ 2 1 + 2 1 ⋅ ( 1/4 ) = 5/8 ,此处恰为等号:二次函数的曲率正好为 L L L ,下降引理取等;而 1 − L η / 2 1-L\eta/2 1 − L η /2 放宽为 1 / 2 1/2 1/2 所引入的差额乘以了零梯度。
有放回地独立抽取 b b b 个指标时,方差为 1 / b 1/b 1/ b ,期望上升量为 1 / ( 8 b ) 1/(8b) 1/ ( 8 b ) 。
写成 g k = x k + ε k g_k=x_k+\varepsilon_k g k = x k + ε k ,其中 ε k \varepsilon_k ε k 与 F k \mathcal F_k F k 独立,等概率取 ± 1 \pm1 ± 1 。于是
x k + 1 = ( 1 − η ) x k − η ε k , 0 < η ≤ 1. x_{k+1}=(1-\eta)x_k-\eta\varepsilon_k,\qquad0<\eta\le1. x k + 1 = ( 1 − η ) x k − η ε k , 0 < η ≤ 1. 记 a k = E x k 2 a_k=\mathbb Ex_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 Ex_k^2=\frac\eta{2-\eta}[1-(1-\eta)^{2k}]\longrightarrow\frac\eta{2-\eta}>0. E x k 2 = 2 − η η [ 1 − ( 1 − η ) 2 k ] ⟶ 2 − η η > 0. 这里梯度平方就是 x k 2 x_k^2 x k 2 ,故平均值 T − 1 ∑ k < T a k T^{-1}\sum\limits_{k<T}a_k T − 1 k < T ∑ a k 也趋于同一极限。因为 f ( x 0 ) = f inf f(x_0)=f_{\inf} f ( x 0 ) = f i n f ,定理的界是 η \eta η 。取 η = 1 / 2 \eta=1/2 η = 1/2 时真实极限为 1 / 3 1/3 1/3 ,界为 1 / 2 1/2 1/2 ;界高估的倍数为 2 − η ≤ 2 2-\eta\le2 2 − η ≤ 2 。这个正下限确实存在。
此精确递推依赖特殊结构:噪声在所有 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 ) 给出 x − 1 x-1 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 ˉ 取 x − 1 x-1 x − 1 、x + 1 x+1 x + 1 、x x x 的概率依次为 1 / 4 , 1 / 4 , 1 / 2 1/4,1/4,1/2 1/4 , 1/4 , 1/2 。
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 Vb. 4 1 ( 1 ) 2 + 2 1 ( 0 ) 2 + 4 1 ( 1 ) 2 = 2 1 = b V . 3 不同指标
不放回时两个指标必然各出现一次,g ˉ = x \bar g=x g ˉ = x ,方差为零,与 V b n − b n − 1 = 1 2 ⋅ 0 \frac Vb\frac{n-b}{n-1}=\frac12\cdot0 b V n − 1 n − b = 2 1 ⋅ 0 一致。
看下一步 (2/3) 全部展开
练习 3.3.9
(在例子中取 η = 1 / 2 \eta=1/2 η = 1/2 、x 0 = 0 x_0=0 x 0 = 0 ,求 x 2 x_2 x 2 的分布、E x 2 2 \mathbb Ex_2^2 E x 2 2 、E f ( x 2 ) \mathbb Ef(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 的分布
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=-\varepsilon_0/4-\varepsilon_1/2 x 2 = 2 1 x 1 − 2 1 ε 1 = − ε 0 /4 − ε 1 /2 。四种符号组合等概率给出 { ± 3 / 4 , ± 1 / 4 } \lbrace\pm3/4,\pm1/4\rbrace { ± 3/4 , ± 1/4 } 。
2 二阶矩与期望目标值
E x 2 2 = 1 2 ⋅ 9 16 + 1 2 ⋅ 1 16 = 5 16 , \mathbb Ex_2^2=\tfrac12\cdot\tfrac9{16}+\tfrac12\cdot\tfrac1{16}=\tfrac5{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 Ef(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 = 22 32 , \mathbb Ef(x_2)\le\tfrac58-\tfrac14\cdot\tfrac14+\tfrac18=\tfrac{22}{32}, E f ( x 2 ) ≤ 8 5 − 4 1 ⋅ 4 1 + 8 1 = 32 22 , 确有 21 / 32 ≤ 22 / 32 21/32\le22/32 21/32 ≤ 22/32 。
依据: E f ( x 1 ) = 5 8 \mathbb Ef(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 Ex_1^2=\tfrac14 E ∥ ∇ f ( x 1 ) ∥ 2 = E x 1 2 = 4 1 。
4 找出差额的来源
用精确系数 η ( 1 − η / 2 ) = 3 / 8 \eta(1-\eta/2)=3/8 η ( 1 − η /2 ) = 3/8 代替 η / 2 = 1 / 4 \eta/2=1/4 η /2 = 1/4 ,得到 ( 20 − 3 + 4 ) / 32 = 21 / 32 (20-3+4)/32=21/32 ( 20 − 3 + 4 ) /32 = 21/32 。差额 1 / 32 1/32 1/32 恰是把 1 − L η / 2 1-L\eta/2 1 − L η /2 放宽为 1 / 2 1/2 1/2 的松弛量。
看下一步 (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=1/8 η = 1/8 的界;(b) 单指标方差统一不超过 9 9 9 时,使用大小为 9 9 9 的有放回小批量的界;(c) 使该 T T T 下原界最小的步长。)
核心
解答 (3) 1 (a) 计算界
1 / 8 ≤ 1 / 4 = 1 / L 1/8\le1/4=1/L 1/8 ≤ 1/4 = 1/ L ,步长符合要求。界为
2 ⋅ 10 ( 1 / 8 ) ⋅ 1000 + 4 ⋅ 1 8 ⋅ 9 = 0.16 + 4.5 = 4.66. \frac{2\cdot10}{(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 ,期望梯度范数至多 4.66 ≈ 2.159 \sqrt{4.66}\approx2.159 4.66 ≈ 2.159 ;梯度平方至少为 10 10 10 的概率至多 0.466 0.466 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 2\Delta/(\eta T)+L\eta\sigma^2 2Δ/ ( η T ) + L η σ 2 求导并令其为零:
η ∗ = 2 Δ T L σ 2 = 20 36000 = 1 1800 ≈ 0.02357 ≤ 1 4 . \eta^*=\sqrt{\frac{2\Delta}{TL\sigma^2}}=\sqrt{\frac{20}{36000}}=\frac1{\sqrt{1800}}\approx0.02357\le\tfrac14. η ∗ = T L σ 2 2Δ = 36000 20 = 1800 1 ≈ 0.02357 ≤ 4 1 . 此时两项各为 36 η ∗ ≈ 0.8485 36\eta^*\approx0.8485 36 η ∗ ≈ 0.8485 ,总界约为 1.697 1.697 1.697 。这一调参依赖 T T T ,并非收敛性结论。
看下一步 (2/3) 全部展开
练习 3.3.11
(在例子中独立于历史以 q 1 = 3 / 4 q_1=3/4 q 1 = 3/4 、q 2 = 1 / 4 q_2=1/4 q 2 = 1/4 抽样,并取 g = ∇ f I ( x ) / ( 2 q I ) g=\nabla f_I(x)/(2q_I) g = ∇ f I ( x ) / ( 2 q I ) 。证明无偏,计算条件方差,判断定理的方差假设是否在整个 R \mathbb R R 上成立。)
综合
解答 (3) 1 g g g 的两个取值及其均值
I = 1 I=1 I = 1 时 g = 2 3 ( x − 1 ) g=\frac23(x-1) g = 3 2 ( x − 1 ) ;I = 2 I=2 I = 2 时 g = 2 ( x + 1 ) g=2(x+1) g = 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 , 故无偏。
2 条件方差
相对于均值的偏差分别为 − ( x + 2 ) / 3 -(x+2)/3 − ( x + 2 ) /3 和 x + 2 x+2 x + 2 ,方差是
3 4 ⋅ ( x + 2 ) 2 9 + 1 4 ( x + 2 ) 2 = ( x + 2 ) 2 3 . \tfrac34\cdot\frac{(x+2)^2}{9}+\tfrac14(x+2)^2=\frac{(x+2)^2}{3}. 4 3 ⋅ 9 ( x + 2 ) 2 + 4 1 ( x + 2 ) 2 = 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 验算。
3 判断全局假设
在 x = 0 x=0 x = 0 时方差为 4 / 3 4/3 4/3 ,大于均匀抽样的 1 1 1 ;它在 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 。不放回、重新洗牌及非均匀抽样等其他方案,都必须分别检查无偏性和方差后才能应用定理。