Exemple de descente de gradient préconditionné de base

Question

J'explore la descente de gradient préconditionnée en utilisant un problème de jouet similaire décrit dans la première partie de la conférence 8: Accélérer la SGD avec des taux de préconditionnement et d'apprentissage adaptatif .

J'ai la fonction $f(x,y) = x^2 + 10\,y^2$ qui a un gradient de $[2x, 20y]$.

Je sais que la forme idéale de la fonction est $f(x,y) = x^2 + y^2$ qui a un gradient de $[2\,x, 2\,y]$.

Comment résoudre la matrice de précondition dans l'équation, $w_{t+1} = w_t - \alpha\,P\,\nabla f(w_t)$, comme le demande la première boîte d'activités? Dans ce cas$P$ serait juste $[1, \frac{1}{10}]$?

Au bas de la deuxième page, il est dit:

J'ai du mal à comprendre comment le résoudre formellement dans le contexte de la variance décrit dans la réponse ici Préconditionnement de la descente de gradient . Je vois aussi dans cette réponse, la référence de la troisième approche w /$P = [H f(x^*)]^{-1}$.

Je ne peux trouver aucun autre exemple parcouru en ligne.

Answer 1

Puisque la toile de jute est constante $P = H^{-1}$ est optimal (vous récupérez complètement la méthode de Newton): $P = H^{-1} = \text{diag}(1/2, 1/20)$. Cela équivaut à faire le changement de variables$x = \frac{1}{\sqrt{2}} x'$ et $y = \frac{1}{\sqrt{20}} y'$ qui vous donne le désir $\frac{1}{2} (x'^2 + y'^2)$ forme.

Quant à l'approche 2, il ne s'agit que d'une manière systématique d' estimer l'échelle de vos variables. Obtenez une estimation empirique de la matrice de covariance $\Sigma \approx \text{Cov}(x)$. La réponse que vous avez mentionnée montre comment$P = \Sigma$ découle d'un changement de variable et de règle en chaîne.

Quelle distribution échantillonnez-vous si vous souhaitez utiliser l'approche 2? Si vous traitez votre fonction objectif comme une log-vraisemblance négative, vous devriez alors échantillonner à partir d'une distribution normale avec$\frac{1}{2} \Sigma^{-1} = \operatorname{diag}(1, 10)$. Alors tu devrais avoir$\Sigma = \operatorname{diag}(1/2, 1/20)$. Si vous deviez prendre de nombreux échantillons aléatoires de cette distribution et calculer leur covariance, vous obtiendriez la même réponse puisque$\Sigma_{i,j} := \operatorname{E} [(x_i - \mu_i)( x_j - \mu_j)] = \operatorname{Cov}(x)$(voir wikipedia ).

Ces approches sont équivalentes lorsque vos données sont normalement distribuées et que vous en avez beaucoup. En pratique, l'approche 2 est plus généralement applicable aux situations où le Hessian n'est pas constant, mais peut être quelque peu grossier.

Le calcul automatique d'une matrice de préconditionnement dynamique est un sujet très bien étudié. Les méthodes d'optimisation qui font cela sont appelées méthodes Quasi-Newton .

Answer 2

Je suis assez sûr que vous pouvez simplement utiliser le Hessian, qui dans ce cas est $$ 2\begin{bmatrix} 1 & 0\\ 0 & 10 \end{bmatrix} $$

Cela provient de la méthode 3 (utilisant des informations dérivées partielles secondes), et éventuellement aussi de la méthode 1.

La raison pour laquelle nous utilisons la matrice exacte ici au lieu d'une approximation est que c'est un cas simple; comme indiqué ailleurs, l'efficacité peut être un problème de plus grande dimension.

Nous avons déjà une matrice diagonale, donc même si nous nous approchions comme suggéré, ce serait la même chose. Notez que cette matrice satisfait également les critères d'être symétrique et semi-définie positive.

Answer 3

C'est le problème que le préconditionnement tente de résoudre:

De ce blog (également discuté ici sur stackexchange: l' ajustement du modèle SIR avec les données 2019-nCoV ne converge pas )

Problèmes:

• Avec les méthodes de descente en gradient, vous suivez un chemin descendant. Mais votre algorithme n'est souvent pas aussi fluide que l'eau et ne coule pas directement de la manière la plus efficace. Au lieu de cela, souvent l'algorithme «over-shoot» et suit un chemin en zigzag (inefficace).
• Un autre problème est que l'algorithme peut avoir des règles de base pour décider quand s'arrêter. Par exemple, décider d'arrêter lorsque les tailles de pas deviennent très petites. Cependant, pour cette règle d'arrêt, lorsque vous ne regardez pas dans la direction de l'optimum (parce que vous regardez le long du chemin en zigzag lent), il se peut que vos tailles de pas soient petites alors que l'optimum est encore loin.

(le premier problème concerne la vitesse d'obtention d'une solution / convergence, le second problème concerne la précision du résultat)

Méthodes pour «pré-conditionner»:

Ce serait donc bien si vous pouviez changer l'échelle des différentes variables d'une manière ou d'une autre (les rendre plus égales au lieu d'avoir cette vallée). Vous avez seulement besoin de savoir comment .

• méthode 1: utilisez la formule du problème ou une certaine intuition sur le problème.

  Dans votre cas, la fonction $f(x,y) = x^2 + 10y^2$, vous pouvez calculer la mise à l'échelle / le préconditionnement en fonction de la formule. Dans la formulation de votre référence ...$P$devrait être une matrice. C'est$P$ n'est pas $\left[1,1/10\right]$ mais plutôt $$P = \begin{bmatrix} 1 & 0 \\ 0 & 1/10 \end{bmatrix}$$ C'est la mise à l'échelle des variables qui est un vecteur, à savoir $R = \left[1,\sqrt{1/10}\right]$.

  Sans formule, vous pouvez utiliser «l'intuition». Par exemple, vous pouvez avoir des fonctionnalités avec des échelles très variables. Je fais souvent cela. Mettez les variables à l'échelle de sorte que la plage de la solution «attendue» soit similaire pour chaque variable. (Dans l'image ci-dessous, vous voyez également cela. La plage de$R_0$ et $K$ le paramètre est très différent)

• méthode 2: utilisez les données / variance. Je crois que cela fait référence à l'utilisation d'un échantillon de distribution des fonctionnalités (ou d'autres informations sur l'échelle de propagation). La variance des caractéristiques est liée à la courbure de la fonction de vraisemblance ( matrice d' information observée ). Peut-être que cette méthode est aussi à peu près la même que «utiliser l'intuition».

  En plus de simplement regarder l'échelle des paramètres, il est également important de regarder la «variation». Si un paramètre est autour$1 \, kilometer \pm 0.001 \, kilometer$, alors la fonction de perte a plus de courbure qu'un paramètre autour de $10 \, meter \pm 2 \, meter$. (vous pouvez le voir dans l'image ci-dessous, le paramètre$R_0 \approx 1$ a une échelle plus grande que le $K \approx 0.4$ paramètre, mais la variation est dans une plage beaucoup plus petite)

• méthode 3: Vous n'avez peut-être pas de formule ou d'intuition comme dans la méthode 1, mais vous pouvez calculer le Hessian à un moment donné pendant la descente et adapter la mise à l'échelle en conséquence.

  Cette méthode 3 est particulièrement intéressante si le problème n'est pas continu. Par exemple, dans l'image ci-dessous, vous voyez que la toile de jute et l'échelle varient. Intuitivement, la ligne que suit le "half-pipe" est courbée (au début le$K$ paramètre a plus de courbure, mais plus tard, le $R_0$paramètre). Dans ces cas, vous ne pouvez pas facilement résoudre les problèmes de convergence en définissant simplement un (unique) pré-conditionnement dès le départ, et vous devez le changer en plusieurs étapes (le long du chemin).