梯度下降法简介
Steepest descent follows from minimising the $1^{\text {st }}$ order laylor
$$
f(x+\alpha d) \leq f(x)+\alpha \nabla f(x)^{T} d+\alpha^{2} \frac{L}{2}|d|^{2}
$$
Proof:
$$
\begin{aligned}
f(x+\alpha d) &=f(x)+\alpha \nabla f(x)^{T} d+\alpha\left[\int_{0}^{1} \nabla f(x+\eta \alpha d)-\nabla f(x) d \eta\right]^{T} d \
& \leq f(x)+\alpha \nabla f(x)^{T} d+\alpha\left[\int_{0}^{1}|\nabla f(x+\eta \alpha d)-\nabla f(x)| d \eta\right]|d|_{2} \
& \leq f(x)+\alpha \nabla f(x)^{T} d+\alpha|d|_{2} \int_{0}^{1} L \alpha|d|_{2} \eta d \eta
\end{aligned}
$$
Step-length $\alpha_{k}=L^{-1}$ for $d=-\nabla f(x)$ by minimising the upper bound $f(x)+\alpha \nabla f(x)^{T} d+\alpha^{2} \frac{L}{2}|d|^{2}$ over $\alpha:$ setting its derivative to zero $\nabla f(x)^{T} d+\alpha L|d|^{2}=0$ and solving for $\alpha$.
Corollary
( $f$ sufficient decrease): Steepest descent, $x^{k+1}=x^{k}+\alpha_{k} \phi^{k}$ with $\phi^{k}=-\nabla f\left(x^{k}\right)$ and $\alpha=L^{-1}$ satisfies
$f\left(x^{k+1}\right)=f\left(x^{k}-L^{-1} \nabla f\left(x^{k}\right)\right) \leq f\left(x^{k}\right)-\frac{1}{2 L}\left|\nabla f\left(x^{k}\right)\right|_{2}^{2}$
Convergence of steepest descent:
- Sublinear with rate $\mathcal{O}\left(k^{-1 / 2}\right)$ for general $f$
$\mathbf{-}$ Sublinear with rate $\mathcal{O}\left(k^{-1}\right)$ for $f$ convex, - $Q$ -Linear with rate $1-\gamma / L$ for $f \gamma$ -strongly convex.
Theorem 1 (SD convergence for $f$ general): If $f$ is bounded below by $\bar{f}$, then steepest descent with $\alpha_{k}=L^{-1}$ satisfies
$$
\min {0 \leq k \leq T-1}\left|\nabla f\left(x^{k}\right)\right|{2} \leq\left(\frac{2 L\left(f\left(x^{0}\right)-\bar{f}\right)}{T}\right)^{1 / 2} \quad \forall T \geq 1
$$
$$
\sum_{k=0}^{T-1}\left|\nabla f\left(x^{k}\right)\right|_{2}^{2} \leq 2 L \sum_{k=0}^{T-1}\left[f\left(x^{k}\right)-f\left(x^{k+1}\right)\right]=
$$
$2 L\left[f\left(x^{0}\right)-f\left(x^{T}\right)\right]$
and
$$
\min {0 \leq k \leq T-1}\left|\nabla f\left(x^{k}\right)\right| \leq\left(\frac{1}{T} \sum{k=0}^{T-1}\left|\nabla f\left(x^{k}\right)\right|^{2}\right)^{1 / 2} \leq\left(\frac{2 L\left(f\left(x^{0}\right)-\bar{f}\right)}{T}\right)^{1 / 2}
$$
$$
\sum_{k=0}^{T-1} f\left(x^{k+1}\right)-f\left(x^{}\right) \leq \frac{L}{2} \sum_{k=0}^{T-1}\left(\left|x^{k}-x^{}\right|_{2}^{2}-\left|x^{k+1}-x^{}\right|_{2}^{2}\right) \leq \frac{L}{2}\left|x^{0}-x^{}\right|_{2}^{2}
$$
We then use that $f\left(x^{T}\right) \leq f\left(x^{k+1}\right)$ for $k \in[0, T-1]$ and the above bound to achieve
$$
f\left(x^{T}\right)-f\left(x^{}\right) \leq T^{-1} \sum_{k=0}^{T-1}\left(f\left(x^{k+1}\right)-f\left(x^{}\right)\right) \leq \frac{L}{2 T}\left|x^{0}-x^{*}\right|_{2}^{2}
$$
Theorem 3 (SD convergence for convex $f \gamma$ -strongly convex $):$ If $f$ is $\gamma$ -strongly convex there there exists a unique minimiser $x^{}$ and $f\left(x^{k+1}\right)-f\left(x^{}\right) \leq(1-\gamma / L)\left(f\left(x^{k}\right)-f\left(x^{*}\right)\right)$ for all $k$
Proof: Strong convexity and Proposition 2 gives
$$
f(y) \geq f\left(x^{k}\right)+\nabla f\left(x^{k}\right)^{T}(y-x)+\frac{\gamma}{2}\left|y-x^{k}\right|_{2}^{2}
$$
Therefore $\min {y} f(y)$ is bounded below by the minimiser of the above lower bound, which has minimiser $y^{}=x^{}-\gamma^{-1} \nabla f\left(x^{k}\right)$
$$
\begin{aligned}
f\left(x^{}\right) & \geq \min {y} f(y) \geq f\left(x^{k}\right)+\nabla f\left(x^{k}\right)^{T}\left(y^{}-x^{}\right)+\frac{\gamma}{2}\left|y^{}-x^{}\right|_{2}^{2} \ & \geq f\left(x^{k}\right)-\frac{1}{2 \gamma}\left|\nabla f\left(x^{k}\right)\right|_{2}^{2} \end{aligned} $$ and consequently $\left|\nabla f\left(x^{k}\right)\right|_{2}^{2} \geq 2 \gamma\left(f\left(x^{k}\right)-f\left(x^{}\right)\right)$. Corollary 1
$$
\text { then gives } f\left(x^{k+1}\right)-f\left(x^{}\right) \leq f\left(x^{k}\right)-f\left(x^{}\right)-\frac{\gamma}{L}\left(f\left(x^{k}\right)-f\left(x^{*}\right)\right)
$$
(P) $\min {x} f(x) \quad$ subject to $x \in \mathcal{F}$ Subject to $f$ smooth with $\nabla f(x)$ being $L$ -Lipschitz continuous. Line-search methods iterative update estimates $x^{k}$ of the minimiser $$ x^{k+1}=x^{k}+\alpha{k} \phi^{k}
$$
with $\alpha_{k}$ the step length and $\phi^{k}$ the search direction. Steepest descent methods use some form of the negative gradient as the search direction, $\phi^{k}=-\nabla f\left(x^{k}\right)$, and can use step-length $\alpha_{k}=L^{-1}$
Steepest descent follows from minimising the $1^{s t}$ order Taylor
$$
f(x+\alpha \phi) \leq f(x)+\alpha \nabla f(x)^{T} \phi+\alpha^{2} \frac{L}{2}|\phi|^{2}
$$
$$
\begin{aligned}
f(x+\alpha \phi) &=f(x)+\alpha \nabla f(x)^{T} \phi+\alpha\left[\int_{0}^{1} \nabla f(x+\eta \alpha \phi)-\nabla f(x) \phi \eta\right]^{\top} \phi \
& \leq f(x)+\alpha \nabla f(x)^{T} \phi+\alpha\left[\int_{0}^{1}|\nabla f(x+\eta \alpha \phi)-\nabla f(x)| \phi \eta\right]|\phi|_{2} \
& \leq f(x)+\alpha \nabla f(x)^{T} \phi+\alpha|\phi|_{2} \int_{0}^{1} L \alpha|\phi|_{2} \eta \phi \eta
\end{aligned}
$$
Step-length $\alpha_{k}=L^{-1}$ for $\phi=-\nabla f(x)$ by minimising the upper bound $f(x)+\alpha \nabla f(x)^{T} \phi+\alpha^{2} \frac{L}{2}|\phi|^{2}$ over $\alpha$ : setting its derivative to zero $\nabla f(x)^{T} \phi+\alpha L|\phi|^{2}=0$ and solving for $\alpha$.
梯度下降法中的步长
对于SGD，普通的line searchi一丨<__CJKFIN__>算量太大根本不可能。目前没有非常成熟的办法，实际中还是靠手 动调步长。当然，最近几年也有一些工作:
最有名的是AdaGrad和改进版的AdaDelta, 这两个方法有用，至少可以确保收玫，但速度上不够 好，远不如手动调的最好步长，特别迭代次数多了之后。当然他们的优点就是在不怎么要手动调 参、基本不用额外计算量的情况下收敘的还可以。
[4] 中有提出过一种简化版line search方法。这种方法每轮迭代只用一个子函数做一次line search 来估计Lipschitz常数 $L$, 然后选择理论上最好的步长，比如说 $1 / L$, 这样相对计算量还可以接受
了。但这个方法有两个问题：一是只能用在SAG、SVRG这种固定步长能保证收敘的算法上，原始 的SGD不行; 第二就是, 就算知道了 $L$, 但实际中最佳步长和理论最佳往往差了很远。但总的来 说, 根据我实验观察, 这是种比较靠谱的方法。
[5] 提出了一种probabilistic line search。基本思想就是在每个迭代点计算一个子函数的值，然戌 用Gaussian Process来做拟合，给出目标函数在每个的估计值，然后利用这个估计值来做line search。我自己没有亲自实验过这种方法，但个人感觉就是计算量仍然偏大 (除了每次迭代要计算 个函数值, 还要要不断计算和更新一个Gaussian process)，而且感觉不一定能收数。
[6] 是做SGD步长估计的，几个月前才出炉的paper。大概思想是假设步长服从某个简单的函数，比 如 $C / k$ (因为SGD需要diminishing的步长来保证收敘) , 这儿 $k$ 是指第几轮迭代, $C$ 是某个我 们要估计的常数。然后在每轮迭代的时候用online梯度下降的方法更新下对 $C$ 的估计。但是这篇 paper实验做的巨简单无比，不太清楚这个方法到底盾样。
1) 一般的凸的、连续可导的情况下，我喜欢采用 Goldstein-Armijo rule 的方法来寻找步长。这类 似于一个ine-search, 只是line search寻找的是 stepsize $=\arg \min {h \geq 0} f\left(x{k}-h \nabla f\left(x_{k}\right)\right)$
我们只找一个能让函数值下降到一阶近似一定比例的情况即可. 这类方法对有约東的凸问题都适用。
2) 一般的凸的、连续可导的情况下，还有一种很好的方法叫bb-rule, 这种方法也非常快，缺点是 不能保证函数单调下降，我试过与1) 一起使用效果还不错。
还有一些其它寻找梯度的经典方法, 比如steepset descent
对于凸的，一阶可导的，梯度Lipschitz-continuous问题, 如eta li所说。要看梯度的Lipschitz constant是多少，假设为L, 我们需要步长<=1/L才能保证函数收玫。 $\quad$ (但是我们可以用1)中所述方 法来寻找一个不那么保守的步长来减小迭代步数) 如果strongly convex constant 和Lipschitz constant都能确定的特殊条件下，我比较建议用一阶 方法 (梯度下降这类的) 先让函数收敘到牛顿法的邻域之内，在用LBFGS这类方法，然后就能很快 收敘了。
梯度下降法的收敛性
梯度下降法(SGD)做为主流的优化算法，很多后来的优化算法都是基于此进行的改良比如Adam 梯度下降法在强凸函数上是会严格收敘到最小值的, 一般来讲SGD算法对应的优化问题如下
$\min f(x)$
对于强凸函数也就是(凸函数的定义就是二阶Hessian矩阵半正定比强凸条件宽松一点)
$\exists m>0, \nabla^{2} f(x)-m I \succeq 0$
这里的 $A \succeq 0$ 代表A是半正定矩阵
为了方便表示, 有以下假设
$\exists M>0, M I-\nabla^{2} f(x) \succeq 0$
对于强凸函数根据上述假设有以下不等式(对于f( $(\mathrm{y})$ 泰勒展开后将二阶梯度矩阵替换 $)$
$f(y) \geq f(x)+\nabla f^{T}(x)(y-x)+\frac{|y-x|_{2}^{2}}{2 m}$ (1)
对于y的函数 $H(y)=f(x)+\nabla f^{T}(x)(y-x)+\frac{|y-x|_{2}^{2}}{2 m}$ 是凸函数
对于H $(\mathrm{y})$ 的求导为0有 $\nabla f(x)+m(y-x)=0 \Rightarrow y=x-\frac{\nabla f(x)}{m}$
所以有 $\forall y, H(y) \geq f(x)-\frac{|\nabla f(x)|_{2}^{2}}{2 m}$
不妨设 $f\left(x^{*}\right)=p=\min f(x)$ 于是我们有
$p+\frac{|\nabla f(x)|_{2}^{2}}{2 m} \geq f(x) \geq p$
同样的泰勒展开有 $f(y) \leq f(x)+\nabla f^{T}(x)(y-x)+\frac{|y-x|_{2}^{2}}{2 M}$ (
对于梯度下降法每一步x的卒化是 $x^{k+1}=x^{k}-\alpha \nabla f\left(x^{k}\right)$ 由@式有以下不等式
$U(\alpha)=f\left(x^{k+1}\right) \leq f\left(x^{k}\right)-\alpha\left|\nabla f\left(x^{k}\right)\right|_{2}^{2}+\frac{M \alpha^{2}\left|\nabla f\left(x^{k}\right)\right|_{2}^{2}}{2}$
上述关于 $\alpha$ 的二次函数当 $\alpha=\frac{1}{M}$ 时最小, 代入这个值有
$f\left(x^{k+1}\right) \leq f\left(x^{k}\right)-\frac{\left|\nabla f\left(x^{k}\right)\right|_{2}^{2}}{2 M}$
将 $x^{k}$ 代入(2中有
$f\left(x^{k}\right)-\frac{\left|\nabla f\left(x^{k}\right)\right|_{2}^{2}}{2 m}-p \leq 0$
对于(4式变形有
$f\left(x^{k+1}\right)+\frac{\left|\nabla f\left(x^{k}\right)\right|_{2}^{2}}{2 M}-p \leq f\left(x^{k}\right)-p$ @
合并M* $(\mathrm{G})+\mathrm{m}^{*}{(6)}$ 有
$f\left(x^{k+1}\right)-p \leq\left(1-\frac{m}{M}\right)\left(f\left(x^{k}\right)-p\right)$
所以可知梯度下降法必定以指数方式收敘到最小值
收鋒满足的条件为强凸函敕且有界, 同时 $\alpha=\frac{1}{M}$
很多时候我们并不知到M的值, 这时可以通过一种Amijo rule的方式去解巴设定 $\alpha$ 的问题
Steepest Descent
