非凸问题的陷阱与重启

当山谷不止一个时

许多有意思的模型都不是凸的。它们的目标有多个局部极小点、鞍点和平坦高原，梯度下降只会滚进它出发时所在的山谷。以 $f(x)=x^4-3x^2+x$ 为例，其导数 $4x^3-6x+1$ 在 $x=-1.301$、$x=0.170$、$x=1.131$ 处为零。第一个和最后一个是极小点，$f$ 分别为 $-3.514$ 和 $-1.070$，中间的是二者之间的小山丘。从 $x_0=2$ 出发的小步长下降停在 $1.131$，那只是局部极小；从 $x_0=-2$ 出发则停在全局极小 $-1.301$。像 $x_0=0.1$ 与 $x_0=0.2$ 这样隔着 $0.170$ 处山丘、彼此很近的两个起点，也会进入不同的山谷。

鞍点是另一个陷阱。那里梯度为零，但 Hessian 的特征值有正有负，函数在某些方向下降、在另一些方向上升。高维空间中大多数驻点都是鞍点，普通梯度下降在其附近会慢如爬行。动量、小批量的噪声和二阶信息都有助于逃离。大范围内梯度极小的高原看似收敛，其实并不是。

标准对策是重启。从 $K$ 个不同起点运行优化器，保留目标值最低的结果。若每个起点独立地以概率 $p$ 落入全局山谷，则 $K$ 个起点中至少有一个落入的概率是 $1-(1-p)^K$。对 $p=0.2$、$K=10$，这是 $0.893$；要达到 $99\%$ 需要 $K\ge\ln0.01/\ln0.8=20.6$，即 21 个起点。更好的起点也有帮助：凸松弛的解、昨天的校准结果，或对最关键的少数参数做网格搜索。

• 局部极小：下降停在起点所在的山谷，所以起点决定答案。
• 鞍点与高原：梯度为零或极小却不是极小点；动量和噪声有帮助。
• 重启：$K$ 个起点成功的概率为 $1-(1-p)^K$；保留最优目标值。

实验：评分内容

• 全局极小值15 分
• 从 x = 2 出发15 分
• 两个相近的起点15 分
• 随机重启的成功率15 分
• 需要多少次重启15 分
• 鞍点附近10 分
• 比较重启结果15 分