Qual é a complexidade temporal da regressão de Lasso?

14

Qual é a complexidade temporal assintótica da regressão de Lasso à medida que o número de linhas ou colunas cresce?

user2763361
fonte

Respostas:

4

Lembre-se de que o laço é um modelo linear com uma regularização de .l1

Encontrar os parâmetros pode ser formulado como um problema de otimização irrestrito, onde os parâmetros são fornecidos por

.argminβ||yXβ||2+α||β||1

Na formação restrita, os parâmetros são dados por

argminβ||yXβ||2s.t.||β||1<α

O que é um problema de programação quadrática e, portanto, polinomial.

Quase todas as rotinas de otimização convexas, mesmo para coisas não lineares flexíveis, como redes neurais, dependem da computação da derivada dos parâmetros wrt de destino. Você não pode obter a derivada de embora. Como tal, você confia em diferentes técnicas. Existem muitos métodos para encontrar os parâmetros. Aqui está um artigo de revisão sobre o assunto, Otimização dos mínimos quadrados com regularização da norma L1 . A complexidade de tempo da otimização convexa iterativa é meio difícil de analisar, pois depende de um critério de convergência. Geralmente, problemas iterativos convergem em menos épocas à medida que as observações aumentam.α||w||1

Jessica Collins
fonte
4
Várias coisas: dizer que um problema é "polinomial" não é particularmente útil, a menos que você esteja procurando algum tipo de problema combinatório (que geralmente é exponencial). Segundo, calcular as derivadas nem sempre é o passo limitante. Terceiro, geralmente quando se discute a complexidade do tempo de um algoritmo iterativo, normalmente se observa o custo por etapa e, portanto, não depende de critérios de convergência. Finalmente, não é tipicamente o caso que mais observações = menos iterações.
Cliff AB
13

Embora o @JacobMick forneça uma visão geral mais ampla e um link para um artigo de revisão, deixe-me dar uma "resposta de atalho" (que pode ser considerada um caso especial de sua resposta).

KnO(K3+K2n)

  • K<nK3<K2nO(K2n)K
  • KnK3K2nO(K3)

Referências:

Richard Hardy
fonte
Richard, você pode comentar sobre a complexidade da iteração para a abordagem GLM aqui stats.stackexchange.com/questions/280304/… ?
Rnoodle 9/08/19
@moodle, eu não posso sem me aprofundar nisso (que não tenho tempo no momento), mas +1 na sua pergunta.
Richard Hardy
Eu dei uma olhada, mas não está claro - seria bom obter um segundo par de olhos nela. Portanto, há complexidade de iteração e complexidade de convergência total, e acho que a literatura é um tanto vaga às vezes sobre as definições. Basicamente, eu tenho um algoritmo que usa um solucionador de laço em uma posição muito crítica, de modo que a complexidade do meu algoritmo depende fortemente do solucionador. Seria bom acertar isso. Felicidades! Vou colocar uma recompensa por ele para sua entrada
rnoodle
@ rnoodle, duvido muito que seja capaz de ajudá-lo em breve, mas uma recompensa pode certamente atrair outras pessoas que conhecem melhor. Boa sorte!
Richard Hardy