Structural Extensions of Basis Pursuit: Guarantees on Adversarial Robustness

• URL: http://arxiv.org/abs/2205.08955v1
• Date: Thu, 5 May 2022 09:12:07 GMT
• Title: Structural Extensions of Basis Pursuit: Guarantees on Adversarial Robustness
• Authors: D\'avid Szeghy, Mahmoud Aslan, \'Aron F\'othi, Bal\'azs M\'esz\'aros, Zolt\'an \'Ad\'am Milacski, Andr\'as L\H{o}rincz
• Abstract summary: We prove that the stability of BP holds upon the following generalizations. We introduce classification based on the $ell$ norms of the groups and show numerically that it can be accurate and offers considerable speedups.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While deep neural networks are sensitive to adversarial noise, sparse coding using the Basis Pursuit (BP) method is robust against such attacks, including its multi-layer extensions. We prove that the stability theorem of BP holds upon the following generalizations: (i) the regularization procedure can be separated into disjoint groups with different weights, (ii) neurons or full layers may form groups, and (iii) the regularizer takes various generalized forms of the $\ell_1$ norm. This result provides the proof for the architectural generalizations of Cazenavette et al. (2021), including (iv) an approximation of the complete architecture as a shallow sparse coding network. Due to this approximation, we settled to experimenting with shallow networks and studied their robustness against the Iterative Fast Gradient Sign Method on a synthetic dataset and MNIST. We introduce classification based on the $\ell_2$ norms of the groups and show numerically that it can be accurate and offers considerable speedups. In this family, linear transformer shows the best performance. Based on the theoretical results and the numerical simulations, we highlight numerical matters that may improve performance further.

Related papers

• An Intermediate-level Attack Framework on The Basis of Linear Regression [89.85593878754571]
  This paper substantially extends our work published at ECCV, in which an intermediate-level attack was proposed to improve the transferability of some baseline adversarial examples. We advocate to establish a direct linear mapping from the intermediate-level discrepancies (between adversarial features and benign features) to classification prediction loss of the adversarial example. We show that 1) a variety of linear regression models can all be considered in order to establish the mapping, 2) the magnitude of the finally obtained intermediate-level discrepancy is linearly correlated with adversarial transferability, and 3) further boost of the performance can be achieved by performing multiple runs of the baseline attack with
  arXiv  Detail & Related papers  (2022-03-21T03:54:53Z)
• The Sample Complexity of One-Hidden-Layer Neural Networks [57.6421258363243]
  We study a class of scalar-valued one-hidden-layer networks, and inputs bounded in Euclidean norm. We prove that controlling the spectral norm of the hidden layer weight matrix is insufficient to get uniform convergence guarantees. We analyze two important settings where a mere spectral norm control turns out to be sufficient.
  arXiv  Detail & Related papers  (2022-02-13T07:12:02Z)
• Controlling the Complexity and Lipschitz Constant improves polynomial nets [55.121200972539114]
  We derive new complexity bounds for the set of Coupled CP-Decomposition (CCP) and Nested Coupled CP-decomposition (NCP) models of Polynomial Nets. We propose a principled regularization scheme that we evaluate experimentally in six datasets and show that it improves the accuracy as well as the robustness of the models to adversarial perturbations.
  arXiv  Detail & Related papers  (2022-02-10T14:54:29Z)
• i-SpaSP: Structured Neural Pruning via Sparse Signal Recovery [11.119895959906085]
  We propose a novel, structured pruning algorithm for neural networks -- the iterative, Sparse Structured Pruning, dubbed as i-SpaSP. i-SpaSP operates by identifying a larger set of important parameter groups within a network that contribute most to the residual between pruned and dense network output. It is shown to discover high-performing sub-networks and improve upon the pruning efficiency of provable baseline methodologies by several orders of magnitude.
  arXiv  Detail & Related papers  (2021-12-07T05:26:45Z)
• Efficient Semi-Implicit Variational Inference [65.07058307271329]
  We propose an efficient and scalable semi-implicit extrapolational (SIVI) Our method maps SIVI's evidence to a rigorous inference of lower gradient values.
  arXiv  Detail & Related papers  (2021-01-15T11:39:09Z)
• DessiLBI: Exploring Structural Sparsity of Deep Networks via Differential Inclusion Paths [45.947140164621096]
  We propose a new approach based on differential inclusions of inverse scale spaces. We show that DessiLBI unveils "winning tickets" in early epochs.
  arXiv  Detail & Related papers  (2020-07-04T04:40:16Z)
• Consistency of Spectral Clustering on Hierarchical Stochastic Block Models [5.983753938303726]
  We study the hierarchy of communities in real-world networks under a generic block model. We prove the strong consistency of this method under a wide range of model parameters. Unlike most of existing work, our theory covers multiscale networks where the connection probabilities may differ by orders of magnitude.
  arXiv  Detail & Related papers  (2020-04-30T01:08:59Z)
• Revealing the Structure of Deep Neural Networks via Convex Duality [70.15611146583068]
  We study regularized deep neural networks (DNNs) and introduce a convex analytic framework to characterize the structure of hidden layers. We show that a set of optimal hidden layer weights for a norm regularized training problem can be explicitly found as the extreme points of a convex set. We apply the same characterization to deep ReLU networks with whitened data and prove the same weight alignment holds.
  arXiv  Detail & Related papers  (2020-02-22T21:13:44Z)
• Understanding Generalization in Deep Learning via Tensor Methods [53.808840694241]
  We advance the understanding of the relations between the network's architecture and its generalizability from the compression perspective. We propose a series of intuitive, data-dependent and easily-measurable properties that tightly characterize the compressibility and generalizability of neural networks.
  arXiv  Detail & Related papers  (2020-01-14T22:26:57Z)

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.