Exemplo básico de descida gradiente pré-condicionado

Question

Estou explorando a descida gradiente pré-condicionada usando um problema de brinquedo semelhante ao descrito na primeira parte da Aula 8: Acelerando o SGD com pré-condicionamento e taxas de aprendizado adaptativas .

Eu tenho a função $f(x,y) = x^2 + 10\,y^2$ que tem um gradiente de $[2x, 20y]$.

Eu sei que a forma ideal da função é $f(x,y) = x^2 + y^2$ que tem um gradiente de $[2\,x, 2\,y]$.

Como faço para resolver para a matriz de pré-condição na equação, $w_{t+1} = w_t - \alpha\,P\,\nabla f(w_t)$, como a primeira caixa de atividade pergunta? Nesse caso$P$ seria apenas $[1, \frac{1}{10}]$?

No final da segunda página diz:

Estou tendo problemas para entender como resolvê-lo formalmente no contexto de variância descrito na resposta aqui Descida de gradiente de pré-condicionamento . Também vejo nessa resposta a referência da terceira abordagem c /$P = [H f(x^*)]^{-1}$.

Não consigo encontrar nenhum outro exemplo percorrido online.

Answer 1

Uma vez que o hessian é constante $P = H^{-1}$ é ótimo (você recupera totalmente o método de Newton): $P = H^{-1} = \text{diag}(1/2, 1/20)$. Isso é equivalente a fazer a mudança de variáveis$x = \frac{1}{\sqrt{2}} x'$ e $y = \frac{1}{\sqrt{20}} y'$ o que dá a você o desejado $\frac{1}{2} (x'^2 + y'^2)$ Formato.

Quanto à abordagem 2, esta é apenas uma forma sistemática de estimar a escala de suas variáveis. Obtenha uma estimativa empírica para a matriz de covariância $\Sigma \approx \text{Cov}(x)$. A resposta que você referiu mostra como$P = \Sigma$ segue de uma mudança de variável e regra da cadeia.

Que distribuição você obtém se quiser fazer a abordagem 2? Se você tratar sua função objetivo como uma probabilidade logarítmica negativa, então você deve fazer uma amostragem de uma distribuição normal com$\frac{1}{2} \Sigma^{-1} = \operatorname{diag}(1, 10)$. Então você deve obter$\Sigma = \operatorname{diag}(1/2, 1/20)$. Se você tomasse muitas amostras aleatórias desta distribuição e calculasse sua covariância, você obteria a mesma resposta, pois$\Sigma_{i,j} := \operatorname{E} [(x_i - \mu_i)( x_j - \mu_j)] = \operatorname{Cov}(x)$(veja wikipedia ).

Essas abordagens são equivalentes quando seus dados são normalmente distribuídos e você tem muitos deles. Na prática, a abordagem 2 é mais geralmente aplicável a situações em que o Hessian não é constante, mas pode ser um tanto grosseiro.

A computação automática de uma matriz de pré-condicionamento dinâmico é um tópico muito bem estudado. Os métodos de otimização que fazem isso são chamados de métodos Quasi-Newton .

Answer 2

Tenho quase certeza de que você pode usar apenas o Hessian, que neste caso é $$ 2\begin{bmatrix} 1 & 0\\ 0 & 10 \end{bmatrix} $$

Isso vem do método 3 (usando informações derivadas da segunda parcial) e, possivelmente, também do método 1.

O motivo pelo qual estamos usando a matriz exata aqui em vez de uma aproximação é porque este é um caso simples; como observado em outros lugares, a eficiência pode ser um problema com dimensões maiores.

Já temos uma matriz diagonal, portanto, mesmo se fizéssemos a aproximação sugerida, seria a mesma. Observe que esta matriz também satisfaz os critérios de ser simétrica e semi-definida positiva.

Answer 3

Este é o problema que o pré-condicionamento tenta resolver:

Deste blog (também discutido aqui no stackexchange: Adaptando o modelo SIR com dados 2019-nCoV não convergem )

Problemas:

• Com os métodos de descida gradiente, você segue um caminho morro abaixo. Porém, seu algoritmo geralmente não é tão suave quanto a água e não flui diretamente para baixo da maneira mais eficiente. Em vez disso, muitas vezes o algoritmo 'ultrapassa' e segue um caminho em zigue-zague (ineficiente).
• Outro problema é que o algoritmo pode ter algumas regras básicas para decidir quando parar. Por exemplo, decidir parar quando os tamanhos dos passos estão ficando muito pequenos. No entanto, para essa regra de parada, quando você não está olhando na direção do ideal (porque está olhando ao longo do caminho em zigue-zague lento), pode ser que o tamanho dos seus passos seja pequeno enquanto o ótimo ainda está longe.

(o primeiro problema é sobre a velocidade de obtenção de uma solução / convergência, o segundo problema é sobre a precisão do resultado)

Métodos para 'pré-condicionar':

Portanto, seria bom se você pudesse alterar a escala das diferentes variáveis ​​de alguma forma (torná-las mais iguais em vez de ter este vale). Você só precisa saber como .

• método 1: use a fórmula para o problema ou alguma intuição sobre o problema.

  No seu caso, a função $f(x,y) = x^2 + 10y^2$, você pode calcular a escala / pré-condicionamento com base na fórmula. Na formulação de sua referência ...$P$deve ser uma matriz. Isso é$P$ não é $\left[1,1/10\right]$ mas ao invés $$P = \begin{bmatrix} 1 & 0 \\ 0 & 1/10 \end{bmatrix}$$ É a escala das variáveis ​​que é um vetor, a saber $R = \left[1,\sqrt{1/10}\right]$.

  Sem fórmula, você pode usar 'intuição'. Por exemplo, você pode ter recursos com escalas amplamente variadas. Costumo fazer isso. Dimensione as variáveis ​​de forma que o intervalo da solução 'esperada' seja semelhante para cada variável. (Na imagem abaixo você também pode ver isso. O intervalo do$R_0$ e $K$ parâmetro é muito diferente)

• método 2: use os dados / variação. Eu acredito que isso se refere ao uso de uma distribuição de amostra dos recursos (ou alguma outra informação sobre a escala de propagação). A variância dos recursos está relacionada à curvatura da função de verossimilhança ( matriz de informação observada ). Talvez esse método também seja o mesmo que "usar a intuição".

  Além de apenas olhar para a escala dos parâmetros, também é importante olhar para a 'variação'. Se algum parâmetro estiver próximo$1 \, kilometer \pm 0.001 \, kilometer$, então a função de perda tem mais curvatura do que um parâmetro em torno $10 \, meter \pm 2 \, meter$. (você pode ver isso na imagem abaixo, o parâmetro$R_0 \approx 1$ tem uma escala maior do que o $K \approx 0.4$ parâmetro, mas a variação está em uma faixa muito menor)

• método 3: você pode não ter uma fórmula ou intuição como no método 1, mas pode calcular o Hessian em algum ponto durante a descida e adaptar a escala de acordo.

  Este método 3 é particularmente bom se o problema não for contínuo. Por exemplo, na imagem abaixo você percebe que a juta e a escala estão variando. Intuitivamente, a linha que o "half-pipe" segue é dobrada (no início o$K$ parâmetro tem mais curvatura, mas depois o $R_0$parâmetro). Nestes casos, você não pode resolver facilmente os problemas de convergência apenas definindo um (único) pré-condicionamento desde o início, e você precisa alterá-lo em várias etapas (ao longo do caminho).