PaperlayerView exact revision on arXiv

Source-linked AI summary

Analysis of classifiers' robustness to adversarial perturbations

Alhussein Fawzi, Omar Fawzi, Pascal Frossard

arXiv:1502.02590v4cs.LGcs.CVstat.ML

TL;DR

The paper asks why classifiers can be highly accurate yet unstable to barely perceptible adversarial perturbations. It develops theoretical robustness bounds and shows that, for linear classifiers at d = 2500, random-noise robustness is at least 15 times larger than adversarial robustness.

  • Problem

    The paper investigates why accurate classifiers can be unstable to minimally perceptible adversarial perturbations and whether this behavior extends beyond deep networks.

  • Method

    The paper develops a binary-classification framework comparing adversarial and uniform random-noise robustness, with bounds specialized to linear and quadratic classifiers.

  • Results

    For d = 2500, robustness to random uniform noise is at least 15 times larger than adversarial robustness for a linear classifier.

  • Takeaways & Limitations

    Small distinguishability fundamentally limits adversarial robustness, while linear classifiers can remain robust to random noise in high-dimensional tasks.

  • Takeaways & Limitations

    Designing training procedures that explicitly account for robustness in general nonlinear classifiers such as neural networks remains future work.

Abstract

from arXiv · show

The goal of this paper is to analyze an intriguing phenomenon recently discovered in deep networks, namely their instability to adversarial perturbations (Szegedy et. al., 2014). We provide a theoretical framework for analyzing the robustness of classifiers to adversarial perturbations, and show fundamental upper bounds on the robustness of classifiers. Specifically, we establish a general upper bound on the robustness of classifiers to adversarial perturbations, and then illustrate the obtained upper bound on the families of linear and quadratic classifiers. In both cases, our upper bound depends on a distinguishability measure that captures the notion of difficulty of the classification task. Our results for both classes imply that in tasks involving small distinguishability, no classifier in the considered set will be robust to adversarial perturbations, even if a good accuracy is achieved. Our theoretical framework moreover suggests that the phenomenon of adversarial instability is due to the low flexibility of classifiers, compared to the difficulty of the classification task (captured by the distinguishability). Moreover, we show the existence of a clear distinction between the robustness of a classifier to random noise and its robustness to adversarial perturbations. Specifically, the former is shown to be larger than the latter by a factor that is proportional to \sqrt{d} (with d being the signal dimension) for linear classifiers. This result gives a theoretical explanation for the discrepancy between the two robustness properties in high dimensional problems, which was empirically observed in the context of neural networks. To the best of our knowledge, our results provide the first theoretical work that addresses the phenomenon of adversarial instability recently observed for deep networks. Our analysis is complemented by experimental results on controlled and real-world data.

1 Introduction

The paper introduces a theoretical framework for classifier robustness to adversarial perturbations, establishing fundamental limits for linear and quadratic classifiers. It contrasts adversarial instability with robustness to random noise and supports the analysis with experiments.

  • Motivation: Deep networks can have their estimated labels switched by minimal, barely perceptible adversarial perturbations, unlike random noise.This instability was reported even when classifier performance was strong.
  • Theoretical framework: The paper formulates binary-classifier robustness to adversarial perturbations and derives a general upper bound, specialized to linear and quadratic classifiers.For both families, the bound expresses a fundamental robustness limit.
  • Random-noise robustness: In high-dimensional tasks, linear classifiers can remain robust to random noise despite small distinguishability.The relevant scaling depends on d, the input-signal dimension.
  • Experiments: The theoretical analysis is complemented by experiments on a running example and more complex classifiers.The experiments show that the intuition from the theory also holds beyond the analyzed classifier families.
  • Scope distinction: The paper studies robustness of a fixed classifier, distinct from security work on attacks that manipulate the learning system or its training data.Related defenses address malicious training points and other attacks on the learning procedure.

2 Problem setting

The paper formulates robustness analysis for binary classifiers on R^d, defining adversarial robustness through minimal sign-flipping perturbations and uniform-noise robustness through sphere-based random perturbations. These quantities are distribution-dependent and can involve perturbed points outside the data distribution’s support.

  • Problem formulation: The framework restricts analysis to binary classification, with data points x ∈ R^d sampled from a probability measure μ and labels y(x) ∈ {−1, 1}.
  • Adversarial robustness: Adversarial perturbation size Δ_adv(x; f) is the norm of the smallest perturbation that switches the sign of classifier f at x.The perturbation is chosen minimally to flip the estimated label; the analysis uses the ℓ2 norm.
  • Perturbation domain: Both adversarial and uniform-noise definitions allow perturbed points x + r or x + n to lie outside the support of μ.
  • Adversarial robustness: Adversarial robustness ρ_adv(f) is the average norm of minimal sign-flipping perturbations over datapoints sampled from μ.ρ_adv(f) depends on both the classifier and μ, but not on the true labels y, and differs from the traditional SVM margin.
  • Uniform random noise: For ε ∈ [0, 1], uniform-noise robustness Δ_unif,ε(x; f) is the largest sphere radius whose uniformly sampled perturbations preserve x’s predicted label with high probability.The uniform measure is taken over a sphere centered at 0 in R^d, then applied to perturbations around x.

3 Running example

A binary image task separates classes by line orientation, while also allowing classification through pixel-sum bias. The example shows that perfect accuracy can coexist with weak adversarial robustness, whereas a more flexible classifier captures the stronger visual concept.

  • Running example: The binary task uses square images containing one vertical or horizontal line, with class-dependent pixel biases of +a or −a.Class 1 has vertical lines and positive background bias; class −1 has horizontal lines and negative background bias.
  • Running example: Line orientation is the most visually relevant separating concept, while image bias also separates the classes but is harder to detect visually.Both concepts can yield correct classification, motivating comparison of classifiers that capture different features.
  • Running example: R(flin) = 0 for every a > 0, yet flin is vulnerable to small adversarial perturbations because it captures bias and ignores line orientation.When a = 0, the datapoints are not linearly separable; for small a, perturbing the bias can switch the estimated label.
  • Running example: Among zero-risk linear classifiers, flin maximizes ρadv(f), but its adversarial robustness can still be made arbitrarily small by choosing a sufficiently small.Thus, all zero-risk linear classifiers are non-robust for this task.
  • Running example: A degree-2 polynomial classifier captures line orientation and is more robust than flin, with ρadv(flin) ≪ρadv(fquad).The comparison illustrates that adversarial robustness measures concept strength: larger ρadv(f) indicates a stronger learned concept for comparable risk.

4 Upper limit on the adversarial robustness

This section introduces a theoretical framework for bounding adversarial robustness under a classifier regularity assumption. The resulting general bound depends on classification risk and the separation between expected classifier values across the two class distributions.

  • Theoretical framework: Assumption (A) bounds each datapoint’s distance to oppositely classified points using the classifier’s positive or negative residual.The assumption requires parameters τ > 0 and 0 < γ ≤ 1.
  • General robustness bound: Lemma 4.1 establishes a general upper bound on adversarial robustness for any classifier satisfying assumption (A).The bound applies without restricting the classifier to a particular function class.
  • General robustness bound: The bound depends on classifier risk and the separation between expected classifier values under distributions µ1 and µ−1.The framework is subsequently applied to linear and quadratic classifier classes to obtain interpretable bounds involving distinguishability.

5 Robustness of linear classifiers to adversarial and random perturbations

For linear classifiers, adversarial robustness is upper-bounded by class-mean distinguishability and risk, while robustness to random uniform noise can exceed adversarial robustness substantially in high dimensions.

  • Adversarial robustness: Theorem 5.2 upper-bounds ρadv(f) using the class-mean difference, class-prior imbalance, classifier risk, and the input-radius parameter M.The bound is ρadv(f) ≤ ∥p1Eµ1(x) − p−1Eµ−1(x)∥2 + M(|p1 − p−1| + 4R(f)).
  • Adversarial robustness: Small class-mean distinguishability implies that every accurate linear classifier has low adversarial robustness, even when its classification risk is small.The mean difference is classifier-independent and reflects task distinguishability, whereas classifier dependence enters through R(f).
  • Random uniform noise: At ϵ = 0, the random-noise robustness result is tight because ρunif,0(f) = ρadv(f).In typical high-dimensional problems, the result also permits robustness to random noise despite small class-mean distinguishability.
  • Random uniform noise: For d = 2500, ρunif,ϵ is at least 15 times larger than ρadv, demonstrating a growing high-dimensional gap between random-noise and adversarial robustness.In the example, adversarial robustness remains constant with dimension while random-uniform-noise robustness increases.

6 Adversarial robustness of quadratic classifiers

The section derives upper bounds for quadratic classifiers f(x)=xT Ax, showing that adversarial robustness depends on second-order-moment distinguishability and classifier risk. In a running example, a quadratic classifier achieves zero risk and substantially greater adversarial robustness than a linear classifier for small bias.

  • Quadratic classifier framework: Quadratic classifiers f(x)=xT Ax are analyzed as a natural extension of linear classifiers, with robustness depending on the classifier family.The analysis assumes A is symmetric and imposes conditions on its extremal eigenvalues.
  • Theoretical robustness bound: Theorem 6.2 bounds quadratic-classifier adversarial robustness using the distributions’ second-order moment matrices and the classifier’s risk.The matrices are C±1(i,j)=Eµ±1(xixj), and the nuclear norm is the sum of singular values.
  • Theoretical robustness bound: Small ||C1−C−1||∗ makes any low-risk quadratic classifier satisfying the assumptions non-robust to adversarial perturbations.Here ||C1−C−1||∗ serves as the distinguishability measure for the classification task.
  • Comparison with linear classifiers: Unlike the linear case, quadratic distinguishability is based on second-order moments, so close means with different second-order moments can permit zero-risk robust quadratic classifiers.Under the same distributional setting, zero-risk linear classifiers remain non-robust to adversarial noise.
  • Running example: ρadv(fquad)=1/2 for every bias a, while both fquad and flin achieve zero risk; for small a, ρadv(flin)≪ρadv(fquad).The quadratic classifier distinguishes image orientation, whereas the linear classifier relies on the bias.

7 Experimental results

Experiments on MNIST, CIFAR-10, and CNNs support the theoretical link between classifier flexibility and adversarial robustness, while showing persistent instability on a harder natural-image task.

  • Experimental setup: Experiments on real data test the theoretical robustness limit and compare adversarial with random-noise robustness across several classifier families.The study includes linear SVMs, polynomial-kernel SVMs, RBF-kernel SVMs, and convolutional neural networks.
  • Experimental setup: The adversarial-robustness optimization is nonconvex, so the procedure is guaranteed only to provide an upper bound on the true minimal perturbation.The limitation applies to arbitrary classifiers and means the empirical adversarial robustness estimate may not be optimal.
  • MNIST: On MNIST, more flexible classifiers improve both accuracy and adversarial robustness: third-order classifiers outperform second-order ones, and RBF-SVM(0.1) outperforms RBF-SVM(1).The result occurs in a digit “4” versus digit “5” task where the distinguishability measure is small.
  • CIFAR-10: On CIFAR-10, all tested classifiers remain unstable to adversarial perturbations despite fairly good test accuracy.The authors suggest using a more flexible classifier family or a better training algorithm to improve robustness.
  • CNNs: Increasing CNN depth significantly improves adversarial robustness, especially from 1 to 2 hidden layers, whereas increasing depth from 2 to 3 layers has a marginal effect.This mirrors the role of polynomial degree in determining robustness.

8 Discussion and perspectives

The discussion emphasizes a general limit on adversarial robustness and derives specialized upper bounds for linear and quadratic classifiers. Linear classifiers are generally not robust to adversarial noise, whereas quadratic classifiers have larger limits that may permit robustness with appropriate training.

  • A general limit on classifier robustness to adversarial perturbations was established in Lemma 4.1, motivating specialized upper bounds for linear and quadratic families.
  • For most problems of interest, the robustness limit for linear classifiers is very small, so they are usually not robust to adversarial noise.Robustness to random noise might nevertheless be achieved.
  • Quadratic classifiers generally have a larger adversarial-robustness limit than linear classifiers, offering hope for robust classifiers under appropriate training.

A Proofs · A.1 Proof of Lemma 4.1

The appendix proves Lemma 4.1 by combining a symmetric concavity bound with Jensen’s inequality and a decomposition of classifier errors. The argument then relates the resulting terms to the risk R(f) and bounds a conditional expectation using ||f||∞.

  • A.1 Proof of Lemma 4.1: The concavity argument shows the maximum occurs when z1 = · · · = zn, attaining n^(1−γ).Equal normalized components maximize the expression.
  • A.1 Proof of Lemma 4.1: The proof of Lemma 4.1 seeks an upper bound on ρadv(f) = Eµ(∆adv(x; f)) using assumption (A).The assumption supplies the intermediate upper bounds used in the derivation.
  • A.1 Proof of Lemma 4.1: Jensen’s inequality gives E(X^γ) ≤ E(X)^γ for γ ≤ 1, and the proof also uses P(A) ≤ P(A)^γ.These inequalities transform the probabilistic terms in the bound.
  • A.1 Proof of Lemma 4.1: Lemma A.1 is applied with n = 4 to control the resulting sum of four terms.This is the finite-dimensional specialization used in the proof.
  • A.1 Proof of Lemma 4.1: An equality rewrites one conditional contribution as a term involving Pµ1(f(x) < 0), its conditional mean magnitude, and its conditional mean.The proof then invokes an analogous equality for the negative class.
  • A.1 Proof of Lemma 4.1: The argument identifies R(f) = p1Pµ1(f(x) < 0) + p−1Pµ−1(f(x) ≥ 0) and bounds |Eµ−1(f(x)|f(x) ≥ 0)| by ||f||∞.These observations yield the proof’s concluding upper bound.

A.2 Proof of Theorem 5.3

The proof of Theorem 5.3 combines spherical-cap concentration with bounds on adversarial and uniform-noise perturbation probabilities for linear classifiers. It applies upper and lower spherical-cap estimates to derive corresponding bounds on perturbation radii and their relationship.

  • Spherical-cap concentration: The proof uses concentration of measure on the sphere, beginning with bounds on the measure of a spherical cap.Theorem A.2 bounds spherical-cap probabilities, which are then used to establish Lemma A.3 for a uniformly sampled unit-sphere vector.
  • Linear-classifier bounds: For f(x) = wT x + b with f(x) > 0, the proof applies Lemma A.3 to bound the probability that a perturbation changes the classifier output.The argument treats perturbations sampled uniformly from a sphere and derives both upper- and lower-probability conditions for crossing the decision boundary.
  • Uniform-noise radius bounds: The resulting analysis provides an upper bound and a lower bound on ∆unif,ϵ(x; f), including a lower-bound form involving C2(ϵ).The bounds are obtained from the adversarial-radius expression and the spherical concentration estimates.
  • Dimension dependence: The quantity d(1−(12ϵ)1/d) is shown to decrease with d, supporting the dimension-dependent behavior of the derived bounds.The proof establishes monotonicity by analyzing the derivative and using a logarithmic inequality.
  • Global robustness comparison: The same reasoning applies when f(x) ≤ 0, and combining the bounds yields a final comparison using ρunif,ϵ(f) ≥ρadv(f).The comparison is obtained after taking expectations over the pointwise inequalities.

B Vertical-horizontal example: quadratic classifier

The quadratic-classifier example diagonalizes A via a basis change, formulates the minimum label-switching perturbation, and solves it explicitly for the first datapoint. In transformed coordinates, the optimum has ˜r1 = −1/2 and ˜r4 = 1/2, corresponding to r = [0, −1/2, 1/2, 0]T in the original space.

  • Quadratic classifier: The analysis changes to the diagonalizing basis P of A before analyzing the quadratic classifier.The transformed input is defined by ˜x = Px.
  • Quadratic classifier: For a point x and label y, the method finds the minimal perturbation that switches the estimated label.This optimization is posed in the transformed-coordinate analysis.
  • Quadratic classifier: For x = [1 + a, 1 + a, a, a]T, the optimal transformed perturbation is ˜r1 = −1/2 and ˜r4 = 1/2.The example gives ˜x1 = 1 and ˜x4 = 0; the other datapoints are handled similarly.
  • Quadratic classifier: The corresponding perturbation in the original space is r = [0, −1/2, 1/2, 0]T.It is obtained through r = P^T ˜r.

C Discussion on the norms used to measure the magnitude of adversarial perturbations

The section argues that measuring adversarial robustness requires choosing a norm and radius that faithfully represent perceptibility and class preservation. Comparisons between ℓ2 and ℓ∞ are volume-sensitive and application-dependent, so neither norm is universally preferable.

  • Definitions: Robustness is defined through a norm-based region R(x) assumed to contain points sharing x’s true class, with non-robustness when the classifier changes its prediction inside that region.The theoretical upper bound certifies non-robustness using distinguishability and risk.
  • Choosing the norm and radius: The central difficulty is selecting N and η so R(x) contains all images with the same underlying class, since existing ℓ2 and ℓ∞ choices rely on task-specific assumptions.The discussion cites pixel precision for ℓ∞ and derives η = κ/10 when ℓ2 perturbations are one order of magnitude below κ.
  • Application dependence: There is no universal norm for measuring adversarial robustness because the appropriate choice depends strongly on the application.The section calls for further theoretical research on the advantages of each norm.
  • Comparing ℓ2 and ℓ∞: In high dimensions, R∞ is a tiny fraction of R2, with their volume ratio decaying exponentially, making direct comparisons potentially unfair.A volume-matched ℓ2 region is proposed to remove this bias.
  • Comparing ℓ2 and ℓ∞: Using volume matching changes the “3” versus “7” example from an ℓ∞ limit of 0.1414 to approximately 0.3, producing images roughly twice as perturbed.The revised comparison is intended to highlight norm advantages without region-volume bias.
  • Application dependence: The sport-ball example shows that ℓ2 can be preferable: with η0 = 0.11, ℓ∞ does not define a valid region, whereas ℓ2 with η′′ 0 = 0.0532 excludes invalid images.The example is presented as a proof of concept rather than a universal ranking of norms.
Loading 1502.02590v4…