虽然@JacobMick 提供了更广泛的概述和评论论文的链接，但让我给出一个“快捷答案”（这可能被认为是他答案的一个特例）。

设候选变量（特征、列）的数量为，样本大小（观察数、行数）为。考虑使用 LARS 算法（Efron 等人，2004 年）实现的 LASSO。LASSO 的计算复杂度为 (同上)$K$$n$$\mathcal{O}(K^3 + K^2 n)$

• 对于 ,，LASSO 的计算复杂度为个变量的回归相同（ Efron et al., 2004 年，第 443-444 页；也在Schmidt，2005 年，第 2.4 节中引用；有关回归的计算复杂性，请参阅这篇文章）。$K<n$$K^3 < K^2 n$$\mathcal{O}(K^2 n)$$K$
• 对于 ,和 LASSO 的计算复杂度是 ( Efron et al., 2004 )。$K \geqslant n$$K^3 \geqslant K^2 n$$\mathcal{O}(K^3)$

参考：

• 埃夫隆、布拉德利等人。“最小角度回归”。 统计年鉴32.2（2004 年）：407-499。
• 施密特，马克。“具有 l1 范数正则化的最小二乘优化。” CS542B 项目报告（2005 年）。

回想一下，lasso 是一个线性模型，具有$l_1$正则化。

寻找参数可以表述为一个无约束的优化问题，其中参数由下式给出

$\arg \min_\beta ||y - X\beta||^2 + \alpha||\beta||_1$.

在受约束的公式中，参数由下式给出

$\arg \min_\beta ||y - X\beta||^2 s.t.||\beta||_1 < \alpha$

这是一个二次规划问题，因此是多项式的。

几乎所有的凸优化例程，甚至对于像神经网络这样灵活的非线性事物，都依赖于计算目标 wrt 参数的导数。但是，您不能取$\alpha||w||_1$的导数。因此，您依赖于不同的技术。有很多方法可以找到参数。这是一篇关于该主题的评论论文，Least Squares Optimization with L1-Norm Regularization。迭代凸优化的时间复杂度很难分析，因为它取决于收敛标准。通常，随着观测值的增加，迭代问题会在更少的时期内收敛。