深刻理解线性回归 - 优化算法 - FISTA论文精读

前言

我们往往使用梯度下降求解线性回归问题，但该优化方法的收敛速度并不是最快的。

本文将介绍一种收敛速度更快的优化算法——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

（编辑：上海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!