梯度下降

基本概念

这个不赘述了

这儿t是步长。

其思想便是在前点使用二阶近似来拟合邻域，然后在邻域里找部分最小值。二阶近似为f(y)=f(x)+∇f(x)T(y−x)+12t∣∣y−x∣∣22f(y)=f(x)+\nabla f(x)^T (y-x)+\frac{1}{2t}||y-x||_2^2f(y)=f(x)+∇f(x)T(y−x)+2t1​∣∣y−x∣∣22​。这儿把二阶导的Hessen矩阵用t代替了，然后关于y求梯度=0，能够得到$y=x+t\nabla f(x)$。

步长设置

太大会震荡不收敛，太小会练习太慢，怎么选取适宜的步长？

backtracking

初始化t=t0t=t_0t=t0​，每次迭代，假如f(x−t∇f(x))>f(x)−t∣∣∇f(x)∣∣22f(x-t\nabla f(x))>f(x)-\alpha t||\nabla f(x)||_2^2f(x−t∇f(x))>f(x)−t∣∣∇f(x)∣∣22​，则$t=t$，之后梯度下降。这儿\alpha一般是1/2,$0<<1$

这个图很直观，这儿的$x=-\nabla f(x)$（沿着负梯度行进）。实线是实践的函数图，两条虚线是在当时x的线性近似，假如乘\alpha会减缓近似的那条直线下降的速度。这样相当于把近似夹在了一个空间里。假如实线大于了上面那条虚线，那么阐明现在的近似不太对，或许说t有点偏大了，因而shrink一下。

exact 最速下降法

就说前面咱们使用$f(x)$的二阶近似找的，那我直接找最佳能够吗，这个理论上能够但不太实际，即直接找t=arg⁡min⁡s≥0f(x−s∇f(x))t=\arg\min_{s\ge 0}f(x-s\nabla f(x))t=argmins≥0​f(x−s∇f(x))

收敛剖析

先来一个前置知识：李比希次接连 ∣∣f(x)−f(y)∣∣2≤L∣∣x−y∣∣2||f(x)-f(y)||_2\le L||x-y||_2∣∣f(x)−f(y)∣∣2​≤L∣∣x−y∣∣2​

再来一个前置，矩阵的范数，注意它和向量范数有区别。

• p取1时，矩阵的最大列和。
• p取2时，矩阵ATAA^TAATA特征值根号的最大值。
• p取无穷，矩阵的最大行和。

关于凸函数$f$，假如他的一阶导数是李比希次接连，那么∣∣∇f(y)−∇f(x)∣∣2≤L∣∣x−y∣∣2||\nabla f(y)-\nabla f(x)||_2\le L||x-y||_2∣∣∇f(y)−∇f(x)∣∣2​≤L∣∣x−y∣∣2​。

假如是二次可微，则对恣意x它的Hessian矩阵最大特征值不会超越L，因而∣∣∇2f∣∣2<L||\nabla^2 f||_2<L∣∣∇2f∣∣2​<L，所以∇2f(x)≤LI\nabla^2 f(x)\le LI∇2f(x)≤LI，这儿表明半负定。

收敛性剖析的一般思路：
最终方针是要结构一个形如∣f(xk+t)−p∗∣∣f(xk)−p∗∣≤\frac{|f(x^{k+t})-p^*|}{|f(x^k)-p^*|}\le \epsilon∣f(xk)−p∗∣∣f(xk+t)−p∗∣​≤。以此树立t和\epsilon的联系。
关键是lhs怎么结构。这儿一般根据递推结构，即首要结构f(xk+1)f(x^{k+1})f(xk+1)和f(xk)f(x^k)f(xk)的不等联系。
最终剖析收敛程度，横轴是迭代次序，纵轴是log⁡(f(xk)−p∗)\log(f(x^k)-p^*)log(f(xk)−p∗)，看向下的趋势。

重要定理

关于固定的步长$t=1/L$，f(x(k))−f∗≤∣∣x0−x∗∣∣222tkf(x^{(k)})-f^* \le \frac{||x^{0}-x^*||_2^2}{2tk}f(x(k))−f∗≤2tk∣∣x0−x∗∣∣22​​，假如是backtracking的办法，则$t$替换成$/L$即可。

在初始点确认、参数确认的状况下，右侧随着k增大而减小，因而收敛率为$O(1/k)$，从另一个角度看，相当于实现\epsilon-optimal需求$O(1/)$步。

假如函数不仅仅是导数李比希次，还能够强凸(f(x)−m2∣∣x∣∣22f(x)-\frac{m}{2}||x||_2^2f(x)−2m​∣∣x∣∣22​，此刻有∇2f(x)≥mI\nabla^2f(x)\ge mI∇2f(x)≥mI)，那么收敛速度还能够更快，关于固定的$t\le 2/(m+L)$，有

其间$=O(1-m/L)$,这样是指数的速度，换句话说\epsilon-optimal只需求$O(\log (1/))$的复杂度。

这儿弥补一下$p$阶收敛的知识，设e=∣xk−x∗∣e=|x_k-x^*|e=∣xk​−x∗∣表明第k步的绝对误差。lim⁡k→∞ek+1ekp=c\lim_{k\rightarrow\infty} \frac{e_{k+1}}{e_k^p}=climk→∞​ekp​ek+1​​=c建立的p便是收敛阶数。

二次型上的小应用

f()=12(y−X)T(y−X)f(\beta)=\frac{1}{2}(y-X\beta)^T(y-X\beta)f()=21​(y−X)T(y−X)，那么这是一个没有限制条件的二次型凸优化问题

• 先来评论李比希次条件，∇2f()=XTX\nabla^2 f(\beta)=X^TX∇2f()=XTX，因而假如∇2f≤LI\nabla^2 f \le LI∇2f≤LI，则L=max⁡(XTX)L=\lambda_{\max}(X^TX)L=max​(XTX)。
• 再剖析强凸条件，需求确保f(x)−m2∣∣x∣∣22f(x)-\frac{m}{2}||x||_2^2f(x)−2m​∣∣x∣∣22​是凸的，即∇2f≥mI\nabla^2 f\ge mI∇2f≥mI，所以m=min⁡(XTX)m=\lambda_{\min}(X^TX)m=min​(XTX)。因而假如这个矩阵的列数大于行数，一定不满秩，最小特征值为0，那就没发确保强凸了。

停止定理

假如$f$强凸，且参数为$m$，那么∣∣∇f(x)∣∣2≤2m→f(x)−f∗≤||\nabla f(x)||_2\le \sqrt{2m\epsilon}\rightarrow f(x)-f^*\le \epsilon∣∣∇f(x)∣∣2​≤2m​→f(x)−f∗≤

Newton法

前面梯度下降法关于二阶近似直接把hassian矩阵近似掉了。Newton法便是不去近似，直接写出来。即

那么$\nabla f(y)=0$处应该为极小值，所以有

因而y=x−H−1(x)∇fT(x)y=x-H^{-1}(x)\nabla f^T(x)y=x−H−1(x)∇fT(x)。这便是迭代更新公式。能够很明显看到和梯度下降的区别，便是学习率从t的近似变成了hassian矩阵的拟。

假如矩阵是正定的，而且初始值适宜，能够确保二阶收敛。

缺点也很明显：计算Hassian矩阵太复杂，还得求逆（未必有），可能收敛于鞍点。位了确保正定可逆，选用逼迫正定策略，即$H(x)+I$再求逆。

另外最速下降法的思路在这儿一样能够用，便是依然再更新时添加步长，y=x−tH−1(x)∇fT(x)y=x-tH^{-1}(x)\nabla f^T(x)y=x−tH−1(x)∇fT(x)。t=arg⁡min⁡tf(x−tH−1(x)∇fT(x))t=\arg\min_t f(x-tH^{-1}(x)\nabla f^T(x))t=argmint​f(x−tH−1(x)∇fT(x))

应对不行导状况：次梯度法

次梯度

一种梯度概念的推行， 其界说是一个闭区间中的恣意值，区间左右端点分别是左导数和右导数。

例如$f(x)=|x|$，在$x\ne 0$的时候导数很简单求，但在$x=0$处不行导，可是使用次梯度的概念，其次梯度为$[-1,1]$中的任何数。

次微分便是把整个区间看作一个整体。它的性质有：

• 假如可导，次微分便是一个单点即导数。
• 反过来也建立，假如次微分只包含一个单点，那这个单点便是导数。
• 凸函数的次微分非空。
• 最优化条件：f(x∗)=min⁡f(x)⇔0∈∂f(x∗)f(x^*)=\min f(x)\Leftrightarrow0\in \partial f(x^*)f(x∗)=minf(x)⇔0∈∂f(x∗)。即极值点处的次微分包含0。

eg Lasso问题

极值点满足0∈∂(12∣∣y−X∣∣22+∣∣∣∣1)0\in \partial (\frac{1}{2}||y-X\beta||_2^2+\lambda ||\beta||_1)0∈∂(21​∣∣y−X∣∣22​+∣∣∣∣1​)。

分状况评论

• i≠0\beta_i\ne 0i​=0，那么次微分就一个值，满足最优化条件必须得等于0，因而XT(y−Xi)=sgn(i)X^T(y-X\beta_i)=\lambda sgn(\beta_i)XT(y−Xi​)=sgn(i​)
• 关于i=0\beta_i=0i​=0的状况，那么此刻绝对值的次微分为$[-1,1]$，为了让0在整个loss的次微分里，需求满足−XT(y−Xi)−≤0-X^T(y-X\beta_i)-\lambda\le0−XT(y−Xi​)−≤0 且−XT(y−Xi)+≥0-X^T(y-X\beta_i)+\lambda\ge0−XT(y−Xi​)+≥0，即∣∣XT(y−Xi)∣∣≤||X^T(y-X\beta_i)||\le \lambda∣∣XT(y−Xi​)∣∣≤

在$X=I$的状况下，上面的两个状况简化为

• yi−i=sgn(i),i≠0y_i-\beta_i=\lambda sgn(\beta_i), \beta_i \ne 0yi​−i​=sgn(i​),i​=0
• ∣yi−i∣≤,i=0|y_i-\beta_i|\le \lambda, \beta_i =0∣yi​−i​∣≤,i​=0

测验求出\beta，假如i\beta_ii​的解为0，那意味着∣yi∣≤|y_i|\le \lambda∣yi​∣≤，否则，yi−i=sgn(i)y_i-\beta_i=\lambda sgn(\beta_i)yi​−i​=sgn(i​)，因而i=[S(y)]i\beta_i=[S_\lambda(y)]_ii​=[S​(y)]i​

• yi−,(yi>)y_i-\lambda, (y_i > \lambda)yi​−,(yi​>)
• 0,(∣yi∣≤)0, (|y_i|\le \lambda)0,(∣yi​∣≤)
• yi+,(yi<−)y_i+\lambda, (y_i <-\lambda)yi​+,(yi​<−)。

形状类似阶梯型。被称为软阈值。

次梯度法

适用于凸的未必可微函数。便是梯度下降的梯度替换成了次梯度，替换办法便是从次微分区间里任选一个值。还要注意次梯度并不确保每次都下降，因而不能只记载当时值，还得保护最优值。

步长能够定长或衰减，可是不能应用最速下降。收敛率为O(1/2)O(1/\epsilon^2)O(1/2)，慢于梯度下降。

应对不行导：proximal gradient

近端梯度也是一种应对不行导的办法。 考虑凸优化问题$f(x)=g(x)+h(x)$，咱们把优化方针拆分成两块，其间$g$是凸且可微的，$h$凸不行微，但他是闭函数（sublevel test凸）。

在这种状况下，咱们发现其实即便只要$g$的梯度也能够找到一个适宜的优化方向。即xk=proxtk,h(xk−1−tk∇g(xk−1))x^k=prox_{t_k,h}(x^{k-1}-t_k\nabla g(x^{k-1}))xk=proxtk​,h​(xk−1−tk​∇g(xk−1))。

首要清晰符号表明proxtk,h(n(x))=arg⁡min⁡u{h(u)+12tk∣∣u−n(x)∣∣22}prox_{t_k,h}(n(x))=\arg\min_u \{h(u)+\frac{1}{2t_k}||u-n(x)||_2^2\}proxtk​,h​(n(x))=argminu​{h(u)+2tk​1​∣∣u−n(x)∣∣22​}。

然后把前面说的proxtk,h(xk−1−tk∇g(xk−1))prox_{t_k,h}(x^{k-1}-t_k\nabla g(x^{k-1}))proxtk​,h​(xk−1−tk​∇g(xk−1))带入看

这儿前四行都很简单，到第5行的代换，是由于外面是关于u的argmin，这阐明所有和u无关的项都能够随意替换。于是替换凑成了一个关于g在xk−1x^{k-1}xk−1的二阶Taylor展开。

上面的推导阐明使用prox选取的xkx^kxk能够让原问题进一步变小。然后重新写一下迭代式

步长选择tkt_ktk​，能够固定，也能够使用线性查找，不断衰减$t=t$直到g(x−tGt(x))g(x-tG_t(x))g(x−tGt​(x))不超越$g(x)$的二阶近似值。这个很奇特，$g$括号里边便是下一步的x值，咱们只要求这个值在g函数上是减小的，丝毫没考虑h，就能够确保迭代收敛了。

应对不行导：坐标下降法

关于$f(x)$能够写成g(x)+∑h(xi)g(x)+\sum h(x_i)g(x)+∑h(xi​)的状况，g是可微凸函数，h是凸的。

使用坐标下降求最小值，关于x0=(x10,…,xn0)x^0=(x_1^0,…,x_n^0)x0=(x10​,…,xn0​)，先固定n-1个维度，把其间一个维度作为变量，求最小。这一步由于只要一个变量，所以一维查找或许求导很简单得到。

求完再求第二个维度，以此类推，得到x1=(x11,…,xn1)x^1=(x_1^1,…,x_n^1)x1=(x11​,…,xn1​)。直至两次迭代的坐标点距离很近。

坐标下降的顺序恣意、关键是一次一个坐标更新，否则可能不收敛。能够把恣意一个坐标推行成一部分坐标。假如是悉数坐标那便是梯度下降。