Robust Online Learning
This work addresses robust online learning for adversarial environments, offering a novel theoretical framework that is incremental in extending existing dimensions to new settings.
The paper tackles the problem of learning robust classifiers when both clean data and labels are adversarially chosen, formulating it as an online learning problem. It introduces a new dimension for hypothesis classes that controls mistake bounds in realizable settings and regret bounds in agnostic settings, generalizing to multiclass cases and handling unknown perturbation sets.
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.