matlab - L1-Regularized系统的最小化，收敛于非最小位置？

Question

这是我在 stackoverflow 上的第一篇文章，所以如果这不是正确的区域，我深表歉意。我正在致力于最小化 L1 正则化系统。

这个周末是我第一次深入优化，我有一个基本的线性系统 Y = X*B，X 是一个 n-by-p 矩阵，B 是一个 p-by-1 模型系数向量，Y 是一个n×1 输出向量。

我试图找到模型系数，我已经实现了梯度下降和坐标下降算法来最小化 L1 正则化系统。为了找到我正在使用回溯算法的步长，我通过查看梯度的 norm-2 并在它“足够接近”到零(目前我使用的是 0.001)时终止算法来终止算法。

我试图最小化的函数是以下 (0.5)*(norm((Y - X*B),2)^2) + lambda*norm(B,1)。 (注意:norm(Y,2) 我指的是向量 Y 的 norm-2 值)我的 X 矩阵是 150×5 并且不稀疏。

如果我将正则化参数 lambda 设置为零，我应该会收敛于最小二乘解，我可以验证我的两个算法都非常好且相当快地完成了这一点。

如果我开始增加 lambda，我的模型系数都趋向于零，这是我所期望的，但我的算法永远不会终止，因为梯度的 norm-2 总是正数。例如，1000 的 lambda 会给我 10^(-19) 范围内的系数，但我的梯度的 norm2 是~1.5，这是在几千次迭代之后，而我的梯度值都收敛到 0 到 1 之间范围，我的步长变得非常小(10 ^(-37)范围)。如果我让算法运行更长时间，情况并没有改善，它似乎不知何故陷入困境。

我的梯度下降算法和坐标下降算法都收敛于同一个点，并为终止条件给出相同的 norm2(gradient) 数。它们在 lambda 为 0 的情况下也能很好地工作。如果我使用一个非常小的 lambda(比如 0.001)我会收敛，一个 0.1 的 lambda 看起来如果我运行它一两个小时它就会收敛，一个更大的 lambda 和收敛速度太小了，没用。

我有几个我认为可能与问题相关的问题？

在计算梯度时，我使用的是有限差分法 (f(x+h) - f(x-h))/(2h))，h 为 10^(-5)。对这个 h 值有什么想法吗？

另一个想法是，在这些非常小的步长上，它在几乎与最小值正交的方向上来回移动，使得收敛速度如此之慢以至于毫无用处。

我最后的想法是，也许我应该使用不同的终止方法，也许看看收敛速度，如果收敛速度非常慢则终止。这是一种常见的终止方法吗？

Answer 1

1-范数不可微分。这将导致很多事情出现根本性问题，尤其是您选择的终止测试；梯度将在您的最小值附近急剧变化，并且在一组测量零上不存在。

您真正想要的终止测试将遵循“subgradient 中有一个非常短的向量。”

在 ||Ax-b||_2^2 + lambda ||x||_1 的子梯度中找到最短向量相当容易。明智地选择公差 eps并执行以下步骤:

1. 计算 v = grad(||Ax-b||_2^2).

2. 如果 x[i] < -eps , 然后从 v[i] 中减去 lambda .如果x[i] > eps , 然后将 lambda 添加到 v[i] .如果-eps <= x[i] <= eps , 然后添加 [-lambda, lambda] 中的数字至 v[i]最小化 v[i] .

您可以在这里进行终止测试，处理 v作为梯度。我还建议使用 v选择下一次迭代的位置时的梯度。