La descente de gradient proximal suivre-le-leader-régularisé utilise cette étape de mise à jour:
$$ w_ {t + 1} = argmin_w (w \ cdot \ sum_ {s = 1} ^ t g_s + \ frac {1} {2} \ sum_ {s = 1} ^ t \ sigma_s (w-w_s) ^ 2 + \ lambda_1 | w |) $$
-
Nous sommes sur le rond $ t + 1 $, nous avons déjà vu $ t $ points de données .
-
$ g_s $ est le dégradé de léchantillon $ s $.
-
$ \ sigma_s $ est un taux dapprentissage non croissant, défini comme $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
et enfin $ \ lambda_1 $ est un terme de régularisation.
Pouvez-vous donner une intuition simple géométrique / physique / autre pour ce que nous faisons avec les 2 premiers termes? Le premier représente-t-il une sorte délan? Le second exige-t-il que notre nouvel emplacement soit différent de nos emplacements précédents?
Veuillez être patient si cela vous semble être une tentative de simplification excessive dune théorie lourde …
Réponse
À la suite de McMahan » s Follow-the-Regularized-Leader and Mirror Descent: Equivalence théorems .
Le document montre que la règle de mise à jour de descente de gradient simple peut être écrite dune manière très similaire à la règle ci-dessus.
La règle de mise à jour intuitive de FOBOS (une variante de descente de gradient) est:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
où
- $ g_t $ est le gradient de l échantillon précédent $ t $ – nous voulons nous déplacer dans cette direction car cela diminue la perte de notre hypothèse sur cet échantillon.
- Cependant, nous ne voulons pas changer notre hypothèse $ x_t $ trop (de peur de mal prédire sur des exemples que nous avons déjà vus). $ \ mu_t $ est une taille de pas pour cet exemple, et cela devrait rendre chaque étape plus conservatrice.
Nous pouvons trouver où le dérivé est 0 et obtenir une règle de mise à jour explicite:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
Le document continue en montrant que la même règle de mise à jour intuitive ci-dessus peut également être écrite comme:
$$ x_ {t + 1} = argmin_x [g_ {1: t} x + \ phi_ {1: t-1} x + \ psi (x) + \ frac {1} {2} \ sum_ {s = 1} ^ t {| x-x_s | ^ 2}] $$
Ce qui est assez similaire à la formulation FTRL-proximale. En fait, la partie gradient (1er terme) et la forte convexité proximale (3ème terme) sont les mêmes, et cétaient les parties intéressantes pour moi.
Commentaires
- Alors que larticle aborde des détails techniques qui me dépassaient, je serais heureux si quelquun pouvait vérifier cette réponse et sassurer que cette explication est logique …
Réponse
pour FOBOS, la formulation originale est essentiellement une extension de SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
le document FTRL essaie de donner une vue unifiée en formulant le formulaire fermé Duchi mise à jour de la même manière que FTRL. le terme g * x (également mentionné dans la réponse de ihadanny) est un peu bizarre, mais si vous travaillez à partir du pdf ci-dessus, cest assez clair:
à la page 8 du pdf ci-dessus, si nous ignorons le terme de régularisation R pour le moment,
$$ \ begin {eqnarray} \ mathbf {w} _ {t + 1} & = & argmin _ {\ mathbf {w}} \ {\ frac {1} {2} \ | \ mathbf {w} – \ mathbf {w} _ {t + 1/2} \ | ^ 2 \} \\ & = & argmin _ {\ mathbf {w}} \ {\ frac {1} {2} \ | \ mathbf {w} – (\ mathbf {w} _ {t} – \ eta \ mathbf {g} _t) \ | ^ 2 \} \ mbox {considérant la page 7 du pdf Duchi} \\ & = & (\ mathbf {w} – \ mathbf {w} _t) ^ t (\ mathbf {w} – \ mathbf {w} _t) + 2 \ eta (\ mathbf {w} – \ mathbf {w} _t) ^ t \ mathbf {g} _t + \ eta ^ 2 \ mathbf {g} _t ^ t \ mathbf {g} _t \ end {eqnarray} $$
les $ \ mathbf {w} _t $ et $ \ mathbf {g} _t $ ci-dessus sont toutes des constantes pour largmin, donc sont ignorés, alors vous avez la forme donnée par ihadanny
la forme $ \ mathbf {w} \ mathbf {g} _t $ a du sens (après la dérivation déquivalence ci-dessus à partir de la forme Duchi), mais sous cette forme elle est très peu intuitive, et plus encore le $ \ mathbf {g} _ {1: t} \ mathbf {w} $ form dans le papier FTRL. pour comprendre la formule FTRL sous la forme Duchi plus intuitive, notez que la différence majeure entre FTRL et FOBOS est simplement le $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ (voir https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf noter quil y a en fait une faute de frappe pour FOBOS dans le tableau de la page 2, vous devriez regarder le équations dans les paragraphes) puis changez simplement $ \ mathbf {g} _ {t} $ en $ \ mathbf {g} _ {1: t} $ dans la dérivation déquivalence ci-dessus, et vous constaterez que FTRL est fondamentalement le fermé- forme une mise à jour FOBOS avec un plus « conservateur » pour la valeur de $ \ mathbf {g} _ {t} $ en utilisant la moyenne de $ \ mathbf {g} _ {1: t} $