点对学习（pairwise learning）在数据挖掘和机器学习中占有很重要的地位. 在数据挖掘方面，主要的应用场景有运营式传统行业、互联网领域、物联网领域等^[1]；在机器学习方面，包括排序^[2-5]、接收机操作特性曲线的面积计算^[6]、度量学习^[7]等.

关于在线点对学习泛化性的研究，Wang等人^[8]建立的损失函数是一致有界条件下的泛化分析，给出遗憾界$O({T^{ - 1}})$. Ying等人^[9-10]基于非正则的再生核希尔伯特空间（reproducing kernel Hilbert space, RKHS）的在线点对学习算法，在损失函数没有强凸性和有界性的假设条件下，得到遗憾界$O\left( {{T^{ - 1/3}}\log T} \right)$. Chen等人^[11]假设迭代序列满足更紧的一致约束，给出遗憾界$O\left( {{T^{ - 1/2}}} \right)$，同时提高了算法最后一次迭代的收敛率. Guo等人^[12]基于正则的RKHS，对于特定的铰链损失函数有$O\left( {{T^{ - 1/4}}\log {T^{1/2}}} \right)$收敛率. Wang等人^[13]分析了具有多项式衰减步长和多个正则化参数的在线点对学习算法最后一次迭代的收敛性，给出遗憾界$O\left( {{T^{ - 2/3}}} \right)$. 文献[14]提出了基于分而治之策略的多正则化项的分布式在线点对学习的误差分析.

作为用来分析泛化性的重要工具之一，稳定性分析已经被广泛应用于单点学习算法的泛化边界研究^[15-16]. 但是，除了Shen等人^[17]和Lei等人^[18]的工作以外，关于点对学习的稳定性研究较少. Shen等人^[17]建立了随机梯度下降（stochastic gradient descent, SGD）在凸和强凸损失函数中的稳定性结果，从而给出了泛化边界，并权衡了SGD下的泛化误差和优化误差，Lei等人^[18]提供了一个更细化的稳定性分析，并将泛化边界改进为$O(\gamma \log n)$.

以上所述都是假设损失函数是强凸或一般凸，缺乏对非凸损失函数的在线点对学习的理论分析. 针对这一问题，本文基于稳定性分析，提出了非凸损失函数的在线点对学习的遗憾界. 本文包含2点贡献：1）提出了可以扩展到非凸损失函数的广义在线点对学习框架；2）建立了该框架下稳定性和遗憾界之间的关系，并给出了该框架的遗憾界及理论分析.

1.   广义在线点对学习框架

1.1   广义在线点对学习

传统的机器学习与在线学习模式不同，传统的机器学习中，一次性地取全部训练样本进行学习，样本分为训练样本和测试样本. 而在线学习没有训练样本和测试样本的区分，学习者（learner）实时获取样本，每获取到1个实例，就调整1次假设.

假设一个样本空间$Z{\mathbf{ = }}X \times Y$，其中$X \subset {\mathbb{R}^d}$是一个输入空间，$Y \subset \mathbb{R}$是一个输出空间，${{\boldsymbol{x}}} \in X$和$y \in Y$分别是输入和输出. 在线点对学习的学习过程迭代$T$轮，学习者每轮接收2个实例$({{\boldsymbol{x}}_t},{y_t}),({\boldsymbol{x}}_t^\prime ,y_t^\prime )$，并进行预测，然后接收标签，再依损失函数${\ell _t} \in L$遭受的损失更新假设${{\boldsymbol{w}}_{t + 1}} \in W$.

广义在线点对学习表示为

显而易见，与在线点对学习模型相比，广义在线点对学习是一个更鲁棒、更广义的框架. 该框架中包含一个${{\boldsymbol{\sigma }}}$项，${{\boldsymbol{\sigma }}}$项是一个从${\text{exp}}(\eta )$（参数为$\eta$的指数分布）采样的随机噪声. 引入随机噪声项${{\boldsymbol{\sigma }}}$避免过拟合，从而提高在线点对学习的泛化能力. 因此，广义在线点对学习是鲁棒的在线点对学习，是一个更广义的在线框架. FTRL（follow the regularized leader）是一种广泛用于凸假设的非常有效的算法^[19]. 事实上，当广义在线点对学习中的随机噪声为$\mu {{\boldsymbol{w}}}$时，FTRL即为广义在线点对学习的一个特例：

1.2   离线神谕模型

直觉上，度量在线学习质量的方式是学习者遭受的损失函数的累计加和，学习者的目标是使累计损失尽可能的小，这也是一般学习模式性能度量的方式. 但是，在线学习中的数据通常是对抗性生成的，对手知道学习者的所有信息，包括学习者给出的预测函数和损失函数等. 因此，对手总是会给出与学习者预测值相反的标签，使得学习者的预测总是错误的，并遭受最大的损失. 在这种对抗环境中，累计损失的度量方式难以奏效，为了解决这个问题，引入了专家（expert）这一概念. 专家就是一个映射集合$h:X \to Y$，对输入${\boldsymbol{x}} \in X$给出预测$h({\boldsymbol{x}})$，与学习者不同的是，专家是固定的，学习者会随着时间根据损失进行更新，而专家给出的预测不会受到对手影响. 采用专家的损失作为参考，矫正学习者的预测，学习者在专家中选择的时候，只需要选择对输入实例的累计损失函数值最小的专家，即最优专家. 有了专家的参与，在线学习性能度量方式就是学习者遭受的损失与最优专家的损失之差的累计加和，以此避免对手的干扰.

有专家建议的在线点对学习是学习者和对手之间的重复游戏，其特征是学习者可以从含有$N$个专家的有限集合$H$中进行选择，对手从一组决策集合$Y$中选择，还有一个损失函数${\ell _t} \in L$. 首先，在游戏开始前，对手从$Y$中选择一个任意的决策序列${y_1},{y_2}, …$，在游戏的每一轮$t = 1,2, …$，学习者必须选择（可能是随机的）一个专家${h_t} \in H$，然后对手揭示其决策${y_t} \in Y$，学习者遭受损失. 学习者每接收到一对实例${z},{{z}^\prime } \in Z$后的目标是使学习者遭受的损失与最优假设${{\boldsymbol{w}}^*} \in W$的损失之间的累积差尽可能的小，因此，遗憾界是衡量在线点对学习性能的标准，对于算法$\mathcal{A}$定义为

基于神谕的学习模型可称之为“可优化的专家”，该模型本质上是经典的在线学习模型，即学习者通过专家的建议和一个离线神谕进行预测. 在“可优化的专家”模型中，假设最初学习者对损失函数$\ell$是未知的，并允许学习者通过神谕来获取$\ell$. 离线神谕模型是通过学习者提交一系列的损失函数，返回使得累积损失最小的假设. 定义1给出离线神谕模型的一种近似神谕模型定义.

定义1.^[20] 一个离线神谕模型，其输入是一个损失函数$\ell :W \to \mathbb{R}$和一个$d$维向量${{\boldsymbol{\sigma}} }$，输出是一个${{\boldsymbol{w}}} \to \ell ({\boldsymbol{w}}, {z},{{z}^\prime }) - \langle {{\boldsymbol{\sigma}} },{\boldsymbol{w}}\rangle$的近似最小值. 若它返回的${{\boldsymbol{w}}^*} \in W$满足

则称其为“$(\alpha ,\beta )$-近似神谕”.

为 方 便 起 见，将 一 个 “$(\alpha ,\beta )$-近 似 神 谕” 记 为${{ORA}}{{{L}}_{\alpha ,\beta }} (\ell - \langle {{\boldsymbol{\sigma}} }, \cdot \rangle )$. 使用近似神谕是因为我们不可能知道一个假设是全局最小值还是仅为一个鞍点. ${{ORAL}}$可以输出一个${{\boldsymbol{w}}}$而不需要保证其最优性. 在大多数情况下，${\boldsymbol{w}}$实际上只是近似最优. 离线神谕模型 （返回${{\boldsymbol{w}}^*} \in \arg \; \min \ell ({\boldsymbol{w}})$）与$(\alpha ,\beta )$-近似神谕模型的区别在于，近似神谕模型有一个关于变量$\alpha$，$\beta$，${{\boldsymbol{\sigma}} }$的扰动项. 在指定变量$\alpha$和$\beta$的大小时可以获得更好的遗憾界. 近似神谕模型关于在线单点学习的应用包括的实例有：当Query-GAN算法采用近似神谕时，对于非凸损失函数以${T^{ - 1/2}}$的速度收敛^[21]，$\alpha = \dfrac{{\hat R + {R_d}(T)}}{T}$（$\hat R$为累积遗憾）；FTRL和FTL（follow the leader）算法采用近似神谕时，对于半凸损失函数可以达到${T^{ - 1}}$的遗憾界^[22]，$\alpha = {T^{ - 1/2}}$. 在上述应用中，$\beta {\text{ = }}0$，只有$\alpha$被用作近似神谕的参数.

2.   非凸广义在线点对学习的稳定性分析

2.1   非凸广义在线点对学习算法

非凸广义在线点对学习算法的原理是迭代$T$轮，每轮产生一个随机向量${{\boldsymbol{\sigma }}}$（该向量服从关于参数$\eta$的指数分布），并获得一个假设${{\boldsymbol{w}}}$，该假设来自于$(\alpha ,\beta )$-近似离线神谕模型，然后，学习者会遭受相应损失并调整假设. 算法1给出当学习者可以访问$(\alpha ,\beta )$-近似离线神谕的非凸广义在线点对学习的算法.

算法1.非凸的广义在线点对学习算法.

输入：参数$\eta$，近似神谕${{ORAL}_{\alpha ,\beta }}$；

输出：${{{\boldsymbol{w}}}^*} \in W$.

① for $t = 1,2, … ,T$ do

②　$\left\{ {{\sigma _{t,j}}} \right\}_{j = 1}^d\mathop \sim \limits^{{\rm{i}}{\rm{.i}}{\rm{.d}}} \exp (\eta )$；/*生成随机向量${{\boldsymbol{\sigma }}_t}$*/

③　学习者在时刻$t$的假设：

④　　${{{\boldsymbol{w}}}_t} = {ORAL}_{\alpha ,\beta }\left( {\displaystyle \sum\limits_{i = 1}^{t - 1} {{\ell _i}} - \left\langle {{{{\boldsymbol{\sigma}} }_t}, \cdot } \right\rangle } \right)$；

⑤　学习者遭受损失${\ell _t}$；

⑥ end for

与在线点对学习相比，广义在线点对学习中包含一个${\boldsymbol{\sigma }}$项，是一个具有更强鲁棒性、更广义的算法. 一些在线学习算法，如在线镜像下降（online mirror descent，OMD）^[23]、 在线梯度下降（online gradient decent ，OGD） ^[24]、FTL、FTRL等，通常需要在凸甚至强凸的条件下实现收敛. 文献[20]通过损失函数的随机扰动来保证遗憾消失，这种随机扰动具有与FTRL和OMD中使用的显式正则项类似的作用，将广义在线单点学习算法扩展到非凸设置中，然而缺少关于非凸在线点对学习的内容. 针对这一问题，本文将单点学习扩展到点对设置中，通过稳定性分析将在线点对中的点对耦合进行解耦，从形式上把具有耦合的点对通过稳定性分析变换成2步假设之间的差，从而实现单点到点对学习的推广.

2.2   稳定性分析

算法稳定性是机器学习理论分析中一个重要的概念. 稳定性可以衡量一个学习算法的输出对训练数据集微小变化的敏感性. 对于批量学习假设中独立同分布的样本，稳定性是可学习性的一个关键特性. 类似地，对于在线学习的可学习性，稳定性条件也是同样有效的. 一种特别常用的稳定性度量方式是一致稳定性，已经被广泛应用到在线点对学习中，除此以外，还有由定义2给出的平均稳定性. 下文中用${{\boldsymbol{a}}^{\text{T}}}{\boldsymbol{b}}$或$\langle {\boldsymbol{a}},{\boldsymbol{b}}\rangle$表示${\boldsymbol{a}}$和${\boldsymbol{b}}$之间的欧几里得点积. 用$\Vert \cdot \Vert$表示2范数，$\Vert \cdot {\Vert }_{p}$来表示一个特定的${\ell _p}$范数. 若$\left| {f(x) - f(y)} \right| \leqslant G\left\| {x - y} \right\|,\forall x,y \in \mathcal{C}$，则称$f:\mathcal{C} \to \mathbb{R}$是关于$\Vert \cdot \Vert$范数$G$-Lipschitz连续的.

定义2.^[18,25] 假设学习者遭受的损失序列是$G$-Lipschitz连续的. 若$\exists \gamma \gt 0$使得

则称算法$\mathcal{A}$是$\gamma -$平均稳定的.

显然，平均稳定性比一致稳定性（$||{\ell _t}\left( {{{{\boldsymbol{w}}}_t},z,{z^\prime }} \right) -$${\ell _{t + 1}}\left( {{{{\boldsymbol{w}}}_{t + 1}},{z},{z^\prime }} \right)|| \leqslant G\gamma$）更弱，因为前者要求的条件仅仅是${{{\boldsymbol{w}}}_t}$的期望值和平均值满足不等式（1）. 本文主要研究平均稳定性，所有定理采用的也是平均稳定性，以此放松理论分析中的假设条件.

稳定性分析首先将广义在线点对学习的期望遗憾与平均稳定性建立联系. 如定理1所示，构建了广义在线点对学习的期望遗憾与平均稳定性的相关性.

定理1. 假设$D$为决策集$W \subseteq {\mathbb{R}^d}$的界，学习者遭受的损失满足${\ell _1}$范数的$G$-Lipschitz连续性. 则广义在线点对学习的遗憾上界可以表示为

证明. 在“遗忘的对手”模型中，假设对手的决策${\text{\{ }}{\ell _t}{\text{\} }}_{t = 1}^T$与广义在线点对学习算法的假设$\{ {{\boldsymbol{w}}_t}\} _{t = 1}^T$无关，假设损失函数的序列${\text{\{ }}{\ell _t}{\text{\} }}_{t = 1}^T$是预先固定的. 而在“非遗忘的对手”模型中，对手的决策取决于算法过去的假设，即每个${\ell _t}$由来自某函数${L_t}:{W^{t - 1}} \to F$的${\ell _t}: = {L_t}[{{\boldsymbol{w}}_{ \lt t}}]$给出，其中$F$是对手所有可能决策的集合，${{\boldsymbol{w}}_{ \lt t}}$是${{\boldsymbol{w}}_1}, {{\boldsymbol{w}}_2}, … ,{{\boldsymbol{w}}_{t - 1}}$的缩写，${L_t}$是一个常数函数，其中函数${L_1},{L_2}, … ,{L_T}$决定了一个非遗忘的对手. 令${P_t}$是广义在线点对学习基于之前的假设${{\boldsymbol{w}}_{ \lt t}}$给出的假设${{\boldsymbol{w}}_t}$的条件分布，若在“遗忘的对手”中，${P_t}$独立于${{\boldsymbol{w}}_{ \lt t}}$. 但无论是在“遗忘的对手”模型或是“非遗忘的对手”模型中，${P_t}$都完全由对手之前的决策${\ell _{ \lt t}}$决定. 任何对“遗忘的对手”有界的算法对“非遗忘的对手”也有界^[26]，令$B$是一个正常数，假设广义在线点对学习满足对“遗忘的对手”的遗憾约束${E}\left[ {\displaystyle \sum\limits_{t = 1}^T {{\ell _t}({{\boldsymbol{w}}_t})} - \mathop {\inf }\limits_{{{{\boldsymbol{w}}}} \in W} \displaystyle \sum\limits_{t = 1}^T {{\ell _t}({\boldsymbol{w}})} } \right] \leqslant B, \forall {\ell _1}, {\ell _2}, … ,{\ell _T} \in F$，那么它也满足对“非遗忘的对手”的遗憾约束$\displaystyle \sum\limits_{t = 1}^T {{\ell _t}({P_t})} - \mathop {\inf }\limits_{{\boldsymbol{w}} \in W} \displaystyle \sum\limits_{t = 1}^T {{\ell _t}({\boldsymbol{w}})} \leqslant B$.

本文研究“遗忘的对手”设定，因此只需使用单一的随机向量${\boldsymbol{\sigma }}$，而不是在每次迭代中生成一个新的随机向量. ${{\boldsymbol{w}}_t}({\boldsymbol{\sigma }})$为非凸广义在线点对学习基于随机扰动${\boldsymbol{\sigma }}$，在第$t$次迭代时的假设.

对于任意${{\boldsymbol{w}}^*} \in W$，都有

令$\gamma ({\boldsymbol{\sigma }}) = \alpha + \beta {\left\| {\boldsymbol{\sigma }} \right\|_1}$. 由归纳法证明

步骤$T$= 1：由于${{\boldsymbol{w}}_2}$是${\ell _1}({\boldsymbol{w}},z,{z^\prime }) - \langle {\boldsymbol{\sigma }},{\boldsymbol{w}}\rangle$的近似最小化，因此

式（3）中最后一个不等式对任何${{\boldsymbol{w}}^*} \in W$均成立. 即

归纳步骤：假设归纳对所有$T \leqslant {T_0} - 1$成立，下面证明它对${T_0}$也成立.

其中①处是由于归纳对任何$T \leqslant {T_0} - 1$都成立，而②处是由于${{\boldsymbol{w}}_{{T_0} + 1}}$的近似最优化.

由上述结果，得到非凸的广义在线点对学习的期望遗憾上界：

由指数分布的属性${E}\left[ {{\sigma _i}} \right] = \dfrac{1}{{{\eta _i}}}$，得证.证毕.

定理1表明期望遗憾与平均稳定性相关. 式（2）中的稳定性即为定义2中的平均稳定性. 定理1的证明是受文献[26]的启发，证明了当平均稳定性的上界可得时，遗憾也可以实现收敛. 因此，定理2将着重于研究稳定项${E}\left[ {{{\left\| {{{\boldsymbol{w}}_t} - {{\boldsymbol{w}}_{t + 1}}} \right\|}_1}} \right]$的上界.

定理2. ${{\boldsymbol{w}}_t}({\boldsymbol{\sigma }})$为广义在线点对学习在第$t$次迭代时的假设，其中，${\boldsymbol{\sigma }}$为随机扰动. ${{\boldsymbol{e}}_i}$表示第$i$个标准基向量，${{\boldsymbol{w}}_{t,i}}$表示${{\boldsymbol{w}}_t}$在$i$坐标上的假设. 对于任意$c \gt 0$，都有单调性成立：

证明. 令${\ell _{1:t}}({\boldsymbol{w}},z,{z^\prime }) = \displaystyle \sum\limits_{i = 1}^t {{\ell _i}} ({\boldsymbol{w}},z,{z^\prime })$，${{\boldsymbol{\sigma }}^\prime } = {\boldsymbol{\sigma }} + c{{\boldsymbol{e}}_i}$，$\gamma ({\boldsymbol{\sigma }}) = \alpha + \beta {\left\| {\boldsymbol{\sigma }} \right\|_1}$为离线神谕的近似误差. 由${{\boldsymbol{w}}_t}({\boldsymbol{\sigma }})$的近似最优化，得

其中①处是由于${{\boldsymbol{w}}_t}\left( {{{\boldsymbol{\sigma }}^\prime }} \right)$的近似最优化. 结合式（4）中的第1项和最后1项，得

${{\boldsymbol{w}}}_{t,i}\left({\boldsymbol{\sigma}}^{\prime }\right)\ge {\boldsymbol{w}}_{t,i}(\boldsymbol{\sigma})-\dfrac{2\gamma (\boldsymbol{\sigma})}{c}-\beta .$ 证毕.

定理2证明了包含随机扰动项${\boldsymbol{\sigma }}$的广义在线点对学习的稳定性. 通过观察扰动向量的变化对广义在线点对学习的输出产生的影响，表明了其在一维情况下的单调性，由于在线学习中稳定性是指相邻2次迭代得到的假设之间的距离，因此，定理2得到的即为一维情况下的稳定性.

定理3. ${{\boldsymbol{w}}_t}({\boldsymbol{\sigma }})$为广义在线点对学习在第$t$次迭代时的假设，其中${\boldsymbol{\sigma }}$为随机扰动. ${{\boldsymbol{e}}_i}$表示第$i$个标准基向量，${{\boldsymbol{w}}_{t,i}}$表示${{\boldsymbol{w}}_t}$在$i$坐标上的假设. 假设${\left\| {{{\boldsymbol{w}}_t}({\boldsymbol{\sigma }}) - {{\boldsymbol{w}}_{t + 1}}({\boldsymbol{\sigma }})} \right\|_1} \leqslant 10d\left| {{{\boldsymbol{w}}_{t,i}}({\boldsymbol{\sigma }}) - {{\boldsymbol{w}}_{t + 1,i}}({\boldsymbol{\sigma }})} \right|$，对于${{\boldsymbol{\sigma }}^\prime } = {\boldsymbol{\sigma }} + 100Gd{{\boldsymbol{e}}_i}$，有单调性成立：

证明. 令${\ell _{1:t}}({\boldsymbol{w}},z,{z^\prime }) =\displaystyle \sum\limits_{i = 1}^t {{\ell _i}} ({\boldsymbol{w}},z,{z^\prime })$，${{\boldsymbol{\sigma }}^\prime } = {\boldsymbol{\sigma }} + c{{\boldsymbol{e}}_i}$，$\gamma ({\boldsymbol{\sigma }}) = \alpha + \beta {\left\| {\boldsymbol{\sigma }} \right\|_1}$为离线神谕的近似误差. 由${{\boldsymbol{w}}_t}({\boldsymbol{\sigma }})$的近似最优化，得

其中①处是由于${\ell _t}( \cdot )$的Lipschitz连续性，②处是由于${\left\| {{{\boldsymbol{w}}_t}({\boldsymbol{\sigma }}) - {{\boldsymbol{w}}_{t + 1}}({\boldsymbol{\sigma }})} \right\|_1}$上的假设. 由${{\boldsymbol{w}}_{t + 1}}\left( {{{\boldsymbol{\sigma }}^\prime }} \right)$的近似最优化，得

其中①处是由于${{\boldsymbol{w}}_{t + 1}}({\boldsymbol{\sigma }})$的近似最优化. 结合式（5）和式（6），得

同理

从定理2中的单调性，得

结合上述不等式（7）~（10）得证. 证毕.

定理3证明了$d$维情况下广义在线点对学习的稳定性. 虽然$d$维相较于一维的单调性证明会更具挑战性，但可以通过分别改变扰动项的每个坐标来有效地将分析减少到一维. 同理，定理2由单调性表明在线点对学习的稳定性可得$d$维情况下的稳定性.

3.   非凸广义在线点对学习的遗憾界

利用定理1所给出的非凸的广义在线点对学习稳定性分析，对其遗憾界进行研究. 由于定理2和定理3分别给出了一维和高维情况稳定性${E}\left[ {{{\left\| {{{\boldsymbol{w}}_t} - {{\boldsymbol{w}}_{t + 1}}} \right\|}_1}} \right]$的界，结合定理2和定理3引导定理4，对定理4进行讨论.

定理4. 假设$D$为决策集$W \subseteq {\mathbb{R}^d}$的界. 学习者遭受的损失满足${\ell _1}$范数的$G$-Lipschitz连续性. 学习者可访问$(\alpha, \beta)$-近似神谕. 对于任意$\eta$，广义在线点对学习的假设都满足遗憾界：

证明. 使用与定理2和定理3中相同的符号定义，${E}\left[ {{{\left\| {{{\boldsymbol{w}}_t}({\boldsymbol{\sigma }}) - {{\boldsymbol{w}}_{t + 1}}({\boldsymbol{\sigma }})} \right\|}_1}} \right]$也记作

因此，由${E}\left[ {\left| {{{\boldsymbol{w}}_{t,i}}({\boldsymbol{\sigma }}) - {{\boldsymbol{w}}_{t + 1,i}}({\boldsymbol{\sigma }})} \right|} \right],\forall i \in [d]$的界，可得${E}\left[ {{{\left\| {{{\boldsymbol{w}}_t}({\boldsymbol{\sigma }}) - {{\boldsymbol{w}}_{t + 1}}({\boldsymbol{\sigma }})} \right\|}_1}} \right]$的界. 对于任意的$i \in [d]$，定义${{E}_{ - i}}\left[ {\left| {{{\boldsymbol{w}}_{t,i}}({\boldsymbol{\sigma }}) - {{\boldsymbol{w}}_{t + 1,i}}({\boldsymbol{\sigma }})} \right|} \right]$为

其中${\sigma _j}$是${\boldsymbol{\sigma }}$第$j$个坐标值.

令${{\boldsymbol{w}}_{\max ,i}}({\boldsymbol{\sigma }}) = \max \left( {{{\boldsymbol{w}}_{t,i}}({\boldsymbol{\sigma }}),{{\boldsymbol{w}}_{t + 1,i}}({\boldsymbol{\sigma }})} \right)$. 类似地，令${{\boldsymbol{w}}_{\min ,i}}({\boldsymbol{\sigma }}) = \min \left( {{{\boldsymbol{w}}_{t,i}}({\boldsymbol{\sigma }}),{{\boldsymbol{w}}_{t + 1,i}}({\boldsymbol{\sigma }})} \right)$. 则

定义

对式（12）中的${T_1},{T_2}$求取下界：

由于第$i$个坐标的域位于某个长度为$D$的区间内，并且由于${T_1}$和${{E}_{ - i}}\left[ {{{\boldsymbol{w}}_{\max ,i}}({\boldsymbol{\sigma }})} \right]$是这个区间的点，它们的差值被$D$所界限. 所以${T_1}$的下界为${{E}_{ - i}}\left[ {{{\boldsymbol{w}}_{\max ,i}}({\boldsymbol{\sigma }})} \right] - D.$将${T_2}$重新定义为：

改变积分中的1个变量，令${\sigma _i} = \sigma _i^\prime + 100Gd$且${{\boldsymbol{\sigma }}^\prime } = \left( {{\sigma _1},{\sigma _2}, … ,{\sigma _{i - 1}},\sigma _i^\prime ,{\sigma _{i + 1}}, … } \right)$是将在第$i$个坐标的${\boldsymbol{\sigma }}$替换为$\sigma _i^\prime$得到的向量，得

则${T_2} = \exp \left( { - 100\eta Gd} \right){{E}_{ - i}}\left[ {{{\boldsymbol{w}}_{\min ,i}}\left( {{\boldsymbol{\sigma }} + 100Gd{{\boldsymbol{e}}_i}} \right)} \right]$. 将${T_1},{T_2}$的下界代入式（12）中，可得

则${{E}_{ - i}}\left[ {{{\boldsymbol{w}}_{\min ,i}}({\boldsymbol{\sigma }})} \right]$下界：

其中${{P}_{ - i}}({\varepsilon}): = {P}\left( {{\varepsilon}|{{\left\{ {{\sigma _j}} \right\}}_{j \ne i}}} \right)$. 由定理2和定理3证明的单调性，得${{E}_{ - i}}\left[ {{{\boldsymbol{w}}_{\min ,i}}({\boldsymbol{\sigma }})} \right]$下界. $\gamma ({\boldsymbol{\sigma }}) = \alpha + \beta {\left\| {\boldsymbol{\sigma }} \right\|_1}$，则

其中式（13）中第1个不等式来自于定理2和定理3，第2个不等式来自于${\varepsilon ^c}$的定义. 由${{P}_{ - i}}(\varepsilon) \leqslant 1$，可得

其中①处是由于$\exp ({\boldsymbol{w}}) \geqslant 1 + {\boldsymbol{w}}$. 得

由于式（14）对任意${\left\{ {{\sigma _j}} \right\}_{j \ne i}}$均成立，因此可得无条件期望的界：

将式（15）代入到式（11）中，可得稳定性界：

将式（16）代入式（2）中，得证. 证毕.

由定理4知，若取$\eta = \dfrac{d}{{{d^{3/2}}{T^{1/2}} - d}}$，可得遗憾界$O\left( {{d^{3/2}}{T^{ - 1/2}} + \alpha + \beta {d^{3/2}}{T^{1/2}}} \right)$. 此外，若取$\alpha = O\left( {{T^{ - 1/2}}} \right), \; \beta = O\left( {{T^{ - 1}}} \right)$，可得遗憾界$O\left( {{T^{ - 1/2}}} \right)$. 关于在线点对学习的理论分析的结论如表1所示.

表  1  在线点对学习遗憾界对比

Table  1.  Comparison of Online Pairwise Learning Regret Bounds

基本假设	遗憾界
一致有界的强凸损失函数	$O({T^{ - 1}})$[8]
具有最小平方损失函数的RKHS	$O\left( {{T^{ - 1/3}}\log T} \right)$[10]
正则的RKHS	$O\left( {{T^{ - 1/4}}\log {T^{1/2}}} \right)$[12]
具有最小平方损失函数的RKHS	$O\left( {{T^{ - 1/2}}} \right)$[11]
具有最小平方损失函数的正则RKHS	$O\left( {{T^{ - 2/3}}} \right)$[13]
具有非凸损失函数的广义在线学习（本文）	$O({T^{ - 1/2}})$

下载: 导出CSV 

| 显示表格

由表1可知，本文对具有非凸损失函数的广义在线点对学习得到了$O({T^{ - 1/2}})$的遗憾界优于已有的遗憾界.

4.   结束语

本文通过引入随机噪声提出了广义在线点对学习框架. 基于文献[26]提出的近似神谕的近似最优假设，提出了非凸广义在线点对学习算法. 进一步，对广义在线点对学习进行泛化性研究，通过稳定性分析，得到广义在线点对学习的遗憾界$O({T^{ - 1/2}})$.

基于在线梯度下降算法，可进一步研究具有非凸损失函数的在线点对学习的遗憾界. 此外，本文中的遗憾界和平均稳定性结果是建立在期望意义下的，而如何得到高概率的界也是未来可进行的工作.

作者贡献声明：郎璇聪负责研究方案的设计、证明推导，以及论文的撰写和修改；李春生指导论文撰写与修改；刘勇提出论文研究思路、设计研究方案；王梅指导论文结构设计.