Nestrov优化算法

• 结合动量的方法
• 在随机梯度下降算法中，方向的更新依赖于当前的batch，更新不稳定，所以引入动量
• 在更新的时候保持原方向，然后依据batch的方向，微调；
• 稳定性得到了增强，还可以学习的较快
• 通过nesterov加速

分类

• 无约束凸优化；约束凸优化
• 目标函数是否光滑函数：光滑凸优化和非光滑凸优化

平滑凸函数的一阶算法

• 梯度法
• 共轭梯度法(conjugate gradient method)
• Nesterov最优化法

* 光滑凸函数，处处可导

1. 引论

* 凸性定义

• 凸集
• 凸函数：设C是凸集，若对任意的$u,v\in C$,及$\alpha\in[0,1]$，函数满足：

$f(\alpha x+(1-\alpha)y)\leq \alpha f(x)+(1-\alpha)f(y)$

• 严格凸函数(只是小于，不是小于等于)

$f(\alpha x+(1-\alpha)y)< \alpha f(x)+(1-\alpha)f(y)$

• 强凸函数：($\mu$是凸性参数)

  $f(\alpha x+(1-\alpha) y)\leq \alpha f(y)+(1-\alpha)f(x)-\frac{\mu}{2}\alpha (1-\alpha)||x-y||_2^2$

  $(\bigtriangledown f(x)-\bigtriangledown f(y))^T(x-y)\geq \mu||x-y||_2^2$

  $f(y)\geq f(x)+[\bigtriangledown f(x)]^T(x-y)+\frac{\mu}{2}||y-x||_2^2$

=>强凸函数--->严格凸函数--->凸函数

利普希茨性

• 利普希茨性本事定义在欧式范空间，定义f是$\rho$-利普希茨的：对任意的$w_1,w_2$:

$||f(w_1)-f(w_2)||\leq \rho||w_1-w_2||$

• 利普希茨：变化不会太快

• 利普希茨函数不一定可微，；但是利普希茨连续梯度的函数f(x),一定是光滑函数

• $C_L^{k,p}(Q)$表示具有如下性质的lipschitz连续函数类：

  1. $f\in C_L^{k,p}(Q)$是在Q上可以k次微分
  2. $f\in C_L^{k,p}(Q)$的p阶导数都是lipschitz常数为L的lipschitz连续函数:$||f^{(p)}(x)-f^{(y)}(y)||\leq L||x-y||$

• 函数f(x)是平滑函数，则它可微且导数是利普希茨函数

光滑性

• 一个处处可微的函数称为光滑函数
• 利普希茨连续梯度的函数f(x),一定是光滑函数 $||\bigtriangledown f(v)-\bigtriangledown f(v)||\leq \beta||v-w||$

稳定性

• 若算法输入的一个小的变化不会太多的改变算法的输出，称算法稳定

• 正则化的方法是稳定的，可以作为稳定剂

• condition number是稳定性的度量

• 算法稳定，就不会过拟合

* 收敛速度

• 设序列$\{\delta_i\}$：

$\lim\limits_{i->\infty}\frac{\delta_{i+1}}{\delta_i}=\sigma$

1. $\sigma=0$: 超线性
2. $\sigma=1$: 次线性
3. $\sigma\in (0,1)$:线性

2. Nesterov最优梯度法

Nesterov最优梯度法的理论基础

• 对于强凸函数最优收敛速度是：$o(\frac{1}{k^2})$

• 梯度法是$o(\frac{1}{k})$

动量方法

• 设$p_0,x_0$是两个初始向量，$\alpha_k,\beta_k$是两个正值序列，则求解无约束优化问题:$\min\limits_{x\in R^n}f(x)$的一阶方法可以采用两步更新：

$p_k=-\bigtriangledown f(x_k)+\beta p_{k-1}$

$x_{k+1}=x_k+\alpha_k p_k$

=>当$p_0=0$ =>

$x_{k+1}=x_k-\alpha_k\bigtriangledown f(x_k)+\beta_k(x_k-x_{k-1})$

=>$x_k-x_{k-1}$是动量

• SGD 的优化方法缺点，更新方法完全依赖于当前的batch，因此会不稳定。引入动量方法，模拟物体运动的惯性，在更新时一定程度的保持之前的方向，从而学习的更快，还有一定的摆脱局部的能力

Nesterov最优化算法

* Nesterov适用于：

• 无约束最小化的$min f(x)$,
• f(x)的梯度是lipschitz连续的

* 算法

• 产生两个序列 $\{x_k\}:逼近序列,\{y_k\}：搜索点序列$

$x_k=y_k=\frac{1}{L}\bigtriangledown f(y_k)$

$\alpha_{k+1}=\frac{1}{2}(1+\sqrt{4\alpha^2+1})$

$y_{k+1}=x_k+\frac{\alpha_k-1}{\alpha_{k-1}}(x_k-x_{k-1})$

3. 碎碎念

强凸函数和平滑函数

• Lispchitz连续：大于连续，小于可微
• f(x)具有lispchitz连续梯度
• 实质是投影梯度法和重球法的结合
• 强凸函数的定义：

$f(x)-\frac{1}{2}\sigma ||x||^2$ 是凸函数 =》f(x)需是二阶函数

总结

• 可以证明，一阶方法的最优梯度速度是$O(\frac{1}{k^2})$
• 梯度法是：$O(\frac{1}{k})$