Origins of Low-dimensional Adversarial Perturbations

• URL: http://arxiv.org/abs/2203.13779v1
• Date: Fri, 25 Mar 2022 17:02:49 GMT
• Title: Origins of Low-dimensional Adversarial Perturbations
• Authors: Elvis Dohmatob, Chuan Guo, Morgane Goibert
• Abstract summary: We study the phenomenon of low-dimensional adversarial perturbations in classification. The goal is to fool the classifier into flipping its decision on a nonzero fraction of inputs from a designated class. We compute lowerbounds for the fooling rate of any subspace.
• Score: 17.17170592140042
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this note, we initiate a rigorous study of the phenomenon of low-dimensional adversarial perturbations in classification. These are adversarial perturbations wherein, unlike the classical setting, the attacker's search is limited to a low-dimensional subspace of the feature space. The goal is to fool the classifier into flipping its decision on a nonzero fraction of inputs from a designated class, upon the addition of perturbations from a subspace chosen by the attacker and fixed once and for all. It is desirable that the dimension $k$ of the subspace be much smaller than the dimension $d$ of the feature space, while the norm of the perturbations should be negligible compared to the norm of a typical data point. In this work, we consider binary classification models under very general regularity conditions, which are verified by certain feedforward neural networks (e.g., with sufficiently smooth, or else ReLU activation function), and compute analytical lower-bounds for the fooling rate of any subspace. These bounds explicitly highlight the dependence that the fooling rate has on the margin of the model (i.e., the ratio of the output to its $L_2$-norm of its gradient at a test point), and on the alignment of the given subspace with the gradients of the model w.r.t. inputs. Our results provide a theoretical explanation for the recent success of heuristic methods for efficiently generating low-dimensional adversarial perturbations. Moreover, our theoretical results are confirmed by experiments.

Related papers

• Subspace Defense: Discarding Adversarial Perturbations by Learning a Subspace for Clean Signals [52.123343364599094]
  adversarial attacks place carefully crafted perturbations on normal examples to fool deep neural networks (DNNs) We first empirically show that the features of either clean signals or adversarial perturbations are redundant and span in low-dimensional linear subspaces respectively with minimal overlap. This makes it possible for DNNs to learn a subspace where only features of clean signals exist while those of perturbations are discarded.
  arXiv  Detail & Related papers  (2024-03-24T14:35:44Z)
• On the Dynamics Under the Unhinged Loss and Beyond [104.49565602940699]
  We introduce the unhinged loss, a concise loss function, that offers more mathematical opportunities to analyze closed-form dynamics. The unhinged loss allows for considering more practical techniques, such as time-vary learning rates and feature normalization.
  arXiv  Detail & Related papers  (2023-12-13T02:11:07Z)
• Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm [30.08981916090924]
  We present the first optimal rates for infinite-dimensional vector-valued ridge regression on a continuous scale of norms that interpolate between $L$ and the hypothesis space. We show that these rates are optimal in most cases and independent of the dimension of the output space.
  arXiv  Detail & Related papers  (2023-12-12T11:48:56Z)
• On the Identification and Optimization of Nonsmooth Superposition Operators in Semilinear Elliptic PDEs [3.045851438458641]
  We study an infinite-dimensional optimization problem that aims to identify the Nemytskii operator in the nonlinear part of a prototypical semilinear elliptic partial differential equation (PDE) In contrast to previous works, we consider this identification problem in a low-regularity regime in which the function inducing the Nemytskii operator is a-priori only known to be an element of $H leakyloc(mathbbR)$.
  arXiv  Detail & Related papers  (2023-06-08T13:33:20Z)
• Random Smoothing Regularization in Kernel Gradient Descent Learning [24.383121157277007]
  We present a framework for random smoothing regularization that can adaptively learn a wide range of ground truth functions belonging to the classical Sobolev spaces. Our estimator can adapt to the structural assumptions of the underlying data and avoid the curse of dimensionality.
  arXiv  Detail & Related papers  (2023-05-05T13:37:34Z)
• Optimal Discriminant Analysis in High-Dimensional Latent Factor Models [1.4213973379473654]
  In high-dimensional classification problems, a commonly used approach is to first project the high-dimensional features into a lower dimensional space. We formulate a latent-variable model with a hidden low-dimensional structure to justify this two-step procedure. We propose a computationally efficient classifier that takes certain principal components (PCs) of the observed features as projections.
  arXiv  Detail & Related papers  (2022-10-23T21:45:53Z)
• Beyond the Edge of Stability via Two-step Gradient Updates [49.03389279816152]
  Gradient Descent (GD) is a powerful workhorse of modern machine learning. GD's ability to find local minimisers is only guaranteed for losses with Lipschitz gradients. This work focuses on simple, yet representative, learning problems via analysis of two-step gradient updates.
  arXiv  Detail & Related papers  (2022-06-08T21:32:50Z)
• On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
  We show that a phenomenon can be precisely characterized in the context of kernel methods. We consider the minimization of a quadratic objective in a separable Hilbert space, and show that with early stopping, the choice of learning rate influences the spectral decomposition of the obtained solution.
  arXiv  Detail & Related papers  (2022-02-28T13:01:04Z)
• The Interplay Between Implicit Bias and Benign Overfitting in Two-Layer Linear Networks [51.1848572349154]
  neural network models that perfectly fit noisy data can generalize well to unseen test data. We consider interpolating two-layer linear neural networks trained with gradient flow on the squared loss and derive bounds on the excess risk.
  arXiv  Detail & Related papers  (2021-08-25T22:01:01Z)
• On the Role of Optimization in Double Descent: A Least Squares Study [30.44215064390409]
  We show an excess risk bound for the descent gradient solution of the least squares objective. We find that in case of noiseless regression, double descent is explained solely by optimization-related quantities. We empirically explore if our predictions hold for neural networks.
  arXiv  Detail & Related papers  (2021-07-27T09:13:11Z)
• Attribute-Guided Adversarial Training for Robustness to Natural Perturbations [64.35805267250682]
  We propose an adversarial training approach which learns to generate new samples so as to maximize exposure of the classifier to the attributes-space. Our approach enables deep neural networks to be robust against a wide range of naturally occurring perturbations.
  arXiv  Detail & Related papers  (2020-12-03T10:17:30Z)

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.