L1-Regularized系統最小化，收斂於非最小位置？

Question

這是我的第一篇文章到stackoverflow，所以如果這是不正確的領域，我表示歉意。我正致力於最小化L1正則化系統。

這個週末是我第一次潛入優化，我有一個基本的線性系統Y = X * B，X是一個n×p矩陣，B是一個p×1的模型係數矢量，Y是一個n乘1的輸出向量。

我想找到模型係數，我已經實現了梯度下降和座標下降算法，以最小化L1正則化系統。爲了找到我的步長，我使用了回溯算法，我通過查看梯度的2範數終止算法，並終止如果'足夠接近'到零（現在我使用0.001）。我試圖最小化的函數是下面的（0.5）*（norm（（Y-X * B），2）^ 2）+ lambda * norm（B，1）。 （注：根據範數（Y，2）我的意思是向量Y的範數2值）我的X矩陣是150乘5，並且不是稀疏的。

如果我將正則化參數lambda設置爲零，我應該收斂在最小二乘解上，我可以驗證這兩個算法都能很好地完成這項工作。

如果我開始增加lambda我的模型係數都傾向於零，這是我所期望的，我的算法從不終止，因爲梯度的常模-2總是正數。例如，一個1000的λ可以給我10 ^（ - 19）範圍內的係數，但是我的梯度norm2是〜1.5，這是在幾千次迭代之後，而我的梯度值都收斂到0到1之間的某個值範圍內，我的步長變得非常小（10 ^（ - 37）範圍）。如果我讓算法運行時間更長，情況並沒有改善，它似乎陷入了某種程度。

我的梯度和座標下降算法都收斂在同一點上，並給出終止條件相同的norm2（梯度）數。如果我使用一個非常小的lambda（比如說0.001），我會得到收斂性，如果我運行它一兩個小時，lambda會更大，並且收斂速度如此之小，毫無用處。

我有幾個問題，我認爲可能與問題有關？

在計算梯度時，我使用h（10 ^（ - 5））的有限差分法（f（x + h） - f（x-h））/（2h））。有關這個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]減去拉姆達。如果x[i] > eps，則將lambda添加到v[i]。如果-eps <= x[i] <= eps，然後將[-lambda, lambda]中的數字添加到v[i]，最大限度地減少v[i]。

您可以在此處進行終止測試，將v作爲漸變處理。我還建議在選擇下一次迭代的位置時使用v作爲漸變。