这篇文章主要写的是对梯度下降中学习率的优化过程，谈到牛顿法和拟牛顿法，梯度下降算法不是本文章的重点，如果对梯度下降算法还有不理解的地方，可以参考博文https://blog.****.net/weixin_43970346/article/details/104654613

我们从多变量线性回归中对我们建立的目标函数
$J(\theta) = \frac{1}{2}\sum_{i=1}^m (h_\theta(x^{(i)})-y^{(i)})^2$J(θ)=21​∑i=1m​(hθ​(x(i))−y(i))2
利用梯度下降算法
$\theta_j :=\theta_j - \alpha\frac{\partial}{\partial\theta_j}J(\theta)$θj​:=θj​−α∂θj​∂​J(θ)
可以求得$\theta$θ的最优解。问题似乎解决了。但是还有一个参数$\alpha$α（学习率、步长）我们没有去过多地考虑。

那么学习率$\alpha$α如何确定呢？
是使用固定的学习率还是变化的学习率？
学习率的设置只能够凭借经验值吗？

我们先来看两个简单的例子（说明：对于x，我们可以看成是$\theta$θ，对于y或F(x)，我们可以看成是$J(\theta)$J(θ)，对于f(x),则是F(x)的导数。这里只是将变量名称进行了一个改变，下面得都是如此）F

对于$y=x^2$y=x2，我们取x=1.5,学习率使用0.01

分析：经过200次迭代，x = 0.0258543；经过1000次迭代，x = 2.52445 * $10^{-9}$10−9 ，效果还不错。

对于$y = x^{4}$y=x4，我们同样取初始值x = 1.5，学习率使用0.01

分析：经过200次迭代，x = 0.24436；经过1000次迭代，x = 0.111275。我们可以看到效果很不理想。随着迭代次数的增加，收敛得越来越慢。

对学习率的优化

学习率$\alpha$α在f(x)中是步长，与方向导数一起构成梯度下降的大小。$\alpha$α越大，步长越大，梯度也越大；$\alpha$α越小，步长越小，梯度也越小。那我们可以有一个思路：
动态调整学习率，在斜率（方向导数）大的地方，使用小的学习率；在斜率（方向导数）小的地方，使用大的学习率。这样就可以保证下降的梯度始终保持在同一个水平线上，不至于时快时慢。

梯度下降的运行过程分析

设$x_{k+1} = x_k - \alpha f(x_k)$xk+1​=xk​−αf(xk​)
当$x_k =a$xk​=a，沿着负梯度方向，移动到$x_{k+1} = b$xk+1​=b，有:
$b = a - \alpha f(a) \\ \text{ 则 }f(a)\geqslant f(b)$b=a−αf(a) 则 f(a)⩾f(b)
从$x_0$x0​为出发点，每次沿着当前函数梯度的反方向移动一定距离$\alpha k$αk，得到序列
$x_0,x_1,...,x_n$x0​,x1​,...,xn​
对应的各点的函数值序列之间的关系为：
$f(x_0) \geqslant f(x_1) \geqslant f(x_2) ... \geqslant f(x_n)$f(x0​)⩾f(x1​)⩾f(x2​)...⩾f(xn​)
当n达到一定值时，函数f(x)收敛到局部最小值。

视角转换

记当前点为$x_k$xk​，当前搜索方向为$d_k$dk​(负梯度方向），因为学习率$\alpha$α为待考察的对象，因此，我们可以将下列函数$f(x_k + \alpha d_k)$f(xk​+αdk​)看作时关于$\alpha$α的函数$h(\alpha)$h(α)。
$h(\alpha) = f (x_k + \alpha d_k), \alpha > 0$h(α)=f(xk​+αdk​),α>0
当$\alpha$α = 0时，$h(0) = f(x_k)$h(0)=f(xk​)
导数 $\nabla h(\alpha) = \nabla f(x_k + \alpha d_k)^T d_k$∇h(α)=∇f(xk​+αdk​)Tdk​

因为梯度下降是寻找$f(x)$f(x)的最小值 ，那么在$x_k$xk​$d_k$dk​给定的前提下，即寻找函数$f(x_k+\alpha d_k)$f(xk​+αdk​)的最小值。即：
$\alpha = arg \min_{\alpha > 0} h(\alpha)$α=argα>0min​h(α)
如果$h(\alpha)$h(α) 可导，局部最小值的处的$\alpha$α满足:
$h'(\alpha) = \nabla f(x_k + \alpha d_k)^T d_k = 0$h′(α)=∇f(xk​+αdk​)Tdk​=0
接下来我们分析$h'(\alpha) = \nabla f(x_k + \alpha d_k)^T d_k = 0$h′(α)=∇f(xk​+αdk​)Tdk​=0
将 $\alpha = 0$α=0带入：
$h'(0) = \nabla f(x_k + 0* d_k) ^T d_k = \nabla f(x_k)^T d_k$h′(0)=∇f(xk​+0∗dk​)Tdk​=∇f(xk​)Tdk​
下降的方向$d_k$dk​可选负梯度方向 $d_k = -\nabla f(x_k)$dk​=−∇f(xk​)，则$h'(0) < 0$h′(0)<0。如果能够找到足够大的$\alpha$α,使得$h(\hat\alpha) > 0$h(α^)>0。则必存在某$\alpha$α，使得$h(\alpha) = 0$h(α)=0。至此，我们可以寻找到我们所需要的学习率了。

为了寻找我们所需要的学习率，我们可通过采用二分线性搜索、回溯线性搜索、插值法、二次插值法。

二分线性搜索（Bisection Line Search）

不断将区间分成两半，选择端点异号的一侧，直到区间足够小或者找到当前最优学习率。（二分查找）

回溯线性搜索（Backing Line Search）

基于Armijo准则计算搜索方向上的最大步长，其基本思想是沿着搜索方向移动一个较大的步长估计值，然后以迭代的形式不断缩减步长，直到改步长使得函数值$f(x_k+\alpha d_k)$f(xk​+αdk​)相对与当前函数值$f(x_k)$f(xk​)的减小成都大于预设的期望值（即满足Armijo准则）为止。
$f(x_k +\alpha d_k \le f(x_k) + c_1\alpha \nabla f(x_k)^T d_k ;\quad c_1 \in(0,1)$f(xk​+αdk​≤f(xk​)+c1​α∇f(xk​)Tdk​;c1​∈(0,1)

二分线性搜索的目标是求得满足$h'(\alpha) \approx 0$h′(α)≈0的最优步长近似值。而回溯线性搜索放松了对步长的约束，只要步长能使函数值有足够大的变化即可。二分线性搜索可以减少下降次数，但在计算最优步长上花费了不少代价；而回溯线性搜索则是找到一个差不多的步长即可。

插值法

• 采用多项式插值法拟合简单函数，然后根据该简单函数估计函数的极值点，这样选择合适步长的效率会高很多。
• 对于以上分析，现在拥有数据为：$x_k$xk​处的函数值$f(x_k)$f(xk​)及其导数$f'(x_k)$f′(xk​)，再加上第一次尝试的步长$\alpha_0$α0​。如果$\alpha_0$α0​满足条件，显然算法退出；若$\alpha_0$α0​不满足条件，则根据上述信息可以构造一个二次近似函数:
  $h_q(\alpha) = \frac{h(\alpha_0)-h'(0)\alpha_0 - h(0)}{\alpha_0^2}\alpha^2 + h'(0)\alpha + h(0)$hq​(α)=α02​h(α0​)−h′(0)α0​−h(0)​α2+h′(0)α+h(0)

二次插值法求极值

显然，导数为0的最优解为：
$\alpha_1 = \frac{h'(0)\alpha_0^2}{2[h'(0)\alpha + h(0) - h(\alpha_0)]}$α1​=2[h′(0)α+h(0)−h(α0​)]h′(0)α02​​
若$\alpha$α 满足Armijo准则，则输出该学习率，否则继续迭代。