论文标题
宽容的对抗性强大的学习
Adversarially Robust Learning with Tolerance
论文作者
论文摘要
我们启动有关度量扰动集的耐受性对抗性PAC学习的研究。在对抗性PAC学习中，允许对手用$ x $ $ x $的封闭的半径$ r $中的任意点替换测试点$ x $。在耐受版本中，将学习者的误差与最佳可实现的错误相对于稍大的扰动半径$（1+γ）r $进行了比较。这种简单的调整有助于我们弥合理论与实践之间的差距，并为在实践中流行的算法技术获得第一个PAC型保证。 我们的第一个结果涉及广泛使用的``扰动和平滑''方法。对于具有加倍尺寸$ d $的扰动集，我们表明这些方法的一种变体PAC-LEARNS在$γ$ - γ$ -tolerant的对抗环境中使用VC-Dimension $ v $带有VC-Dimension $ v $ $ o \ left（\ frac {v（1+1/γ）^{o（d）}}} {\ varepsilon} \ right）$样本。这与传统（不耐耐受性的）设置相反，在这种情况下，正如我们所表明的那样，扰动和平滑的方法可能会失败。 我们的第二个结果表明，可以使用$ \ widetilde {o} \ left（\ frac {d.v \ log（1+1/γ）} {\ varepsilon^2} \ right）$ samples $即使在不可知的环境中，也可以使用$ \ wideTilde {o} \ left（\ frac {d.v \ log（1+1/γ）} {该结果基于一种新型的基于压缩的算法，并实现了对双倍维度和VC维度的线性依赖性。这与不耐耐受性的设置相反，在该设置中没有已知的样品复杂性上限在多个百货上依赖于VC维度。
We initiate the study of tolerant adversarial PAC-learning with respect to metric perturbation sets. In adversarial PAC-learning, an adversary is allowed to replace a test point $x$ with an arbitrary point in a closed ball of radius $r$ centered at $x$. In the tolerant version, the error of the learner is compared with the best achievable error with respect to a slightly larger perturbation radius $(1+γ)r$. This simple tweak helps us bridge the gap between theory and practice and obtain the first PAC-type guarantees for algorithmic techniques that are popular in practice. Our first result concerns the widely-used ``perturb-and-smooth'' approach for adversarial learning. For perturbation sets with doubling dimension $d$, we show that a variant of these approaches PAC-learns any hypothesis class $\mathcal{H}$ with VC-dimension $v$ in the $γ$-tolerant adversarial setting with $O\left(\frac{v(1+1/γ)^{O(d)}}{\varepsilon}\right)$ samples. This is in contrast to the traditional (non-tolerant) setting in which, as we show, the perturb-and-smooth approach can provably fail. Our second result shows that one can PAC-learn the same class using $\widetilde{O}\left(\frac{d.v\log(1+1/γ)}{\varepsilon^2}\right)$ samples even in the agnostic setting. This result is based on a novel compression-based algorithm, and achieves a linear dependence on the doubling dimension as well as the VC-dimension. This is in contrast to the non-tolerant setting where there is no known sample complexity upper bound that depend polynomially on the VC-dimension.
