follow-the-regularized-leader 近接勾配降下は、次の更新手順を使用します。
$$ 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 |）$$
-
$ t + 1 $ラウンド中ですが、すでに$ t $データポイントを確認しています。
-
$ g_s $は、$ s $サンプルの勾配です。
-
$ \ sigma_s $は増加しない学習率であり、$ \ sum_ {s = 1} ^ t \ sigma_s = \ sqrt {t} $
-
そして最後に$ \ lambda_1 $は正則化項です。
最初の2つの用語で何をしているのかについて、幾何学的/物理的/その他の簡単な直感を教えていただけますか？最初のものはある種の勢いを表していますか？ 2つ目は、新しい場所が以前の場所と異なる必要がありますか？
これが重い理論を過度に単純化する試みが好きだと思われる場合は、しばらくお待ちください…
回答
次の McMahanのFollow-the-Regularized-Leaderand Mirror Descent：Equivalent theorems 。
この論文は次のことを示しています。単純な勾配降下更新ルールは、上記のルールと非常によく似た方法で記述できます。
FOBOS（勾配降下バリアント）の直感的な更新ルールは次のとおりです。
$$ x_ {t + 1} = argmin_x [g_tx + \ frac {1} {2 \ mu_t} | x-x_t | ^ 2] $$
ここで
- $ g_t $は、前のサンプル$ t $の勾配です。その方向に移動すると、そのサンプルでの仮説の損失が減少します。
- ただし、仮説を変更したくありません。 $ x_t $が多すぎます（すでに見た例でひどく予測することを恐れて）。 $ \ mu_t $はこのサンプルのステップサイズであり、各ステップをより保守的にする必要があります。
導関数が0の場所を見つけて、明示的な更新ルールを取得できます。
$$ x_ {t + 1} = x_t- \ mu_tg_t $$
このペーパーでは、上記と同じ直感的な更新ルールを次のように記述できることを示しています。
$$ 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}] $$
これは、FTRL近位の定式化と非常によく似ています。実は、勾配部分（第1項）と近位の強い凸面（第3項）は同じで、これらは私にとって興味深い部分でした。
コメント
- この論文は私を超えた技術的な詳細になっているので、誰かがこの答えをチェックして、この説明を確認できれば幸いです。理にかなっています…
回答
FOBOSの場合、元の定式化は基本的にSGDの拡張です： http://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf
FTRLペーパーは、Duchiの閉じた形式を定式化することにより、統一されたビューを提供しようとします。 FTRLと同様の方法で更新します。 g * xという用語（ihadannyの回答でも言及されています）は少し奇妙ですが、上記のpdfから作業する場合、それはかなり明確です：
上記のpdfの8ページにある場合今のところ、正則化項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 {Duchipdfの7ページを考慮} \\ & = &（\ 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 $と$ \ mathbf {g} _t $はすべてargminの定数であるため、無視されます。ihadannyによって与えられた形式になります
$ \ mathbf {w} \ mathbf {g} _t $形式は理にかなっていますが（Duchi形式からの上記の同等性の導出の後）、この形式では非常に直感的ではなく、さらに$ \も同様です。 FTRLペーパーのmathbf {g} _ {1：t} \ mathbf {w} $フォーム。より直感的なDuchi形式でFTRLの式を理解するには、FTRLとFOBOSの主な違いは単に$ \ mathbf {g} _ {1：t} $-> $ \ mathbf {g} _ {t} $であることに注意してください。 （ https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/37013.pdf を参照してください。実際には、2ページの表にFOBOSのタイプミスがあることに注意してください。段落内の方程式）次に、上記の等価導出で$ \ mathbf {g} _ {t} $を$ \ mathbf {g} _ {1：t} $に変更するだけで、FTRLは基本的に閉じていることがわかります- $ \ mathbf {g} _ {1：t} $
の平均を使用して、$ \ mathbf {g} _ {t} $の値をより「保守的」にしたFOBOS更新を作成します。