Robustness of classifiers: from adversarial to random noise

Alhussein Fawzi; Seyed-Mohsen Moosavi-Dezfooli; Pascal Frossard

Source-linked AI summary

Robustness of classifiers: from adversarial to random noise

Alhussein Fawzi, Seyed-Mohsen Moosavi-Dezfooli, Pascal Frossard

arXiv:1608.08967v1Aug 31, 2016cs.LGcs.CVstat.ML

TL;DR

Classifiers can be vulnerable to adversarial perturbations yet robust to random noise, leaving the broader intermediate regime insufficiently characterized. The paper analyzes semi-random perturbations in random subspaces, deriving curvature-dependent bounds that interpolate between random and worst-case robustness and match experiments on deep networks and datasets.

Problem
Existing work shows adversarial vulnerability and empirical random-noise robustness, but does not quantitatively characterize the intermediate semi-random regime.
Method
The paper derives robustness bounds for random-subspace perturbations, relating them to adversarial robustness through decision-boundary curvature and subspace dimension.
Results
The bounds interpolate between random and worst-case regimes and provide very accurate estimates for state-of-the-art deep networks across various datasets.
Takeaways & Limitations
Small decision-boundary curvature can support robustness to random noise in high-dimensional classification even when adversarial robustness is relatively small.
Takeaways & Limitations
The curvature condition applies to smooth pairwise class boundaries, not necessarily to the global boundary at junction points where curvature may be large or infinite.

Abstract

from arXiv · show

Several recent works have shown that state-of-the-art classifiers are vulnerable to worst-case (i.e., adversarial) perturbations of the datapoints. On the other hand, it has been empirically observed that these same classifiers are relatively robust to random noise. In this paper, we propose to study a \textit{semi-random} noise regime that generalizes both the random and worst-case noise regimes. We propose the first quantitative analysis of the robustness of nonlinear classifiers in this general noise regime. We establish precise theoretical bounds on the robustness of classifiers in this general regime, which depend on the curvature of the classifier's decision boundary. Our bounds confirm and quantify the empirical observations that classifiers satisfying curvature constraints are robust to random noise. Moreover, we quantify the robustness of classifiers in terms of the subspace dimension in the semi-random noise regime, and show that our bounds remarkably interpolate between the worst-case and random noise regimes. We perform experiments and show that the derived bounds provide very accurate estimates when applied to various state-of-the-art deep neural networks and datasets. This result suggests bounds on the curvature of the classifiers' decision boundaries that we support experimentally, and more generally offers important insights onto the geometry of high dimensional classification problems.

1 Introduction

The paper studies classifier robustness beyond worst-case perturbations by introducing a semi-random regime that permits random subspaces with adversarial perturbations within them. Its bounds relate robustness to decision-boundary curvature and explain robustness to random noise in high dimensions.

Motivation: State-of-the-art deep networks can be unstable to worst-case perturbations, motivating robustness analysis for uncontrolled or hostile environments.The paper contrasts this vulnerability with empirical robustness to random noise.
Problem and approach: The semi-random regime chooses a random subspace and seeks the smallest misclassifying perturbation within that subspace, generalizing random noise.The analysis quantifies robustness through the curvature of the classifier’s decision boundary.
Contributions: √d times the distance to the classification boundary characterizes random-noise robustness when boundary curvature is sufficiently small.This implies robustness can hold in high-dimensional problems even for datapoints close to the boundary.
Contributions: √(d/m) times the distance to the boundary characterizes semi-random robustness, where m is the random subspace dimension.Even a small subspace fraction can permit small misclassifying perturbations.
Empirical support: Theoretical estimates are accurately satisfied by state-of-the-art deep networks across various datasets, supporting experimentally limited curvature of their decision boundaries.The paper also visualizes and estimates boundary behavior using two-dimensional sections.

2 Definitions and notations

The paper measures robustness by the smallest perturbation that changes a classifier’s label, either without constraints or within a chosen subspace. Random directions give the random-noise regime, while random subspaces of dimension m define the semi-random regime.

Classifier notation: An L-class classifier maps x ∈ R^d to class scores, and the estimated label is the index of the largest score.The notation fixes the classifier output components as f_k(x).
Robustness measure: The constrained perturbation r*_S is the minimum-norm vector in subspace S required to change the estimated label at x_0.Perturbations that reach the boundary are treated as changing the label.
Robustness measure: The unconstrained adversarial perturbation r* has norm equal to the minimum distance from x_0 to the classifier boundary.Restricting perturbations to S yields robustness measured by ||r*_S||_2.
Random noise regime: Random noise uses a one-dimensional subspace m = 1 whose direction is sampled uniformly from the unit sphere.The robustness is the smallest absolute scalar displacement along that random direction causing misclassification.
Semi-random noise regime: Semi-random noise uses a randomly chosen subspace of arbitrary dimension m and searches adversarially within that subspace.The random-noise regime is the special case m = 1.

3 Robustness of affine classifiers

For affine classifiers, the paper derives high-probability relations between robustness in random subspaces and unconstrained adversarial robustness. These relations interpolate between random and worst-case noise through the subspace dimension.

Theorem and bounds: Theorem 1 bounds semi-random robustness using ζ1(m, δ) and ζ2(m, δ), with a random m-dimensional subspace and confidence parameter δ.The constants control the inequality factors and do not depend on the data dimension d.
Theorem and bounds: For sufficiently large m, ζ1(m, δ) and ζ2(m, δ) are close to 1; in the illustrated setting, both lie in [0.8, 1.3] for m ≥250.The interval is unavoidably wider when m = 1.
Random-noise consequence: In the random regime, robustness behaves as Θ(√d||r*||_2) with high probability for affine classifiers, even when the datapoint lies very close to the boundary.For m sufficiently large, semi-random robustness approaches the corresponding √(d/m) scaling.
Interpolation across regimes: √(d/m)||r*||_2 relates semi-random robustness to adversarial robustness with high probability when the inequality constants are near 1.This relation interpolates between √d||r*||_2 for random noise and ||r*||_2 for worst-case noise.
Interpolation across regimes: 10||r*||_2 results when m = 0.01d, showing that semi-random robustness can remain small even when the subspace is only a small fraction of the data dimension.The paper notes that this magnitude might still be imperceptible in complex visual tasks.

4 Robustness of general classifiers

The paper characterizes random and semi-random robustness of nonlinear classifiers through the curvature of pairwise decision boundaries, relating these quantities to worst-case robustness. Under sufficiently small curvature, the bounds recover linear behavior and explain when random noise is less damaging than adversarial noise.

4.1 Decision boundary curvature: The analysis defines pairwise decision boundaries between classes and measures their nonlinearity using curvature based on inscribed balls.The boundary is assumed smooth; curvature is the inverse of the worst-case inscribed-ball radius over boundary points.
4.1 Decision boundary curvature: The curvature measure is zero for affine classifiers and equals 1/R when the boundary consists of sufficiently distant spheres of radius R.This connects the geometric definition to familiar linear and spherical decision boundaries.
4.2 Robustness to random and semi-random noise: Theorem 2 establishes upper and lower bounds relating semi-random robustness to worst-case robustness for a random m-dimensional subspace under a sufficiently small curvature condition.The result is stated with probability larger than 1 − 4δ and constants C = 0.2, C1 = 0.625, and C2 = 2.25.
4.2 Robustness to random and semi-random noise: For nonlinear classifiers, the robustness bounds extend the random and semi-random relations previously obtained for affine classifiers when the boundary curvature is sufficiently small.When κ(Bk) = 0, the result recovers the affine-classifier theorem.
4.2 Robustness to random and semi-random noise: The multiclass extension constrains curvature only on pairwise boundaries involving sufficiently close competing classes, excluding classes whose boundaries are far away or absent.The curvature condition is not imposed on the global decision boundary, because junction points can have very large or infinite curvature.
4.2 Robustness to random and semi-random noise: In high-dimensional settings, sufficiently flat boundaries make classifiers more robust to random noise than to adversarial noise, while low-dimensional semi-random subspaces can retain vulnerability.The paper states that vulnerability can persist even when the subspace dimension is a tiny fraction of d, such as m = 0.01d.

5 Experiments

Experiments test the proposed robustness estimates on classifiers and datasets, finding close agreement and supporting limited decision-boundary curvature. Visual examples also demonstrate that semi-random perturbations can remain imperceptible while causing misclassification.

The experiments evaluate random and semi-random robustness across image classifiers, datasets, and subspace dimensions.
The estimate β(f; m) compares measured semi-random robustness with the predicted d/m∥r∗(x)∥2 scaling and is ideally 1.
β is surprisingly close to 1 even when m is a small fraction of d, indicating accurate estimates for semi-random robustness.
Random, semi-random, and worst-case perturbations all fool VGG-F on the same cauliflower image, changing its classification to “Artichoke”.
Semi-random perturbations with m = 10 are less perceptible than random noise, consistent with attenuation from the 1/√m factor.
Two-dimensional boundary visualizations show small curvature away from class-junction points, supporting the curvature assumption used by the bounds.
A structured subspace formed from translated and scaled words produces an apparently indistinguishable perturbation that still causes misclassification.

6 Conclusion

The conclusion characterizes semi-random robustness through adversarial robustness, curvature, data dimension, and subspace dimension. It reports robustness to random noise for sufficiently flat boundaries but continued vulnerability to mildly adversarial semi-random perturbations.

The bounds characterize semi-random robustness in relation to adversarial robustness, decision-boundary curvature, data dimension, and subspace dimension.
When decision boundaries have small curvature, classifiers can remain robust to random noise even when adversarial robustness is relatively small.
For small subspaces, semi-random noise is mostly random but mildly adversarial, and state-of-the-art classifiers remain vulnerable.
The analysis encourages geometric constraints on decision-boundary curvature to improve robustness to semi-random noise.
The hidden-message example uses a subspace of linear combinations of random words to illustrate the semi-random vulnerability.

A.1 Proof of Theorem 1 (affine classifiers)

The appendix proves the affine-classifier robustness theorem by relating random-subspace projections to projections of uniformly random sphere vectors and extending binary bounds to multiclass settings.

A sphere-projection lemma analyzes a uniformly random vector projected onto its first m coordinates.
The proof derives bounds involving β and δ^2/m, including separate approximations for small and large m.
Theorem 1 relates the norms of semi-random and worst-case perturbations for a random m-dimensional subspace.
For affine classifiers, the linear case permits closed-form computation of the perturbations for any subspace.
A unitary-invariance argument converts projection onto a random subspace into projection of a uniformly random sphere vector onto a fixed subspace.
The proof obtains the multiclass result by applying a binary-to-multiclass lemma and a union bound over bad events.

A.2 Proof of Theorem 2 and Corollary 1 (nonlinear classifiers)

The proof bounds semi-random robustness by comparing nonlinear decision boundaries with tangent spaces and curved-ball geometries under sufficiently small curvature. It then extends these bounds from binary to multiclass classifiers.

Upper bound: A planar constant-curvature lemma approximates directional distance to the curve using distance to its tangent line when curvature is sufficiently small.The proof applies this lemma in the two-dimensional normal section through the boundary and perturbation directions.
Theorem 2: Theorem 2 bounds semi-random robustness in terms of worst-case robustness when the decision-boundary curvature is sufficiently small.The proof uses tangent classifiers and geometric comparisons with inscribed balls.
Upper bound: An inscribed ball of radius 1/κ provides an upper-bound surrogate because the ball lies inside the relevant classification region.Upper bounds for the sphere are therefore valid for the actual nonlinear boundary.
Technical qualification: The maximal radius 1/κ need not be attained at a fixed boundary point, so the proof uses a convergent sequence of radii and takes limits.The same bounds follow by applying the argument to balls with radii 1/κ_n.
Lower bound: The lower bound uses an inscribed ball in the opposite region and a cross-section spanned by the semi-random and worst-case perturbations.The spherical boundary supplies a lower-bound comparison for the real nonlinear boundary.
Corollary 1: Corollary 1 applies Theorem 2 across competing classes under curvature assumptions and simplifies the resulting bounds.The proof combines the binary-to-multiclass lemma with the condition κ(Bk)∥r∥2 ≤ 0.2 ζ2(m,δ).

A.3 Useful results

The auxiliary results characterize worst-case perturbations for tangent planes and spheres, establishing their geometric relationship within an arbitrary subspace.

Lemma 6: For a sphere and its tangent space at the closest boundary point, Lemma 6 compares the corresponding worst-case perturbations within any subspace S.The construction is illustrated using the tangent space Tx∗(∂B) and spherical boundary ∂B.
Lemma 6: The spherical perturbation is obtained from a constrained optimization problem on the sphere, whose points satisfy ∥x∥2 = R.The Lagrangian optimality condition is used to characterize the perturbation.
Lemma 6: The optimal spherical perturbation lies in the subspace S because any orthogonal component could be removed while lowering its ℓ2 norm.This yields the necessary optimality condition used in the proof.
Geometric characterization: The auxiliary calculation concludes that the relevant perturbation vectors are collinear with projected directions associated with the data point and boundary geometry.The proof explicitly states collinearity with PSx0 and PS(x∗−x0).