深刻理解线性回归
前言我们往往使用梯度下降求解线性回归问题，但该优化方法的收敛速度并不是最快的。
本文将介绍一种收敛速度更快的优化算法——FISTA，它改进了近端梯度算法ISTA，将收敛速度从o（1/k）提升至o（1/k^2）。此外，本文将证明FISTA的收敛速度。
背景介绍
假设我们要求解一个回归问题
A和b已知，w是噪音，要求x。A是矩阵，x和b是向量。
我们可以使用最小二乘法求解该问题，得到一个闭式解。
然而，如果A是病态矩阵、奇异矩阵，最小二乘法就失效。
我们可以引入正则化项，例如l1范数，问题变为：
我们有很多方法求解该优化问题
a. 内点法
该问题可以使用内点法解决，但该方法的时间复杂度为O(N^3)
b. 梯度下降
所以我们往往用基于梯度的方法解决
最朴素的方法是梯度下降，但是我们的优化函数并不处处可导，无法直接用梯度下降求解，所以我们使用近端梯度下降法求解，例如ISTA。
此外，梯度下降的速度容易受学习率/迭代步长影响，而ISTA则几乎没有这一问题。
c.近端梯度下降、ISTA
近似梯度算法使用二阶泰勒展开近似x_k-1附近的函数值，在梯度下降的每一步迭代中，将点xk-1处的近似函数的最小值点作为下一次迭代的起始点xk
每一次近端梯度下降的过程中都因为L1范数求导的原因要用到软阈值分析，因此这整个过程被称为迭代软阈值算法（Iterative Shrinkage Thresholding Algorithm, ISTA）。
ISTA算法分为固定步长和带回溯两种。
固定步长的ISTA的缺点是：Lipschitz常数L(f)不一定可知或者可计算。例如，L1范数约束的优化问题，其Lipschitz常数依赖于ATA的最大特征值。而对于大规模的问题，非常难计算。因此，使用以下带回溯（backtracking）的ISTA，它基于过去的L，计算当前的L，使得L的计算量大大减少。
d.FISTA算法
理论证明，ISTA的收敛速度为O(1/k)；
而本文提出了新的优化算法FISTA，它的收敛速度为O(1/k^2)，这是本文的重要贡献。
作者假设了一些条件，建立了分析框架，在此框架内，证明ISTA算法的收敛速度为O（1/k），FISTA算法的收敛速度为O(1/k^2)，这也是本文的重要贡献。
下文将对这些贡献进行介绍。
问题定义、数学符号
为了得出更具普遍性的结论，我们将lasso回归抽象成如下优化问题：
其中，g(x)是一个连续、不一定光滑的凸函数，例如l1范数
f(x)是一个连续、光滑的凸函数，并且具有李普希兹常数L(f)：
在这种设定下，F（x）在点y处的二阶近似为
近似函数的极小值点是：
进行一些简单运算，并忽略常数项，极小值点是：
基于以上推导，我们可以得到ISTA的迭代公式：
其中L是迭代步长。
引理
作者准备了几条引理，这不仅有助于ISTA算法的分析，也有助于后续FISTA新算法的分析 。
（1）引理一
（2）引理二
该引理主要针对g(z)不可导的情况，在该情况下，只需要从g（z）的次梯度中选择一个梯度，使得2.8式成立。
（3）引理三
该引理非常重要，后续关于收敛率的证明都用到了该引理。
该引理的证明主要依据凸函数的性质、PL()函数和Q()函数的定义、引理2.2，此处不详细介绍
对ISTA算法的分析
ISTA算法流程
在本节中作者给出了ISTA算法的收敛率。在此之前，我们先给出ISTA的算法流程，算法的大致思想已经在“背景介绍”中提及。
（1）固定步长方法
该方法需要计算李普希兹常数，即A^T A的最大特征值，该操作很耗时，所以我们往往采用带回溯的方法，简化L_k的计算。
（2）回溯方法
ISTA的收敛速度
随后作者给出了一个比较重要的结论——ISTA算法的收敛速度。
值得一提的是，同时期的其他工作也给出了该结论，不过，这些工作的假设条件，以及最终的收敛公式并不完全相同。并且作者的核心目标并不是证明ISTA的收敛速度，而是证明自己提出的FISTA的收敛速度。只不过，对于ISTA的证明，至少能够侧面体现出作者的假设条件、分析框架的合理性。
该收敛速度的证明用到了引理2.3，分别将x=x*, y=x_n和x=x_n, y=x_n带入该引理的不等式中，并进行一些数学变换（线性组合），即可证明，此处不详细介绍。
FISTA算法
ISTA算法的收敛速度是o(1/k)，而FISTA算法的收敛速度为o（1/k^2）
在这篇工作之前，已经有其他工作提出，在无约束的条件下，存在一种基于梯度的优化算法，收敛速度能达到o（1/k^2），并且该工作在每轮迭代中的梯度计算次数不变，仅仅额外计算了一个点。
作者借鉴了该工作，提出了FISTA优化算法，它可以使有约束问题的收敛速度也达到o（1/k^2），这显然是比ISTA算法快很多的。
算法流程
在固定步长的情况下，FISTA和ISTA的主要差别在于p_L算子并不直接作用在x_k-1上，而是作用在y_k上，而y_k则是x_k-1，x_k-2的简单的线性组合。
FISTA仅仅多计算了t_k和y_k序列，这意味着每一次迭代的计算量几乎不变，p_L算子占用了主要计算量。
与上面的分析类似，李普希兹常数的计算比较耗时，所以FISTA也有“带回溯”版本的算法：
引理
（1）引理4.1
在分析FISTA的收敛率之前，我们再给出几个引理，这些引理的证明，又基于之前提出的引理，尤其是引理2.3
迭代算法会产生x_k序列和t_k序列，该引理刻画了这两个序列的关系.
该引理的证明用到了之前提到的引理2.3，分别将x=x_k，y=y_k+1和x=x*，y=y_k+1带入该不等式，得到两个不等式
随后对这两个不等式线性组合：
进一步的推导要求t_k序列满足
（这也是FISTA算法中4.2式的来源）
在tk满足该关系后，我们得到了：
随后使用毕达哥拉斯关系进行推导：
将其中的a、b、c赋予相应的值
我们得到：
不等号左边第一个式子就是uk+1，我们希望第二个式子是uk，所以我们定义：
这样一来，第二个式子就是uk了。该定义也解释了FISTA算法中式4.3的由来
随后经过一些基本数学计算，引理得证。
（2）引理4.2
ak+bk是递减的，ak和bk是正数，所以ak一定小于等于c
（3）引理4.3
从tk的迭代公式可以看出，该引理显然成立
收敛率
随后作者给出并证明了FISTA的收敛率，它是o（1/k^2）的
证明
首先将引理4.1带入到引理4.2中，可以得到：
我们先假设a1+b1<=c，展开一些推导，最后证明a1+b1<=c
在该假设成立的情况下，ak<c成立，将刚刚得到的ak、c带入，得到：
不等式变换一下得到：
我们易知Lk有上下界：
将Lk带入，最终就得到了我们的收敛率：
最后，我们还需要证明a1+b1<=c成立。此处的证明依然用到了引理2.3，将x=x*，y=y1代入2.3的不等式，再经过简单运算，即可完成证明。
总结
作者在图片去模糊任务上比较了不同算法，FISTA的收敛速度显著快于其它算法。
本文分析了ISTA的收敛速度，提出了新算法FISTA，将收敛速度从o（1/k）提高至o（1/k^2）。
随后分析了FISTA的收敛速度，并在下游任务上进行了实验比较，证明了FISTA的有效性。
页:
[1]