Как Лассо масштабируется с размером матрицы дизайна?

Если у меня есть проектная матрица , где - число наблюдений измерения , какова сложность решения для с LASSO, без и ? Я думаю, что ответ должен относиться к тому, как масштабируется одна итерация LASSO с этими параметрами, а не к тому, как масштабируется количество итераций (сходимость), если вы не чувствуете иначе. п d β = argmin β $X\in\mathcal{R}^{n\times d}$$n$$d$н$\hat{\beta}=\text{argmin}_{\beta}\frac{1}{2n} ||X\beta-y||^{2} + \lambda||\beta||_{1}$$n$$d$

Я читал этот предыдущий вопрос о сложности LASSO , но он, кажется, расходится с обсуждением glmnet здесь и здесь . Я знаю, что существует множество алгоритмов, включая подход GLMnet для GLMnet, но я пишу статью о замене компонента LASSO на родительский алгоритм и хотел бы включить обсуждение сложности LASSO в целом, особенно с и . Я также хотел бы знать сложность glmnet в базовом не разреженном случае, но упомянутая статья немного сбивает с толку, поскольку вся сложность алгоритма не является явной.$d$$n$

Ответы из ссылок,

• для регрессии наименьшего угла$\mathcal{O}(d^2n)$
• для координатного спуска$\mathcal{O}(dn)$

, верны.

Разница в том, что

Уравнения ЛАРС пишутся в замкнутом виде и находят точное решение

$O(d^2n)$

пока

$\mathcal{O}(dn)$

$d$$\mathcal{O}((d-k)n+k^2)$$d-k$$k$

$d^2n$$d$$d$$d>>100$$d=100$

Масштабирование LARS - это проблема сложности вычислений. Масштабирование спуска координат является проблемой, связанной с вычислительной сложностью и сходимостью.