模型从线性拓展到非线性通常有两个方法，一个是加入非线性激活函数，构成神经网络；一个是核技巧，将数据投射到高维空间实现非线性。在这里，我们将介绍核方法如何应用在在线学习场景中。
首先我们看核函数相关的知识，在这里我们研究的是在再生核希尔伯特空间（RKHS）$\mathcal{H}$中的函数$f:\mathcal{X}\to\mathbb{R}$。这表示有一个核函数$k:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$，以及一个点积运算，使得
$\Vert f\Vert^2=\big<f,f\big>$是正则化函数，表示$\mathcal{H}$中向量的长度。对于正则化项，我们有
\[\begin{aligned} \Omega[f]&=\dfrac12\Vert f\Vert^2\\ \partial_{f}\Omega[f]&=f \end{aligned}\]当然我们可以用更一般的正则化项：
\[\begin{aligned} \Omega[f]&=\omega(\Vert f\Vert)\\ \partial_f\Omega[f]&=\omega'(\Vert f\Vert)\Vert f\Vert^{-1}f \end{aligned}\]利用可再生性，我们可以对$f$这个函数进行求导：
\[\partial_f f(x)=\partial_{f}\big<f(\cdot),k(x,\cdot)\big>=k(x,\cdot)\]这里$f$和$k(x,\cdot)$都是一个函数，也可以将其视作一个无限维的向量，所以上面的求导就说得通了。
在offline场景下，我们考虑结构风险最小化：
\[\min_f\quad\frac1m\sum_{i=1}^m\ell(y_i,f(x_i))+\lambda\Omega[f],\lambda>0\]在online场景中，我们只能考虑随机优化结构风险，即用$x_t,y_t$作为损失函数进行优化：
\[\min_{f}\quad R_{\text{stoch}}[f,t]=\ell(y_t,f(x_t))+\lambda\Omega[f]\]对上式求导，正则化项取$\Vert{f}\Vert^2/2$
\[\begin{aligned} \partial_fR_{\text{stoch}}[f,t]&=\partial_f\ell(y_t,f(x_t))+\lambda\partial_f\Omega[f]\\ &=\ell'(y_t,f(x_t))\partial_ff(x_t)+\lambda f\\ &=\ell'(y_t,f(x_t))k(x_t,\cdot)+\lambda f \end{aligned}\]令学习率为$\eta(\eta>0)$，那么有更新规则
\[\begin{aligned} f&\to f-\eta\partial_fR_{\text{stoch}}[f,t]\\ &=(1-\eta\lambda)f-\eta\ell'(y_t,f(x_t))k(x_t,\cdot) \end{aligned}\]上式的表述是抽象的，我们需要将$f$参数化：
\[f(x)=\sum_{i}^t\alpha_ik(x_i,x)\]其中$x_i$是已经见过的样本。基于核的在线学习，实际上是不断将已经见过的样本对应的核函数加入到分类器中。$f$的更新本质上是$\alpha_i$的更新，所以更新规则改写成
\[\begin{aligned} \sum_{i}^{t}\alpha_ik(x_i,\cdot)&\to(1-\eta\lambda)\sum_{i}^{t-1}\alpha_ik(x_i,\cdot)-\eta\ell'(y_t,f(x_t))k(x_t,\cdot)\\ &=\sum_{i}^{t-1}(1-\eta\lambda)\alpha_ik(x_i,\cdot)-\eta\ell'(y_t,f(x_t))k(x_t,\cdot) \end{aligned}\]所以当$i\neq t$，$\alpha_i$衰减$1-\eta\lambda$，更新后$\alpha_t$为$-\eta\ell’(y_t,f(x_t))$。所以$\alpha_i$的表达式是可以写出来的：
\[\begin{aligned} \pmb\alpha_1&=\begin{bmatrix}-\eta\ell'(y_1,f(x_1))\end{bmatrix}^\top\\ \pmb\alpha_2&=\begin{bmatrix}-(1-\eta\lambda)\eta\ell'(y_1,f(x_1))&-\eta\ell'(y_2,f(x_2))\end{bmatrix}^\top\\ \pmb\alpha_3&=\begin{bmatrix}-(1-\eta\lambda)^2\eta\ell'(y_1,f(x_1))&-(1-\eta\lambda)\eta\ell'(y_2,f(x_2))&-\eta\ell'(y_3,f(x_3))\end{bmatrix}^\top\\ \pmb\alpha_4&=\cdots\\ \pmb\alpha_t&=\begin{bmatrix} -(1-\eta\lambda)^{t-1}\eta\ell'(y_1,f(x_1))\\\vdots\\-(1-\eta\lambda)^{t-i}\eta\ell'(y_i,f(x_i))\\\vdots\\ -(1-\eta\lambda)\eta\ell'(y_{t-1},f(x_{t-1}))\\ -\eta\ell'(y_t,f(x_t)) \end{bmatrix} \end{aligned}\]所以一个高效实现的技巧便是存储$(1-\eta\lambda)$的幂次，避免重复浮点计算。可以发现随着时间不断推移，$\pmb\alpha$是线性增长的，带来的是计算量和存储的增加。然而我们也可以发现，时间推移使得靠前的样本权重不断减小，在$\tau$轮迭代后，$\alpha_i$会变成原来的$(1-\eta\lambda)^\tau$倍。所以我们可以使用“截断”，即只考虑最近的$\tau$个样本的核函数作为分类器。
Proposition：给定利普希茨常数为$C$的损失函数$\ell$，以及范数有界的核函数：$\Vert k(x,\cdot)\Vert\leq X$，如果我们删除$t-\tau+1$之前所有样本的核函数作为截断，那么其导致的误差是有界的
\[\Vert f-f_{\text{trunc}}\Vert\leq\sum_{i=1}^{t-\tau}\eta(1-\eta\lambda)^{t-i}CX\lt\lambda^{-1}(1-\eta\lambda)^\tau CX\]其中$f_{\text{trunc}}=\sum_{i=t-\tau+1}^t\alpha_ik(x_i,\cdot)$。这是一个简单的等比级数求和，这里省略证明。
这种截断设计不仅能够节省计算和存储，还能够定期遗忘样本，可以应对分布变化，即concept drift的状况。
接下来看几个理论结果。考虑我们使用软间隔损失函数：
\[\ell(y, f(x))=\max(0,\rho-yf(x))\]其中$\rho$是一个固定超参数。令$f_t$为看到前面$t-1$个样本得到的假设模型，即
\[f_t=\sum_{i=1}^{t-1}\alpha_ik(x_i,\cdot)\]在第$t$轮，算法先得到输入$x_t$，做出预测，然后得到正确标签$y_t$，依照前面的算法将$f_t$更新到$f_{t+1}$。我们现在想要求累积损失$\sum_{t=1}^mR_{\text{stoch}}[f_t,t]$的上界。假如在线学习中分布固定，即都是从分布$P$中采样，那么定义
\[R_\text{P}[f]=E_{(x,y)\sim P}[\ell(y,f(x))]+\lambda\Omega[f]\]我们希望在线假设$f_t$能够收敛到$f_\star=\arg\min_{f}R_{\text{P}}[f]$。只要累积损失的渐进复杂度为$mR_{\text{stoch}}[f_\star,t]+o(m)$，那么就说明$f_t$可以收敛到$f_\star$（其实就是次线性遗憾界）。
首先我们要获取累积损失的上界，这里的正则化项仍然为$\ell_2$范数正则。首先有定理1：
令$((x_t,y_t))_{t=1}^m$为一个样本序列，且每个样本都满足$k(x_t,x_t)\leq X^2$。固定$B>0$，$\eta=B/(X\sqrt m)$，那么对于任意满足$\Vert g\Vert\leq B$的$g$，我们有
\[\sum_{i=1}^mR_{\text{stoch}}[f_t,t]\leq\sum_{i=1}^mR_{\text{stoch}}[g,t]+BX\sqrt m+O(1)\]
这个bound是没有任何概率假设的，如果一个$g$能做得很好，那么在线学习器的表现也很好。但有一点，这里的学习率需要预先设定，随着序列越长，学习率就越小。我们可以用逐步衰减的学习率来避免这个情况。这样会导出一个类似的界，但是常数项会更大一点：
令$((x_t,y_t))_{t=1}^m$为一个样本序列，且每个样本都满足$k(x_t,x_t)\leq X^2$。固定$B>0$，设置$\eta_t=1/(3\lambda\sqrt t)$，那么对于任意满足$\Vert g\Vert\leq B$的$g$，我们有
\[\sum_{i=1}^mR_{\text{stoch}}[f_t,t]\leq\sum_{i=1}^mR_{\text{stoch}}[g,t]+2\lambda(B+\frac{X}{\lambda})^2\sqrt m+O(1)\]
现在我们假设样本是独立同分布的：
令$P$是$\mathcal{X}\times\mathcal{Y}$上的分布，使得$k(x,x)\leq X^2$对$(x,y)\sim P$以1的概率成立。令$\hat{f}m=(1/m)\sum{t=1}^{m-1}f_t$，其中$f_t$是第$t$步根据$P$上分布采样数据学出来的模型。固定$B>0$，更新学习率$\eta_t=1/(3\lambda\sqrt t)$，那么对于任意满足$\Vert g\Vert\leq B$的$g$，我们有
\[E[R_\text{P}[\hat{f}_m]]\leq R_\text{P}[g]+2\frac{\lambda}{\sqrt m}(B+\frac{X}{\lambda})^2+O(\frac1m)\]
这是一个次线性遗憾界。
