We consider a model of robust learning in an adversarial environment. The learner gets uncorrupted training data with access to possible corruptions that may be affected by the adversary during testing. The learner's goal is to build a robust classifier, which will be tested on future adversarial examples. The adversary is limited to $k$ possible corruptions for each input. We model the learner-adversary interaction as a zero-sum game. This model is closely related to the adversarial examples model of Schmidt et al. (2018); Madry et al. (2017). Our main results consist of generalization bounds for the binary and multiclass classification, as well as the real-valued case (regression). For the binary classification setting, we both tighten the generalization bound of Feige et al. (2015), and are also able to handle infinite hypothesis classes. The sample complexity is improved from $O(\frac{1}{\epsilon^4}\log(\frac{|H|}{\delta}))$ to $O\big(\frac{1}{\epsilon^2}(kVC(H)\log^{\frac{3}{2}+\alpha}(kVC(H))+\log(\frac{1}{\delta})\big)$ for any $\alpha > 0$. Additionally, we extend the algorithm and generalization bound from the binary to the multiclass and real-valued cases. Along the way, we obtain results on fat-shattering dimension and Rademacher complexity of $k$-fold maxima over function classes; these may be of independent interest. For binary classification, the algorithm of Feige et al. (2015) uses a regret minimization algorithm and an ERM oracle as a black box; we adapt it for the multiclass and regression settings. The algorithm provides us with near-optimal policies for the players on a given training sample.
翻译:我们考虑在敌对环境中进行强力学习的模式。 学习者会得到不间断的培训数据, 从而获得可能受对手测试期间受到对手影响的潜在腐败。 学习者的目标是建立一个强大的分类器, 在未来的敌对实例中测试。 对手仅限于每个输入可能存在的k美元腐败。 我们将学习者- 反向互动模式建为零和游戏。 这个模式与Schmid et al. (2018); Madry et al. (2017) 的对抗性复杂度范例模式密切相关。 我们的主要结果包括二进制和多级分类的通用约束; 以及真实价值的分类( Regression)。 对于二进制的分类设置, 我们同时收紧Fege 和 al. (2015), 还可以处理无限的假设类。 样本的复杂性从 $O (\ ferc{ 1\\\ epsalxlickral) 和 rickal- blickal- blickral (\) a. freal2\\\\\\\\\\\\\\\\\\\ hlex a tral deal deal deal deal deal a.