Adversarial or test time robustness measures the susceptibility of a
classifier to perturbations to the test input. While there has been a flurry of
recent work on designing defenses against such perturbations, the theory of
adversarial robustness is not well understood. In order to make progress on
this, we focus on the problem of understanding generalization in adversarial
settings, via the lens of Rademacher complexity. We give upper and lower bounds
for the adversarial empirical Rademacher complexity of linear hypotheses with
adversarial perturbations measured in $l_r$-norm for an arbitrary $r \geq 1$.
This generalizes the recent result of [Yin et al.'19] that studies the case of
$r = \infty$, and provides a finer analysis of the dependence on the input
dimensionality as compared to the recent work of [Khim and Loh'19] on linear
hypothesis classes.
We then extend our analysis to provide Rademacher complexity lower and upper
bounds for a single ReLU unit. Finally, we give adversarial Rademacher
complexity bounds for feed-forward neural networks with one hidden layer.
Unlike previous works we directly provide bounds on the adversarial Rademacher
complexity of the given network, as opposed to a bound on a surrogate. A
by-product of our analysis also leads to tighter bounds for the Rademacher
complexity of linear hypotheses, for which we give a detailed analysis and
present a comparison with existing bounds.

研究了在 $l_r$-norm 测量下带有敌对干扰的线性假设的敌对经验 Rademacher 复杂性的上限和下限，扩展了已有的结果并提供了更精细的维度依赖性分析，并在单个 ReLU 单元和具有一层隐藏层的前馈神经网络中提供了 Rademacher 复杂度上下界。