遵循McMahan 的 Follow-the-Regularized-Leader 和 Mirror Descent：等价定理。

论文表明，简单的梯度下降更新规则可以写成与上述规则非常相似的方式。

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-proximal 公式非常相似。事实上，梯度部分（第 1 项）和近端强凸性（第 3 项）是相同的，这些都是我感兴趣的部分。

对于 FOBOS，原始公式基本上是 SGD 的扩展：http ://stanford.edu/~jduchi/projects/DuchiSi09c_slides.pdf

FTRL 论文试图通过以与 FTRL 类似的方式制定 Duchi 封闭形式更新来给出统一的观点。术语 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{considering page 7 of the 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$和 $\mathbf{g}_t$以上是 argmin 的所有常量，因此被忽略，那么你有 ihadanny 给出的形式

这$\mathbf{w} \mathbf{g}_t$形式是有道理的（在上述 Duchi 形式的等价推导之后），但在这种形式中它非常不直观，更是如此$\mathbf{g}_{1:t}\mathbf{w}$FTRL 论文中的表格。要以更直观的 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 基本上是封闭形式的 FOBOS 更新，对于值更“保守”$\mathbf{g}_{t}$通过使用平均值$\mathbf{g}_{1:t}$