Como o Lasso é dimensionado com o tamanho da matriz de design?

Se eu tiver uma matriz de design , em que é o número de observações da dimensão , qual é a complexidade da solução para com LASSO, wrt e ? Acho que a resposta deve se referir a como uma iteração do LASSO é escalonada com esses parâmetros, e não como o número de iterações (convergência), a menos que você sinta o contrário.$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$

Eu li essa pergunta anterior sobre complexidade do LASSO , mas parece estar em desacordo com a discussão sobre o glmnet aqui e aqui . Estou ciente de que existem muitos algoritmos por aí, incluindo a abordagem GLM da glmnet, mas estou escrevendo um artigo sobre a substituição de um componente LASSO por um algoritmo pai e gostaria de incluir uma discussão sobre a complexidade do LASSO em geral, especialmente com e . Eu também gostaria de conhecer a complexidade do glmnet no caso básico não escasso, mas o artigo referenciado é um pouco confuso, pois toda a complexidade do algoritmo não é explícita.$d$$n$

As respostas das referências,

• $\mathcal{O}(d^2n)$ para regressão de menor ângulo
• $\mathcal{O}(dn)$ para descida de coordenadas

, estão corretas.

A diferença é que

As equações LARS são escritas de forma fechada e encontram uma solução exata

(e fazendo isso percorrendo todo o caminho possível λ enquanto a complexidade computacional está escalando o mesmo que encontrar a solução do problema dos mínimos quadrados comuns, que também é escalado como )$O(d^2n)$

enquanto

descida de coordenadas é um esquema iterativo para aproximar a solução. O passo referido (cujos custos computacionais escalam como ) é "apenas" um único passo de aproximação, convergindo / 'descendo' mais perto do mínimo do problema do LASSO.$\mathcal{O}(dn)$

O LARS usa (exatamente) etapas para encontrar a solução (com a complexidade do k-ésimo escalonamento como , primeiro termo para encontrar produtos internos no inativo definir e segundo termo para resolver o novo ângulo nas variáveis ​​ativas) . Com a descida de coordenadas, ninguém realmente conhece a taxa de convergência e o número de etapas necessárias / esperadas para a convergência 'suficiente' (ou pelo menos não foi bem descrita).$d$$\mathcal{O}((d-k)n+k^2)$$d-k$$k$

Por outro lado, o custo aumenta muito para dimensões altas (embora não haja motivos fortes para esperar que a taxa de convergência da descida coordenada seja escalada de maneira semelhante, = linear, se aumentar). Portanto, a descida coordenada intuitivamente terá um desempenho melhor acima de um determinado limite para . Isso também foi demonstrado por estudos de caso (veja também a referência que mostra que o glmnet tem desempenho melhor do que o LARS quando , enquanto que para os algoritmos têm desempenho semelhante).$d^2n$$d$$d$$d>>100$$d=100$

Escalar o LARS é um problema que envolve complexidade computacional. A descida de coordenadas de escala é um problema que envolve complexidade e convergência computacional .