重球法 | Codeboy's Blog

在平缓方向，连续几步往往朝同一边移动。重球法把上一位移保留下来，希望减少这种方向上的拖延。代价是算法拥有两份位置状态：即使当前位置相同，不同的上一位置也可能产生完全不同的下一步。

形式陈述

两个状态与一次当前梯度

给定可微目标 $f:\mathbb R^d\to\mathbb R$ 、 $d\ge1$ ，步长 $\alpha>0$ 、动量 $0\le\beta<1$ 、两初始状态 $x_{-1},x_0$ 及容差和预算，重球法迭代

x_{k+1}=x_k-\alpha\nabla f(x_k)+\beta(x_k-x_{k-1}). \tag{1}

它在当前梯度步上加了历史位移。常用 $x_{-1}=x_0$ 表示初始速度为零；也可以明确给定非零初始速度。每轮一次梯度及 $O(d)$ 向量运算，状态空间为 $O(d)$ 。输出当前点、真实梯度、已用查询、两状态初始化与退出原因。

$\beta=0$ 时更新式退化成常步长GD。一般可微目标上，式(1)本身没有全局收敛承诺；下面先给出能完整判定的二次模型。

正定二次模型的稳定域

设

f(x)=\frac12x^\mathsf THx-b^\mathsf Tx+c, \qquad H=H^\mathsf T,\qquad 0<\mu I\preceq H\preceq LI. \tag{2}

式(2)使用正定矩阵的Loewner界，规定同一个二次模型的曲率范围。

最小点为 $x^*=H^{-1}b$ 。对于整个谱区间 $[\mu,L]$ 内的二次模型族，以及任意两初始状态，式(1)收敛当且仅当

0\le\beta<1,\qquad 0<\alpha<\frac{2(1+\beta)}{L}. \tag{3}

这里“当且仅当”针对允许出现特征值 $L$ 的整个模型族。若某个具体矩阵的最大特征值严格小于给定松上界 $L$ ，式(3)仍充分，却不再是该矩阵最宽的允许区间。

当 $0<\mu<L$ 时，令

q=\frac{\sqrt L-\sqrt\mu}{\sqrt L+\sqrt\mu},\qquad \alpha_* =\frac4{(\sqrt L+\sqrt\mu)^2},\qquad \beta_*=q^2. \tag{4}

这组参数使最坏二次模态谱半径达到 $q$ ，并在常数 $\alpha>0$ 、 $0\le\beta<1$ 中最小。谱半径描述渐近指数因子，不承诺每一步误差都小于初始误差乘 $q^k$ 。

直觉

每个特征方向都是二阶递推

对 $H$ 实际使用有限维谱定理，在正交特征坐标里令误差分量为 $z_k$ 、对应特征值为 $\lambda$ 。式(1)化为

z_{k+1}=(1+\beta-\alpha\lambda)z_k-\beta z_{k-1}. \tag{5}

试代 $z_k=r^k$ ，得到特征多项式

p_\lambda(r)=r^2-(1+\beta-\alpha\lambda)r+\beta. \tag{6}

两个不同根给两个指数分量；重根 $r$ 一般给 $(a+bk)r^k$ 。所以两根绝对值都小于1，恰好保证任意初始状态的这个模态趋零。

不跳步的稳定性判断

记 $a=1+\beta-\alpha\lambda$ 。若两根在单位圆内，它们的乘积 $\beta<1$ ，并有

p_\lambda(1)=\alpha\lambda>0, \qquad p_\lambda(-1)=2(1+\beta)-\alpha\lambda>0.

反过来，假设 $0\le\beta<1$ 且这两个值正。非实根共轭，模长为 $\sqrt\beta<1$ 。若根都为实数，一个根越过1而另一个留在1以下会使 $p(1)\le0$ ；两个都至少为1又会使乘积至少为1。负端点同理由 $p(-1)>0$ 排除。因此实根也都在 $(-1,1)$ 。把 $\lambda$ 遍历 $[\mu,L]$ 便得到式(3)。

在上端边界 $\alpha\lambda=2(1+\beta)$ ， $-1$ 已经是一个根，某些初始状态永久交替。根恰在单位圆上不能归入收敛区。

与Nesterov的查询点不同

Nesterov加速梯度先外推 $y_k$ ，再查询 $\nabla f(y_k)$ ；重球在 $x_k$ 查询 $\nabla f(x_k)$ ，之后才加历史位移。即使两者都出现相邻点差，查询位置和误差递推仍不同。Nesterov的特定势函数证明不能因为“都有动量”就搬给式(1)。

例子与边界

谱半径小，前几步仍可上升

取 $H=\operatorname{diag}(1,25)$ 、 $b=0$ 、 $x_{-1}=x_0=(1,1)$ 。式(4)给 $\alpha=1/9$ 、 $\beta=4/9$ 、 $q=2/3$ 。两个端点模态是重根 $2/3$ 与 $-2/3$ 。由 $z_0=1$ 和 $z_1=1-\alpha\lambda$ 求出

x_{k,1}=\left(1+\frac k3\right)\left(\frac23\right)^k, \qquad x_{k,2}=\left(1+\frac{5k}3\right)\left(-\frac23\right)^k. \tag{7}

例如 $x_1=(8/9,-16/9)$ ，所以 $f(x_0)=13$ ，而 $f(x_1)=3232/81>13$ 。第二坐标越过最小点的瞬态很大，随后仍因 $k(2/3)^k\to0$ 而衰减。

正定二次模型的重球目标先升后降；相同参数作用于分段强凸目标时出现精确三周期 — 重球瞬态与非二次三周期

图左使用式(7)的真实目标值；图右使用下一例指定的两初始状态。它们采用同一组 $\alpha,\beta,\mu,L$ ，但第二个目标没有固定Hessian，不能沿用左侧的独立模态递推。

强凸光滑也不能无条件沿用二次最优参数

定义连续可微函数

f(x)= \begin{cases} 25x^2/2,&x<1,\\ x^2/2+24x-12,&1\le x<2,\\ 25x^2/2-24x+36,&x\ge2. \end{cases} \tag{8}

两处分界的函数值和导数都相接。导数分别是 $25x,x+24,25x-24$ ；对任意 $x<y$ ，逐段积分其斜率给

y-x\le f'(y)-f'(x)\le25(y-x).

故 $f$ 为1-强凸、梯度为25-Lipschitz，唯一最小点仍为0。使用与上例相同的 $\alpha=1/9,\beta=4/9$ ，设

p=\frac{792}{1225},\qquad q_0=-\frac{2208}{1225},\qquad r_0=\frac{2592}{1225}. \tag{9}

这里 $p<1,q_0<1,r_0>2$ 。以 $x_{-1}=r_0,x_0=p$ 启动，直接代入式(1)给 $x_1=q_0,x_2=r_0,x_3=p$ ，之后周期重复。例如第一步为

\frac{13}9p-\frac49r_0-\frac{25}9p =-\frac43p-\frac49r_0=q_0.

另外两步同样精确成立。这份反例使用非零初始速度，足以否定“所有初始状态都在强凸光滑类上收敛”的无条件断言。它没有证明任何给定的零初速度启动都会失败。三个循环点都不是最小点，有限容差也不能把这条周期轨迹解释成收敛。

推论与应用

二次最优参数的证明

式(4)代入后， $1+\beta_*-\alpha_*\lambda$ 从 $2q$ 线性变到 $-2q$ 。因此式(6)的两根要么是端点重根 $\pm q$ ，要么是模长 $q$ 的共轭根，最坏谱半径至多 $q$ 。

再证没有另一组常参数能把整个区间的谱半径降得更小。设所有根的模长至多 $\rho<1$ 。因 $\mu<L$ ，必有 $\rho>0$ ，且乘积给 $0\le\beta\le\rho^2$ 。在实点 $\pm\rho$ 处，多项式非负：实根时是两个同号因子的乘积，复根时是模平方。分别对 $\lambda=\mu,L$ 使用，得到

\alpha\mu\ge(1-\rho)(1-\beta/\rho),\qquad \alpha L\le(1+\rho)(1+\beta/\rho).

所有分母为正，所以

\frac L\mu \le\frac{(1+\rho)(1+\beta/\rho)}{(1-\rho)(1-\beta/\rho)} \le\left(\frac{1+\rho}{1-\rho}\right)^2.

整理得 $\rho\ge q$ ，完成最优性证明。若候选参数本就不稳定、谱半径至少1，更不可能优于 $q$ 。若 $\mu=L$ ， $H=\mu I$ ，取 $\beta=0,\alpha=1/\mu$ 一次到解，单独处理即可。

怎样报告可用精度

对式(2)，真实梯度 $g=H(x-x^*)$ 给

f(x)-f^*=\frac12g^\mathsf TH^{-1}g\le\frac{\|g\|^2}{2\mu}.

这份误差证书由目标几何保证，与候选是重球、GD还是手工产生无关。对式(7)，还可直接计算完整目标表达式

f(x_k)=\frac12\left[\left(1+\frac k3\right)^2+25\left(1+\frac{5k}3\right)^2\right]\left(\frac49\right)^k.

首次达到 $1/100$ 在 $k=18$ ；只取 $q^{2k}f(x_0)$ 会漏掉重根多项式因子，产生过早的认证。常参数调优解决的是特定二次族的渐近最坏因子，不能替代真实残差检查、启动状态或模型类别。

参考资料

Laurent Lessard、Benjamin Recht、Andrew Packard，Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints，SIAM Journal on Optimization26(1),2016,57–95；作者2017-10-16更正版，§2.2 Proposition1、§4.6式(4.11)、AppendixB，PDF pp.5–6、23–24、39–40。式(8)–(9)按其反例写出并精确核验；本文不用数值IQC求解器替代稳定性证明。

形式陈述 ​

两个状态与一次当前梯度 ​

正定二次模型的稳定域 ​

每个特征方向都是二阶递推 ​

不跳步的稳定性判断 ​

与Nesterov的查询点不同 ​

谱半径小，前几步仍可上升 ​

强凸光滑也不能无条件沿用二次最优参数 ​

二次最优参数的证明 ​

怎样报告可用精度 ​

反向链接