牛顿法是一种迭代求根法。

第一步：我们先任意选定一个初始点$x_0$和迭代误差$\epsilon$

第二步：$x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)}$。反复迭代直到$|x_{n+1}-x_{n}|<\epsilon$。

最终的$x_n$就是方程$f(x)$的近似解。

对于逼近$\sqrt{2}$，实际上就是求$f(x)=x^2-2$的正根。

先求出$f'(x)=2x$。$\sqrt{2}$肯定在1到2之间，我们不妨选定$x_0=1.5$，误差$\epsilon=0.00001$。

初始0：$x_0=1.5$, $f(x_0)=0.25$, $f'(x_0)=3$, $f(x_0)/f'(x_0)=0.08333$

迭代1：$x_1=1.5 - 0.08333=1.41667$, $f(x_1)=0.00694$, $f'(x_1)=2.83333$, $f(x_1)/f'(x_1)=0.00245$

迭代2：$x_2=1.41667 - 0.00245=1.41422$, $f(x_2)=0.00001$, $f'(x_2)=2.82843$, $f(x_2)/f'(x_2)=0.00001$

迭代3：$x_3=1.41422 - 0.00001=1.41421$

停止迭代，最终近似解就是$1.41421$.

牛顿法求根的python代码

def findSqrt(x, tol=0.01):

    if x == 0: return 0

    if x < 0: return findSqrt(-x) * 1j

    init_guess = 1

    while init_guess ** 2 < x:

        init_guess *= 2

    r_o = init_guess

    err = r_o ** 2 - x

    while abs(err) > tol:

        r = r_o - err / (2 * r_o)

        r_o, err = r, r ** 2 - x

    return r_o

是的，对于凸优化来说，局部最优就是全局最优，换句话说，极小值就是最小值。

至于为什么？这个就是数学证明了，这个要用到凸函数、凸集的定义。

我们可以用反证法来证明。已知$x_0$是个局部最优点，假设在全集$S$上存在一个点$x_*$，使得

$$f(x_*) < f(x_0).$$

因为$f(x)$是凸函数，所以对于任意的$t$

$$f(tx_*+(1-t)x_0)\leq tf(x_*) + (1-t)f(x_0)$$

注意，这个$t$是$0$到$1$之间的任意值，所以$t$可以非常接近$0$，此时$(tx_*+(1-t)x_0)$这个点就可以无限接近$x_0$，但是函数在这个点的值又比$f(x_0)$小，所以$f(x_0)$不可能是局部最小值。故假设矛盾，因此不存在这样的$x_*$。$f(x_0)$必定为最小值。

是的，这是凸优化极好的一个性质。

找到局部最优也就找到了全局最优。这让很多类梯度下降的优化算法有了大展拳脚的空间。

是的。对于每一次更新，我们只是随机地挑选一个样本，然后根据这个样本来确定下降方向。但是这并不代表剩下的没有用呀，在下一次更新的时候，我们还会从这500个里随机挑一个。因为一般来说步长比较小，达到最终收敛，我们会迭代很多次，每次随机挑一个，这样很多样本都会被用到。

如果你是想每次迭代的时候多用几个样本点的话，可以考虑使用小批量梯度下降法(Mini-Batch Gradient Descent)。MBGD是每次随机选出m个样本点，然后对这m个点的梯度求平均值，这个平均值就是下降的反方向。

凸集：

如果对于一个集合$S$中的任意两个点$A$和$B$，这两个点的连线$AB$也在$S$内，那么$S$就是一个凸集。

换句话说，凸集不能有洞，不同有任何凹陷。

凸函数：

一个函数$f$满足

（1）它的定义域是凸集

（2）对于其定义域中的任意两点$x_1$，$x_2$，对任意$0\leq \alpha \leq 1$，$f(\alpha x_1 +(1-\alpha)x_2)\leq \alpha f(x_1)+(1-\alpha)f(x_2)$，

那么这个函数$f$就是凸函数。

比如实数域上的$f(x)=x^2$就是凸函数，$f(x)=\sin x$就不是凸函数。

凸集：没有“洞”，没有凹陷

凸函数：二阶导数大于等于0

凸优化问题是一种特殊的优化问题。凸优化问题的形式是

$$\min_{x\in S} f(x),$$

其中$f(x)$是凸函数，可行域$S$是凸集。

此外还有个等价形式

\begin{eqnarray*}&&\min_{x}f(x)\\ &\text{subject to}&g_i(x) \leq 0, \text{for }i=1,2,\cdots,k\end{eqnarray*}

其中$f(x)$和所有的限制函数$g_i(x)$都必须是凸函数。

凸优化问题有个很好的性质，它的局部最优解一定是全局最优解。（为什么？可以看这里）

是的，这个算法的确很新，论文是两年前的。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，收敛速度快了很多。这一点上面的论文中有具体的描述和证明。

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

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

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

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

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

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

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

这篇论文On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima给出了关于mini-batch样本点的一些观察：

1. 样本点太少，训练时间长；样本点太多，训练时间也太长。

2. 样本点多，训练单个epoch时间更短

3. 样本点越小，模型的泛化越好。

理论归理论，实际上还是自己选一些比较小的数值，比如8，12，32，64。

一般来说是16到256之间。

随机剃度下降是不会收敛的，它总是在最优点附近跳来跳去。即使我们到达了最优点，它依然会跳动，因为对于随机的样本来说，这些少数的样本在最优点的梯度也未必是0（整体的梯度是0）。

有一个方法可以使随机梯度下降收敛——让步长衰减。因为随机梯度很快就能到达最优点附近，如果步长逐步减小，最终它会停在最优点附近一个较优的点上（未必是正好停在最优点）。

是的，不收敛的。随机梯度下降（Stochastic Gradient Descent）和小批量梯度下降（mini-batch）都存在这个现象。

现在很多的算法和一些封装好的package在使用SGD或者类似算法的时候都使用了不固定的learning rate（步长），其目的就是为了解决不收敛。

凸优化的全局最优点是针对训练数据而言的，更换了当前训练数据，当前的最优点就变了。所以SGD本来就没有固定的全局最优点。最后得到的是多个batch上最优点的一个或几何均值。比如多个batch上最优点组成一个圆，那么最后结果就是圆内随机一点。因为GD用了全部训练数据，所以最优点固定，是圆的重心。

以简单二维输入最小二乘为例，每一个训练数据产生loss funtion的曲面是以此点对应系数为中心的倒钟形，有点像沙坑里落下一个铅球，每个点都产生一个坑。一个batch的数据生成的坑的乘积就是batch对应的loss funtion的曲面。换一组铅球的话，最低点自然就会移动。

随机类型的算法，看收敛性质是看Expectation期望的，是error的期望值收敛。

Adam(Adaptive Moment Estimation)本质上是带有动量项的RMSprop，它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏置校正后，每一次迭代学习率都有个确定范围，使得参数比较平稳。

特点：

1. 结合了Adagrad善于处理稀疏梯度和RMSprop善于处理非平稳目标的优点 
2. 对内存需求较小
3. 为不同的参数计算不同的自适应学习率
4. 也适用于大多非凸优化 - 适用于大数据集和高维空间

牛顿法是用来求根的。

比如说要求$f(x)=0$的解，先随机选个初始点$x_0$，然后开始迭代。迭代公式为

$$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_{n})}$$

当$|x_{n+1}-x_n|<\epsilon$时（$\epsilon$为你设置的容忍误差），迭代结束，$x_{n+1}$就是$f(x)=0$的近似数值解。

可以清楚地看到，在迭代公式中我们使用了一阶导数$f'(x)$。所以此处牛顿法是一阶算法。

但是，当我们将牛顿法用作优化算法的时候，它就是二阶的。

假设我们有一个凸优化问题

$$\min_{x} f(x)$$

也就是说我们要找一个$x$来最小化$f(x)$。对于凸优化问题，$f(x)$的最小值点就是$f(x)$的极值点，也就是导数为0的点。那么我们上面的优化问题就转换为了如下的求根问题：

$$f'(x)=0.$$

利用牛顿法求解上面的式子，我们先选取初始点$x_0$，然后进行如下迭代

$$x_{n+1}=x_n-\frac{f'(x_n)}{f''(x_n)}$$

直到$|x_{n+1}-x_n|<\epsilon$。

综上，牛顿法求根是一阶算法，我们将优化问题转为求根问题需要一阶导数，所以用牛顿法进行最优化是二阶算法。

当我们用牛顿法来求根，牛顿法是基于一阶导数的。

当我们用牛顿法来优化，牛顿法就是基于二阶导数的。

马什么梅，什么冬梅，马东什么？

维基百科这个说法不是太严谨。

准确来说，它们并不是完全等价。

对于梯度下降法，我们需要预先设定步长$\alpha$。

$$x_{i+1}=x_i-\alpha \nabla f_{x_i}$$

而最速下降法的这个步长$\alpha_k$是通过一个优化函数计算得到的。

$$\alpha_k=\text{argmin}_{\alpha_k}f(x_i-\alpha_k \nabla f_{x_i})$$

如果对梯度下降感兴趣，可以阅读我写的文章自己动手用python写梯度下降。

1.RMSProp是AdaGrad算法的改进。鉴于神经网络都是非凸条件下的，RMSProp在非凸条件下结果更好，改变梯度累积为指数衰减的移动平均以丢弃遥远的过去历史。

2.经验上，RMSProp被证明有效且实用的深度学习网络优化算法。

与AdaGrad相比，RMSProp增加了一个衰减系数来控制历史信息的获取多少。

所以我建议题主先看一下adagrad的算法实现

其实就是一回事

我正好看过那一段

对于损失函数，我们要求最小值，所以是梯度下降（梯度的反方向）

对于似然函数，我们要求最大值，所以是梯度上升（梯度的同方向）

本质都是利用梯度来解最值

要求最小值(如loss function)的时候，用梯度下降

要求最大值(如score function)的时候，用梯度上升

可尝试随机地增大学习速率/学习步长。其想法是像模拟退火算法样，在优化时有一定概率接受非最优解，从而增大跳出局部最优的概率。

在每个epoch/iteration后需要把数据洗牌一遍，让每个batch的数据都不一样。我的理解是每个data point的loss funtion曲面不一样，一个batch的曲面是相关曲面的平均。如果每次batch中data不一样，也就是曲面都不一样，那就减小了停在局部最优的可能性。

可以尝试更多的初始值

也可以使用更好的优化算法，如动量、Adam

有可能是初始点不好，也可能是学习率太小。

先以一个二元函数为例，$f(x,y)$

我们知道梯度是函数在各坐标轴方向上的变化率，比如梯度$\nabla f(x_0,y_0)$是函数在$(x_0,y_0)$上关于$x$轴和$y$轴的变化率

$$\nabla f(x,y)=\begin{pmatrix}f_x(x,y) \\ f_y(x,y)\end{pmatrix}$$

对于一个任意单位方向$u$，假设$\alpha$是$u$和$x$轴的夹角，那么函数$f(x,y)$在$u$这个方向上的变化率为

$$f_x(x,y) \cos \alpha + f_y(x,y) \sin \alpha=\nabla f(x,y)^T\begin{pmatrix}f_x(x,y) \\ f_y(x,y)\end{pmatrix}=\nabla f(x,y)^Tu$$

也就是两个向量的点积。我们知道向量点积的结果和向量本身的大小以及两者夹角相关，假设$\nabla f(x,y)$和$u$的夹角为$\theta$，那么函数$f(x,y)$在$u$这个方向上的变化率可以写成

$$\nabla f(x,y)^Tu=\|\nabla f(x,y)\|_2 \|u\|_2 \cos \theta=\|\nabla f(x,y)\|_2\cos \theta$$

$\cos \theta$的取值范围为$[-1, 1]$。当$\cos \theta = 1$时，函数变化率最大（上升最快），此时$u$和梯度$\nabla f(x,y)$同方向；当$\cos \theta = -1$时，函数变化率最小（下降最快），此时$u$是梯度$\nabla f(x,y)$的反方向。

推广到$n$元函数，函数$f$在单位方向$u$的变化率为

$$\nabla f^T u$$

假设$\nabla f(x,y)$和$u$的夹角为$\theta$，同样函数$f$在$u$这个方向上的变化率可以写成

$$\nabla f^Tu=\|\nabla f\|_2\|u\|_2 \cos \theta=\|\nabla f\|_2\cos \theta$$

变化率由$\cos \theta$决定。$u$和梯度$\nabla f(x,y)$同方向，上升最快；$u$和梯度$\nabla f(x,y)$反方向，下降最快。

假设$v$为任意方向的单位向量,$f(x)$在$x$可导，沿$v$的方向导数是

$$\nabla_vf(x)=\lim_{h\to 0} \frac{f(x+hv)-f(x)}{h}=\nabla f(x) \cdot v=|\nabla f(x)|cos\theta$$

$\theta$是$\nabla f(x)$和$v$夹角。左边表示当$x$变化$hv$时，$f(x+hv)-f(x)$的变化量，它等于梯度$\nabla f(x)$和$v$的内积。当二者方向相反时， $\theta=\pi$，此时$f(x)$改变的绝对值最大。

也可以从泰勒级数展开来看$f(x+\delta v)=f(x)+\delta \nabla f(x) \cdot v+\cdots$ , $\delta$是很小的步长。第二项就是一阶增量，正比于方向导数。

因为这个时候$cos\theta=-1$，最小。

$\theta$是梯度和$\Delta x$之间的夹角

凸优化指的是在凸集上的凸目标函数只有一个最优解，也就是只有一个max point, gradient=0。凸优化最主要目的是保证理论上局部最优就是全局最优。但是实际中学习步长不可能无限小，有可能也会有局部最优解。

GD和牛顿发都是最优化算法，目的是找gradient=0的点。

梯度下降（一阶算法）和牛顿法（二阶算法）都是去找梯度为0的点（驻点）。

至于这些点是极大（小）值还是最大（小）值，牛顿法和梯度下降法是无法保证的，所以牛顿法不是全局优化算法。

鞍点的梯度为0，各方向上二阶偏导的正负性不一致

-------------------------------------------------------------

比如函数$f(x,y)=x^2-y^2$

梯度

$$\text{grad}_f (x,y)=\begin{pmatrix}\frac{\partial f}{\partial x} \\ \frac{\partial f}{\partial y}\end{pmatrix}=\begin{pmatrix}2x \\ -2y\end{pmatrix}$$

在$(0,0)$处，梯度是零向量。

在$(0,0)$二阶偏导

$$\frac{\partial^2 f}{\partial x^2}=2$$

在$x$方向上大于0，说明是在$x$方向上极小值点

$$\frac{\partial^2 f}{\partial y^2}=-2$$

在$y$方向上小于0，说明在$y$方向上是极大值点；两者不一致，所以$(0,0)$是鞍点

一个鞍点(saddle point)

首先，必须是驻点，也就是函数的导数（梯度）为0的点

其次，不能是极大值或者极小值点

大家常见的是马鞍图，其实更简单的一个例子是$f(x)=x^3$上的$0$点，也是鞍点。

1牛顿法收敛速度为二阶，对于正定二次函数一步迭代即达最优解。

2牛顿法是局部收敛的，当初始点选择不当时，往往导致不收敛

3牛顿法不是下降算法，当二阶海塞矩阵非正定时，不能保证产生方向是下降方向。

4二阶海塞矩阵必须可逆，否则算法进行困难。

5对函数要求苛刻（二阶连续可微，海塞矩阵可逆），而且运算量大。

一阶算法就是用了一阶导数的算法。对于多元函数，一阶导数就是梯度（一维张量）。

二阶算法就是用了二阶导数的算法。对于多元函数，二阶导数就是海森矩阵（二维张量）。

n阶算法就需要计算n维张量。

这么看很显然阶数越高，需要计算的张量维度越高，计算量越大。

虽然高阶算法收敛快，但是考虑到计算导数本身的代价，二阶算法不一定总是比一阶算法实用。所以在神经网络里，经常是使用一阶优化算法。

是有可能的。比如我们有梯度下降求解$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$

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

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

解$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$时，过阻尼，无振荡衰减。

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

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

学习过大，算法发散

左边是经典的momentum，右边是nestrov momentum

经典的momentum，可以参考我另一个回答优化算法中momentum是什么意思？

两者区别是经典的momentum是在当前点($X_i$)计算gradient step；而nesterov momentum是想在下一个迭代点$X_{i+1}$计算gradient step，两步并一步向前跨，当然这是无法做到的，所以就用momentum step后的点来近似实际的$x_{i+1}$。也就是图中说的“lookahead”，“前瞻点”。这样做的好处就是加速收敛。

参考链接http://cs231n.github.io/neural-networks-3/#sgd

他们是一回事，就是叫法不同吧

Newton–Raphson方法有时候是特指一维函数的牛顿法

其实神经网络基本上都是非凸的，但是很多情况下SGD照用不误。

对于非凸的情况，不管是GD还是SGD都不能保证收敛到全局最优，AdaGrad更好。

参考维基百科：https://en.wikipedia.org/wiki/Stochastic_gradient_descent#AdaGrad

可以，但是会陷入局部最优解 很可能解不出全局最优解

求立方根就是等价于求$f(x)=x^3-a$的根，也就等价于求$g(x)=f^2(x)=(x^3-a)^2$的最小值。梯度下降法要求$g(x)$是凸函数，但是显然它并不是凸函数。

上面是$g(x)=(x^3-1)^2$的图像，也有可能会收敛到0点。一般不用梯度下降，如果用的话要多试几个初始点，并且最后结果要代回原式子验算一遍。

先建立等式，再建立convex函数，最后用梯度下降解。

$$x^2=y$$

$$L=(x^2-y)^2$$

$$g(x)=dL/dx=4x^3-4xy=4x(x^2-y)$$

$$x_{n+1}=x_n-ag(x_n)$$

------------------------------------------------

根据xiaosu的回答，$(x^2-y)^2$只在局部是convex函数。$d^2L/dx^2=4(3x^2-y)>0=>|x|>\sqrt{y/3}$。所以x的初始值范围是$y$的函数。

import numpy as np
import matplotlib.pyplot as plt
y=10.
n=200
xn=np.zeros(n)
def grad(x,y):
  return 4.*np.power(x,3)-4.*x*y
xn[0]=y
a=0.001 # step size
for i in range(1,n):
  xn[i]=xn[i-1]-a*grad(xn[i-1],y)
plt.figure()
plt.plot(xn)
plt.plot([0,n],np.ones(2)*np.sqrt(y),'--')
plt.show()

2010年的NIPS就有关于SGD并行的论文了。论文Parallelized Stochastic Gradient Descent传送门。

论文里回顾了之前的做法，就是把数据分成k份，各自计算，然后最后做一个平均。（论文中的Algorithm 2）

他们提出的是算法是在算法的过程中不断汇总平均，而不是只在最后做平均。（论文中的Algorithm 3）

具体算法如下：

clipping是对梯度进行剪裁，也就是把每次计算的梯度限制在$[-d, d]$的范围内，如果计算得到的梯度大于$d$，就取$d$；如果小于$-d$，就取$-d$。$d$是自己设置的。

这样的目的主要是防止梯度爆炸。

一般是叫做gradient clipping，就是把绝对值太大的梯度“修剪”下。

RNN如果没有gradient clipping，训练到最后得到的都是NaN了。

这个是数值计算中常用的概念。

对于光滑函数，我们可以用泰勒展开，展开到无穷多项。但是为了计算的方便，我们通常只取前$k$项来进行逼近，把后面的都截去。前$k$项的值和真实值之间的误差就叫做截断误差。比如一个函数$f(x)$的二次逼近就是

$$f(x)=f(x_0)+(x-x_0)f'(x_0)+\frac{(x-x)^2}{2}f''(x_0)+O_2$$

这个$O_2$就是$f(x)$二次展开的截断误差。