动机
最小二乘将数据拟合转化为优化问题。正规方程直接描述最优参数，梯度下降则从一个初始估计出发，通过反复更新接近答案。这两种观点相互配合：方程指出目标位置，迭代说明每一步如何改变当前的误差。
二次目标函数的梯度是参数的仿射函数，曲率在各点相同，而特征向量能把更新分成彼此独立的一维递推。因此，我们可以精确算出哪些步长使误差缩小、哪些使误差交替变号，以及哪些会使迭代发散。这也解释了为什么将损失乘以常数，虽然不会改变拟合结果，却会改变合适的学习率。
本节将参数向量和梯度都写成列向量。“最陡”相对于欧几里得长度而言，背后仍然是投影和主成分分析中的内积几何。我们会直接使用实对称矩阵的谱分解，重点考察特征值怎样控制更新，而不是重新介绍计算特征向量的算法。
定义
定义
二次目标函数与梯度 对参数向量 θ ∈ R d \theta\in\mathbb R^d θ ∈ R d
f ( θ ) = 1 2 θ ⊤ Q θ − b ⊤ θ + c , Q = Q ⊤ . f(\theta)=\frac12\theta^\top Q\theta-b^\top\theta+c,
\qquad Q=Q^\top. f ( θ ) = 2 1 θ ⊤ Qθ − b ⊤ θ + c , Q = Q ⊤ . 其中 Q Q Q d × d d\times d d × d b ∈ R d b\in\mathbb R^d b ∈ R d c c c
∇ f ( θ ) = Q θ − b , ∇ 2 f ( θ ) = Q . \nabla f(\theta)=Q\theta-b,\qquad \nabla^2 f(\theta)=Q. ∇ f ( θ ) = Qθ − b , ∇ 2 f ( θ ) = Q . 若每个非零向量 z z z z ⊤ Q z > 0 z^\top Qz>0 z ⊤ Q z > 0 Q Q Q μ = λ min ( Q ) \mu=\lambda_{\min}(Q) μ = λ m i n ( Q ) L = λ max ( Q ) L=\lambda_{\max}(Q) L = λ m a x ( Q )
将 θ \theta θ θ + h \theta+h θ + h Q Q Q h h h h ⊤ ( Q θ − b ) h^\top(Q\theta-b) h ⊤ ( Qθ − b ) h ⊤ Q h / 2 h^\top Qh/2 h ⊤ Q h /2 1 / 2 1/2 1/2 2 2 2
定义
固定步长的梯度下降 选定初始参数 θ 0 \theta_0 θ 0 η > 0 \eta>0 η > 0
θ k + 1 = θ k − η ∇ f ( θ k ) = θ k − η ( Q θ k − b ) , k = 0 , 1 , 2 , … . \theta_{k+1}=\theta_k-\eta\nabla f(\theta_k)
=\theta_k-\eta(Q\theta_k-b),
\qquad k=0,1,2,\ldots. θ k + 1 = θ k − η ∇ f ( θ k ) = θ k − η ( Q θ k − b ) , k = 0 , 1 , 2 , … . 每一步先在当前向量 θ k \theta_k θ k
令 g = ∇ f ( θ ) g=\nabla f(\theta) g = ∇ f ( θ ) v v v g ⊤ v g^\top v g ⊤ v − ∥ g ∥ 2 -\|g\|_2 − ∥ g ∥ 2 g ≠ 0 g\ne0 g = 0 v = − g / ∥ g ∥ 2 v=-g/\|g\|_2 v = − g /∥ g ∥ 2 − g -g − g η ∥ g ∥ 2 \eta\|g\|_2 η ∥ g ∥ 2
定理/命题
定理
唯一最小点与精确的目标差距 若 Q Q Q f f f
θ ⋆ = Q − 1 b . \theta_\star=Q^{-1}b. θ ⋆ = Q − 1 b . 设 e = θ − θ ⋆ e=\theta-\theta_\star e = θ − θ ⋆
f ( θ ) − f ( θ ⋆ ) = 1 2 e ⊤ Q e , μ 2 ∥ e ∥ 2 2 ≤ f ( θ ) − f ( θ ⋆ ) ≤ L 2 ∥ e ∥ 2 2 . f(\theta)-f(\theta_\star)=\frac12e^\top Qe,
\qquad
\frac{\mu}{2}\|e\|_2^2
\le f(\theta)-f(\theta_\star)
\le\frac{L}{2}\|e\|_2^2. f ( θ ) − f ( θ ⋆ ) = 2 1 e ⊤ Q e , 2 μ ∥ e ∥ 2 2 ≤ f ( θ ) − f ( θ ⋆ ) ≤ 2 L ∥ e ∥ 2 2 . 常数 c c c b b b Q Q Q
定理
固定步长收敛的精确条件 设 Q Q Q e k = θ k − θ ⋆ e_k=\theta_k-\theta_\star e k = θ k − θ ⋆ η \eta η
e k + 1 = ( I − η Q ) e k . e_{k+1}=(I-\eta Q)e_k. e k + 1 = ( I − η Q ) e k . 对每个初始向量都收敛到 θ ⋆ \theta_\star θ ⋆
0 < η < 2 L . 0<\eta<\frac2L. 0 < η < L 2 . 在此范围内，记
ρ = max i ∣ 1 − η λ i ( Q ) ∣ < 1. \rho=\max_i|1-\eta\lambda_i(Q)|<1. ρ = i max ∣1 − η λ i ( Q ) ∣ < 1. 则 ∥ e k ∥ 2 ≤ ρ k ∥ e 0 ∥ 2 \|e_k\|_2\le\rho^k\|e_0\|_2 ∥ e k ∥ 2 ≤ ρ k ∥ e 0 ∥ 2 f ( θ k ) − f ( θ ⋆ ) ≤ ρ 2 k ( f ( θ 0 ) − f ( θ ⋆ ) ) f(\theta_k)-f(\theta_\star)\le
\rho^{2k}\bigl(f(\theta_0)-f(\theta_\star)\bigr) f ( θ k ) − f ( θ ⋆ ) ≤ ρ 2 k ( f ( θ 0 ) − f ( θ ⋆ ) )
“每个初始向量”是条件的一部分。如果某次初始误差在不稳定的特征向量方向恰好为零，那次计算仍可能成功。定理中的步长范围同时控制所有可能出现的误差方向，不能根据一次成功的数值结果扩大它。
证明思路
先展开 f ( θ ⋆ + e ) f(\theta_\star+e) f ( θ ⋆ + e ) Q θ ⋆ = b Q\theta_\star=b Q θ ⋆ = b e e e e ⊤ Q e / 2 e^\top Qe/2 e ⊤ Q e /2 Q = V Λ V ⊤ Q=V\Lambda V^\top Q = V Λ V ⊤ V V V z = V ⊤ e z=V^\top e z = V ⊤ e e ⊤ Q e = ∑ i λ i z i 2 e^\top Qe=\sum_i\lambda_i z_i^2 e ⊤ Q e = ∑ i λ i z i 2 μ \mu μ L L L
接着从更新式中减去驻点方程：
e k + 1 = θ k − η ( Q θ k − b ) − θ ⋆ = e k − η Q e k . \begin{aligned}
e_{k+1}
&=\theta_k-\eta(Q\theta_k-b)-\theta_\star\\
&=e_k-\eta Qe_k.
\end{aligned} e k + 1 = θ k − η ( Q θ k − b ) − θ ⋆ = e k − η Q e k . 转到特征向量坐标 z k = V ⊤ e k z_k=V^\top e_k z k = V ⊤ e k
z k + 1 , i = ( 1 − η λ i ) z k , i , z k , i = ( 1 − η λ i ) k z 0 , i . z_{k+1,i}=(1-\eta\lambda_i)z_{k,i},
\qquad
z_{k,i}=(1-\eta\lambda_i)^kz_{0,i}. z k + 1 , i = ( 1 − η λ i ) z k , i , z k , i = ( 1 − η λ i ) k z 0 , i . 每个坐标都是等比数列。让任意初始值都趋于零的充要条件为 ∣ 1 − η λ i ∣ < 1 |1-\eta\lambda_i|<1 ∣1 − η λ i ∣ < 1 0 < η λ i < 2 0<\eta\lambda_i<2 0 < η λ i < 2 0 < η < 2 / L 0<\eta<2/L 0 < η < 2/ L λ i / 2 \lambda_i/2 λ i /2
当 η = 2 / L \eta=2/L η = 2/ L − 1 -1 − 1 η > 2 / L \eta>2/L η > 2/ L η = 0 \eta=0 η = 0
曲率、进度与条件数
还可以直接计算一步之后的目标变化。令 g = ∇ f ( θ ) g=\nabla f(\theta) g = ∇ f ( θ )
f ( θ − η g ) − f ( θ ) = − η ∥ g ∥ 2 2 + η 2 2 g ⊤ Q g ≤ − η ( 1 − η L 2 ) ∥ g ∥ 2 2 . f(\theta-\eta g)-f(\theta)
=-\eta\|g\|_2^2+\frac{\eta^2}{2}g^\top Qg
\le-\eta\left(1-\frac{\eta L}{2}\right)\|g\|_2^2. f ( θ − η g ) − f ( θ ) = − η ∥ g ∥ 2 2 + 2 η 2 g ⊤ Q g ≤ − η ( 1 − 2 η L ) ∥ g ∥ 2 2 . 所以在 0 < η < 2 / L 0<\eta<2/L 0 < η < 2/ L η = 1 / L \eta=1/L η = 1/ L 0 0 0 1 − μ / L 1-\mu/L 1 − μ / L μ \mu μ L L L
正定二次函数的条件数为 κ = L / μ \kappa=L/\mu κ = L / μ 1 − η μ = − ( 1 − η L ) 1-\eta\mu=-(1-\eta L) 1 − η μ = − ( 1 − η L ) η = 2 / ( μ + L ) \eta=2/(\mu+L) η = 2/ ( μ + L ) ρ = ( κ − 1 ) / ( κ + 1 ) \rho=(\kappa-1)/(\kappa+1) ρ = ( κ − 1 ) / ( κ + 1 )
收缩因子描述反复更新的进度。若 ρ = 3 / 4 \rho=3/4 ρ = 3/4 ( 3 / 4 ) 10 (3/4)^{10} ( 3/4 ) 10 ( 3 / 4 ) 20 (3/4)^{20} ( 3/4 ) 20
在狭长的二次曲面谷地中，离开陡峭侧面可以迅速消除大部分初始损失。之后，剩余误差主要沿平坦方向，进度看起来就会放慢。每一步仍然遵守同一个固定递推；发生变化的是误差中各方向分量的比例，而不是算法突然改变。
例题
例题
1. 一维误差的缩小、交替与发散 设 f ( t ) = 2 ( t − 3 ) 2 f(t)=2(t-3)^2 f ( t ) = 2 ( t − 3 ) 2 4 ( t − 3 ) 4(t-3) 4 ( t − 3 ) t ⋆ = 3 t_\star=3 t ⋆ = 3 L = 4 L=4 L = 4 0 < η < 1 / 2 0<\eta<1/2 0 < η < 1/2
从 t 0 = − 1 t_0=-1 t 0 = − 1 η = 1 / 8 \eta=1/8 η = 1/8 1 − 4 η = 1 / 2 1-4\eta=1/2 1 − 4 η = 1/2
t 0 = − 1 , t 1 = 1 , t 2 = 2 , t 3 = 5 2 . t_0=-1,\quad t_1=1,\quad t_2=2,\quad t_3=\frac52. t 0 = − 1 , t 1 = 1 , t 2 = 2 , t 3 = 2 5 . 损失依次是 32 32 32 8 8 8 2 2 2 1 / 2 1/2 1/2
改取 η = 1 / 2 \eta=1/2 η = 1/2 − 1 -1 − 1 − 1 -1 − 1 7 7 7 32 32 32 η = 3 / 4 \eta=3/4 η = 3/4 − 2 -2 − 2 − 1 -1 − 1 11 11 11 − 13 -13 − 13 32 32 32 128 128 128 512 512 512
例题
2. 两个特征向量方向具有不同的进度 考虑
f ( u , v ) = 1 2 ( ( u − 1 ) 2 + 4 ( v + 1 ) 2 ) . f(u,v)=\frac12\bigl((u-1)^2+4(v+1)^2\bigr). f ( u , v ) = 2 1 ( ( u − 1 ) 2 + 4 ( v + 1 ) 2 ) . 此时 Q = diag ( 1 , 4 ) Q=\operatorname{diag}(1,4) Q = diag ( 1 , 4 ) θ ⋆ = ( 1 , − 1 ) ⊤ \theta_\star=(1,-1)^\top θ ⋆ = ( 1 , − 1 ) ⊤ η = 1 / 4 \eta=1/4 η = 1/4 3 / 4 3/4 3/4 0 0 0 ( u 0 , v 0 ) = ( 3 , 1 ) (u_0,v_0)=(3,1) ( u 0 , v 0 ) = ( 3 , 1 )
( u 1 , v 1 ) = ( 5 2 , − 1 ) , ( u 2 , v 2 ) = ( 17 8 , − 1 ) . (u_1,v_1)=\left(\frac52,-1\right),\qquad
(u_2,v_2)=\left(\frac{17}{8},-1\right). ( u 1 , v 1 ) = ( 2 5 , − 1 ) , ( u 2 , v 2 ) = ( 8 17 , − 1 ) . 第二坐标一步到达最优值，第一坐标则以等比方式逐渐接近 1 1 1 f 0 = 10 f_0=10 f 0 = 10 f 1 = 9 / 8 f_1=9/8 f 1 = 9/8 f 2 = 81 / 128 f_2=81/128 f 2 = 81/128 η = 2 / 5 \eta=2/5 η = 2/5 3 / 5 3/5 3/5 − 3 / 5 -3/5 − 3/5
下面的 Python 程序先计算两个梯度分量，再同时更新参数。将输出与上述精确分数对照，可以逐步检查坐标递推。
u, v = 3.0, 1.0
eta = 0.25
for k in range(4):
loss = 0.5 * ((u - 1.0) ** 2 + 4.0 * (v + 1.0) ** 2)
print(f"{k}: ({u:.6f}, {v:.6f}) f={loss:.6f}")
grad_u, grad_v = u - 1.0, 4.0 * (v + 1.0)
u, v = u - eta * grad_u, v - eta * grad_v
输出为
0: (3.000000, 1.000000) f=10.000000
1: (2.500000, -1.000000) f=1.125000
2: (2.125000, -1.000000) f=0.632812
3: (1.843750, -1.000000) f=0.355957
例题
3. 梯度下降与回归方程得到相同拟合 取三条观测数据：
A = [ 1 − 1 1 0 1 1 ] , y = [ 0 1 3 ] , f ( θ ) = 1 2 n ∥ A θ − y ∥ 2 2 , n = 3. A=\begin{bmatrix}1&-1\\1&0\\1&1\end{bmatrix},
\qquad y=\begin{bmatrix}0\\1\\3\end{bmatrix},
\qquad f(\theta)=\frac{1}{2n}\|A\theta-y\|_2^2,\quad n=3. A = 1 1 1 − 1 0 1 , y = 0 1 3 , f ( θ ) = 2 n 1 ∥ A θ − y ∥ 2 2 , n = 3. 第一个参数是截距，第二个是斜率。展开得到 Q = A ⊤ A / n = diag ( 1 , 2 / 3 ) Q=A^\top A/n=\operatorname{diag}(1,2/3) Q = A ⊤ A / n = diag ( 1 , 2/3 ) b = A ⊤ y / n = ( 4 / 3 , 1 ) ⊤ b=A^\top y/n=(4/3,1)^\top b = A ⊤ y / n = ( 4/3 , 1 ) ⊤ θ ⋆ = ( 4 / 3 , 3 / 2 ) ⊤ \theta_\star=(4/3,3/2)^\top θ ⋆ = ( 4/3 , 3/2 ) ⊤ A A A Q Q Q L = 1 L=1 L = 1
从 θ 0 = ( 0 , 0 ) ⊤ \theta_0=(0,0)^\top θ 0 = ( 0 , 0 ) ⊤ η = 1 \eta=1 η = 1 − b -b − b θ 1 = ( 4 / 3 , 1 ) ⊤ \theta_1=(4/3,1)^\top θ 1 = ( 4/3 , 1 ) ⊤ A θ 1 − y = ( 1 / 3 , 1 / 3 , − 2 / 3 ) ⊤ A\theta_1-y=(1/3,1/3,-2/3)^\top A θ 1 − y = ( 1/3 , 1/3 , − 2/3 ) ⊤ f ( θ 1 ) = 1 / 9 f(\theta_1)=1/9 f ( θ 1 ) = 1/9 θ 2 = ( 4 / 3 , 4 / 3 ) ⊤ \theta_2=(4/3,4/3)^\top θ 2 = ( 4/3 , 4/3 ) ⊤ f ( θ 2 ) = 1 / 27 f(\theta_2)=1/27 f ( θ 2 ) = 1/27
在最小点，残差为 ( − 1 / 6 , 1 / 3 , − 1 / 6 ) ⊤ (-1/6,1/3,-1/6)^\top ( − 1/6 , 1/3 , − 1/6 ) ⊤ 1 / 36 1/36 1/36 1 / 3 1/3 1/3
对于一般设计矩阵 A ∈ R n × d A\in\mathbb R^{n\times d} A ∈ R n × d
∇ f ( θ ) = 1 n A ⊤ ( A θ − y ) , Q = 1 n A ⊤ A . \nabla f(\theta)=\frac1nA^\top(A\theta-y),\qquad
Q=\frac1nA^\top A. ∇ f ( θ ) = n 1 A ⊤ ( A θ − y ) , Q = n 1 A ⊤ A . 满列秩恰好是 Q Q Q z ⊤ Q z = ∥ A z ∥ 2 2 / n z^\top Qz=\|Az\|_2^2/n z ⊤ Q z = ∥ A z ∥ 2 2 / n z z z A A A L = σ max ( A ) 2 / n L=\sigma_{\max}(A)^2/n L = σ m a x ( A ) 2 / n A ⊤ A^\top A ⊤ n n n
这里观测索引与参数索引有不同的作用：预测和残差各有一个分量对应每条观测，梯度则每个分量对应一个参数。乘以 A ⊤ A^\top A ⊤ 1 1 1
所以，迭代收敛时残差未必趋于零。残差可以保留一个垂直于 A A A
实现时分别计算 A θ A\theta A θ A ⊤ r A^\top r A ⊤ r A ⊤ A A^\top A A ⊤ A A A A
损失尺度与停止条件
将 f f f F = α f F=\alpha f F = α f α > 0 \alpha>0 α > 0 α \alpha α α \alpha α F = 2 n f = 6 f F=2nf=6f F = 2 n f = 6 f 6 6 6 0 < η < 1 / 3 0<\eta<1/3 0 < η < 1/3 1 / 6 1/6 1/6 1 1 1
梯度长度 ∥ ∇ f ( θ k ) ∥ 2 \|\nabla f(\theta_k)\|_2 ∥∇ f ( θ k ) ∥ 2 ∇ f = Q e k \nabla f=Qe_k ∇ f = Q e k μ \mu μ ∥ e k ∥ 2 ≤ ∥ ∇ f ( θ k ) ∥ 2 / μ \|e_k\|_2\le\|\nabla f(\theta_k)\|_2/\mu ∥ e k ∥ 2 ≤ ∥∇ f ( θ k ) ∥ 2 / μ η \eta η
常见错误
常见错误
将负梯度方向当作任意长步都会下降 负梯度在非驻点给出局部下降方向，有限长度的步还受曲率影响。二次函数中的每个误差分量由 1 − η λ i 1-\eta\lambda_i 1 − η λ i
常见错误
改变损失尺度后沿用原来的学习率 ∥ A θ − y ∥ 2 2 \|A\theta-y\|_2^2 ∥ A θ − y ∥ 2 2 ∥ A θ − y ∥ 2 2 / ( 2 n ) \|A\theta-y\|_2^2/(2n) ∥ A θ − y ∥ 2 2 / ( 2 n ) 2 n 2n 2 n
总结
正定二次函数的驻点方程给出唯一最小点。从更新式减去驻点方程，可以得到误差的精确线性递推。在特征向量坐标中，每个误差分量乘以 1 − η λ i 1-\eta\lambda_i 1 − η λ i 0 < η < 2 / L 0<\eta<2/L 0 < η < 2/ L
练习
思考检查
1. 设 Q = diag ( 2 , 5 ) Q=\operatorname{diag}(2,5) Q = diag ( 2 , 5 ) b = ( 4 , − 5 ) ⊤ b=(4,-5)^\top b = ( 4 , − 5 ) ⊤ θ 0 = ( 0 , 1 ) ⊤ \theta_0=(0,1)^\top θ 0 = ( 0 , 1 ) ⊤ η = 1 / 5 \eta=1/5 η = 1/5 思考检查
2. 设 f ( t ) = 3 ( t + 2 ) 2 f(t)=3(t+2)^2 f ( t ) = 3 ( t + 2 ) 2 t 0 = 0 t_0=0 t 0 = 0 η = 1 / 3 \eta=1/3 η = 1/3 η = 1 / 4 \eta=1/4 η = 1/4 思考检查
3. 在回归例题中，将 f f f F = 6 f F=6f F = 6 f f f f η = 1 \eta=1 η = 1 F F F 同时追踪梯度的倍率与 Hessian 的最大特征值。
思考检查
4. 设 f ( θ ) = ( θ 1 − 1 ) 2 / 2 f(\theta)=(\theta_1-1)^2/2 f ( θ ) = ( θ 1 − 1 ) 2 /2 θ 0 = ( 0 , 7 ) ⊤ \theta_0=(0,7)^\top θ 0 = ( 0 , 7 ) ⊤ η = 1 \eta=1 η = 1 解答
解答 · 1. 解驻点方程，再使用两个误差乘数 最小点为 θ ⋆ = ( 2 , − 1 ) ⊤ \theta_\star=(2,-1)^\top θ ⋆ = ( 2 , − 1 ) ⊤ L = 5 L=5 L = 5 0 < η < 2 / 5 0<\eta<2/5 0 < η < 2/5 ( − 4 , 10 ) ⊤ (-4,10)^\top ( − 4 , 10 ) ⊤ θ 1 = ( 0 , 1 ) ⊤ − 1 5 ( − 4 , 10 ) ⊤ = ( 4 / 5 , − 1 ) ⊤ \theta_1=(0,1)^\top-\frac15(-4,10)^\top=(4/5,-1)^\top θ 1 = ( 0 , 1 ) ⊤ − 5 1 ( − 4 , 10 ) ⊤ = ( 4/5 , − 1 ) ⊤ 3 / 5 3/5 3/5 0 0 0
解答 · 2. 区分边界交替与逐渐缩小的交替 导数为 6 ( t + 2 ) 6(t+2) 6 ( t + 2 ) 1 − 6 η 1-6\eta 1 − 6 η η = 1 / 3 \eta=1/3 η = 1/3 − 1 -1 − 1 t 1 = − 4 t_1=-4 t 1 = − 4 t 2 = 0 t_2=0 t 2 = 0 η = 1 / 4 \eta=1/4 η = 1/4 − 1 / 2 -1/2 − 1/2 t 1 = − 3 t_1=-3 t 1 = − 3 t 2 = − 3 / 2 t_2=-3/2 t 2 = − 3/2 − 2 -2 − 2 0 < η < 1 / 3 0<\eta<1/3 0 < η < 1/3
解答 · 3. 学习率与目标倍率成反比 由于 ∇ F = 6 ∇ f \nabla F=6\nabla f ∇ F = 6∇ f η F = 1 / 6 \eta_F=1/6 η F = 1/6 L F = 6 L_F=6 L F = 6 0 < η F < 2 / 6 = 1 / 3 0<\eta_F<2/6=1/3 0 < η F < 2/6 = 1/3
解答 · 4. 平坦方向保留初始坐标 梯度为 ( θ 1 − 1 , 0 ) ⊤ (\theta_1-1,0)^\top ( θ 1 − 1 , 0 ) ⊤ ( 1 , 7 ) ⊤ (1,7)^\top ( 1 , 7 ) ⊤ ( 1 , s ) ⊤ (1,s)^\top ( 1 , s ) ⊤ s ∈ R s\in\mathbb R s ∈ R diag ( 1 , 0 ) \operatorname{diag}(1,0) diag ( 1 , 0 )
可以继续阅读最小二乘与残差 、
SVD 与主成分 ，
或查看课程阅读书目 。
