Tight Certificates of Adversarial Robustness for Randomly Smoothed Classifiers

1 Introduction

• Certificates guarantee that no adversarial example exists within a region, whereas failure to find one by searching does not establish that none exists.Exact guarantees can be computationally intractable, and guarantees that scale to realistic architectures have remained somewhat conservative.Source: §1 · p. 1
• Prior noise-induced ensemble guarantees cover additive isotropic Gaussian noise and an ℓ2 radius that depends on noise variance and ensemble margin.The cited work is [6].Source: §1 · p. 1
• This work extends certificates to alternative metrics and noise distributions, including uniform noise.The passage also introduces a stratified approach, but does not complete its description.Source: §1 · p. 1
• The work provides tight, actionable ℓ0 certificates for discrete domains that apply to any measurable classifier.The authors also introduce scalable algorithms for computing these certificates.Source: §1 · p. 2
• Across image and molecule datasets, the ensemble classifiers achieve state-of-the-art certified guarantees against ℓ0-bounded adversaries.The introduction does not specify the individual dataset results.Source: §1 · p. 2

2 Related Work

• A robustness certificate guarantees constant classification within a local region; it is exact when the condition is both sufficient and necessary.The passage gives the ℓ2 distance to a linear classifier as an example of an exact certificate.Source: §2 · p. 2
• Exact methods for piecewise-linear networks use mixed-integer programming or satisfiability modulo theories, but are generally NP-complete and do not scale to large problems.The cited approaches include [22], [4] [25] [36], and [3] [12] [20].Source: §2 · p. 2
• Relaxation-based certificates can be more scalable than exact methods but are conservative; the cited methods use linear, semidefinite, dual, or layerwise relaxations.The authors report no empirical evidence of effective certificates from these methods in large-scale problems, while noting that this may reflect difficulty obtaining robust networks.Source: §2 · p. 2
• Prior randomized-input certificates progressed from differential privacy and Rényi divergence to a tight Neyman–Pearson-based guarantee, but that guarantee was tailored to isotropic Gaussian noise and ℓ2 distance.The approaches are attributed to [21], [23], and [6], respectively; this paper generalizes across distributions and metrics and tightens guarantees using classifier assumptions.Source: §2 · p. 2
• The paper presents tight, actionable ℓ0 certificates for discrete domains, where robustness verification can require exponentially many predictions even for binary black-box models.The authors describe their method as the first to provide such certificates in discrete domains.Source: §2 · p. 2

3.1 A Framework for Tight Certificates of Robustness

• For p > 0.5, the framework uses worst-case pointwise lower bounds over an ℓq neighborhood to certify a majority prediction; the radius is tight for binary classification.For more than two classes, the stated guarantee is sufficient; the tight guarantee also depends on the largest competing-class probability.Source: §3.1 · p. 3

3.2 A Warm-up Example: the Uniform Distribution

• The uniform-noise example gives closed-form ℓ1 and ℓ∞ regional radii, but bounded support makes its ℓ1 radius inadequate and no greater than γ.The construction partitions space into regions where the two randomized inputs have constant likelihoods, reducing the pointwise optimization to one probability per region.Source: §3.2 · pp. 3–4

3.3 A General Lemma for Point-wise Certificate

• A partition into constant-likelihood-ratio regions, sorted from highest to lowest ratio, reduces the tight pointwise bound to a greedy allocation computable in O(n).The optimal allocation assigns class probability first to high-ratio regions until the input probability constraint is met.Source: §3.3 · p. 4

3.4 A Discrete Distribution for ℓ0 Robustness

• For ℓ0 robustness, symmetry makes ρ depend only on distance r, and precomputed ρ_r^-1(0.5) values support radius lookup.The discrete construction uses likelihood-ratio regions indexed by flip counts; rational probabilities and large-integer arithmetic support verifiably accurate computation.Source: §3.4 · pp. 5–6

3.5 Connection Between the Discrete Distribution and an Isotropic Gaussian Distribution

• Thresholding Gaussian-perturbed binary coordinates at 0.5 yields the discrete randomization scheme, whose certificates are always tighter than Gaussian certificates for the composed classifier.The comparison is between classifiers expressible as a classifier composed with the thresholding function and the broader measurable-classifier family under Gaussian randomization.Source: §3.5 · p. 6

3.6 A Certificate with Additional Assumptions

• Classifier-family assumptions can tighten measurability-only certificates; for binary decision trees using each feature at most once, recursion and dynamic programming find the exact adversary at each ℓ0 radius.The method aggregates worst-case changes across the left and right subtrees.Source: §3.6 · pp. 6–7

4 Learning and Prediction in Practice

• The section focuses on certificates and only briefly covers classifier training and practical computation of prediction probabilities.Source: §4 · p. 7
• For deep networks, training uses randomized samples with cross-entropy loss, and prediction probabilities use a lower confidence bound estimated from 100K samples at 99.9% confidence.Because ρx,¯x(p) increases with p, the lower bound on p yields a valid certificate.Source: §4 · p. 7
• Decision trees are trained greedily in breadth-first order with a depth limit, using only previously unused coordinates and a probability-weighted Gini index for splits.Prediction probability is computed by Eq. (8).Source: §4 · p. 7

5 Experiment

• The evaluation compares discrete certificates with Gaussian-derived ℓ0 certificates using average certified radius and certified accuracy within radius r.MNIST uses a 55,000/5,000/10,000 train/validation/test split, with each coordinate binarized at 0.5; the Bace study uses 1,024-dimensional Morgan fingerprints and compares smoothed and vanilla decision trees.Source: §5 · p. 7, §5.1 · p. 7, §5.3 · p. 9

5.1 Binarized MNIST

• For the same randomly smoothed CNN, the proposed certificates improve average certified radius by about 1.7 ℓ0 units and certified accuracy by as much as 0.4 versus Gaussian-derived certificates.The proposed model also consistently outperforms models trained with Gaussian noise on both measures.Source: §5.1 · pp. 7–8, Table 1 · p. 8

5.2 ImageNet

• At ImageNet ℓ0 radius r=1, the proposed model’s guaranteed accuracy is 0.538 vs. 0.372, and it consistently outperforms the baseline across radii.The experiment uses the same ResNet50 classifier and learning procedure as Cohen et al., changing only the noise distribution.Source: Table 2 · p. 8, §5.2 · p. 8

5.1 Binarized MNIST

• At r=1, exhaustive-search certified accuracy is 0.954 versus 0.921 for the proposed certificate; at r=2, it is 0.926 versus 0.774.The authors describe the certificate as reasonably tight at r=1 but too pessimistic at r=2.Source: §5.1 · p. 8

5.2 ImageNet

• For small ImageNet radii, the number of nonempty likelihood-ratio regions is much smaller than (3 × 224 × 224)^2, and ρ^-1_r(0.5) approaches 1 faster at higher α.The quantity ρ^-1_r(0.5) reaches 1 only when r=d.Source: §5.2 · p. 8, Figure 3 · p. 9
• ImageNet certified accuracy varies nonlinearly with radius: higher α gives higher accuracy at small radii and lower accuracy at large radii.The reported analysis also notes that computing ρ^-1_r(0.5) takes about four days for each α and r, although it can be parallelized and precomputed for reuse across ImageNet-scale images and models.Source: §5.2 · p. 8

5.3 Chemical Property Prediction

• Robust AUC is evaluated against both the adversary’s ℓ0 radius and the fraction of test examples it can manipulate.For each test example, the adversary is computed first, then combined with clean examples under the manipulation-fraction constraint to find the worst AUC.Source: §5.3 · p. 9
• The randomly smoothed decision tree is consistently more robust than the vanilla tree under the robust-AUC comparison.At r=1, the vanilla tree’s adversary always changes positive-example predictions to 0 and negative-example predictions to 1, making its plots constant across radii; the average exact-certificate difference from Lemma 2 is 0.358 at r=1 and 0.402 at r=2.Source: §5.3 · p. 9, Figure 4 · p. 9

• The stratified approach spans pointwise to regional certificates and general results to specific examples, with the hierarchy opening avenues for extensions at different levels.Source: §6 · p. 9

• In the proofs, [n] denotes the set {1, 2, . . . , n}.Source: A Proofs · p. 12

A.1 The proof of Proposition 1

• For ℓ1 perturbations, overlap is minimized by putting all displacement on one coordinate; for ℓ∞ perturbations, every coordinate is displaced by r.Both cases minimize overlap between the relevant regions.Source: §A.1 · p. 12

A.2 The proof of Lemma 2

• Reassigning outputs to be constant within each likelihood region preserves the two class probabilities, reducing the proof to an optimization over region-level values.The proof then represents feasible functions through an optimization program and a corresponding region-level solution.Source: §A.2 · p. 13

A.3 The proof of Lemma 4

• For the coordinate-wise randomization, any pair differing in r coordinates can be rearranged into a canonical pair, making ρ independent of the specific inputs.The proof uses symmetry and the fact that randomization acts independently on each coordinate.Source: §A.3 · p. 14

A.4 The proof of Lemma 5

• The likelihood-tuple count partitions outcomes by shared modifications in matching and differing coordinates, then counts the configurations in each case.The proof uses the symmetry between the two canonical inputs to relate counts for likelihood tuples (u, v) and (v, u).Source: §A.4 · pp. 14–15

B.1 Dynamic Programming For Restricted Decision Tree

• The decision-tree dynamic program stores the worst prediction at each node for each perturbation budget and minimizes over whether the split feature is perturbed.When it is perturbed, one feature is spent at the current node and the remaining budget is allocated across the two subtrees.Source: §B.1 · p. 16

B.2 Training Algorithm For Decision Tree

• Training tracks each input's probability of reaching each node, updating it by α or β according to the split feature and input value.Randomization can send an input to multiple leaves rather than along a single standard decision-tree path.Source: §B.2 · p. 16
• Splits are selected greedily in breadth-first order using weighted Gini impurity computed from the inputs' node-arrival probabilities.The standard Gini impurity instead uses all training data that follow the path to that node.Source: §B.2 · p. 16
• When every input's arriving probability is 0 or 1, the weighted Gini impurity becomes the standard Gini impurity.Source: §B.2 · p. 16

C.1 Supplementary Materials for the MNIST Experiment

• The MNIST discrete-noise model uses a four-layer CNN with two convolutional layers and two feedforward layers.The convolutional layers use kernel size 5 and 20 and 50 output channels; the feedforward layers have 500 hidden nodes.Source: §C.1 · p. 17
• Validation certificates selected α = 0.8 for μ(R), and the experiment also trained a Gaussian-noise CNN at the corresponding σ.The candidate α values ranged from 0.72 to 0.96.Source: §C.1 · p. 17
• Models were trained for 30 epochs with batch size 400 and Nesterov momentum 0.9, with the learning rate reduced tenfold every 10 epochs.The learning rate began at 0.05.Source: §C.1 · p. 17

C.2 Supplementary Materials for the ImageNet Experiment

• For ImageNet, ResNet-50 serves as the base classifier using Cohen et al. [6]’s pipeline, but with a different randomization distribution; images are then normalized using dataset means (0.485, 0.456, 0.406) and standard deviations (0.229, 0.224, 0.225).Parameters are optimized by SGD with momentum 0.9; the learning rate starts at 0.1 and is reduced by a factor of 10 every 30 epochs.Source: §C.2 · p. 17
• Figure 5 shows ImageNet images corrupted by varying levels of the discrete noise.Source: Figure 5 · p. 18
• The evaluation compares discrete-noise models across α settings using ACC@r and evaluates every 100th validation image; Table 3 reports guaranteed accuracy across α.The discrete α values tested are 0.1, 0.2, 0.3, 0.4, and 0.5.Source: §C.2 · p. 18, Table 3 · p. 18

C.3 Supplementary Materials for the Chemical Property Prediction Experiment

• The dataset has 1,513 molecules split 80%/10%/10% by Bemis-Murcko scaffold, with molecules in different splits assigned to different scaffolds.The authors report similar results with a random split.Source: §C.3 · p. 18
• Both decision-tree models use tuned depth limit 10; the randomly smoothed tree additionally uses tuned α = 0.8.The tested depth limits were 6–10 and the tested α values were 0.7–0.9.Source: §C.3 · p. 18

C.4 Computing Adversarial AUC

• The adversarial AUC procedure uses class-1 prediction scores, which decrease under perturbation for positive examples and increase for negative examples.Source: §C.4 · p. 18
• With at most k < n + m data points perturbed, the procedure aims to minimize AUC using a program solvable by mixed-integer programming.The text names Gurobi as an example solver.Source: §C.4 · p. 19
• The optimization uses binary variables to indicate perturbed positive and negative examples, and an indicator assigns 1, 0.5, or 0 according to score ordering.The indicator values correspond to x > x′, x = x′, and x < x′, respectively.Source: §C.4 · p. 19