Por que descida proximal do gradiente em vez de métodos simples de subgradiente para Lasso?

9

Eu estava pensando em resolver Lasso através de métodos de subgradiente de baunilha. Mas li pessoas sugerindo o uso da descida proximal do gradiente. Alguém pode destacar por que o GD proximal, em vez de os métodos do subgradiente de baunilha, são usados ​​no Lasso?

chandresh
fonte

Respostas:

13

Uma solução aproximada pode realmente ser encontrada para o laço usando métodos de subgradiente. Por exemplo, digamos que desejamos minimizar a seguinte função de perda:

f(w;λ)=yXw22+λw1

O gradiente do termo da penalidade é para e para , mas o termo da penalidade é indiferenciável em . Em vez disso, podemos usar o subgradiente , que é o mesmo, mas tem um valor de para .λwi<0λwi>00λsgn(w)0wi=0

O subgradiente correspondente para a função de perda é:

g(w;λ)=2XT(yXw)+λsgn(w)

Podemos minimizar a função de perda usando uma abordagem semelhante à descida do gradiente, mas usando o subgradiente (que é igual ao gradiente em todos os lugares, exceto , onde o gradiente é indefinido). A solução pode estar muito próxima da solução do laço real, mas pode não conter zeros exatos - onde os pesos deveriam ser zero, eles usam valores extremamente pequenos. Essa falta de verdadeira escarsidade é um dos motivos para não usar métodos de subgradiente para o laço. Os solucionadores dedicados aproveitam a estrutura do problema para produzir soluções verdadeiramente esparsas de uma maneira computacionalmente eficiente. Esta postagem0diz que, além de produzir soluções esparsas, métodos dedicados (incluindo métodos de gradiente proximal) têm taxas de convergência mais rápidas que os métodos de subgradientes. Ele dá algumas referências.

user20160
fonte