De follow-the-regularized-leader proximale gradiëntafdaling gebruikt deze updatestap:
$$ 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 |) $$
-
We zitten in de $ t + 1 $ ronde, we hebben al $ t $ datapunten gezien .
-
$ g_s $ is het verloop voor het $ s $ -voorbeeld.
-
$ \ sigma_s $ is een niet-stijgend leertempo, gedefinieerd als $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
en tot slot is $ \ lambda_1 $ een regularisatieterm.
Kun je een geometrische / fysieke / andere eenvoudige intuïtie geven voor wat we doen met de eerste 2 termen? Vertegenwoordigt de eerste een soort momentum? Vereist de tweede dat onze nieuwe locatie anders is dan onze vorige locaties?
Even geduld als dit je lijkt als een poging om een zware theorie te vereenvoudigen …
Antwoord
Volgend op McMahans Follow-the-Regularized-Leader en Mirror Descent: Equivalence theorems .
Het artikel laat zien dat de eenvoudige regel voor het bijwerken van de gradiëntafdaling kan op een vergelijkbare manier worden geschreven als de bovenstaande regel.
De intuïtieve updateregel van FOBOS (een variant van de gradiëntdaling) is:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
waar
- $ g_t $ is het verloop voor de vorige steekproef $ t $ – we willen in die richting gaan, omdat het verlies van onze hypothese op die steekproef hierdoor wordt verminderd.
- We willen onze hypothese echter niet wijzigen $ x_t $ te veel (uit angst slecht te voorspellen op basis van voorbeelden die we al hebben gezien). $ \ mu_t $ is een stapgrootte voor dit voorbeeld, en het zou elke stap conservatiever moeten maken.
We kunnen vinden waar de afgeleide 0 is en krijgen een expliciete updateregel:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
Het artikel laat verder zien dat dezelfde intuïtieve updateregel hierboven ook kan worden geschreven als:
$$ 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}] $$
Wat vrij gelijkaardig is aan de FTRL-proximale formulering. In feite zijn het gradiëntgedeelte (1e term) en de proximale sterke convexiteit (3e term) hetzelfde, en dit waren de interessante onderdelen voor mij.
Opmerkingen
- Aangezien het artikel ingaat op technische details die mij te boven gingen, zou ik blij zijn als iemand dit antwoord kan controleren en ervoor kan zorgen dat deze uitleg is logisch …
Antwoord
voor FOBOS is de oorspronkelijke formulering in feite een uitbreiding van SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
de FTRL-paper probeert een uniform beeld te geven door de Duchi gesloten vorm te formuleren update op dezelfde manier als FTRL. de term g * x (ook genoemd in het antwoord van ihadanny) is een beetje raar, maar als je werkt vanuit de bovenstaande pdf, is het vrij duidelijk:
op pagina 8 van de bovenstaande pdf, als we negeren voorlopig de regularisatieterm R,
$$ \ 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 {rekening houdend met pagina 7 van de Duchi pdf} \\ & = & (\ 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} $$
de $ \ mathbf {w} _t $ en $ \ mathbf {g} _t $ hierboven zijn allemaal constanten voor de argmin, dus worden genegeerd, dan heb je de vorm gegeven door ihadanny
de $ \ mathbf {w} \ mathbf {g} _t $ -vorm is logisch (na de bovenstaande equivalentieafleiding van de Duchi-vorm), maar in deze vorm is het erg niet intuïtief, en nog meer is de $ \ mathbf {g} _ {1: t} \ mathbf {w} $ -formulier in het FTRL-document. om de FTRL-formule in de meer intuïtieve Duchi-vorm te begrijpen, merk op dat het belangrijkste verschil tussen FTRL en FOBOS eenvoudig de $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ is (zie https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf opmerking dat er eigenlijk een typefout is voor FOBOS in de tabel op pagina 2, je moet kijken naar de vergelijkingen in de alineas) en verander dan $ \ mathbf {g} _ {t} $ in $ \ mathbf {g} _ {1: t} $ in de bovenstaande equivalentieafleiding, en je zult zien dat FTRL in feite de gesloten- vorm FOBOS-update met een meer “conservatieve” voor de waarde van $ \ mathbf {g} _ {t} $ door het gemiddelde van $ \ mathbf {g} _ {1: t} $
te gebruiken