学习理论：在线弃权学习

上个月京吹新剧场版上映，宇治各种宣发力度挺足的。正好读研时的同学来京都玩，一起去逛了宇治，顺便品抹茶赏樱花。上图就是在宇治市观光中心拍的(#^.^#)。

关于自己的科研进展，目前是读博期间第一份工作已经基本结束，之前先参加了个AISTATS 2026在摩洛哥办的首届workshop并进行了poster发表（论文链接：Multi-Class Classification with absention Based on Crammer–Singer Surrogate with Linear Growth Rate^[1]），然后在摩洛哥的卡萨布兰卡机场完成了往NeurIPS的正式论文提交。这份工作的贡献主要在于基于Crammer-Singer损失为多分类弃权学习给出了凸的代理损失函数族，并在一定的函数配置下可以达到 $O(t)$的excess risk rate，好于目前Mao et al.^[2]那份工作的$O(max\{t,\sqrt{t}\})$的结果（PS: excess risk rate考虑的是$t\to 0$的渐进结果）。关于弃权学习和Mao et al.那份工作的介绍可参见我往期的博客《学习理论：预测器-拒绝器多分类弃权学习》^[3]，后续如果我的那份工作被正式录用了的话也计划写一篇博客进行分享（包括一些在其中用到的证明技巧）。目前的话导师那边已经让我开始构思下一份工作了，于是我接着调研了一下在线弃权学习^[4]的领域情况，本篇博客也就拟对这些领域进行一个大致的介绍。

1 在线弃权学习问题定义

设$X$为输入空间（例如$R^d$的有界子集），$H$为预测器$h:X\to Y$的函数类，并假设$h\in H$ 在有标签样本对$(x,y)\in X\times Y$所计算的损失$l(y,h(x\left)\right)$可以定义为0/1损失$I_{h\left(x\right)\ne y}$或一些其它满足Lipschitz性质的变体。 在在线弃权学习中，有$K$个专家（expert） 对应不同的预测器$h_1(\cdot ),\cdots ,h_K(\cdot )$（可能还会有拒绝器），分别对应$K$个不同的动作（类似bandit中arm）。依赖于设置，$K$可以为有限或（不可数）无限的。假设可供选择的专家集合对学习算法是事先已知的。

大致地说，在线弃权学习的一般流程如下：

在第$t\in \left[T\right]$轮时，在线算法接收输入$x_t\in X$，并根据专家$1,2,\cdots ,K$的输出结果来判定是做预测还是弃权（可能是随机抽取一个专家$I_t$，也可能是多个专家的加权平均）：

• 若选择弃权，则算法弃权并产生一个大小为弃权代价$c\left(x_t\right)\in [0,1]$的损失；

• 否则，根据专家$1,\cdots ,K$的输出$h_1\left(x_t\right),\cdots ,h_K\left(x_t\right)$的来进行预测（可能是随机抽取一个专家$I_t$，也可能是多个专家的加权平均）。

然后，各个专家计算各自的损失$L_{t,i}$，并根据损失更新各个专家的加权参数（如果有的话）。

专家$i$在有标签样本对$z=(x,y)\in X\times Y$上的弃权损失（absention loss） 的典型定义方式为：

$$L(h_i,z)=l(y,h_i(x\left)\right)I_{\text{选择预测}}+c{I}_{\text{选择弃权}}$$

（出于简洁，我们假设弃权代价$c\left(x\right)$为一个独立于$x$的已知常数$c\in [0,1]$）

这个弃权损失与我们在博客《学习理论：预测器-拒绝器多分类弃权学习》^[3]中所介绍的类似，不过这里需要注意的是，标签$y$不一定对所有专家都是可知的：标签$y$可能仅当不弃权时可知^[4]，也可能仅当弃权的时候可知^[8]，也可能无论弃权与否都可知^[9]。而这也就导致了如上式所示的弃权损失函数并不一定对所有专家都是可观测的。对于前两种情况，仅有部分专家可以观测到如上式所示的损失函数，我们称其为是部分信息（partial information） 的 ，而最后一种情况所有专家都可以观测到如上式所示的损失函数，我们称其是 完全信息（full information） 的。

注 所谓部分信息设置可以视为介于完全信息和传统bandit之间的一种设置^[5][7]。此三者的对比如下：

• 完全信息: 每一轮$t$中，学习器可以观测到完整的损失函数$L_t(\cdot )$，因此可以利用函数的信息（比如梯度）更新模型。
• bandit: 每一轮$t$中，学习器通常只能观测到损失函数在所选决策${\xi }_{I_t}$上的值$L_t\left({\xi }_{I_t}\right)$，不能观测到损失函数在其它决策上的值。
• 部分信息: 每一轮$t$中，学习器可以观测到损失函数在一个决策集合$\left\{{\xi }_i\right\}$（包括所选决策${\xi }_{I_t}$在内）上的值${\left\{L_t\right({\xi }_i\left)\right\}}_i$。

部分信息设置的在线学习有时也被称为附加信息的bandit（bandit with side-information）。

和传统bandit问题相似，在线弃权学习也会考虑对抗（adversarial） 和随机（stochastic） 两种设置^[5][7]。

注 传统bandit问题中的对抗和随机设置如下：

• 对抗设置 每一轮$t$中，学习器选择arm ${\xi }_{I_t}$后，一个对手（adversary）对其行动赋予代价$L_t\left({\xi }_{I_t}\right)$。学习器可以观察到行动${\xi }_{I_t}$的代价，除此之外什么也得不到。学习器的目标是最小化它的regret。
• 随机设置 每一轮$t$中，学习器选择arm ${\xi }_{I_t}$后，根据从一个分布中i.i.d采样的损失函数$L_t(\cdot )$来计算其代价$L_t\left({\xi }_{I_t}\right)$。学习器可以观察到行动${\xi }_{I_t}$的代价，除此之外什么也得不到。学习器的目标是最小化它的regret。

具体在在线弃权学习中，它们的区别在于：对抗设置不会对序列$z_t=(x_t,y_t),t\in \left[T\right]$做出分布假设，而随机设置则会假设$z_t$ i.i.d.地采自某个在$X\times Y$上的分布$D$。在这两种设置中，都可以通过算法$A$的（伪）regret $R_T\left(A\right)$ 来度量算法$A$的表现，如果在第$t$轮随机抽取了专家$I_t$，那么它可以采用如下的方式来定义：

$$R_T\left(A\right)=E\left[\sum _{t=1}^{T}L\right(h_{I_t},z_t)-\underset{i\in \left[K\right]}{inf}\sum _{t=1}^{T}L(h_i,z_t\left)\right]$$

其中期望所对应的随机性一是来源于算法所选择的${\left\{I_t\right\}}_{t=1}^T$，二是来源于在随机情形下所采样的${\left\{z_t\right\}}_{t=1}^T$。对于专门设置拒绝器的情况，式子中的$h_{I_t}$和$h$可以分别替换为$(h_{I_t},r_{I_t})$和$(h,r)$。

在随机设置下，考虑专家集合有限的情况，设此时有$K$个专家，则可以将专家 $i\in \left[K\right]$的期望损失和最优专家的期望损失分别表示为：

$${\mu }_i=E_{z\sim D}\left[L\right(h_i,z\left)\right],{\mu }^{\ast }=\underset{i\in \left[K\right]}{min}{\mu }_i$$

其中对于有拒绝器的情况$h_i$可以替换为$h$。然后，可以${\Delta }_i$表示${\mu }_i$和${\mu }^{\ast }$之间的差距：

$${\Delta }_i={\mu }_i-{\mu }^{\ast }$$

这一项经常出现在随机设置相关的regret界中。

2 仅当不弃权时反馈可知

现考虑仅当不弃权时反馈可知的情况，其代表性论文为《Online learning with absention》^[4]。该论文考虑在线二分类场景，设此时的预测器为$h:X\to R$（根据其正负号判断0/1类别），于是0/1损失可以写为$I_{yh\left(x\right)⩽0}$。此外，论文还另外设置有拒绝器$r:X\to R$。设$R$为弃权函数$r:X\to R$的函数类，$r⩽0$表示对$x\in X$进行弃权（或者说拒绝），$r>0$表示对$x$进行预测（或者说接受）。给定$h_i$，一个与之相关的弃权函数$r_i$的自然选择是形如 $r_i\left(x\right)=|h_i\left(x\right)|-\theta$ 的基于置信度的弃权函数，其中$\theta$为某个阈值。除此之外，也可以考虑更多一般形式的$r_i$。

论文算法的基本流程大致如下：在第$t\in \left[T\right]$轮时，在线算法接收输入$x_t\in X$并选择（可能是随机地）一个专家$I_t$。

• 若$r_{I_t}\left(x_t\right)⩽0$，则算法弃权并产生一个大小为弃权代价$c\in [0,1]$的损失。

• 否则，根据$h_{I_t}\left(x_t\right)$的符号来进行预测，并接收真实标签$y_t\in \{\pm 1\}$来计算损失$l(y_t,h_{I_t}(x_t\left)\right)$。

因此，$(h,r)$在标签对$z=(x,y)$上整个弃权损失$L$定义为：

$$L(h,r)=l(y,h(x\left)\right)I_{r\left(x\right)>0}+c{I}_{r\left(x\right)⩽0}$$

这里需要注意的是，如果学习器在第$t$轮选择预测（也即当$r_{I_t}\left(x\right)>0$时），由于标签$y_t$已经暴露给了它，它可以观察到每个专家 $i\in \left[K\right]$的损失$L(h_i,r_i,z_t)$。然而，如果它在第$t$轮选择弃权（也即$r_{I_t}\left(x\right)⩽0$），则它将只观测到与在该轮中选择弃权的专家$j$相关的损失 $L(h_j,r_j,z_t)=c$，其中$j$取自满足$r_j\left(x_t\right)⩽0$的$j$集合。这是因为此时对所有这样的$j$，我们都有$L(h_j,r_j,z_t)=c$。这里需要注意的是，在这两种情况中学习器都可以观测它自己动作$I_t$的损失。

这种部分信息的在线学习设置可以用反馈图（feedback graph） 来描述。带反馈图的在线学习是一个囊括了多种在线学习设置的一般性框架，在完全信息设置下图是全连接的，而在传统bandit设置下顶点通常是只有自环且分离的。设依赖于$x_t$的有向图$G_t^{\text{abs}}=(V,E_t)$。这里，$V=\{{\xi }_1,\cdots ,{\xi }_K\}$表示图的有限顶点集，对应专家组成的有限集。$E_t$表示第$t$轮时的有向边集合。如果当$t$轮时算法选择专家$i$时，专家$j\in \left[K\right]$的损失被观测到，则$E_t$中将会存在边${\xi }_i\to {\xi }_j$。

因此，在仅当不弃权时反馈可知的设置下，反馈图是一个带自环的接近全连接的图，不过在预测顶点和弃权顶点之间，只有从预测顶点到弃权顶点的单向边（下图展示了一个当专家数$K$为5时的一个例子）。

从上图中可以看到反馈图$G_t^{\text{abs}}$完全由$x_t$确定，这是由于$x_t$确定后则可根据$\left\{r_i\right(x_t\left)\right\}$决定每个专家$i$的弃权情况，从而确定反馈图。

依据《Online learning with absention》^[4]这篇论文的作者的观点，对于这种设置下的弃权损失$L(h_i,r_i,z)$，难以找到其代理凸上界来使用在线凸优化方法。事实上，论文作者更多地是采用离散的视角，使用bandit中的许多技术来设计的算法。论文作者讨论了对抗和随机两种设置，我们下面以对抗设置为例进行介绍。而对抗设置又可以具体分为有限和无限个专家的场景。

我们先讨论有限多个专家的对抗设置。论文作者同时结合了诸如EXP3的标准有限arm的bandit算法和反馈图$G_t^{\text{abs}}$来为弃权场景设计在线算法，并将其称为EXP3-ABS（EXP3 with absention）^[4]。该算法为EXP3的变种，其中为了达到对$L_t(h_i,r_i,z_t)$无偏损失估计的重要性采样参数是根据被观测到的专家的损失来计算的，而不是根据被选中的专家的损失来计算的。EXP3-ABS算法的大致流程如下：

• 对每一轮迭代$t\in \left[T\right]$:
  • 采样专家索引
  $$I_t\sim p_t=\frac{w_{t,i}}{\sum w_{t,j}},i\in \left[K\right]$$
  • 如果$r_{I_t}\left(x_t\right)>0$则获得标签$y_t$。
  • 对所有$i\in \left[K\right]$，计算
    $${\hat{L}}_t(h_i,r_i,z_t)=\frac{L_t(h_i,r_i,z_t)}{P_{t,i}}(I_{r_{I_t}\left(x_t\right)⩽0}{I}_{r_i\left(x_t\right)⩽0}+I_{r_{I_t}\left(x_t\right)>0})$$
    其中
    $$P_{t,i}=\{\begin{array}{ccc}& 1& \text{if}{r}_i\left(x_t\right)⩽0\\ & \sum _{i:r_i\left(x_t\right)>0}{p}_{t,i}& \text{if}{r}_i\left(x_t\right)>0\end{array}$$

  • 对所有$i\in \left[K\right]$，做如下更新：
    $$w_{t+1,i}=w_{t,i}\exp (-\eta {\hat{L}}_t(h_i,r_i,z_t\left)\right)$$

该算法满足下列bound：

定理 1 设EXP3-ABS在$K$个专家上以学习率$\eta$运行，于是该算法在$T$轮后满足下列regret保证：

$$R_T\left(\text{EXP3-ABS}\right)⩽\left(\log K\right)/\eta +\eta T(c^2+1)/2$$

特别地，如果EXP3-ABS以$\eta =\sqrt{\frac{2\log K}{(c^2+1)T}}$运行，则有$R_T\left(\text{EXP3-ABS}\right)⩽\sqrt{2(c^2+1)T\log K}$。

这个界对专家个数$K$的依赖相比标准的EXP3更有优势（为$\sqrt{\log K}$而不是$\sqrt{K}$）。可以由此联系到使用上下文bandit算法（contextual bandit algorithm） EXP4达到的界。

接下来考虑不可数无限的专家的情况。为了建模这个更一般的框架，读者可能想要尝试关注函数$h$和$r$的参数化类，也即下列线性函数的类$E$:

$$\left\{\right(h,r):h(x)=w^{\top }x,r(x)=|w^{\top }x|-\theta ,w\in R^d,\theta >0\}$$

并引入一些前文提到的弃权损失$L(h,r,z)$的凸代理并在$(w,\theta )$的参数空间中运行在线凸优化算法^[3]。不过论文作者认为这并不容易，因为这里的代理损失不仅需要确保凸性以及某种形式的校准，也需要确保算法能够观测其自身动作的的损失（也即反馈图$G_t^{\text{abs}}$中的自环）。

论文作者没有通过仅仅求助于凸代理损失来解决这个问题。取而代之地，论文作者引入了满足Lipschitz性质而非凸的代理弃权损失。设每轮迭代的专家$(h,r)$从值域为$E=[-1,1]\times [-1,1]$的连续函数类中采样得到，且假设函数$h$和$r$关于某个$R^d$上的合适度量是$L_E$-Lipschitz的（这里常数$L_E$决定了函数类$E$的大小）。考虑$l(y,h(x\left)\right)=f_{\gamma }(-yh(x\left)\right)$的弃权损失$L(h,r,z)$：

$$L(h,r,z)=f_{\gamma }(-yh(x\left)\right)I_{r\left(x\right)>0}+c\left(x\right)I_{r\left(x\right)⩽0}$$

其中$f_{\gamma }$是一个做为0-1损失函数的变体的分段函数，它在原点斜率为$1/2\gamma$，其定义如下：

$$f_{\gamma }\left(a\right)=\left(\frac{\gamma +a}{2\gamma }\right)I_{\left|a\right|⩽\gamma }+I_{a⩾0}{I}_{\left|a\right|>\gamma }$$

其图像如下：

对于这种不可数无限的情况，使用Cesa-Bianchi等人论文^[5]的idea，作者提出一个在使用弃权设置结构的同时通过有限覆盖来近似动作空间的算法，其中用到了经典的“$ϵ$-网”^[10][11]，在假设原集合有界的情况下尝试用半径为$ϵ$的球去覆盖原集合。这里假设除了$E$之外，输出空间$X$亦有界，则存在常数$C_X>0$使得对所有$0<ϵ⩽1$，$X$都能被至多$C_X{ϵ}^{-d}$个半径为$ϵ$的球覆盖。类似地，存在常数$C_E>0$使得对所有$0<ϵ⩽1$，$E$都能至多被$C_E{ϵ}^{-2}$个半径为$ϵ$的球覆盖。记专家集合$E$关于常数$C_{ϵ}$的覆盖为$C_{ϵ}$。此外，作者在保持反馈假设（即反馈图$G_t^{\text{abs}}）$不变的条件下，定义了做为弃权损失上界的Lipschitz函数$\tilde{L}$。其中一个能够精确解决问题的Lipschitz函数如下：

$$\tilde{L}(h,r,z)=\{\begin{array}{ccc}& c& \text{if}r\left(x\right)⩽-\gamma \\ & 1+\left(\frac{1-c}{\gamma }\right)r\left(x\right)& \text{if}r\left(x\right)\in (-\gamma ,0)\\ & 1-\left(\frac{1-f_{\gamma }(-yh(x\left)\right)}{\gamma }\right)r\left(x\right)& \text{if}r\left(x\right)\in [0,\gamma )\\ & f_{\gamma }(-yh(x\left)\right)& \text{if}r\left(x\right)⩾\gamma \end{array}$$

其中$\gamma \in (0,1)$。$\tilde{L}(h,r,z)$的图像如下图所示：

该图的解释：给定$x$和间隔$a=-yh\left(x\right)$的值（间隔确定后则函数值$f_{\gamma }\left(a\right)\in [0,1]$亦确定），描绘目标弃权损失函数$L(a,r)$（蓝色虚线）和代理弃权损失函数$\tilde{L}(a,r)$（红色实线）随$r=r\left(x\right)\in [-1,1]$的变化。

注意该函数满足反馈假设的要求：若$r_{I_t}\left(x\right)⩽0$，则对使得$r\left(x_t\right)⩽0$的$(h,r)\in E$，算法可以得知$\tilde{L}\left(\right(h\left(x_t\right),r\left(x_t\right)),z_t)$的值（独立于$y_t$）；若$r_{I_t}\left(x\right)>0$，则由于$y_t$被观测到，算法可以得到$\tilde{L}\left(\right(h\left(x_t\right),r\left(x_t\right)),z_t)$关于所有$(h,r)\in E$的完全知识。

论文作者设计了EXP3-ABS的上下文版本以应用于代理损失序列$\tilde{L}(\xi ,z_t),t\in \left[T\right]$。该算法用固定半径$ϵ$的球来自适应地覆盖$X$，每个球对应一个可以运行EXP3-ABS算法的实例。论文作者称这个算法为CONTEXP3-ABS。CONTEXP3-ABS的大致流程如下：

• 对每一轮迭代$t\in \left[T\right]$:
  • 接收$x_t$；
  • 如果$x_t$不属于任何已存在的球，则创建以$x_t$为中心的半径为$ϵ$的新球，并分配一个EXP3-ABS的新实例；
  • 找到离$x_t$最近的现有球中心$x_s$，将该球所对应的实例记为“Active EXP3-ABS”；
  • 使用“Active EXP3-ABS”采样专家
    $$(h,r{)}_{I_t}\in E_{ϵ}$$

  • 获得关于$(h,r{)}_{I_t}$的损失反馈并用其来更新“Active EXP3-ABS”的状态。

定理 2 考虑弃权损失$L(h,r,z)=f_{\gamma }(-yh(x\left)\right)I_{r\left(x\right)>0}+c{I}_{r\left(x\right)⩽0}$并设$(h^{\ast },r^{\ast })={argmin}_{(h,r)\in E}{\sum }_{t=1}^{T}L(h,r,z_t)$，其中$E=\left\{\right(h,r\left)\right\}$由之前提到过的满足Lipschitz性质的函数对组成。如果CONTEXP3-ABS以参数$ϵ\simeq T^{-\frac{1}{2+d}}{\gamma }^{\frac{2}{2+d}}$和一个合适的学习率运行，则它满足以下的regret保证：

$$R_T\left(\text{CONTEXP3-ABS}\right)⩽\tilde{O}\left(T^{\frac{d+1}{d+2}}{\gamma }^{-\frac{d}{d+2}}\right)+M_T^{\ast }\left(\gamma \right)$$

其中$M_T^{\ast }\left(\gamma \right)$是使得$\left|r^{\ast }\right(x_t\left)\right|⩽\gamma$的$x_t$的数量。在上面的叙述中，$\tilde{O}$隐藏了常量与$\ln \left(T\right)$因子，而$\simeq$则忽视了诸如$L_E$的常量与各类log因子。

3 仅当弃权时反馈可知

也有论文假设当学习器选择弃权时反馈可知的，比如《Online Selective Classification with Limited Feedback》^[6]这篇文章。接下来假设不设置拒绝器，而是将标签空间增广为$Y\cup \left\{\perp \right\}$。设$H$为在增广标签空间上定义的预测器$h\left(x\right):X\to Y\cup \left\{\perp \right\}$组成的函数类。

与之前提到的那篇论文类似，该论文也讨论了对抗和随机两种设置。我们下面以随机设置为例进行介绍。专家 $h$在有标签样本对$z=(x,y)\in X\times \{\pm 1\}$上的弃权损失可以定义为：

$$L(h,x,y)=C_{t}l(y,h(x\left)\right)I_{h\left(x_t\right)\ne \perp }+c{I}_{h\left(x_t\right)=\perp }$$

在此基础上，论文提出的Mixed-Loss-Prod算法大致流程如下：

• 对每一轮迭代$t\in \left[T\right]$:
  • 采样专家索引
    $$I_t\sim p_t=\frac{w_{t,i}}{\sum w_{t,j}},i\in \left[K\right]$$

  • 采样伯努利变量 $C_t\sim Bern\left(p\right)$；
  • 如果$C_t=1$则直接返回${\hat{y}}_t=\perp$并获得标签$y_t$，反之返回${\hat{y}}_t=h_i\left(x_t\right)\in Y\cup \left\{\perp \right\}$。
  • 对所有$i\in \left[K\right]$, 计算
    $$L_{t,i}=\{\begin{array}{ccc}& l(y_t,{\hat{y}}_t^i)I_{{\hat{y}}_t^i\ne \perp }+c{I}_{{\hat{y}}_t^i=\perp }& \text{if}{C}_t=1\\ & c{I}_{{\hat{y}}_t^i=\perp }& \text{if}\text{Otherwise}\end{array}$$

  • 对所有$i\in \left[K\right]$, 做如下更新：
    $$w_{t+1,i}=w_{t,i}(1-\eta L(h_i,z_t\left)\right)$$

论文定义了以下两个指标做为算法性能的度量，分别是学习器的犯错数和弃权次数：

$$M_T:=\sum _{t⩽T}{I}_{\hat{y}\notin \{\perp ,y_t\}},A_T=\sum _{t⩽T}{I}_{{\hat{y}}_t=\perp }$$

此外，论文还定义了最佳事后分类器（best-in-hindsight）的概念，也即需要在不犯错的情况下尽量少弃权：

$$f^{\ast }\in {argmin}_{f\in F}\sum _{t⩽T}{I}_{{\hat{y}}_t=\perp },s.t.\sum _{t⩽T}{I}_{\hat{y}\notin \{\perp ,y_t\}}=0$$

对于Mixed-Loss-Prod算法，有如下定理成立：

定理 3 若Mixed-Loss-Prod算法以$\eta =1/2$，$\lambda ⩽c$运行，则满足：

$$E\left[M_T\right]⩽\frac{2\log K}{p}+\frac{2\lambda }{p}E\left[A_T^{\ast }\right],E[A_T-A_T^{\ast }]⩽pT+\frac{2\log K}{\lambda }$$

4 无论弃权与否反馈都可知

也有论文假设无论学习器是否弃权与否反馈都可知的。比如《Fast Rates for Online Prediction with Abstention》^[9]这篇文章。现考虑预测器$h\left(x\right):X\to Y$组成的函数类。论文提出的算法大致流程如下：

• 对每一轮迭代$t\in \left[T\right]$:

  • 对所有专家$i\in \left[K\right]$，计算预测标签${\hat{y}}_{t,i}=h_i\left(x_t\right)\in Y$；

  • 对所有专家的预测标签进行加权平均，得到一个软概率：

    $$p_t=\sum _{i\in \left[K\right]}\frac{w_{t,i}{y}_{t,i}}{{\sum }_{j\in \left[K\right]}{w}_{t,j}}$$

  • 计算置信度参数$p_t^{\ast }=max\{p_t,1-p_t\}$（用于决定是否弃权）；

  • 设弃权概率${\alpha }_t=2(1-p_t^{\ast })$，

    $${\hat{y}}_t=\{\begin{array}{cc}\perp & \text{with probability}{\alpha }_t\\ I_{p_t⩾\frac{1}{2}}& \text{with probability}1-{\alpha }_t\end{array}$$

  • 对所有$i\in \left[K\right]$, 计算

    $$L_{t,i}=l(y_t,{\hat{y}}_{t,i})$$

  • 对所有$i\in \left[K\right]$, 做如下更新：

    $$w_{t+1,i}=w_{t,i}\exp (-\eta L_{t,i})$$

注意由于$p_t^{\ast }⩾\frac{1}{2}$，弃权概率$\alpha \in [0,1]$。为了从直觉上理解这个规则，可以发现当分配给弃权操作一个数值$\perp =\frac{1}{2}$时，预测结果的期望

$$\begin{array}{cc}E\left[p_t\right]& =\frac{1}{2}{\alpha }_t+(1-{\alpha }_t)I_{p_t⩾\frac{1}{2}}\\ & =(1-p_t^{\ast })+(2p_t^{\ast }-1)I_{p_t⩾\frac{1}{2}}\\ & =\{\begin{array}{ccc}& (1-p_t)+(2p_t-1)& \text{if}{p}_t⩾\frac{1}{2}\\ & p_t& \text{if}{p}_t<\frac{1}{2}\end{array}\\ & =p_t\end{array}$$

该算法对应的regret可定义如下：

$$R_T=E[\sum _{t=1}^T{\hat{L}}_t-\underset{i\in \left[K\right]}{inf}\sum _{t=1}^T{L}_{t,i}]$$

其中

$${\hat{L}}_t=\{\begin{array}{ccc}& l(y_t,{\hat{y}}_t)& \text{if}{\hat{y}}_t\in \{0,1\}\\ & c& \text{if}{\hat{y}}_t=\perp \end{array}$$

关于该算法的表现有下列结果：

定理 4 假设$c<\frac{1}{2}$，$\eta ⩽2(1-2c)$。则上述算法的regret满足

$$R_T⩽\frac{\log K}{\eta }$$

特别地，该定理只要弃权损失$c$远离$1/2$，我们都可以设置$\eta =2(1-2c)$且算法可以达到独立于迭代轮数$T$的regret界。然而，当$c$很接近$1/2$时，可能会退回到regret保证为$\sqrt{T\log K}$阶的标准最坏情形。在这种不利情形下，这个阶可以通过选择一个保守的$\eta$值而轻易达到。下面这个关于定理4的推论总结了算法在不同情况下所能达到的率。

推论 1 设$\eta =max\left\{2\right(1-2c),\sqrt{\frac{8\log K}{T}}\}$，算法的regret满足

$$R_T⩽min\{\frac{\log K}{2(1-2c)},\sqrt{\frac{T\log K}{2}}\}$$

参考

• [1] Zhang, Hongyu, Han Bao, and Junya Honda. "Multi-Class Classification with Abstention Based on Crammer–Singer Surrogate with Linear Growth Rate." Towards Trustworthy Predictions: Theory and Applications of Calibration for Modern AI.
• [2] Mao, Anqi, Mehryar Mohri, and Yutao Zhong. "Predictor-rejector multi-class abstention: Theoretical analysis and algorithms." International Conference on Algorithmic Learning Theory. PMLR, 2024.
• [3] 《学习理论：预测器-拒绝器多分类弃权学习》
• [4] Cortes, Corinna, et al. "Online learning with absention." International Conference on Machine Learning. PMLR, 2018.
• [5] Hazan, Elad. "Introduction to online convex optimization." Foundations and Trends in Optimization 2.3-4 (2016): 157-325.
• [6] Cesa-Bianchi, Nicolò, et al. "Algorithmic chaining and the role of partial feedback in online nonparametric learning." Conference on Learning Theory. PMLR, 2017.
• [7] 周志华, 王魏, 高尉, 张利军. 机器学习理论导引[M]. 机械工业出版社, 2020.
• [8] Gangrade, Aditya, et al. "Online selective classification with limited feedback." Advances in Neural Information Processing Systems 34 (2021): 14529-14541.
• [9] Neu, Gergely, and Nikita Zhivotovskiy. "Fast rates for online prediction with abstention." Conference on Learning Theory. PMLR, 2020.
• [10] Zhou, Quan, Mark Kozdoba, and Shie Mannor. "Representative Action Selection for Large Action Space Meta-Bandits." arXiv preprint arXiv:2505.18269 (2025).
• [11] 《学习理论：凸代理、代理与估计误差界》

__EOF__