在上一篇中介绍了梯度下降算法，还是利用了上面的那个x^2+y^2的例子，来求解下，代码如下：
function [] = gradient(step, threadhold)%在这里主要是演示对z=x^2+y^2的用梯度下降算法%设置x和y的初始值%x = 100;y = 100;%先计算前两个步骤的值last_step_result = x*x + y*y;x = x - step*2*x;y = y - step*2*y;this_step_result = x^2 + y^2;%设置最大迭代次数%max_count = ;index = 0;while (abs(this_step_result -last_step_result) &threadhold) && (index & max_count)
%计算此时的结果%
current_dx = 2*x;
current_dy = 2*y;
%计算新的x和y
x = x - step*current_
y = y - step*current_
%计算此时的z的值，并且交换
last_step_result = this_step_
this_step_result = x*x + y*y;
index = index + 1;end%跳出循环判断结果if index &= max_count
fprintf('超过最大迭代次数%i，并且没有找到符合收敛条件的值程序退出\n', index);endif abs(this_step_result - last_step_result) &= threadhold
fprintf('找到最优解：%f，x=%f,y=%f，上一步的结果是:%f，迭代次数：%i\n', this_step_result, x, y, last_step_result, index);endend
我们都知道这个极值是在(0,0,0)处取得的，那么我们取了一些步长和收敛条件（连续两次z值得间隔）
可以看到步长不是越小越好的，相反步长越小反而取得的值不太接近真实的，这是为什么呢?因为连续函数连续两次间隔太近取得值基本相等，也就满足收敛条件了，所以步长不能取太小，当然也不能取太大，试想如果在有两个点x1,x2不同但是他们的函数值相等，正好取到一个步长让在x1,x2来回震荡那么取到的也不真实，所以这个步长取值是有一定的技巧的。
可以看到收敛条件的值，取得越小还是越好的，当然是在步长合理的前提下。至此对梯度下降的理解告一段落！
本文转载自：
欢迎加入我爱机器学习QQ13群：
微信扫一扫，关注我爱机器学习公众号
欢迎加入我爱机器学习QQ13群：
最新文章列表
NIPS 2016 — Day 1 Highlights NIPS 2016 — Day 2 Highlights:...
2017年九月 &(25)
2017年八月 &(58)
2017年七月 &(60)
2017年六月 &(67)
2017年五月 &(66)
2017年四月 &(65)
2017年三月 &(54)
2017年二月 &(48)
2017年一月 &(54)
2016年十二月 &(62)
2016年十一月 &(97)
2016年十月 &(97)
2016年九月 &(124)
2016年八月 &(83)
2016年七月 &(13)
2016年六月 &(10)
2016年五月 &(7)
2016年四月 &(9)
2016年三月 &(7)
2016年二月 &(2)
2016年一月 &(3)
2015年十二月 &(5)
2015年十一月 &(4)
2015年十月 &(2)
2015年九月 &(2)
2015年八月 &(3)
2015年七月 &(6)
2015年六月 &(8)
2015年五月 &(4)
2015年四月 &(1)
2015年三月 &(3)
2015年二月 &(1)
2015年一月 &(2)
2014年十二月 &(4)
2014年十一月 &(2)
2014年十月 &(3)
2014年九月 &(4)
2014年八月 &(22)
2014年七月 &(40)
2014年六月 &(61)
2014年五月 &(63)
2014年四月 &(187)
2014年三月 &(4799)
2014年二月 &(764)
2014年一月 &(330)
2013年十二月 &(145)
2013年十一月 &(126)
2013年十月 &(216)
2013年九月 &(284)
2013年八月 &(327)
2013年七月 &(275)
2013年六月 &(315)
2013年五月 &(228)
2013年四月 &(175)
2013年三月 &(186)
2013年二月 &(118)
2013年一月 &(210)
2012年十二月 &(221)
2012年十一月 &(155)
2012年十月 &(143)
2012年九月 &(98)
2012年八月 &(99)
2012年七月 &(109)
2012年六月 &(75)
2012年五月 &(88)
2012年四月 &(78)
2012年三月 &(78)
2012年二月 &(50)
2012年一月 &(17)
2011年十二月 &(27)
2011年十一月 &(6)
2011年十月 &(11)
2011年九月 &(13)
2011年八月 &(13)
2011年七月 &(19)
2011年六月 &(18)
2011年五月 &(6)
2011年四月 &(12)
2011年三月 &(15)
2011年二月 &(6)
2011年一月 &(9)
2010年十二月 &(6)
2010年十一月 &(11)
2010年十月 &(5)
2010年九月 &(8)
2010年八月 &(5)
2010年七月 &(12)
2010年六月 &(4)
2010年五月 &(7)
2010年四月 &(6)
2010年三月 &(12)
2010年二月 &(7)
2010年一月 &(2)
2009年十二月 &(5)
2009年十一月 &(16)
2009年十月 &(6)
2009年九月 &(7)
2009年八月 &(7)
2009年七月 &(5)
2009年六月 &(6)
2009年五月 &(6)
2009年四月 &(4)
2009年三月 &(7)
2009年二月 &(6)
2009年一月 &(1)
2008年十二月 &(4)
2008年十一月 &(5)
2008年十月 &(1)
2008年八月 &(1)
2008年七月 &(3)
2008年六月 &(3)
2008年五月 &(3)
2008年三月 &(1)
2007年十二月 &(1)
2007年十月 &(1)
2007年八月 &(4)
2007年七月 &(1)梯度下降法的步长到底怎么确定？ - 知乎158被浏览12531分享邀请回答0添加评论分享收藏感谢收起梯度下降法步长的取值范围
已有 3891 次阅读
|个人分类:|系统分类:
在梯度下降法中，我们往往需要设置一个合适的步长。但是有时步长设置太大，使得我们要估计的系数在迭代过程中不断增大，最后趋于无穷大，程序陷入死循环或溢出。下面的讨论给出了步长上限的一个估计，其中参数的迭代公式是(使用矩阵表示)：其中是步长。将这个公式变形一下，得到可以看出，对的每个分量，都是相同的。因此后面我们可以用分量来进行讨论，这时候上面的公式就是一个标量公式。对于这个迭代，要么发散，要么收敛于一个稳定点，要么在多个稳定点中做周期震荡（即周期N）。因此我们可以计算其收敛点，并计算其收敛条件。当收敛时，它是一个稳定点，即，解出，与最小二乘法给出的结果一致。按照非线性理论中的稳定性条件要求：，即，因此（这里使用了标量来求解）。所以，当步长超出这个范围，是不稳定的，很容易导致发散。
转载本文请联系原作者获取授权，同时请注明本文来自袁文彬科学网博客。链接地址：
上一篇：下一篇：
当前推荐数：0
评论 ( 个评论)
扫一扫，分享此博文
作者的其他最新博文
热门博文导读
Powered by
Copyright &加速梯度下降法
我的图书馆
加速梯度下降法
Nesterov’s Accelerated Gradient Descent
一般的梯度下降算法的收敛速率为
o(1/t),t表示迭代的次数。但是人们已经证明了随着迭代次数t的增加。收敛速率可以到达o(1/t2).
加速梯度算法(AGD)是梯度算法(GD)的一个改进的版本。Nesterov 在1983年首次提出。人们已经证明AGD算法是所有基于梯度算法（或者说一阶）算法中最好的方法。然而原始的AGD算法仅能处理光滑的凸优化问题。最新的进展是，将AGD扩展到了更广泛类型的凸优化问题：
minxf(x)+g(x)
其中f(x)是平滑的凸函数,g(x)是闭凸函数。同样可以获得相似的收敛速率。
AGD算法可以概括为算法1：，其中有两种方式确定步长γ
首先，类似于梯度下降算法，为了确保收敛率，我们可以设置γ为一个足够小的数，特别的，γ≤(||▽2f(x)||?1)?x。其次，我们可以使用直线搜索，自适应地确定步长，满足:
f(xk+1)≤myk,γ(xk+1)
xk+1=proxγg(?)(yk?γ▽f(yk))
proxγg(?)(?)表示近端操作（近似操作）。即：
proxγg(?)(v)=argminz∈Rn12γ||v?z||2+g(z)
通常给定γ的情况下，我们先求解：v=yk?γ▽f(yk)，然后再求解proxγg(?)(v).
注意：序列{tk}满足下面的三个属性：
{tk} 是正的，并且递增
tk+1≥tk+12
fract0?1t1=0 并且limt→∞tk?1tk+1=1
3.收敛率：
AGD 是最优的基于梯度的方法。因为它提供了最优的收敛率。假定满足下面的Lipschitz 条件。
假设1. 假定平滑的凸函数f(x)拥有一个Lipschitz梯度。也就是说存在常数L，满足：
f(y)≤f(x)+&▽f(x),y?x&+L2||y?x||2x,y
在这个假设下，如果步长选择的足够小，或者通过直线搜索确定，那么我们有下面的收敛率：
F(xk)?F?≤O(1k2)
另外一种解释方法:
首先定义下面的序列：
λ0=0,λs=1+1+4λ2s?1????????√2,and,γs=1?λsλs+1
注意：γs≤0,。现在算法通过下面的等式简单的定义，初始点x1=y1是任意的。
ys+1=xs?1β▽f(xs)
xs+1=(1?γs)ys+1+γsys
换句话说：
Nesterov加速梯度下降法执行简单的梯度下降步骤,从xs到ys+1。然后通过先前的点y给定的方向上，轻微的滑动，进一步的远离ys+1.
参考文献：
[ORF523: Nesterov’s Accelerated Gradient Descent]
CSC 576: Accelerated Gradient Descent Algorithm
Gradient methods for minimizing composite objective function [Nesterov2007]
TA的最新馆藏[转]&
喜欢该文的人也喜欢}