följer-the-regularized-leader proximal gradient nedstigning använder detta uppdateringssteg:
$$ 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 |) $$
-
Vi är på $ t + 1 $ -rundan, vi har redan sett $ t $ datapunkter .
-
$ g_s $ är gradienten för $ s $ -provet.
-
$ \ sigma_s $ är en icke-ökande inlärningshastighet, definierad som $ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
och slutligen $ \ lambda_1 $ är en ordning för termisering.
Kan du ge en geometrisk / fysisk / annan enkel intuition för vad gör vi med de första två termerna? Representerar den första någon form av fart? Kräver den andra att vår nya plats ska skilja sig från våra tidigare platser?
Var tålmodig om det här verkar som ett försök att förenkla en tung teori …
Svar
Följer McMahans Follow-the-Regularized-Leader och Mirror Descent: Equivalence theorems .
Papperet visar att den enkla gradientuppdateringsregeln kan skrivas på ett mycket liknande sätt som ovanstående regel.
Den intuitiva uppdateringsregeln för FOBOS (en variant med gradientnedstigning) är:
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
där
- $ g_t $ är gradienten för det föregående exemplet $ t $ – vi vill gå i den riktningen eftersom det minskar förlusten av vår hypotes på det exemplet.
- Vi vill dock inte ändra vår hypotes $ x_t $ för mycket (av rädsla för att förutsäga dåligt om exempel vi redan har sett). $ \ mu_t $ är en stegstorlek för detta exempel, och det bör göra varje steg mer konservativt.
Vi kan hitta var derivatet är 0 och få en uttrycklig uppdateringsregel:
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
Papperet fortsätter att visa att samma intuitiva uppdateringsregel ovan också kan skrivas som:
$$ 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}] $$
Vilket liknar den FTRL-proximala formuleringen. Faktum är att gradientdelen (första terminen) och den proximala starka konvexiteten (tredje termen) är desamma, och det här var de intressanta delarna för mig.
Kommentarer
- Eftersom papperet går in i tekniska detaljer som inte har varit för mig, skulle jag vara glad om någon kan kontrollera detta svar och se till att den här förklaringen är vettigt …
Svar
för FOBOS, den ursprungliga formuleringen är i grunden en förlängning av SGD: http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
FTRL-papperet försöker ge en enhetlig bild genom att formulera Duchis slutna form uppdatera på liknande sätt som FTRL. Uttrycket g * x (även nämnt i ihadannys svar) är lite konstigt, men om du arbetar från ovanstående pdf är det ganska tydligt:
på sidan 8 i ovanstående pdf, om vi ignorerar regelbundna termer R för nu,
$$ \ 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 {med tanke på sidan 7 i 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} $$
$ \ mathbf {w} _t $ och $ \ mathbf {g} _t $ ovan är alla konstanter för argmin, så ignoreras, då har du formuläret från ihadanny
$ \ mathbf {w} \ mathbf {g} _t $ form är vettigt (efter ovanstående ekvivalensderivation från Duchi-formen), men i denna form är den väldigt ointuitiv, och ännu mer så är $ \ mathbf {g} _ {1: t} \ mathbf {w} $ form i FTRL-papperet. för att förstå FTRL-formeln i den mer intuitiva Duchi-formen, notera att den största skillnaden mellan FTRL och FOBOS helt enkelt är $ \ mathbf {g} _ {1: t} $ -> $ \ mathbf {g} _ {t} $ (se https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf Obs! Det finns faktiskt ett typsnitt för FOBOS i tabellen på sidan 2, du bör titta på ekvationer i styckena) ändrar sedan bara $ \ mathbf {g} _ {t} $ till $ \ mathbf {g} _ {1: t} $ i ovanstående ekvivalensderivation, och du kommer att upptäcka att FTRL i princip är den slutna- formulär FOBOS-uppdatering med en mer ”konservativ” för värdet $ \ mathbf {g} _ {t} $ genom att använda genomsnittet av $ \ mathbf {g} _ {1: t} $