LASSO的解法

LASSO非常实用，但由于它的惩罚项不可以常规地进行求导，使得很多人以为它无法显式地求出解析解。但其实并不是这样的。

1 单变量情形：软阈值法

1.1 软阈值的分类讨论

将个样本的真实值记为维向量，将个样本的自变量记为，假设我们已经将自变量做过标准化，即，，这也意味着在LASSO模型中截距项为。系数是要优化的参数，惩罚项参数为。

LASSO就是要求解

忽略常数项后，上式等价于

将损失函数写成分段函数形式：

分类讨论：

• 若，则，在处取到最小值，因此解为；
• 若，则，，且在处有，因此解为；
• 若，则，在处取到最小值，因此解为。

利用软阈值算子（soft-thresholding operator），可将以上三种解统一为

其实在我们的设定下，OLS估计量为，因此，将OLS估计量通过一个软阈值算子的操作，就变成了LASSO估计量。

1.2 次梯度

如果引入次梯度（subgradient）的概念，可以更直接地求解式。设的次梯度为，它的形式是，当时有，当时有。根据凸优化（convex optimization）理论，求解相当于求解

的解。化简后得到，最终同样可以解出。比如时，就意味着。

2 多变量情形：循环坐标下降法

我们来看多变量的完整版LASSO问题。将自变量排成的矩阵，我们要求解的是

在这里，我们使用循环坐标下降法（cyclic coordinate descent），它的思想是，按一定顺序依次对个参数进行优化，比如按的顺序，在第次优化时，保持其他所有系数不变，变动使损失函数最小化。

根据以上思想，我们将第次的最优化目标写为

记，这称为partial residual，那么根据第1.1节中的结果，我们可以得出

记，上式相当于更新规则

由于目标函数是凸的，没有局部的极小值，因此，每次更新一个坐标，最终可以收敛到全局最优解。

Pathwise coordinate descent（逐路径坐标下降）：可以先取一个使的最小的，然后，略微减小的值，并以上一次得到的作为“warm start”，用坐标下降法迭代直到收敛，不断重复这个过程，最终就可以得到在的一系列变化范围内的解。

那么，怎样才能使？利用次梯度，我们可以知道，对于，必有，即要求，若要使整个，则可取，这就是使的最小的。

3 其他解法

求解LASSO还有其他的解法，如homotopy method，它可以从开始，得到序列型的解的路径，路径是分段线性的。

还有LARS（least angle regression）算法，这是homotopy method之一，可以有效得到分段线性路径。

这里不作展开。

4 正交基

在上面的过程中，如果将自变量正交化，可以大大简化计算。如在第2节中，如果自变量之间是正交的，则，此时就是将对做回归的OLS解，通过软阈值算子后的值。