Adversarial Learning Guarantees for Linear Hypotheses and Neural Networks
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Adversarial RobustnessMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Differentially Private Learning with Margin Guarantees
We present a series of new differentially private (DP) algorithms with dimension-independent margin guarantees. For the family of linear hypotheses, we give a pure DP learning algorithm that benefits from relative deviat…
Model SelectionSmoothed Analysis of Online and Differentially Private Learning
Practical and pervasive needs for robustness and privacy in algorithms have inspired the design of online adversarial and differentially private learning algorithms. The primary quantity that characterizes learnability i…
On the Complexity of Adversarial Decision Making
A central problem in online learning and decision making -- from bandits to reinforcement learning -- is to understand what modeling assumptions lead to sample-efficient learning guarantees. We consider a general adversa…
Decision Makingreinforcement-learningReinforcement LearningReinforcement Learning (RL)On the Rademacher Complexity of Linear Hypothesis Sets
Linear predictors form a rich class of hypotheses used in a variety of learning algorithms. We present a tight analysis of the empirical Rademacher complexity of the family of linear hypothesis classes with weight vector…
D2A-BSP: Distilled Data Association Belief Space Planning with Performance Guarantees Under Budget Constraints
Unresolved data association in ambiguous and perceptually aliased environments leads to multi-modal hypotheses on both the robot's and the environment state. To avoid catastrophic results, when operating in such ambiguou…