无论在百度搜“在线学习”还是Google”online learning”搜到的都是诸如在线学习网站，在线学习教育等一系列的东西，这波是learning online learning online（
如果下学期周源收我进组的话，为了不让一开始需要补的坑过于庞大，打算自己寒假补一下online learning和bandits theory的东西，剩下的边研究边补。Foundations and Trends in Machine Learning 里面正好有一份online learning的survey，篇幅也不是很多，打算过年这几天拿这个速通一下，然后再把土匪bandits看一下就够了。
Intro
在线学习(online learning)是指再一个连续的回合中，学习者(learner)在第 $t$ 回合接受在事件集合 $\cal{X}$ 中的问题 $x_t$ ，并给出回答(answer) $p_t\in D$ ，在进行回答之后，会和正确答案 $y_t\in\cal{Y}$ 进行比较，并造成损失 $l(p_t,y_t)$ .学习者的最终目的是最小化累积损失(cumulative loss)，这与普通的offline learning的区别在于，学习的过程是动态的. 其中，$x_t$ 和 $y_t$ 的序列可以是确定的、随机的、甚至是对抗性的(adversarially).
例子：(prediction with expert advice)在每一回合中，学习者需要从 $d$ 名给定专家的建议中选择一名，从而 $x_t\in\mathcal X\subset \mathbb R^d$，其中 $x_t[i]$ 是第 $i$ 名专家的建议，且预测集 $D=[d]$，学习者在进行选择后收到回答 $y_t\in\mathcal Y=[0,1]^d$ ，其中 $y_t[i]$ 是选择第 $i$ 名专家的代价，从而 $\ell(p_t,y_t)=y_t[p_t]$. 一般来说，假设集常常设定为 $\mathcal{H}={h_1,\ldots,h_d}$，其中 $h_i(x)=i$，也即无论输入 $x$ 是什么都采取相同专家的建议。
我们给出这样的限制：给定 predictor 集合 $\mathcal H$，并要求学习者必尽可能超过其中最好的 predictor。度量的标准称为该算法的遗憾值(regret)，其中，截止到 $T$ 回合相对 $h^\star$ 的遗憾值定义为
$$
\mathrm{Regre}\text t_T(h^\star)=\sum_{t=1}^T \ell(p_t,y_t)-\sum_{t=1}^T\ell(h^\star(x_t),y_t)
$$
而相对于假设集 $\cal{H}$ 的遗憾值定义为
$$
\mathrm{Regre}\text t_T(\mathcal H)=\max_{h^\star\in\mathcal H}\mathrm{Regre}\text t_T(h^\star)
$$
学习者的目标则为最小化相对于 $\mathcal H$ 的遗憾值.
我们先证明为什么在没有限制的情况下，在线优化算法是没有优化能力的：考虑0-1分类问题，如果假设集有限，考虑遗憾值
$$
\mathrm{Regre}\text t_T(\mathcal{H})=\max_{h\in\mathcal H}\Big(\sum_{t=1}^T|p_t-y_t|-\sum_{t=1}^T|h(x_t)-y_t| \Big)
$$
可以证明，即使在假设集只有 $\mathcal{H}={h_0,h_1}$ 的情况下，遗憾值也是达不到 sublinear bound 的，这是因为：一个 adversary 可以让错误次数等于 $T$，从而 $h_0$ 和 $h_1$ 总有一个能让遗憾值不小于 $T/2$ . 该结果称为 Cover’s impossibility result.
这样的结果是因为 adversarial environment 不讲武德 ，事实上现实中的优化问题没那么逆天以至于一定会反馈给你相反的答案，所以这时候可以引入一些假设来限制 adversary 的能力：
假设回答的生成模式是固定的，也即 $h^\star\in\mathcal H$, $y_t=h^\star(x_t)$，我们将设计一个算法使得 $M_A(\mathcal H)$ 尽可能小，一个自然的想法是选择与之前回合相一致的假设，例如输入 $(x_1, 0),(x_2,1),(x_3,0)$,则在假设集中自动保留相符合的假设.
那么在
consistent算法执行过程中，假设 $V_t$ 是当前的假设集，那么随着执行过程假设集会随着错误的产生而不断缩小，从而当发生 $M$ 次错误后， $|V_t|\leq |\mathcal H|-M$，因为 $V_t$ 一定非空（因为 $h^\star\in\mathcal H$，所以 $1\leq|V_t|\leq |\mathcal H|-M$.事实上我们有更好的算法，也即选择 $V_t$ 中更多的算法（
halves算法），而非始终按照某一算法 $h\in V_t$ 去进行，因此如果我们犯错，我们可以最多移去一半的算法。此时我们有 $M(\mathcal H)\leq \log_2(|\mathcal {H}|)$.（说白了就是二分法，选大多数的那个，只要错一次就能排除超过一半的选项，所以错误次数总是对数级别的）
在线凸优化
下面就可以进入在线凸优化的环节了，首先摆上在线凸优化的基本流程：
input: 一个凸集 $S$.
for $t=1,2,\ldots$
猜测一个向量 $\mathbf{w_t}\in S$，并接受一个凸损失函数 $f_t:S\to\mathbb R$，并计算出损失 $f_t(\mathbf{w}_t)$.
和一般凸优化的区别除了最明显的，优化过程也就是 $\mathbf w_t$ 是动态的之外；还有一点是损失函数是 adversarial 的，这一点在前面的篇幅中也提到了，直观上来讲是，我们需要得到其在最坏的情况下的表现效果。
对在线凸优化而言，其“正确答案”和一般的优化是一样的，都是一个确定的向量 $\bf{u}$，所以遗憾值被定义为
$$
\mathrm{Regre}\text t_T({\bf u})=\sum_{t=1}^T f_t(w_t)-\sum_{t=1}^T f_t({\bf u}).
$$
这里的遗憾值对于所有的 ${\bf u}\in S$ 都是可以定义的，而我们关注的是最优的 $\bf u$，所以我们可以定义对于竞争集 $U$ 上的遗憾值也就是
$$
\mathrm{Regre}\text t_T(U)=\max_{\mathbf u\in U}\mathrm{Regre}\text t_T(\bf u).
$$
例：如在线线性回归问题，每一回合学习者接收到一个特征向量（此特征向量是feature不是eigen（x）$\mathbf x_t\in A \subset \mathbb R^d$ ，在给出回归结果 $p_t$ 后将与正确答案 $y_t$ 比对，并获得损失 $|p_t-y_t|$（从这里我们也可以看到一点，在线凸优化是有明确的顺序的，也即总是先做题后给答案，这和正常的给一堆问题和答案的离线优化是不同的），而比对对象即所有的线性函数 $\langle \mathbf w,\mathbf x\rangle$.
如何解决在线凸优化问题呢？最基本的想法就是用贪心思想在每一步达到最优，其实本质上就是 consistent 算法。我们不知道这一轮的损失函数是什么，所以我们只能在 $t-1$ 回合的信息下作决策，即 Follow-The-Leader(FTL) 算法：
$$
\forall t, {\bf w_t}=\underset{\mathbf w\in S}{\arg\min}\sum_{i=1}^{t-1}f_i(\mathbf w).
$$
下面分析其遗憾值上界，我们先证明一个不等式：
$$
\mathrm{Regre}\text t_T(\mathbf u)=\sum_{t=1}^T(f_t(\mathbf w_t)-f_t(\mathbf u))\leq\sum_{t=1}^T(f_t(\mathbf w_t)-f_t(\mathbf w_{t+1})).\tag{1.1}
$$
可以通过归纳证明，这是因为 $\mathbf w_{t+1}$ 已经是局部上使得 $f_1({\bf u}),\ldots, f_t({\bf u})$ 最小的，所以一定比拍脑袋选一个 $\bf u$ 要好.
例：在线二次优化，其中损失函数 $f_t(\mathbf w)=\frac{1}{2}|\mathbf w-\mathbf z_t|^2$ ，直观上来看就是尽可能找到数据的中心，根据 FTL 算法， $\mathbf w_t=\frac{1}{t-1}\sum_{i=1}^{t-1}\mathbf z_i$ ，那么根据递推有
$$
\mathbf w_{t+1}=(1-\frac{1}{t})\mathbf w_t+\frac{1}{t}\mathbf z_t.
$$
从而
$$
\begin{aligned}
f_t(w_t)-f_t(w_{t+1})&=\frac{1}{2}|w_t-z_t|^2-\frac{1}{2}|w_{t+1}^2-z_t|^2\
&=\frac{1}{2}(1-(1-\frac{1}{t}^2))|w_t-z_t|^2\
&\leq \frac{1}{t}|w_t-z_t|^2.
\end{aligned}
$$
假设诸 $z_t$ 在 $\mathbb B(0,L)$ 内，那么有
$$
\sum_{t=1}^T(f_t(\mathbf w_t))-f_t(\mathbf w_{t+1}))\leq (2L)^2\sum_{t=1}^T \frac{1}{t}=\mathcal{O}(L^2\log(T)).
$$
FTL 算法未必一定奏效，因为其完全通过前 $t-1$ 次的损失函数最小化得到，如果第 $t$ 次的损失函数完全改变了之前的格局，将导致 $\mathbf w_t$ 剧烈震荡，无法得到 sublinear 的遗憾值，为了避免这种情况，一般会引入 regularization。
首先给出一个 FTL 算法失效的反例：
考虑预测集 $S=[-1,1]\subset \mathbb R$，并考虑损失函数 $f_t(w)=z_tw$ ，其中
$$
\begin{equation}
z_t=\left{
\begin{aligned}
-0.5&\quad \text{if}t=1\t
1 &\quad \text{if}\text{is even}\t>1\and t\text{is odd}.
-1 & \quad \text{if}
\end{aligned}
\right.
\end{equation}
$$
这时候，如果选择 $u=0$ 作为目标向量，则累计损失为 $0$，但如果按照 FTL 算法，因为其无法考虑到本次的损失函数，所以每回合都会带来 $1$ 的损失。
Follow-The-Regularied-Leader类似于LASSO的思想，后面加一个正则项来保证预测结果在一个相对稳定的范围内，即
$$
\forall t,\quad w_t=\underset{w\in S}{\arg\min}\sum_{i=1}^{t-1}f_i(w)+R(w).
$$
下面分析 FTRL 算法的遗憾值，类似 FTL 算法，如果将 $R(w)$ 视为 $f_0$ ，那么类似(1.1)可得
$$
\sum_{t=1}^T(f_t(w_t)-f_t(u))\leq R(u)-R(w_1)+\sum_{t=1}^T(f_t(w_t)-f_t(w_{t+1})).
$$
下面分析 $R(w)=\frac{1}{2\eta}|w|2^2$ 、$f_t(w)=\langle w,z_t\rangle$ 时的遗憾值，有
$$
\begin{aligned}
\text{Regre}\text t_T(u)&\leq R(u)-R(w_1)+\sum{t=1}^T(f_t(w_t)-f_t(w_{t+1}))\
&\leq \frac{1}{2\eta}|u|2^2+\sum{t=1}^T\langle w_t-w_{t+1},z_t\rangle \
&=\frac{1}{2\eta}|u|2^2+\eta\sum{t=1}^T|z_t|2^2.
\end{aligned}
$$
其中，根据简单的计算可以得到 $w{t+1}=-\eta\sum_{i=1}^t z_i=w_t-\eta z_t$ ，这个更新规则恰好就是类似于梯度下降法，事实上也的确如此，当 $w$ 与 $z_t$ 反方向时损失函数达到最小，此时恰好就是梯度的反方向！
如果控制 $u$ 的半径为 $B$，$z_t$ 即梯度小于 $L$ 即 Lipschitz，那么通过设定参数 $\eta=\frac{B}{L\sqrt{2T}}$ 可以得到遗憾值小于 $BL\sqrt{2T}$，但这里问题在于， $T$ 可能并不是已知的，所以参数的设置取决于回合数，这并不是我们想要的。如何在回合数未知的情况下达到 $\mathcal{O}(\sqrt T)$ 的遗憾值呢？最简单的方法就是分段，例如第 $2^n$ 到 $2^{n+1}$ 回合利用 $\eta=\frac{B}{L\sqrt{2^{n+1}}}$ 作为参数，最后也能够达到 $\mathcal{O}(\sqrt{T})$ 的遗憾值。
下面来讲在线梯度下降(OGD)，本质思想就是把凸函数转化为线性函数，再按照上面的思想进行。假设 $f_t$ 为凸函数，那么存在 $z_t$ 使得
$$
f_t(w_t)-f_t(u)\leq\langle w_t-u,z_t\rangle.
$$