上一篇文章介绍完在线学习的基本概念，算是对在线学习问题有了一个基本的引入。本文将介绍FTL算法。

FTL

对于当前轮的问题，我们不知道最好的解是什么，但是我们可以利用以前的那些轮得出的结果，一个最直观易懂的想法就是我们直接用使得以往的损失和最小的那个解作为我们当前轮做出的预测。这也就是Follow-The-Leader算法的想法来源，这个leader也就是在之前表现最好的那个解，我们follow这个解，认为这个解在当前轮的表现也会很好。用数学表示就是

$ \begin{gathered} \forall t, \quad \mathbf{w_t}=\underset{\mathbf{w} \in S}{\operatorname{argmin}} \sum_{i=1}^{t-1} f_i(\mathbf{w}) \quad \end{gathered} $

那么这个直觉上的算法可不可行呢？其实在一些简单问题上还是有一个比较小的Regret Bound的。下面将分析FTL算法在在线二次优化问题(Online Quadratic Optimization)上的Regret Bound。

首先，为了简化Regret，我们证明一个引理。

对任意一个向量$\mathbf{u}∈S$,和FTL算法产生的一系列向量$\mathbf{w_1},\mathbf{w_2},\mathbf{w_3},…,$都有下面的不等式成立

$\operatorname{Regret_T}(\mathbf{u})=\sum_{t=1}^T\left(f_t\left(\mathbf{w_t}\right)-f_t(\mathbf{u})\right) \leq \sum_{t=1}^T\left(f_t\left(\mathbf{w_t}\right)-f_t\left(\mathbf{w_{t+1}}\right)\right)$

证明：

在不等式两端减去$\sum_t f_t\left(\mathbf{w_t}\right)$后，其实只需要证明成立即可。

我们利用递归的方法来证明这个不等式。首先，可以很容易的发现，对于T=1，该不等式是显然成立的，我们接下来假设对于T-1成立，即对所有 u∈S 有下面的不等式成立

$\sum_{t=1}^T f_t\left(\mathbf{w_{t+1}}\right) \leq \sum_{t=1}^T f_t(\mathbf{u})$

我们利用递归的方法来证明这个不等式。首先，可以很容易的发现，对于T=1，该不等式是显然成立的，我们接下来假设对于T-1成立，即对所有$\mathbf{u}∈S$有下面的不等式成立。

$\sum_{t=1}^{T-1} f_t\left(\mathbf{w_{t+1}}\right) \leq \sum_{t=1}^{T-1} f_t(\mathbf{u})$

那么我们在两端分别加上后，有

$f_T\left(\mathbf{w_{T+1}}\right)$

上面的不等式对对于所有$\mathbf{u}∈S$都成立，特别的，也对$\mathbf{u}=\mathbf{w_{T+1}}$成立，所以就有了

$\sum_{t=1}^T f_t\left(\mathbf{w_{t+1}}\right) \leq \sum_{t=1}^T f_t\left(\mathbf{w_{T+1}}\right)=\min_{\mathbf{u} \in S} \sum_{t=1}^T f_t(\mathbf{u})$

最后一个等式是根据$\mathbf{w_{T+1}}$的定义得出的。

那我们就先得出了这个不等式。

下面，我们将先介绍在线二次规划问题：

最后，我们给出证明

我们先可以假设$S$是$d$维，那么就有

$\mathbf{w_t}=\frac{1}{t-1} \sum_{i=1}^{t-1} \mathbf{z_i}$

也就是说，$\mathbf{w_t}$是$\mathbf{z}$的平均。我们可以写出

$\mathbf{w_{t+1}}=\frac{1}{t}\left(\mathbf{z_t}+(t-1) \mathbf{w_t}\right)=\left(1-\frac{1}{t}\right) \mathbf{w_t}+\frac{1}{t} \mathbf{z_t}$

得到

\[\begin{aligned} f_t\left(\mathbf{w_t}\right)-f_t\left(\mathbf{w_{t+1}}\right) &=\frac{1}{2}\left\|\mathbf{w_t}-\mathbf{z_t}\right\|^2-\frac{1}{2}\left\|\mathbf{w_{t+1}}-\mathbf{z_t}\right\|^2 \\ &=\frac{1}{2}\left(1-\left(1-\frac{1}{t}\right)^2\right)\left\|\mathbf{w_t}-\mathbf{z_t}\right\|^2 \\ & \leq \frac{1}{t}\left\|\mathbf{w_t}-\mathbf{z_t}\right\|^2 . \end{aligned}\]

我们设$L=\max_t\left|\mathbf{z_t}\right|$。因为$\mathbf{w_t}$是$\mathbf{z}$的平均，所以我们有$\left|\mathbf{w_t}\right| \leq L$,根据三角不等式，也就有$\left|\mathbf{w_t}-\mathbf{z_t}\right| \leq 2 L$,成立，也就可以得到

$\sum_{t=1}^T\left(f_t\left(\mathbf{w_t}\right)-f_t\left(\mathbf{w_{t+1}}\right)\right) \leq(2 L)^2 \sum_{t=1}^T \frac{1}{t}$

由于有$\sum_{t=1}^T 1 / t \leq \log (T)+1$成立，便可以得到FTL算法在在线二次规划上的Regret Bound：

$Regret(FTL)\leq 4 L^2(\log (T)+1)$

可以看到，该Regret Bound是次线性的，我们认为这个算法在在线二次规划的表现上是很好的。