Lasso 回歸的時間複雜度是多少？

隨著行數或列數的增加，Lasso 回歸的漸近時間複雜度是多少？

回想一下，lasso 是一個線性模型，具有正則化。

尋找參數可以表述為一個無約束的優化問題，其中參數由下式給出

.

在受約束的公式中，參數由下式給出

這是一個二次規劃問題，因此是多項式的。

幾乎所有的凸優化例程，甚至對於像神經網絡這樣靈活的非線性事物，都依賴於計算目標 wrt 參數的導數。你不能取儘管。因此，您依賴於不同的技術。有很多方法可以找到參數。這是一篇關於該主題的評論論文，Least Squares Optimization with L1-Norm Regularization。迭代凸優化的時間複雜度很難分析，因為它取決於收斂標準。通常，隨著觀測值的增加，迭代問題會在更少的時期內收斂。

引用自：https://stats.stackexchange.com/questions/76518