SGD
对于目标函数:
目标函数优化步骤:
1.随机旋转索引j,即函数
fj(x)
;
2.更新参数x,采用sgd公式为:
SAGA(STOCHASTIC VARIANCE REDUCTION METHODS)
目标函数优化步骤:
1.随机旋转索引j,即函数
fj(x)
;
2.对于上述目标函数,采用SAGA参数更新公式为:
ϕk+1j=xk
.
SAGA代码:https://github.com/adefazio/point-saga
相比SGD,SAGA有完全不同的收敛性.对于强凸的问题,SAGA可以线性收敛,即计算量为
O(log(1/k))
,而在现有的随机方法中,例如SGD需要计算量为
O(1/k)
,都未达到线性收敛.
图中Incremetal Gradient为SAGA方法.由图可知,在训练过程中,采用SAGA梯度下降法可以使模型快速收敛.
