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

  数学 数值计算 最优化    浏览次数:3749        分享
0

我想知道学习率不当会导致sgd不收敛吗?还是只是会导致收敛慢?

 

Erin   2018-12-10 14:21



   5个回答 
13

是有可能的。比如我们有梯度下降求解$f(x)=x^4$的最小值。

假设初始点是$x=2$,学习率(步长)是$0.5$

初始的时候

$x = 2$, $f'(x) = 32$, $f(x) = 16$

经过一次迭代

$x = -14.0$, $f'(x) = -10976$, $f(x) = 38416$

又一次迭代

$x = 5474$, $f'(x) = 656106545696$, $f(x) = 897881807784976$

我们看到$x$在来回摆荡,而且离最小值越来越远,显然这个情况下就是因为学习率太大了,导致每次更新时都“过犹不及”“矫枉过正”,所以最后并没有收敛。


如果学习率是$0.1$,

$x = 2 $, $f'(x) = 32 $, $f(x) = 16 $

$x = -1.2 $, $f'(x) = -6.91 $, $f(x) = 2.07$

$x = -0.51$, $f'(x) = -0.53$, $f(x) = 0.06$

$x = -0.46$, $f'(x) = -0.38$, $f(x) = 0.04$

$x = -0.42$, $f'(x) = -0.29$, $f(x) = 0.03$

$x = -0.39$, $f'(x) = -0.24$, $f(x) = 0.02$

我们就看到是在逐渐收敛的了

SofaSofa数据科学社区DS面试题库 DS面经

蘑菇蘑菇   2018-12-12 12:02

谢谢你的例子 - Erin   2018-12-16 11:58
5

举一个例子说明学习率足够小,可以保证得到收敛的解。

解$Ax=b$, $A$可做SVD,$A=USV^T$。

Gradient descent解为

$$x_n=x_{n-1}-\alpha A^T(Ax_{n-1}-b)$$

$$=(I-\alpha A^TA)x_{n-1}+\alpha A^Tb$$

为简化计算,把$x,A,b$都投影到singluar value的向量上,$Z=V^Tx, C=U^Tb$

$$VZ_n=V(I-\alpha S^2)Z_{n-1}+V\alpha SC$$

令$B=I-\alpha S^2$

$$Z_n=BZ_{n-1}+\alpha SC$$

$$Z_n=B^nZ_0+(\sum_{k=0}^{n}B^n)\alpha SC$$

令$Z_0=0$

$$Z_n=(\sum_{k=0}^{n}B^n)\alpha SC$$

根据Neumann series,$(I-B)^{-1}=\sum_{k=0}^{\infty}B^k$

$$\lim_{n\to \infty}Z_n=(I-B)^{-1}\alpha SC$$

$$=1/\alpha S^{-2}\alpha SC$$

$$=S^{-1}C$$

$$\lim_{n\to \infty}x_n=VS^{-1}U^Tb$$

Neumann series收敛的条件是$B$的最大singular value小于1,$|B|<1 => \alpha S_1^2-1<1 =>\alpha<2/S_1^2$。当学习率足够小,$\alpha<2/S_1^2$,保证收敛。

从控制论看,$-1<1-\alpha S_1^2<0$时欠阻尼,振荡衰减;$0<1-\alpha S_1^2<1$时,过阻尼,无振荡衰减。

SofaSofa数据科学社区DS面试题库 DS面经

Zealing   2019-04-10 05:55

这么说还是学习率小点稳妥 - Erin   2019-04-10 10:06
4

会,当你的学习率设置的过大的时候,就有可能发生不收敛的情况。

SofaSofa数据科学社区DS面试题库 DS面经

瓶子   2018-12-12 10:56

4

学习率太大就会overshoot(超调),就是一下子冲得过多;太小的话收敛太慢,或者陷入局部最优

SofaSofa数据科学社区DS面试题库 DS面经

数据科学小K   2019-01-13 10:18

2

学习过大,算法发散

SofaSofa数据科学社区DS面试题库 DS面经

陈十一   2018-12-12 16:43



  相关主题

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

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

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

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

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

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

Adam优化算法   1回答

Newton–Raphson和牛顿法区别?   1回答

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

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

nesterov’s momentum和momentum的区别?   1回答

RMSProp的直白解释   1回答



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

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

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

我们谢绝答非所问。

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

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