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

10

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.XRn×dndβ^=argminβ12n||Xβy||2+λ||β||1nd

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.dn

rnoodle
fonte
3
Não está claro por que esta resposta stats.stackexchange.com/a/190717/28666 (no segmento ao qual você vinculou) não responde à sua pergunta. Você pode elaborar? O que está em desacordo com o quê?
Ameba
Página 6 em [pdf] [1], afirma "Assim, um ciclo completo através de todas as variáveis ​​d custa ". No entanto, a pergunta que você vincula aos estados . Estou faltando um loop aqui para obter a complexidade ? [1]: jstatsoft.org/article/view/v033i01O(dn)O(d2n)d2
rnoodle
@amoeba O link que você fornece é para o algoritmo LARS - quero saber sobre a abordagem GLM.
Rnoodle 9/08/19
As referências, para regressão de menor ângulo e para descida de coordenadas, estão corretas. A diferença é que (1) o LARS encontra uma solução exata em (e percorre todo o caminho possível de com complexidade igual ao problema de OLS para todo o problema, o que também é escalonado como ), enquanto (2) a descida de coordenadas está executando "apenas" uma única etapa de aproximação em , convergindo / 'descendo' mais próximo do mínimo Problema do LASSO. O LARS usa etapas. Com descida coordenada ... ninguém sabe. O(d2n)O(dn)O(d2n)λO(d2n)O(dn)d
Sexto Empírico

Respostas:

3

As respostas das referências,

  • O(d2n) para regressão de menor ângulo
  • 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(d2n)

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.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).dO((dk)n+k2)dkk

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).d2nddd>>100d=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 .

Sextus Empiricus
fonte