提出在线学习框架，应对输入被恶意扰动的鲁棒分类问题。
Robust Online Learning
- 将鲁棒学习建模为在线学习问题，引入新维度控制错误率。
- 新维度在可实现与非可实现场景下分别决定误判与累积损失上限。
- 适用于对抗性扰动未知但有先验知识的现实场景。
我们研究鲁棒分类器的学习问题，其中分类器会接收被扰动的输入。与以往研究中仅考虑扰动输入不同，此处干净数据及其标签也由对抗方选择。我们将该设定建模为在线学习问题，考察假设类在可实现与非可实现情形下的可学习性。定义了一种新的类别维度，证明其在可实现设定下控制误判界限，在非可实现设定下控制后悔界限。该维度相较于经典PAC学习中的维度更为简洁，类似Littlestone维数。我们将该维度推广至多分类情形，并在可实现情况下获得类似结果。最后，研究了学习者未知每点允许扰动集，仅具备先验信息的情形。
原文摘要 · Abstract (English)
We study the problem of learning robust classifiers where the classifier will receive a perturbed input. Unlike robust PAC learning studied in prior work, here the clean data and its label are also adversarially chosen. We formulate this setting as an online learning problem and consider both the realizable and agnostic learnability of hypothesis classes. We define a new dimension of classes and show it controls the mistake bounds in the realizable setting and the regret bounds in the agnostic setting. In contrast to the dimension that characterizes learnability in the PAC setting, our dimension is rather simple and resembles the Littlestone dimension. We generalize our dimension to multiclass hypothesis classes and prove similar results in the realizable case. Finally, we study the case where the learner does not know the set of allowed perturbations for each point and only has some prior on them.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。