【机器学习】关于外插修正随机梯度方法的数值实验

1. 随机梯度下降（SGD）

迭代格式：
$x_{k+1} = x_k - \eta_k \nabla f_i(x_k)$
其中， $\eta_k$ 为步长（可能递减）， $\nabla f_i(x_k)$ 是随机采样样本 $i$ 的梯度估计。
优点：
计算效率高，适合大规模数据集，每次迭代仅需单个样本的梯度。
在强凸问题中收敛速度为 $O (1/ t)$ ，非凸问题中为 $O(1/\log t)$ 。
理论分析成熟，易于实现。
缺点：
收敛速度较慢，尤其在非凸问题中易陷入局部最优。
对步长敏感，需要精心调整参数以保证稳定性。

2. 重球随机梯度方法（SHB）

迭代格式：
$x_{k+1} = x_k - \eta_k \nabla f_i(x_k) + \beta (x_k - x_{k-1})$
其中， $\beta \in (0,1)$ 为动量参数，通过历史更新方向加速收敛。
优点：
动量项可加速收敛，尤其在光滑强凸问题中表现优于固定步长的SGD 。
对梯度噪声具有一定鲁棒性，通过历史梯度平均降低方差。

缺点：
早期迭代可能表现不佳，收敛速度不一定始终优于SGD 。
参数选择（如 $\beta$ 和 $\eta_k$ ）需谨慎，否则可能导致震荡或发散。
在有限和随机设置中，缺乏严格的加速收敛证明。

3. Nesterov随机梯度方法（SNAG）

迭代格式：
$y_k = x_k + \gamma_k (x_k - x_{k-1}) \\ x_{k+1} = y_k - \eta_k \nabla f_i(y_k)$
其中， $\gamma_k$ 为动量系数，通常在Nesterov方法中设计为时变参数。
优点：
在凸问题中理论收敛速度可达 $O(1/t^2)$ ，显著快于SGD 。
通过“前瞻梯度”设计，减少震荡并提高稳定性。
实验显示在分类和图像任务中优于传统动量方法。

缺点：
随机环境下（如有限和设置）可能发散，需额外条件保证收敛。
实现复杂度较高，需同时维护多个变量（如 $x_k$ 和 $y_k$ ）。

参数调节更复杂，尤其在非凸问题中收敛性理论尚不完善。

以上段落来自秘塔 AI 综述的结果（先搜索后扩展选项，文献均来自中英文论文而非全网）。该完整版请移步至链接

https://metaso.cn/s/ThPU2bK

以下我们给出一组实验来探讨 Nesterov 加速方法的参数选择，收敛效果请大家自行验证，这里放上一个数值结果图作为代表
在这里插入图片描述

其中一点比较尴尬的现象是确定问题中 $\theta_k=\frac{k-1}{k+2}$ 类型的外插参数在随机问题中的数值实验中的表现并不好，有一子列不收敛到0，但是仍有大量文献包括教材，论文仍然推荐使用这类策略。但是换成任何一个介于开区间 $(0, 1)$ 的常数，例如 0.9, 0.99 则有明显的序列收敛至0的趋势，从本文给的算例来看是非常简单的凸二次 $x_0^2+x_1^2+2\xi_0 x_0+2\xi_1x_0$ ，其中 $\xi_i$ 服从 $N (0, I)$ 二维标准正态分布。为了压缩噪声影响，采用递减步长 $\alpha_k=\frac{1}{(k+2)^\gamma}$ 。

规模小：仅2维问题
强凸
可微，且随机梯度关于自变量 $x$ 是李普希兹连续的
随机样本噪声期望存在，方差有界

很难相信这样二维简单的例子参数 $\theta_k=\frac{k-1}{k+2}$ 都不收敛，其在大规模以及大数据问题中会具有较好的收敛效果，欢迎大家参与实验与讨论。

Python 代码如下：

import numpy as np
import matplotlib.pyplot as plt
import numpy.linalg as la
iters=1000000
root=np.array([1.0,3.0])
vec1=root.copy()
vec2=root.copy()
dim=len(root)
path=np.zeros([iters,dim])
def gobj(x,xi):return(2*(x+xi))
gamma=1#  (k-1)/(k+2)  ===============================
np.random.seed(0)
for k in range(iters):    theta= (k-1)/(k+2)root=(1.0+theta)*vec2-theta*vec1a=1/(k+1)**gammaxi=np.random.randn(2)vec1=vec2.copy()vec2=root - a*gobj(root,xi)path[k,:]=root
V=np.zeros(iters)
for k in range(iters):V[k]=la.norm(path[k,:])
plt.loglog(V,'-.')
plt.grid(True)# 0.99    ===============================
iters=1000000
root=np.array([1.0,3.0])
vec1=root.copy()
vec2=root.copy()
dim=len(root)
path=np.zeros([iters,dim])
np.random.seed(0)
for k in range(iters):    theta= 0.99root=(1.0+theta)*vec2-theta*vec1a=1/(k+1)**gammaxi=np.random.randn(2)vec1=vec2.copy()vec2=root - a*gobj(root,xi)path[k,:]=root
V=np.zeros(iters)
for k in range(iters):V[k]=la.norm(path[k,:])
plt.loglog(V,'--')
plt.grid(True)# 0.9  ===============================
iters=1000000
root=np.array([1.0,3.0])
vec1=root.copy()
vec2=root.copy()
dim=len(root)
path=np.zeros([iters,dim])
np.random.seed(0)
for k in range(iters):    theta= 0root=(1.0+theta)*vec2-theta*vec1a=1/(k+1)**gammaxi=np.random.randn(2)vec1=vec2.copy()vec2=root - a*gobj(root,xi)path[k,:]=root
V=np.zeros(iters)
for k in range(iters):V[k]=la.norm(path[k,:])
plt.loglog(V,'.-')
plt.grid(True)plt.legend(['(k-1)/(k+2)',0.99,0.5,'2/(k+2)'])
plt.show()

Matlab 代码如下

% (k-1)/(k+2)   ===============================
init=[1,3];
lth=length(init);
fobj=@(x,xi)(x*x'+2*xi*x');
gobj=@(x,xi)(2*x+2*xi);
iters=1000000;
path=ones(iters+1,length(init));
path(1,:)=init;
root=init;
randn('seed',1)
for k =1:itersif k<2xi=randn(1,lth);a=1/(k+2)^(2/3);root=root-a*gobj(root,xi);path(k+1,:)=root;elsexi=randn(1,lth);a=1/(k+2)^(2/3);v=root-a*gobj(root,xi);path(k+1,:)=v;theta=(k-1)/(k+2);th=theta;root=(1+th)*path(k+1,:)-theta*path(k,:);end
end
Vk=ones(iters+1,1);
for k=1:iters+1Vk(k)= path(k,:)*path(k,:)';
end
loglog(Vk,'--')
grid on;
hold on;% theta=0.99    ===============================
init=[1,3];
iters=1000000;
path=ones(iters+1,length(init));
path(1,:)=init;
root=init;
randn('seed',1)
for k =1:itersif k<2xi=randn(1,lth);a=1/(k+2)^(2/3);root=root-a*gobj(root,xi);path(k+1,:)=root;elsexi=randn(1,lth);a=1/(k+2)^(2/3);v=root-a*gobj(root,xi);path(k+1,:)=v;theta=0.99;th=theta;root=(1+th)*path(k+1,:)-theta*path(k,:);end
end
Vk=ones(iters+1,1);
for k=1:iters+1Vk(k)= path(k,:)*path(k,:)';
end
loglog(Vk,'--')
grid on;
hold on;% theta=0.9     ===============================
init=[1,3];
iters=1000000;
path=ones(iters+1,length(init));
path(1,:)=init;
root=init;
randn('seed',1)
for k =1:itersif k<2xi=randn(1,lth);a=1/(k+2)^(2/3);root=root-a*gobj(root,xi);path(k+1,:)=root;elsexi=randn(1,lth);a=1/(k+2)^(2/3);v=root-a*gobj(root,xi);path(k+1,:)=v;theta=0.9;th=theta;root=(1+th)*path(k+1,:)-theta*path(k,:);end
end
Vk=ones(iters+1,1);
for k=1:iters+1Vk(k)= path(k,:)*path(k,:)';
end
loglog(Vk,'--')
grid on;
hold on;% theta=0.9  ===================================================================
init=[1,3];iters=1000000;
path=ones(iters+1,length(init));
path(1,:)=init;
root=init;
randn('seed',1)
for k =1:itersif k<2xi=randn(1,lth)a=1/(k+2)^(2/3);root=root-a*gobj(root,xi);path(k+1,:)=root;elsexi=randn(1,lth);a=1/(k+2)^(2/3);v=root-a*gobj(root,xi);path(k+1,:)=v;theta=0.5;th=theta;root=(1+th)*path(k+1,:)-theta*path(k,:);end
end
Vk=ones(iters+1,1);
for k=1:iters+1Vk(k)= path(k,:)*path(k,:)';
end
loglog(Vk,'--')
grid on;
hold on;
legend('(k-1)/(k+2)','0.99','0.9','0.5')