随机平均梯度法(Stochasitc Average Gradient)和随机梯度下降(SGD)有什么区别

  数学 数值计算 最优化    浏览次数: 2989
15

我看到很多封装好的ML算法里都在用这个随机平均梯度法(Stochasitc Average Gradient),但是网上对于这个算法的资料非常非常少。可能是因为这个算法太新了。

有人具体了解过这个算法吗?这个和普通的随机梯度下降有什么改进之处?

 

MrMath   2017-03-27 11:15



   3个回答 
22

是的,这个算法的确很新,论文是两年前的。Minimizing Finite Sums with the Stochastic Average Gradient,2015.1.19。

可以看论文第3页的公式(5)和(6)。我截图贴下面。

我们知道sgd是当前权重减去步长乘以梯度,得到新的权重。sag中的a,就是平均的意思,具体说,就是在第k步迭代的时候,我考虑的这一步和前面n-1个梯度的平均值,当前权重减去步长乘以最近n个梯度的平均值。n是自己设置的,当n=1的时候,就是普通的sgd。


这个想法非常的简单,在随机中又增加了确定性,类似于mini-batch sgd的作用,但不同的是,sag又没有去计算更多的样本,只是利用了之前计算出来的梯度,所以每次迭代的计算成本远小于mini-batch sgd,和sgd相当。效果而言,sag相对于sgd,收敛速度快了很多。这一点上面的论文中有具体的描述和证明。




SofaSofa数据科学社区 DS面经 问答 实战

清风   2017-05-27 11:32

你好,我最近在看python,觉得你比较厉害,能否留个联系方式发到我的邮箱cp20133808@163.com - 陈十一   2017-09-05 14:50
经常在一些package里看到sag,现在看了你的解释终于搞懂了! - NextPage   2017-09-13 13:53
学习了 - wlk1993   2017-11-18 09:43
5

其实SAG就是SGD with momentum(带动量的随机梯度下降)的姊妹版本。

SAG是对过去k次的梯度求均值。

SGD with momentum是对过去所有的梯度求加权平均(权重成指数衰减)。


SofaSofa数据科学社区 DS面经 问答 实战

染盘   2017-11-17 13:35

3

随机梯度下降被发明出来的原因是因为它的下降速度快,可以减少迭代的次数,但是不容易收敛是它的缺点。

在有些特定的情况下呢,需要更多的迭代(更多的计算复杂度)才能达到收敛条件,反而可能不如正常的梯度下降来得好。

为了避免这个情况呢,随机平均梯度法就诞生啦,保证了随机梯度下降原汁原味的优点(下降快),同时又利用平均的特性,让梯度下降能更快达到收敛条件,减少迭代次数。

综上,这个方法呢,以后估计还会改进吧,毕竟平均这个特性太“low”了,不过思想倒是可取的,跟马尔科夫链有点异曲同工,说不定下一个算法就是“马尔科夫链随机梯度下降”呢。


SofaSofa数据科学社区 DS面经 问答 实战

天晴   2017-12-26 17:55

“跟马尔科夫链有点异曲同工”这个想法不错 哈哈 - dzzxjl   2018-03-07 20:31


  相关主题

学习率不当会导致sgd不收敛吗?   3回答

为什么梯度的反方向是函数下降最快的方向?   3回答

对于小批量随机剃度下降法(mini-batch SGD),如何选择每批样本的数量?   1回答

用SGD时陷入局部最优解的解决方法   3回答

Adam优化算法   1回答

牛顿法到底是一阶优化算法还是二阶优化算法?   2回答

随机梯度下降(sgd)的收敛问题   3回答

最速下降法与梯度下降法   1回答

梯度上升算法是什么?   2回答

RMSProp的直白解释   1回答

线性回归有精确的解析解为什么还要用梯度下降得到数值解?   4回答

优化算法中的“带冲量”是什么意思?   1回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!