Gradient Methods Provably Converge to Non-Robust Networks

• URL: http://arxiv.org/abs/2202.04347v1
• Date: Wed, 9 Feb 2022 08:58:54 GMT
• Title: Gradient Methods Provably Converge to Non-Robust Networks
• Authors: Gal Vardi, Gilad Yehudai, Ohad Shamir
• Abstract summary: In adversarial networks, depth-$2LU$ Reperturbible gradient networks are provably non-robust. We show that the well-known implicit bias towards a margin induces bias towards non-robust networks.
• Score: 40.83290846983707
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite a great deal of research, it is still unclear why neural networks are so susceptible to adversarial examples. In this work, we identify natural settings where depth-$2$ ReLU networks trained with gradient flow are provably non-robust (susceptible to small adversarial $\ell_2$-perturbations), even when robust networks that classify the training dataset correctly exist. Perhaps surprisingly, we show that the well-known implicit bias towards margin maximization induces bias towards non-robust networks, by proving that every network which satisfies the KKT conditions of the max-margin problem is non-robust.

Related papers

• The Double-Edged Sword of Implicit Bias: Generalization vs. Robustness in ReLU Networks [64.12052498909105]
  We study the implications of the implicit bias of gradient flow on generalization and adversarial robustness in ReLU networks. In two-layer ReLU networks gradient flow is biased towards solutions that generalize well, but are highly vulnerable to adversarial examples.
  arXiv  Detail & Related papers  (2023-03-02T18:14:35Z)
• Adversarial Examples Exist in Two-Layer ReLU Networks for Low Dimensional Linear Subspaces [24.43191276129614]
  We show that standard methods lead to non-robust neural networks. We show that decreasing the scale of the training algorithm, or adding $L$ regularization, can make the trained network more robust to adversarial perturbations.
  arXiv  Detail & Related papers  (2023-03-01T19:10:05Z)
• Computational Complexity of Learning Neural Networks: Smoothness and Degeneracy [52.40331776572531]
  We show that learning depth-$3$ ReLU networks under the Gaussian input distribution is hard even in the smoothed-analysis framework. Our results are under a well-studied assumption on the existence of local pseudorandom generators.
  arXiv  Detail & Related papers  (2023-02-15T02:00:26Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  We show that gradient flow converges in direction when labels are determined by the sign of a target network with $r$ neurons. Our result may already hold for mild over- parameterization, where the width is $tildemathcalO(r)$ and independent of the sample size.
  arXiv  Detail & Related papers  (2022-05-18T16:57:10Z)
• The Unreasonable Effectiveness of Random Pruning: Return of the Most Naive Baseline for Sparse Training [111.15069968583042]
  Random pruning is arguably the most naive way to attain sparsity in neural networks, but has been deemed uncompetitive by either post-training pruning or sparse training. We empirically demonstrate that sparsely training a randomly pruned network from scratch can match the performance of its dense equivalent. Our results strongly suggest there is larger-than-expected room for sparse training at scale, and the benefits of sparsity might be more universal beyond carefully designed pruning.
  arXiv  Detail & Related papers  (2022-02-05T21:19:41Z)
• Robustness Certificates for Implicit Neural Networks: A Mixed Monotone Contractive Approach [60.67748036747221]
  Implicit neural networks offer competitive performance and reduced memory consumption. They can remain brittle with respect to input adversarial perturbations. This paper proposes a theoretical and computational framework for robustness verification of implicit neural networks.
  arXiv  Detail & Related papers  (2021-12-10T03:08:55Z)
• Directional convergence and alignment in deep learning [38.73942298289583]
  We show that although the minimizers of cross-entropy and related classification losses at infinity, network weights learn by gradient flow converge in direction. This proof holds for deep homogeneous networks allowing for ReLU, max-pooling, linear, and convolutional layers.
  arXiv  Detail & Related papers  (2020-06-11T17:50:11Z)
• Adversarial Robustness Guarantees for Random Deep Neural Networks [15.68430580530443]
  adversarial examples are incorrectly classified inputs that are extremely close to a correctly classified input. We prove that for any $pge1$, the $ellp$ distance of any given input from the classification boundary scales as one over the square root of the dimension of the input times the $ellp$ norm of the input. The results constitute a fundamental advance in the theoretical understanding of adversarial examples, and open the way to a thorough theoretical characterization of the relation between network architecture and robustness to adversarial perturbations.
  arXiv  Detail & Related papers  (2020-04-13T13:07:26Z)

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.