无需先验分布知识,实现对抗性数据流中的高精度预测与合理弃权。
Distribution-Free Sequential Prediction with Abstentions
- 通过提升弱学习器构造弃权算法,适应未知分布的对抗数据流。
- 对一般VC类保证亚线性错误率,且错误弃权数与误分类数存在多项式权衡。
- 适用于结构化模型如线性分类器,适合关注鲁棒性与可靠性场景的研究者。
我们研究一种序列预测问题:在独立同分布(i.i.d.)数据流中,对手可任意注入对抗性样本,但学习者可在每轮选择弃权而不受惩罚(若样本确实被污染)。该半对抗设定介于经典随机情形(已知分布,有限VC维函数类可学习)与完全对抗情形(任意实例,限制极严)之间。Goel等(2023)表明,若学习者事先知晓干净样本分布μ,所有VC类均可在任意对抗污染下学习。然而这一假设在理论和实践中均过强。本文关注分布无关设定(μ未知),提出基于弱学习器提升的算法AbstainBoost,对静态对手下的一般VC类实现亚线性误差。该算法对自适应对手在结构化函数类(如线性分类器)上也具有类似保障。相应下界揭示了误分类误差与错误弃权数间的有趣多项式权衡。
原文摘要 · Abstract (English)
We study a sequential prediction problem in which an adversary is allowed to inject arbitrarily many adversarial instances in a stream of i.i.d. instances, but at each round, the learner may also abstain from making a prediction without incurring any penalty if the instance was indeed corrupted. This semi-adversarial setting naturally sits between the classical stochastic case with i.i.d. instances for which function classes with finite VC dimension are learnable; and the adversarial case with arbitrary instances, known to be significantly more restrictive. For this problem, Goel et al. (2023) showed that, if the learner knows the distribution $μ$ of clean samples in advance, learning can be achieved for all VC classes without restrictions on adversary corruptions. This is, however, a strong assumption in both theory and practice: a natural question is whether similar learning guarantees can be achieved without prior distributional knowledge, as is standard in classical learning frameworks (e.g., PAC learning or asymptotic consistency) and other non-i.i.d. models (e.g., smoothed online learning). We therefore focus on the distribution-free setting where $μ$ is unknown and propose an algorithm AbstainBoost based on a boosting procedure of weak learners, which guarantees sublinear error for general VC classes in distribution-free abstention learning for oblivious adversaries. These algorithms also enjoy similar guarantees for adaptive adversaries, for structured function classes including linear classifiers. These results are complemented with corresponding lower bounds, which reveal an interesting polynomial trade-off between misclassification error and number of erroneous abstentions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。