FTRL介绍

FTRL

FTRL是一种在线线性优化技术，类似于FTL，但在目标函数上有所差别。

FTL目标函数：$x_{T+1} = \arg\min_{x \in \mathcal{K}} \sum_{t=1}^T f’_t x$

FTRL目标函数：$x_{T+1} = \arg\min_{x \in \mathcal{K}} \sum_{t=1}^T f’_t x + cR(x)$
$R(x)$表示凸可微正则化项。
若用于分类，可以参考[1]

在线线性优化

在线线性优化(on-line linear optimization)定义为：学习者(玩家)和环境(对手，或现实)之间重复的游戏。
假设$\mathcal{K} \in \mathbb{R}^n$是一个紧凑的闭凸集。
游戏的协议是：
　　FOR $t=1,2,\dots,T$
　　　玩家选择 $x_t \in \mathcal{K}$
　　　独立的对手选择 $f_t \in \mathbb{R}^n$
　　　玩家损失函数 $f’_t x_t$, 和观察到的反馈。
　　END FOR.

玩家的目标是最小化：

$$
R _ { T } = \sum _ { t = 1 } ^ { T } f _ { t } ^ { \prime } x _ { t } - \min _ { x ^ { * } \in \mathcal { K } } \sum _ { t = 1 } ^ { T } f _ { t } ^ { \prime } x ^ { * }
$$

在完全信息的游戏设定下，玩家可以将$f_t$ 作为反馈，并作为他再次决策的参考。其它的设置是负向作用，玩家观察到只是标量值$f’_t x_t$。不知道“如果我们改变了我们的行动会是什么”，只有反馈。
其实，这样的设置对于各种各样的应用程序都是有用的。
由于这个理论有些缺憾，所以演化出来的FTL(Follow the Leader)算法偶尔被使用，而更多的时候则是使用FTRL(Follow the regularized leader)

FTL

FTL是一个用专家建议预测的算法。它衍生了一些其它算法，如FTRL，一种更有效的算法。
FTL仅仅跟随“到目前为止”最好的专家。
目标函数 $\gamma^T = \arg\min \sum_{t=1}^T \lambda(\omega^t,\gamma^t_k), k=1,\ldots,K$ (可以参考Prediction with expert advice或是其它类似的理论。
可以看出，即使是在平方损失函数的情况下，也不能证明该算法的良好后悔界限。
假设有两种输出${0,1}$，和两个可能的专家。一个总是预测$0$第二个总是预测$1$.在第一步，学习者选择跟随第一个专家，所以他的预测是$0$，然而现实总是可能让你失望，当产出是$1$时，学习者遭受损失$1$，第一个专家遭受损失$1$，第二个专家遭受损失$0$。在第二步中，学习者选择第二个专家，所以他的预测是$1$。实际输出是$0$，所以学习者遭受损失$1$。
(我咋感觉跟我买股票的节奏差不多呢+==+)
就这样, 经过$T$步后，学习者的损失是$T$，专家们的损失是$\dfrac{T}{2}$(只有大约，因为当专家的损失相等时，我们不知道在学习者选择他的决定之前哪个人遭受了非零损失)，所以后悔的代价是$\dfrac{T}{2}$。

[1]:Shai Shalev-Shwartz and Yoram Singer. A primal-dual perspective of online learning algorithms. Mach. Learn., 69(2-3):115–142, 2007.