Adversarial Rademacher Complexity of Deep Neural Networks
- URL: http://arxiv.org/abs/2211.14966v1
- Date: Sun, 27 Nov 2022 23:24:37 GMT
- Title: Adversarial Rademacher Complexity of Deep Neural Networks
- Authors: Jiancong Xiao, Yanbo Fan, Ruoyu Sun, Zhi-Quan Luo
- Abstract summary: A robust model shall perform well on both the perturbed training data and the unseen perturbed test data.
We provide the first bound of adversarial Rademacher complexity of deep neural networks.
- Score: 29.571059373990888
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Deep neural networks are vulnerable to adversarial attacks. Ideally, a robust
model shall perform well on both the perturbed training data and the unseen
perturbed test data. It is found empirically that fitting perturbed training
data is not hard, but generalizing to perturbed test data is quite difficult.
To better understand adversarial generalization, it is of great interest to
study the adversarial Rademacher complexity (ARC) of deep neural networks.
However, how to bound ARC in multi-layers cases is largely unclear due to the
difficulty of analyzing adversarial loss in the definition of ARC. There have
been two types of attempts of ARC. One is to provide the upper bound of ARC in
linear and one-hidden layer cases. However, these approaches seem hard to
extend to multi-layer cases. Another is to modify the adversarial loss and
provide upper bounds of Rademacher complexity on such surrogate loss in
multi-layer cases. However, such variants of Rademacher complexity are not
guaranteed to be bounds for meaningful robust generalization gaps (RGG). In
this paper, we provide a solution to this unsolved problem. Specifically, we
provide the first bound of adversarial Rademacher complexity of deep neural
networks. Our approach is based on covering numbers. We provide a method to
handle the robustify function classes of DNNs such that we can calculate the
covering numbers. Finally, we provide experiments to study the empirical
implication of our bounds and provide an analysis of poor adversarial
generalization.
Related papers
- Generalization and Risk Bounds for Recurrent Neural Networks [3.0638061480679912]
We establish a new generalization error bound for vanilla RNNs.
We provide a unified framework to calculate the Rademacher complexity that can be applied to a variety of loss functions.
arXiv Detail & Related papers (2024-11-05T03:49:06Z) - Bridging the Gap: Rademacher Complexity in Robust and Standard Generalization [29.044914673801856]
Training Deep Neural Networks (DNNs) with adversarial examples often results in poor generalization to test-time adversarial data.
This paper investigates this issue through the lens of Rademacher complexity.
We aim to construct a new cover that possesses two properties: 1) compatibility with adversarial examples, and 2) precision comparable to covers used in standard settings.
arXiv Detail & Related papers (2024-06-08T06:45:19Z) - Wasserstein distributional robustness of neural networks [9.79503506460041]
Deep neural networks are known to be vulnerable to adversarial attacks (AA)
For an image recognition task, this means that a small perturbation of the original can result in the image being misclassified.
We re-cast the problem using techniques of Wasserstein distributionally robust optimization (DRO) and obtain novel contributions.
arXiv Detail & Related papers (2023-06-16T13:41:24Z) - Benign Overfitting for Two-layer ReLU Convolutional Neural Networks [60.19739010031304]
We establish algorithm-dependent risk bounds for learning two-layer ReLU convolutional neural networks with label-flipping noise.
We show that, under mild conditions, the neural network trained by gradient descent can achieve near-zero training loss and Bayes optimal test risk.
arXiv Detail & Related papers (2023-03-07T18:59:38Z) - AdAUC: End-to-end Adversarial AUC Optimization Against Long-tail
Problems [102.95119281306893]
We present an early trial to explore adversarial training methods to optimize AUC.
We reformulate the AUC optimization problem as a saddle point problem, where the objective becomes an instance-wise function.
Our analysis differs from the existing studies since the algorithm is asked to generate adversarial examples by calculating the gradient of a min-max problem.
arXiv Detail & Related papers (2022-06-24T09:13:39Z) - Certifiable Robustness for Nearest Neighbor Classifiers [6.487663563916903]
We study the complexity of certifying for a simple but widely deployed classification algorithm, $k$-Nearest Neighbors ($k$-NN)
Our main focus is on inconsistent datasets when constraints are functional dependencies (FDs)
We exhibit a similar counting version of the problem, where the goal is to count the number of possible worlds that predict a certain label.
arXiv Detail & Related papers (2022-01-13T02:55:10Z) - Generalization of Neural Combinatorial Solvers Through the Lens of
Adversarial Robustness [68.97830259849086]
Most datasets only capture a simpler subproblem and likely suffer from spurious features.
We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features.
Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound.
Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
arXiv Detail & Related papers (2021-10-21T07:28:11Z) - Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
Modern machine learning models often employ a huge number of parameters and are typically optimized to have zero training loss.
We examine how these benign overfitting phenomena occur in a two-layer neural network setting.
We show that it is possible for the two-layer ReLU network interpolator to achieve a near minimax-optimal learning rate.
arXiv Detail & Related papers (2021-06-06T19:08:53Z) - How benign is benign overfitting? [96.07549886487526]
We investigate two causes for adversarial vulnerability in deep neural networks: bad data and (poorly) trained models.
Deep neural networks essentially achieve zero training error, even in the presence of label noise.
We identify label noise as one of the causes for adversarial vulnerability.
arXiv Detail & Related papers (2020-07-08T11:07:10Z) - Adversarial Learning Guarantees for Linear Hypotheses and Neural
Networks [45.06091849856641]
We give upper and lower bounds for the adversarial empirical Rademacher complexity of linear hypotheses.
We 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.
arXiv Detail & Related papers (2020-04-28T15:55:16Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.