梯度下降

沿着斜坡下行

梯度下降只重复一个动作：逆着梯度走一步， $\mathbf w_{k+1}=\mathbf w_k-\eta\,\nabla f(\mathbf w_k)$ 。数 $\eta>0$ 是步长，常称学习率。 $\eta$ 小则安全但慢； $\eta$ 大则会越过谷底，迭代点可能越跳越远。

f(w)=\tfrac12 a\,w^{2}\ \Rightarrow\ w_{k+1}=(1-\eta a)\,w_k,\qquad |1-\eta a|<1\iff 0<\eta<\frac{2}{a}

(1)

在最简单的碗形函数上，每次更新把 $w$ 乘以 $1-\eta a$ ，所以迭代点趋于零当且仅当 $|1-\eta a|<1$ ，即 $\eta<2/a$ 。取 $\eta=1/a$ 一步就落在极小点上， $1/a$ 到 $2/a$ 之间的 $\eta$ 仍然收敛，但途中会正负交替。超过 $2/a$ 后因子的绝对值大于一，迭代点会发散。

在 f = 3x² 上走三步这里

f'(x)=6x

，所以

a=6

。从

x_0=4

、

\eta=0.1

出发，因子为

1-0.6=0.4

，得到

x_1=1.6

、

x_2=0.64

、

x_3=0.256

。稳定上限是

2/6=0.333

。取

\eta=0.5

时因子为

1-3=-2

，迭代点依次为

4,-4,8,\dots

，每步大小翻倍。

多变量时各方向的曲率不同。Hessian 的最大特征值 $L$ 限制了可用步长（ $\eta<2/L$ ），最小特征值 $\mu$ 决定穿越最平坦方向有多慢。二者之比 $\kappa=L/\mu$ 就是条件数。用最佳固定步长 $\eta=2/(L+\mu)$ 时，误差每步约缩小为原来的 $(\kappa-1)/(\kappa+1)$ ，所以 $\kappa$ 大意味着因子接近一，在狭长山谷里缓慢地锯齿式下行。对 2010 年以来 12 只美国大盘股的协方差矩阵， $\kappa$ 约为 $33$ ：因子是 $0.941$ ，把误差缩小到百分之一约需 76 步。

\eta^{*}=\frac{2}{L+\mu},\qquad \lVert\mathbf w_k-\mathbf w^{*}\rVert\ \lesssim\ \Big(\frac{\kappa-1}{\kappa+1}\Big)^{k}\lVert\mathbf w_0-\mathbf w^{*}\rVert,\qquad \kappa=\frac{L}{\mu}

(2)

安全步长： $\eta<2/L$ ，其中 $L$ 为 Hessian 最大特征值，否则迭代发散。
速度：由条件数 $\kappa=L/\mu$ 决定，越大下降越慢。
停止准则：当 $\lVert\nabla f\rVert$ 低于容差时停止，并设迭代次数上限。

统一变量尺度条件数大往往源于变量尺度悬殊，比如介于 0 和 1 之间的权重旁边放着以基点计的波动率。把各变量缩放到相近大小能降低

\kappa

，可能把几千次迭代变成几十次。预条件处理是同一想法的一般形式。

实验：评分内容

第一步15 分
第二步10 分
最大稳定步长15 分
步长过大15 分
条件数15 分
最佳收缩因子15 分
病态为何慢15 分

沿着斜坡下行

f(w)=\tfrac12 a\,w^{2}\ \Rightarrow\ w_{k+1}=(1-\eta a)\,w_k,\qquad |1-\eta a|<1\iff 0<\eta<\frac{2}{a}

(1)

在 f = 3x² 上走三步这里

f'(x)=6x

，所以

a=6

。从

x_0=4

、

\eta=0.1

出发，因子为

1-0.6=0.4

，得到

x_1=1.6

、

x_2=0.64

、

x_3=0.256

。稳定上限是

2/6=0.333

。取

\eta=0.5

时因子为

1-3=-2

，迭代点依次为

4,-4,8,\dots

，每步大小翻倍。

\eta^{*}=\frac{2}{L+\mu},\qquad \lVert\mathbf w_k-\mathbf w^{*}\rVert\ \lesssim\ \Big(\frac{\kappa-1}{\kappa+1}\Big)^{k}\lVert\mathbf w_0-\mathbf w^{*}\rVert,\qquad \kappa=\frac{L}{\mu}

(2)

安全步长： $\eta<2/L$ ，其中 $L$ 为 Hessian 最大特征值，否则迭代发散。
速度：由条件数 $\kappa=L/\mu$ 决定，越大下降越慢。
停止准则：当 $\lVert\nabla f\rVert$ 低于容差时停止，并设迭代次数上限。

统一变量尺度条件数大往往源于变量尺度悬殊，比如介于 0 和 1 之间的权重旁边放着以基点计的波动率。把各变量缩放到相近大小能降低

\kappa

，可能把几千次迭代变成几十次。预条件处理是同一想法的一般形式。

实验：评分内容

第一步15 分
第二步10 分
最大稳定步长15 分
步长过大15 分
条件数15 分
最佳收缩因子15 分
病态为何慢15 分

沿着斜坡下行

实验：评分内容

登录后即可运行你的代码。

梯度下降

沿着斜坡下行

实验：评分内容

登录后即可运行你的代码。