PaperlayerView exact revision on arXiv

Source-linked AI summary

Randomized Smoothing of All Shapes and Sizes

Greg Yang, Tony Duan, J. Edward Hu, Hadi Salman, Ilya Razenshteyn, Jerry Li

arXiv:2002.08118v5cs.LGcs.CVcs.NEstat.ML

TL;DR

Randomized smoothing lacked a general theory connecting smoothing distributions to perturbation norms. The paper introduces geometric and certification tools, identifies Wulff Crystal optima, improves ℓ1 certified accuracy, and proves limits for current techniques.

  • Problem

    Existing randomized-smoothing guarantees required substantial effort for different metrics, motivating a general theory of smoothing distributions and perturbation norms.

  • Method

    The paper combines Wulff Crystal geometry, two methods for deriving robust radii, and Banach space cotype theory to analyze randomized smoothing.

  • Results

    The approach achieves state-of-the-art ℓ1 certified accuracy and shows that label-statistics-based smoothing cannot certify nontrivial accuracy beyond Ω(min(1, d^(1/p − 1/2))) ℓp radius.

  • Takeaways & Limitations

    The results provide a framework for designing smoothing schemes while exposing limits of current certification techniques, especially for p > 2.

  • Takeaways & Limitations

    The no-go result is formulated for binary classification, although it applies straightforwardly to current certification methods that reason about the two most likely classes.

Abstract

from arXiv · show

Randomized smoothing is the current state-of-the-art defense with provable robustness against $\ell_2$ adversarial attacks. Many works have devised new randomized smoothing schemes for other metrics, such as $\ell_1$ or $\ell_\infty$; however, substantial effort was needed to derive such new guarantees. This begs the question: can we find a general theory for randomized smoothing? We propose a novel framework for devising and analyzing randomized smoothing schemes, and validate its effectiveness in practice. Our theoretical contributions are: (1) we show that for an appropriate notion of "optimal", the optimal smoothing distributions for any "nice" norms have level sets given by the norm's *Wulff Crystal*; (2) we propose two novel and complementary methods for deriving provably robust radii for any smoothing distribution; and, (3) we show fundamental limits to current randomized smoothing techniques via the theory of *Banach space cotypes*. By combining (1) and (2), we significantly improve the state-of-the-art certified accuracy in $\ell_1$ on standard datasets. Meanwhile, we show using (3) that with only label statistics under random input perturbations, randomized smoothing cannot achieve nontrivial certified accuracy against perturbations of $\ell_p$-norm $Ω(\min(1, d^{\frac{1}{p} - \frac{1}{2}}))$, when the input dimension $d$ is large. We provide code in github.com/tonyduan/rs4a.

1. Introduction

The paper develops a general framework for randomized smoothing across perturbation norms, combining new certification methods, geometric optimality results, empirical gains, and impossibility bounds.

  • Randomized smoothing provides provable robustness by predicting the class most likely under random perturbations, while Gaussian noise canonically protects against ℓ2 attacks.
  • The paper introduces two certificate-computation methods, identifies Wulff Crystal level sets for optimal ℓ1, ℓ2, and ℓ∞ smoothing distributions, and derives a Banach-cotype limitation.
  • > 30% advantage over prior SOTA for ℓ1 radius ≥1.5 is achieved on CIFAR-10 with stability training, semi-supervised learning, and pre-training.
  • Table 1 compares certified top-1 accuracies of the paper’s ℓ1-robust classifiers with previous state-of-the-art on ImageNet and CIFAR-10 across radii.

2. Related Works

Prior work spans empirical and certified defenses, randomized-smoothing guarantees, geometric Wulff Crystal theory, and emerging impossibility results.

  • Empirical defenses use heuristics such as adversarial training but provide no guarantee that stronger attacks cannot break them.
  • Certified defenses guarantee locally constant predictions, using exact but inefficient methods or conservative certification methods.
  • Randomized smoothing progressed from heuristic defense to differential-privacy, information-theoretic, and tight Gaussian ℓ2 guarantees.
  • The paper relates adversarial robustness to Wulff Crystals, whose energy-minimizing shape was proposed by George Wulff in 1901.
  • Unlike prior indirect barriers, the paper directly rules out a broad suite of current certificate techniques for standard certified robustness across ℓp norms with p > 2.

3. Randomized Smoothing

Randomized smoothing maps a base classifier and noise distribution to a smoothed classifier that predicts the most probable noisy label, yielding stability against additive perturbations.

  • Given classifier f and noise distribution q, the smoothed classifier g assigns each input the class most likely under random noise perturbation.
  • The growth function Gq(p, v) measures the maximal increase in a decision region’s q-measure after shifting q by v, given initial measure p.
  • For an additive adversary constrained to an allowed set B, robustness certificates depend on the smoothing distribution and perturbation geometry.

4. Methods for Deriving Robust Radii

The paper derives robust radii through complementary level-set and differential methods, covering broad distribution families and clarifying their tightness and computational trade-offs.

  • Level Set Method: The Neyman-Pearson lemma characterizes the relevant shifted-measure comparison, but general distributions make its set geometry difficult to analyze.
  • Level Set Method: The level-set method decomposes Neyman-Pearson geometry into integrals over density superlevel sets and can be efficient when those sets are symmetric.
  • Level Set Method: The level-set procedure computes growth functions and robust-radius bounds, which become tight under sufficient symmetry and can be tabulated for certification.
  • Differential Method: The differential method bounds the largest infinitesimal increase in q-measure under a perturbation and integrates this bound into a robust radius.
  • Differential Method: For q(x) ∝ exp(−||x||∞/λ), the differential method provides an ℓ1 robust radius, and related product distributions recover tight Gaussian, Laplace, and Uniform bounds.
  • Comparison: The level-set method is always as tight as Neyman-Pearson, whereas the differential method is more general and often symbolic but is ordinarily tight only infinitesimally.
  • Comparison: In high dimensions, the two methods yield almost identical robustness certificates for distributions covered by both.

5. Wulff Crystals

The section develops a geometric theory linking adversarial norms to optimal smoothing distributions through Wulff Crystals, and characterizes when these distributions maximize certified radii. The main optimality result is strongest for inputs classified correctly only barely.

  • Theory setup: The relationship between adversary B and smoothing distribution q is analyzed through uniform distributions and an optimality theorem for reasonable distributions.The framework begins with uniform smoothing distributions before extending the analysis to broader density families.
  • Uniform smoothing: For uniform smoothing on a set S, the certified-bound expression depends on the volume added by translating S by a perturbation v.The relevant quantity is Gq(p, v) = min(1, p + Vol((S + v) \ S)).
  • Uniform smoothing: For fixed misclassification probability p, smaller sup_v∈B ||v||2 Vol(ΠvS) yields a more robust smoothed classifier.This quantity controls the robust radius in the small-radius regime when the classifier's error probability under smoothing is near one-half.
  • Wulff Crystals: The Wulff Crystal is the unit ball of a norm defined through expected absolute inner products with uniformly sampled vertices of B.For sufficiently symmetric polytope adversaries, this crystal solves the associated energy-minimization problem without requiring convexity.
  • Optimal smoothing: Among reasonable even densities with matched superlevel-set volumes, the unique optimizer has superlevel sets proportional to the Wulff Crystal of B.The volume constraint indirectly controls distribution variance.
  • Optimal smoothing: Wulff Crystal level sets give the best robust radii for hard inputs with correct-class probability ρ = 1/2 + ε, but the theorem does not address ρ far from 1/2.The paper reports that these distributions are nevertheless empirically effective beyond this narrow theoretical regime.

6. Experiments

The experiments compare smoothing distributions on ImageNet and CIFAR-10 using certified-accuracy upper envelopes across matched noise variances. Uniform smoothing is strongest for ℓ1 certification, spherical distributions are competitive for ℓ2, and spherical level sets outperform cubical or cross-polytope level sets for ℓ∞.

  • Experimental setup: Experiments evaluate smoothing distributions on ImageNet and CIFAR-10 using certificates derived by the level-set or differential methods.The procedure follows prior randomized-smoothing experiments and reports certified accuracy across adversarial radii.
  • Experimental setup: Certified accuracy is the test-set fraction correctly classified and certified at an ℓp radius ϵ, using N = 100,000 samples and failure probability α = 0.001.Models are trained across scale parameters corresponding to matched noise-variance ranges, and plots show upper envelopes over those scales.
  • Additional training methods: Stability training, ImageNet pre-training, and semi-supervised self-training further improve the reported results.These techniques are studied beyond the noise-augmentation-only experiments summarized in this section.
  • ℓ1 adversary: Uniform smoothing performs best for ℓ1 certified accuracy on ImageNet and CIFAR-10, significantly outperforming Gaussian and Laplace distributions.Other distributions with cubic level sets match but do not exceed Uniform after hyperparameter sweeps.
  • ℓ2 adversary: Spherical-level-set distributions perform similarly to, but do not surpass, Gaussian smoothing for ℓ2 certification on CIFAR-10.The ℓ2 comparison is shown in the left panel of Figure 3.
  • ℓ∞ adversary: For ℓ∞ certification, spherical level sets outperform cubical and cross-polytope level sets, while the corresponding Wulff Crystal is a complex zonotope.The paper states that Gaussian smoothing is optimal up to a dimension-independent factor when using no more powerful technique than Neyman–Pearson.

7. No-Go Results for Randomized Smoothing

The section formalizes a tradeoff between robustness and accuracy, then proves that information-limited randomized smoothing faces dimension-dependent limits across normed spaces.

  • Framework: Randomized smoothing estimates prediction confidence from the probability mass of a base classifier’s decision region under noise.A sufficiently large confidence prevents small perturbations from changing the smoothed prediction.
  • Framework: Useful smoothing requires robustness within radius ε while preserving distinguishability for points separated by norm distance at least 1.These requirements are captured by (ε, s, ℓ)-useful smoothing: robustness margin s and non-collapse parameter ℓ.
  • Metric-Embedding View: The smoothing scheme can be viewed as a mapping from inputs to distributions, whose total-variation geometry connects useful smoothing to metric embeddings.Banach-space cotype bounds then constrain the distortion achievable by this mapping.
  • Cotype Limits: For ℓp spaces, cotype bounds imply that useful smoothing has dimension-dependent limits, with the Gaussian scheme matching these limits up to constants.The result applies across p ∈ [1, ∞].
  • Cotype Limits: No smoothing technique using only correct-class probability ρ can certify nontrivial accuracy at ℓ∞ radius Ω(d^-1/2), or at ℓ2 or ℓ1 radius Ω(1).These bounds apply when confidence is the only information extracted from random perturbations.
  • Possible Extensions: The barrier may be bypassed by using more base-classifier information or exploiting multi-class structure, although full-information certification is substantially slower.A cited full-information method is described as 100 times slower than information-limited algorithms.

8. Conclusion

The paper combines new certification techniques, geometric analysis, and empirical evaluation to advance randomized smoothing while identifying limits for higher-order norm adversaries.

  • Contributions: The work presents two techniques for deriving robustness guarantees, analyzes the geometry connecting noise distributions to norms, and reports state-of-the-art ℓ1 provable defense.The conclusion frames these advances as the main ways the paper pushes randomized smoothing across different ℓp adversaries.
  • Future Directions: The paper identifies leveraging more base-classifier information and exploiting multi-class structure as directions for bypassing current certification barriers.The conclusion leaves both directions for future investigation.
  • Broader Relevance: The authors suggest that robustness-certificate methods and noise-distribution optimization may also be useful for differential privacy.They note that both areas study stability while maintaining utility.

B. Analysis of Robust Radii

Robust radii depend primarily on level-set shape and concentration, while the differential method becomes practically as tight as the level-set method in high dimensions. The analysis also contrasts the methods’ tightness, efficiency, and applicability.

  • Level-set structure: Distributions concentrated around the same level set have similar robust radii, because the level-set and differential expressions evaluate similarly.This similarity is reported for multiple exponential, power-law, and Pareto examples.
  • Level-set structure: Among distributions concentrated around a level set, its shape is the biggest determinant of performance.
  • Level-set structure: Distributions that do not concentrate on a level set have smaller robust radii than distributions that do.The comparison is illustrated by large- versus small-power examples and several subplots.
  • Level-set structure: Singularities at the origin reduce robust radii, providing no evidence for the proposed soap-bubble hypothesis.
  • Level-set structure: Fatter tails yield larger robust radii for large lower confidence probabilities when level-set concentration is unchanged.The exponential distribution’s radius tends to infinity as ρ approaches 1, whereas the uniform distribution has a finite maximum radius.
  • Method comparison: In dimensions d = 32 or 1024, level-set and differential methods produce indistinguishable robust radii, although the differential method is slightly loose at d = 2 and 4.
  • Comparison with prior certification: The information-limited comparison method is constrained by the difficulty of manually computing divergence balls, limiting the distributions it can handle beyond matching norm pairs.The paper contrasts this limitation with differential certificates for mismatched norms, such as Laplace smoothing against ℓ∞ perturbations.

C. Additional Experimental Results

Additional experiments examine noise distributions, model architectures, and train–test noise choices. Results indicate that level-set shape and compatibility between noise, architecture, and data strongly influence certified or clean accuracy.

  • ℓ1 adversary: For ℓ1 adversaries, distributions with cubic level sets match the Uniform distribution, while distributions without cubic level sets perform worse.The experiments include Gaussian, Laplace, Uniform, exponential, power-law, and i.i.d. Pareto distributions.
  • ℓ1 adversary: The experiments suggest that level-set shape matters more than noise tail behavior for ℓ1 certification.
  • ℓ1 adversary: Uniform noise significantly outperforms Gaussian and Laplace at fixed perturbation levels across nearly all Wide ResNet training accuracies.The exception is training accuracies very close to 1.
  • ℓ1 adversary: Much of the ℓ1 certified-accuracy improvement appears to come from how well classifiers train under the smoothing noise, rather than only from improved certified radius per ρ.
  • Architecture and data interaction: Rotating the noise while leaving images unmodified makes the training-accuracy difference vanish, unlike rotating images with unmodified noise.
  • Architecture and data interaction: The results suggest Uniform noise’s training-accuracy advantage reflects synergy among model architecture, data distribution, and smoothing noise.The paper therefore frames noise choice as balancing robustness properties with compatibility with architecture and data.
  • ℓ2 adversary: After hyperparameter search, exponential and power-law distributions with spherical level sets match Gaussian performance against ℓ2 adversaries.
  • Train–test noise mismatch: At fixed σ = 0.5, testing with the same noise used during training gives the best clean accuracy for all considered noises.Using a different certification noise does not improve clean accuracy in this comparison.

D. Experimental Details

The experiments compare smoothing distributions, training procedures, architectures, noise settings, and data strategies using certified and clean accuracy measurements. Standard ImageNet and CIFAR-10 experiments use ResNet-50 and Wide ResNet 40-2 models, while additional studies examine distribution-specific and training effects.

  • Training Methods: Experiments compare four training options: noise augmentation, direct smoothed-classifier training, adversarial training, and stability training.Unless otherwise noted, experiments use noise augmentation; stability training with γ = 6 performed best among the four options.
  • Noise Comparisons: At fixed training accuracy, the Uniform distribution significantly outperforms Gaussian and Laplace for top-1 ℓ1 certified accuracy at ϵ = 0.25.The comparison covers ImageNet and CIFAR-10; increasing σ decreases both training and certified accuracy.
  • Certified Accuracy: Certified accuracy curves report the maximum certified accuracy over σ for Gaussian, Laplace, and Uniform distributions on ImageNet and CIFAR-10.The upper envelope is defined pointwise across the tested σ values.
  • Additional Experiments: Models perform best when tested with the same noise distribution used during training, while spherical level-set distributions can match Gaussian performance after hyper-parameter search.Additional experiments evaluate AlexNet, rotation settings, and larger σ values for cubic level sets.
  • Experiment Hyperparameters: ImageNet experiments use ResNet-50 for 30 epochs with batch size 64, whereas CIFAR-10 experiments use Wide ResNet 40-2 for 120 epochs with batch size 128.All experiments use cosine-annealed learning rates, stochastic gradient descent with momentum 0.9, and weight decay 0.0001.
  • More Data and Training: Stability training, pre-training, and semi-supervised self-training improve certified top-1 accuracy against the ℓ1 adversary.Pre-training uses downsampled ImageNet, while semi-supervised learning uses 500k pseudo-labeled images together with CIFAR-10.

F. The Differential Method

The differential method bounds how quickly a smoothed classifier’s class probability can change under perturbations. It applies to regular exponential-family smoothing distributions and yields robust radii by integrating a distribution-dependent growth function.

  • Growth Function: The growth function is derived from γ_u = ⟨u, ∇ψ(δ)⟩ with δ sampled from q and its complementary CDF.The direction u ranges over vertices of the norm’s unit ball when the ball is a full-dimensional polytope.
  • Examples: The framework recovers known Gaussian, Laplace, and Uniform robustness bounds and gives a tight ℓ1 radius for q(x) ∝ exp(−∥x∥∞/λ).For cubical distributions against an ℓ1 adversary, the resulting radii typically have a logarithmic form in the class probability.
  • Setup: The differential method computes robust certificates for smoothing distributions q(x) ∝ exp(−ψ(x)) under an arbitrary norm.The framework assumes a measurable base function and a regular smoothing density.
  • Robustness Guarantee: If G(x) < 1/2, then the smoothed classifier remains correct under perturbations whose norm is bounded by the theorem’s integrated growth expression.Here G(x) represents the probability assigned to classes other than the correct one.
  • Derivation: The method maximizes infinitesimal measure growth by reallocating probability mass toward regions with large directional derivatives of ψ.This greedy allocation parallels the reasoning used in the Neyman–Pearson lemma.

G.2.1. GROWTH CALCULATIONS FOR STANDARD SHAPES

This section calculates boundary-growth quantities for standard shapes and uses them to analyze optimal smoothing distributions. Wulff Crystal level sets minimize the relevant worst-case growth under stated symmetry and regularity conditions, but the strongest radius implication is local to near-tie predictions.

  • Standard Shapes: The section computes growth for the ℓ2 ball, ℓ1 cross-polytope, axis-parallel cube, and related zonotopes under selected perturbation directions.The calculations use boundary measures, projections, and volume identities for standard convex shapes.
  • Wulff Crystal Geometry: For the ℓ∞ unit ball, the Wulff Crystal is the unit ball of the dual norm and can be represented as a zonotope generated by the hypercube’s sign vectors.Its farthest vertices are coordinate vectors and their negations, while closest facets have constraints of the form ±x_i ± x_j ≤ 1.
  • Regular Distributions: Among regular, even, level-equivalent densities, concentric Wulff Crystal superlevel sets minimize the relevant growth quantity.The proof uses equal-volume superlevel sets and the symmetry of the Wulff Crystal.
  • High-Dimensional Behavior: For d = 3 × 1024, the asymptotic quantity is 1.00016, making the associated bound close to tight in the CIFAR-10 dimension.The comparison concerns the asymptotic result for the standard-shape calculations.

H. Generalization of Differential Method and Wulff Crystal Optimality Results to Bounded Variation Densities

The paper extends its differential-method and Wulff Crystal results from regular densities to bounded-variation densities, covering discontinuous distributions such as uniform laws on finite-perimeter sets.

  • Bounded-variation framework: Bounded variation generalizes differentiability while allowing controlled jump discontinuities, including indicator functions of finite-perimeter sets.The paper states that its concrete probability densities have bounded variation.
  • Main extension: The differential method and Wulff Crystal optimality results generalize to smoothing distributions with BV densities.The paper separately decomposes the variation measure into absolutely continuous and singular parts when defining the generalized construction.
  • Bounded-variation framework: BV functions are characterized through finite-perimeter superlevel sets via the coarea formula and a converse result.For almost every level, superlevel sets have finite perimeter; conversely, this property implies bounded variation.
  • Differential method: For BV densities, convolution with bounded measurable functions is absolutely continuous along every line and almost everywhere differentiable.The directional derivative is represented using the directional variation measure of the density.
  • Wulff Crystal optimality: For symmetric polytopal adversary sets, even BV densities with concentric Wulff Crystal superlevel sets minimize the stated objective among level-equivalent distributions.The resulting Wulff Crystal analysis also yields a constant depending only on the crystal for radial BV densities.
  • Robustness guarantees: The resulting robust radii are tight in several stated cases, including half-plane classifiers and the uniform distribution.The BV differential theorem provides another proof of robust radii for uniform distributions against an ℓ1 adversary.

I.2. ℓ∞Norm-Based Exponential Law

This section analyzes exponential smoothing laws based on the ℓ∞ norm and derives certified radii from the smoothed classifier’s correct-class probability, including the uniform-cube limit.

  • General family: A broader family of ℓ∞-based exponential distributions is analyzed by deriving the corresponding gradient variables and applying the general differential-method theorem.The derivation uses the coordinate attaining the maximum absolute value and a Gamma(d/k) random variable.
  • Overview: ℓ∞ norm-based distributions generally yield certified radii linear in ρ − 1/2, where ρ is the smoothed classifier’s correct-class probability.The section specializes the general framework to the ℓ∞ norm and its Boolean-cube unit-ball vertices.
  • Basic exponential law: For q(x) ∝ exp(−∥x∥∞), the differential method reduces the certificate calculation to a Rademacher random variable and an integral of its tail behavior.The resulting integral simplifies to log(1 / (2(1 − ρ))).
  • General family: The general-family certificate covers correct-class probabilities in a stated interval and specializes to the uniform-cube certificate as j = 0 and k → ∞.The section explicitly notes convergence of both the distribution and robust certificate to the uniform-distribution result.
  • Uniform-cube limit: For uniform smoothing on the cube [−λ, λ]^d, the certified radius is the previously derived uniform-distribution guarantee.The theorem assumes the correct-class probability satisfies ρ > 1/2.
  • Basic exponential law: The basic ℓ∞ exponential law certifies ∥η∥∞ < λ log(1 / (2(1 − ρ))) when the correct class has probability ρ > 1/2.The statement is presented as a provable robustness radius for the smoothed classifier.

J.2. Proof of Lemma J.1

The proof converts a useful smoothing scheme into a threshold map under total variation distance, then invokes metric-embedding and cotype results to constrain the underlying norm.

  • From smoothing to embeddings: Assuming absolutely continuous smoothing distributions, the scheme maps each input x to its associated distribution q_x in the total-variation space.The proof notes that general distributions can be handled using Lebesgue decomposition and Radon–Nikodym derivatives.
  • Embedding step: The total-variation space of probability distributions is an infinite-dimensional L1 space with squared-L2 distortion Θ(1).This permits transferring the threshold map into a Hilbert space with square-root threshold parameters.
  • Threshold map: An (ε, r, ℓ)-useful smoothing scheme induces small total-variation distance for inputs within ε and large distance for inputs separated by at least 1.The resulting threshold-map parameters are (ε, 1, 2r, ℓ).
  • Embedding step: When s/ℓ ≤ 1/162, the threshold-map construction yields a Hilbert-space embedding with controlled distances for near and far pairs.The proof combines the total-variation threshold map with the cited Hilbert-space theorem.
  • Cotype conclusion: A cotype-based distortion lower bound then applies to the finite-dimensional normed space, completing the proof of Lemma J.1.The argument combines the Hilbert embedding with the theorem relating embeddings to cotype constants.
Loading 2002.08118v5…