Source-linked AI summary
On the tradeoff between robustness and geometric accuracy in adversarial training
Rachel Morris, Ryan Murray, Kerrek Stinson
TL;DR
The paper asks whether adversarial robustness necessarily costs accuracy, particularly when earlier incompatibility results concerned rigid hypothesis classes. It proves geometric error bounds for non-parametric binary classifiers, with rates determined by Bayes-boundary regularity. The bounds extend across norms and to finite-data settings.
Problem
The paper asks whether adversarial robustness sacrifices accuracy, against prior incompatibility results for linear or rigid hypothesis classes.
Source: §1 · p. 1Method
Results
Geometric error is O(√ε) for locally Lipschitz Bayes boundaries and O(ε) with stronger regularity, with analogous estimates for any norm and finite data.
Source: §1 · pp. 1–2, §2.1 · p. 4Takeaways & Limitations
The dimension-independent geometric estimate gives a precise robustness–accuracy tradeoff that is meaningful for high-dimensional statistics.
Source: §1 · p. 1The rates assume non-degenerate densities and a locally Lipschitz Bayes boundary; the improved O(ε) rate additionally requires σ-regularity.
Source: §2.1 · p. 4
Abstract
from arXiv · showhide
For non-parametric binary classification in the presence of an adversary, we prove an optimal quantitative estimate for adversarial classifiers controlling geometric accuracy, as measured by the Hausdorff distance to the Bayes classifier, in terms or their robustness, as encoded by the adversarial budget $\varepsilon$. This rigorously shows that robust classifiers sacrifice at most $O(\sqrt{\varepsilon})$ or $O(\varepsilon)$ in accuracy, depending on the regularity of the underlying Bayes classifier. In contrast to prior work on the incompatibility of robustness and accuracy over low-complexity hypothesis classes, our work shows that high-complexity hypothesis classes allow for robust classifiers with precisely quantified accuracy. Our results apply for adversaries determined by any norm on Euclidean space and in both the infinite and finite data settings.
1. Introduction
The paper quantifies how adversarial robustness trades off with geometric accuracy in non-parametric binary classification. Its estimates give dimension-independent error rates that depend on Bayes-boundary regularity and extend to general norms and finite data.
1. Introduction
- The paper asks whether robustness sacrifices accuracy, showing that flexible non-parametric classes permit robust classifiers with quantified accuracy despite prior incompatibility results for rigid classes.Prior work described the conflict over linear classifiers as a consequence of insufficient hypothesis-class complexity.Source: §1 · p. 1
- Robust classifiers have O(√ε) geometric error for Lipschitz Bayes boundaries and O(ε) with stronger regularity, with estimates extending to any norm and finite data.The finite-data result holds with near-optimal sample complexity.Source: §1 · pp. 1–3
- Compared with an earlier ε^(1/(d+2)) estimate under additional assumptions, the new dimension-independent scaling makes geometric accuracy estimates meaningful in high-dimensional statistics.The paper justifies optimality with examples and prior curvature-flow results.Source: §1 · p. 2
- To control boundary displacement, the proofs construct energetic competitors by removing a ball and use them to form barriers whose scale depends on ε and Bayes-boundary regularity.The finite-data construction also accounts for empirical-to-continuum distribution error through Wasserstein control and an averaging initialization.Source: §1 · pp. 2–3
AI use declaration
- The authors report that ChatGPT assisted with simplifying arguments and extending Theorem 2.7 to non-smooth norms, and that Figure 2 was AI-assisted.They state that they take responsibility for the validity of the arguments.Source: AI use declaration · p. 3
2. Main results
The paper establishes geometric convergence of adversarial classifiers to the Bayes classifier in both continuum and empirical settings. The accuracy rate depends on Bayes-boundary regularity, while empirical convergence also requires control of sampling error.
2.1. Convergence for the continuum adversarial training problem.
- The continuum estimates assume non-degenerate densities; locally Lipschitz Bayes boundaries give the √ε control, while σ-regularity enables the improved ε estimate.For the Euclidean norm, σ-regularity corresponds to a C1,1-regular boundary; crystalline norms also allow certain polygonal geometries.Source: §2.1 · p. 4
- For non-degenerate densities and a locally Lipschitz Bayes boundary, continuum minimizers are locally close to the Bayes classifier, with dimension-independent scaling determined by boundary regularity.The estimate uses a local Hausdorff metric on a compact set K.Source: §2.1 · pp. 4–5
- The continuum rates are optimal: geometric error scales as O(√ε) for Lipschitz boundaries and O(ε) in the high-regularity setting.The paper gives heuristic examples establishing optimality for both rates.Source: §2.1 · p. 5
2.2. Convergence for the empirical adversarial training problem.
- The empirical results are stated on a bounded connected domain Ω where both class densities are supported and bounded below by a positive constant.The paper does not pursue the analogous empirical theorem on all of Rd.Source: §2.2 · pp. 5–6
- With η(n) < c0ε^3/2, the empirical low-regularity estimate controls geometric error by √ε with probability 1−O(n^-α/2).The theorem assumes non-degenerate densities and a locally Lipschitz Bayes boundary in Ω.Source: §2.2 · p. 6
- With η(n) < cκε^(2+κ), the empirical high-regularity estimate gives dH,K(Aε, A0) ≤ C1ε with probability 1−O(n^-α/2).This result additionally assumes a locally σ-regular Bayes boundary in Ω.Source: §2.2 · p. 6
- The empirical sampling condition costs an extra factor of ε in η compared with the hoped-for high-regularity scale, due to delicate averaging of perimeter terms.The paper states η ≲ ε² rather than the hoped-for η ≲ ε, ignoring κ; this shortcoming is not exacerbated in higher dimensions.Source: §2.2 · p. 6
3. Heuristic argument: Proof in smooth case
The smooth-case heuristic uses first variation to explain the geometric convergence estimate under regularity assumptions on the Bayes classifier and the adversarial minimizer. It yields O(ε) Hausdorff control, while the general proof avoids assuming regularity of the minimizer’s boundary.
Heuristic argument for Theorem 2.3(2)
- The smooth-case argument assumes Euclidean perturbations, compact C2 boundaries, a non-degenerate Bayes classifier, C1 densities, and a nonzero boundary gradient of the density difference.The smoothness argument is illustrative and is not a prerequisite for the general proof.Source: §3 · pp. 6–7
- At the point x0 farthest from A0, the distance maximum gives a curvature lower bound when ε is sufficiently small.This local geometric control is used in the first-variation heuristic.Source: §3 · p. 7
- The smooth-case estimates yield dH(Aε, A0) < Cε, with C independent of ε.The proof also bounds the distance from the farthest boundary point to A0 by a constant times ε.Source: §3 · p. 7
- The general proof bypasses regularity of ∂Aε by using one-sided regularity at farthest points to construct energetic competitors.The smooth-case heuristic is presented to clarify the basic argument without technical details that hinder intuition.Source: §3 · pp. 6–7
4. Preliminaries on adversarial training
The preliminaries define set dilations, erosions, openings, and closings in metric spaces, and distinguish continuum operations from those on sampled domains. They also establish existence of minimizers and that opening or closing a minimizer preserves minimality.
Set operations
- The ε-dilation contains points at distance less than ε from a set, while the ε-erosion keeps points at least ε from its complement; opening and closing compose these operations.The opening is erosion followed by dilation, and the closing is dilation followed by erosion.Source: §4 · p. 8
Metric spaces and domains
- The framework uses norm-induced metrics on Euclidean space or finite samples, with erosions, dilations, and complements taken in the relevant domain.For dilations, the measure term ν0(Aε) is unchanged whether dilation is taken in the sample domain or in Rd.Source: §4 · p. 8
Existence and minimizers
- For ε > 0, both continuum and empirical adversarial classification problems have minimizers.The minimizers are denoted Aε and Aε, respectively.Source: §4 · p. 8
Minimizer properties
- Opening or closing a minimizer preserves minimality, in both the continuum and empirical problems.The empirical result uses erosions and dilations relative to the sampled domain Xn.Source: §4 · p. 8
5. The continuum problem
The continuum analysis constructs energy-improving competitors by removing balls, then bounds how far an adversarial minimizer can lie from the Bayes classifier. The resulting accuracy rate depends on the regularity of the Bayes boundary.
5.1. Energetic competitor.
- The basic competitor excises an ε-neighborhood of a ball, improving energy when the integrand in the corresponding estimate is positive.The ball's center and radius can be chosen for different settings.Source: §5.1 · pp. 8–9
5.2. Convergence in the low regularity setting.
- The low-regularity argument gives O(√ε) Hausdorff control, and a rounded-cone example shows this scaling is likely optimal.The example balances a perimeter gain of order εr against a bulk cost of order r^3.Source: §5.2 · p. 12
5.3. Convergence in the high regularity setting.
- For σ-regular Bayes boundaries, the proof uses tangential-normal coordinates to choose a competitor-ball radius independent of its distance from A0.This avoids a dimension-dependent loss from Euclidean and σ-distance equivalence; the proof replaces √ε by ε.Source: §5.3 · pp. 12, 14
- A ball example shows that O(ε) is the best expected Hausdorff scaling in the high-regularity setting.Among concentric-ball competitors, the optimizer is at least O(ε) away from A0.Source: §5.3 · p. 14
6. The empirical problem
The empirical analysis adapts competitor construction to sampled discrete classifiers, controlling the empirical–continuum gap before deriving convergence in low- and high-regularity settings. In the high-regularity proof, ε replaces √ε in the corresponding lower-regularity argument.
6.1. Probabilistic setting.
- The probabilistic setup treats labels as independent Bernoulli samples and uses transport estimates to relate empirical and continuum measures.The passage also applies Hoeffding’s inequality to sample counts.Source: §6.1 · pp. 14–15
6.2. Empirical energetic competitor.
- The empirical competitor controls distributional errors by averaging over radii to find a good radius, under a stated volume condition.The competitor is conditional on the volume condition, and its choice of Q depends on ε and the regularity of A0.Source: §6.2 · pp. 15, 16, 18
6.3. Convergence in the low regularity setting.
- In the low-regularity setting, the proof obtains a one-sided estimate controlling the first term of d_H,K(Aε, A0) at O(√ε), choosing Q = 2 and η = O(ε^(3/2)).Source: §6.3 · pp. 18–19
6.4. Convergence in the high regularity setting.
- In the high-regularity setting, an averaging argument to select Q is the main novelty in the one-sided estimate for empirical convergence.The proof synthesizes strategies from the continuum and empirical low-regularity analyses.Source: §6.4 · p. 20
- With the one-sided estimate established, Theorem 2.7(2) follows the corresponding argument with ε replacing √ε.The proof uses Remark 5.7 and Proposition 6.4 in place of Lemma 5.3 and Proposition 6.3, respectively.Source: §6.4 · p. 21
Appendix A. Geometric inequality
The appendix uses the geometry of Voronoi cells to establish a set relation for neighborhoods of the sample points.
Appendix A. Geometric inequality
- Each Voronoi cell Vi is star-shaped about its sample point pi, though it need not be convex for every norm σ.The proof contracts points toward pi within each cell.Source: Appendix A · p. 21
- The text sets u = ε − η and v = ε + η within (A.1); it also states that η ≤ ε/(8d) implies dt ≤ 1/2.Source: Appendix A · pp. 21–22
- The resulting neighborhood relation is stated for the sets Sε+η and Sε−η.The proposition concludes with Sε+η = (Sε)η and Sε−η ⊂ (Sε)−η.Source: Appendix A · p. 22