梯度下降

梯度与方向导数

方向导数，注意并不只是沿着坐标轴方向，而是任意方向上求导。

上升最快的方向导数，即是梯度。

如何直观形象的理解方向导数与梯度以及它们之间的关系

梯度下降

求最小值时的解，很难直接写出解析解，改用沿着下降方向的前进，找到最小值。有几点：

• 下降方向：比如负梯度，牛顿方向

• 停止条件：函数值变化很小，梯度趋近于0， 设置最大迭代次数

• 前进的步长

梯度下降选的就是负梯度方向，就是下降充要条件：$\nabla f(x^k)^T d^k \le 0$ 选L2范数时，这个值最小。若选L1范数，则方向是梯度最大分量的反方向，就是最速下降法。

过程： 1. 设置初始步长$t \gt 0$，容许度$0 \lt \alpha \lt 1$，折半因子$0 \lt \beta \lt 1$ ，尝试次数$k=1$，最大尝试次数$k_{max}$, 2. 获取搜索方向d，这里可以为负梯度，牛顿方向 3. 尝试$w^{new} \leftarrow w + td ; k \leftarrow k+1$,计算$L(w^{new})$ 4. 如果$L(w) - L(w^{new}) \lt t*\alpha |<d,\nabla L(w)>|$ 或者$k \ge k_{max}$,跳出，返回$w^{new},L(w^{new})$ ;否则，减小步长：$t \leftarrow \beta t$跳到3.

line search

line search可以用来搜索任何下降方向的可行步长。 $f(x^k + t^k d^k) = \min_t f(x^k + t d^k)$ 有精确直线搜索和非精确直线搜索

注意精确直接搜索,新点处的梯度与搜索方向垂直。 $\nabla f(x^{(k+1)}) \bot \nabla f(x^{(k)})$ 这也是为什么梯度下降会出现锯齿状。

证明：

$$\min_t f(x^k + td^k) \\ {d^k}^T \nabla f(x^k + t^k d^k) =0 \\ {d^k}^T d^{k+1}=0$$

wolfe条件

1. 直线搜索停止条件Armijo Condition： $L(w+td) \le L(w) + \alpha*t*\nabla L(w)^T d$

   函数值需要充分下降

2. Curvature条件： $\nabla L(w+td)^T d \gt \eta \nabla L(w)^T d ; 0 \lt \alpha \lt \eta \lt 1$

   函数下降的情况下步长尽可能的长

这两个条件合起来成为wolfe条件，可推导迭代优化的收敛性

缺点：收敛速度慢，需要迭代轮数过多

收敛性分析

$\left \| \nabla f(x) \right \|_2 \leqslant \epsilon$ 这是一般梯度下降的停止条件之一。

$||x_{k+1} - x||_Q^2 \le (\frac {\lambda_n - \lambda_1}{\lambda_n + \lambda_1})^2 ||x_k - x||_Q^2$

梯度下降的数据由二次型矩阵的最大和最小特征值比值确定著作权归作者所有。这两个值越接近，收敛越快。特别的，若它们相等（意味着所有等高线都是正圆），一次迭代即可收敛。

所以，feature scaling会 使gradient descent的收敛更好。

feature scaling?减去均值，再除以标准差？

凸优化里面有探讨过这个问题, 具体证明可参考一般的凸优化课本. 想补充的一点是, 这也是Newton's method优于gradient descent的一个方面. Newton's method是affine invariant的, 就是收敛速度不受坐标系变换影响。

但是用adaptive gradient descent就没这个问题了。

参考佳文

为什么feature scaling会 使gradient descent的收敛更好? Gradient Descent, Wolfe's Condition and Logistic Regression The vanishing gradient problem

为什么梯度反方向是函数值下降最快的方向？