A Certified Robustness Framework for Backdoor Poisoning Attacks using $f$-Divergences

A Certified Robustness Framework for Backdoor Poisoning Attacks using f -Divergences

arXiv:2610.34934v1 [cs.LG] 26 Oct 2026

Evan Rose Northeastern University rose.ev@northeastern.edu

Alina Oprea Northeastern University a.oprea@northeastern.edu

Abstract Machine learning systems trained on untrusted data are vulnerable to data and backdoor poisoning attacks, in which an adversary corrupts training and test samples to manipulate predictions at inference time. Randomized smoothing yields provable defenses against such attacks, but existing applications to train-time robustness are limited to specific threat models and smoothing mechanisms. We propose a general framework that allows expressing complex adversary constraints on the number of corrupted training examples, feature and label perturbation magnitudes, and test-time corruptions. Our framework randomizes inputs by combining data subsampling with feature, label and test-sample noising. We develop a composable certification procedure based on f -divergences that handles arbitrary combinations of threat models and noising strategies, and recovers several prior certification regimes exactly as special cases. We demonstrate our framework experimentally by certifying, for the first time, robustness under general ℓp -constrained poisoning adversaries under bagging with additive Laplace, Gaussian, and Uniform noises.

1

Introduction

Despite their continued adoption in wide-reaching domains, machine learning systems remain susceptible to adversarial attacks that subvert their reliability and can cause harmful outcomes. These attacks span a broad class of threat models, including both training- and inference-phase attacks. Of particular concern are data and backdoor poisoning attacks, in which an adversary corrupts a portion of the training data to degrade or control model behavior [Gu et al., 2019, Shafahi et al., 2018, Saha et al., 2020, Aghakhani et al., 2021, Geiping et al., 2021, Souri et al., 2022]. To defend against such attacks, certified defenses have been proposed that provide provable guarantees on the consistency of a classifier’s output around an input. The most popular of these techniques, randomized smoothing, works by lifting the classifier into a function over a noised version of the input and defining a new classifier by taking the expectation [Lecuyer et al., 2019, Cohen et al., 2019]. The intuitive reason randomized smoothing works is that averaging a function over a noised input induces a uniform continuity property whose stability depends primarily on the consistency of the function around the input, rather than on the continuity properties of the base function. This principle applies whether the input and noise are simple (e.g., classification under Gaussian noise) or complex (e.g., an entire randomized dataset). In the case of data poisoning or backdoor attacks, several natural noising strategies exist, including data subsampling, feature noising, and label flipping. However, as the noising procedures become more complex, analyzing the certified guarantees becomes increasingly difficult. As a result, existing certified defenses for data poisoning attacks remain limited to smoothing strategies such as simple bagging or discrete label flipping [Jia et al., 2021, Chen et al., 2022, Zhang et al., 2022]. In this work, we ask, can we develop a highly general randomized smoothing framework for data poisoning and backdoor adversaries that easily handles complex threat models and smoothing strategies? Our insight is to leverage the convex-optimization view of randomized smoothing first introduced by Dvijotham et al. [2020], in which the admissible perturbation set is replaced by a convex outer approximation defined by f -divergence constraints. The certification condition relies on the smoothing mechanism and threat model only through a set of divergence constraints corresponding to a certain dual problem with nice composition properties. We argue this is the “right” perspective for composite mechanisms such as those arising in the backdoor poisoning setting. Contributions We present a randomized smoothing framework for backdoor and data poisoning attacks that incorporates rich attacker threat models, a multi-step randomization scheme, and efficient certification via convex relaxation 1

using f -divergences. Our framework makes it straightforward to describe complex threat models spanning feature, label, and test instance corruptions, to describe noising strategies that defend against them, and to derive sound robustness certificates under the resulting schemes. We explain how our framework recovers the tight certificates of several prior works as special cases. We use our framework to study certifiably robust classification under backdoor and data poisoning attacks in a wide range of settings not considered in prior works.

2

Background and related work

A growing body of work studies how to obtain certifiable robustness guarantees against data poisoning and backdoor attacks. Appendix C gives a more detailed treatment of selected works. Randomized smoothing In response to the weaknesses of empirical defenses [Athalye et al., 2018], randomized smoothing emerged as a technique to obtain provable robustness to adversarial examples [Lecuyer et al., 2019, Cohen et al., 2019, Li et al., 2019, Salman et al., 2019]. Early work established the standard certificate analysis methodology via the Neyman–Pearson Lemma [Neyman & Pearson, 1933] and the use of confidence-corrected estimates of the smoothed prediction. Other characterizations have also been explored, including functional optimization over f -divergence constraints [Dvijotham et al., 2020] and a nonlinear Lipschitz condition [Salman et al., 2019]. Learner-specific defenses Some works derive robustness certificates for specific learning algorithms. Early work studied duality-based upper bounds on the total test error [Steinhardt et al., 2017]. Rosenfeld et al. [2020] derive an efficient certified inference algorithm under label flipping attacks for classifiers trained using linear regression and label flipping noise. Drews et al. [2020] train certifiably robust decision trees with abstract interpretation. Jia et al. [2022] derive efficient certified guarantees for nearest neighbor classifiers under label flipping attacks. Sabanayagam et al. [2025] and Gosch et al. [2026] certify graph neural networks and SVMs against data poisoning, backdoor, and label flipping attacks using the neural tangent kernel and linear programming. Sosnin et al. [2025] extend abstract interpretation to gradient-based training to certify gradient-based learners. Differential privacy for robustness Another line of work obtains robustness from differentially private (DP) learners. Ma et al. [2019] certify global accuracy using the stability of expectation under a differentially private algorithm, and Xie et al. [2023] study a similar property in federated learning. Liu et al. [2023] extend the results of Ma et al. [2019] to instance-wise poisoning by improving the group privacy analysis of the subsampled Gaussian mechanism. Saxena et al. [2026] connect the standard hypothesis testing framework for certification to the theory of DP privacy profiles, enabling efficient analysis of composed mechanisms such as DP-SGD. Voting-based poisoning defenses The most popular strategy for provable robustness to poisoning is to train an ensemble of learners over different partitions or randomized samples and to use robustness properties of the majority vote. One line of work considers deterministic partitioning strategies [Levine & Feizi, 2021, Wang et al., 2022, Rezaei et al., 2023, Hammoudeh & Lowd, 2024]. Another line of work considers Randomized Smoothing by training ensembles on randomized samples of training data [Weber et al., 2023, Jia et al., 2021, Chen et al., 2022, Zhang et al., 2022].

3

Problem statement and preliminaries

3.1

Learning setup

We consider classification tasks with input space X ⊆ Rd and label space Y = [C], and write Z := X × Y for the labeled input space and S := Z ∗ for the space of training sets. We absorb training and inference into a single f for some ambient space W. f 1 A base procedure: define the joint input space W := S × X and suppose W ⊆ W f predictor G : W → P(Y) maps a joint input w = (S, xte ) to a distribution over labels. Concretely, G composes a learning algorithm A with evaluation at a test point, G(w) = G(S, xte ) = A(S)(xte ). The induced hard predictor 1We introduce W f because the randomization we introduce later means the base learner must process datasets from a slightly different space than

W.

2

is g(w) := arg maxy∈Y G(w)y , with a fixed tie-breaking rule. A can be randomized, in which case G denotes the expectation over A’s internal randomness (and thus G is a deterministic function of w).

3.2

Threat model

We consider a replacement adversary who jointly corrupts the training set and test sample. For joint input w = (S, xte ) with S = ((xi , yi ))ni=1 , denote the corrupted input by w′ = (S ′ , x′te ), where S ′ = ((x′i , yi′ ))ni=1 . In particular, the adversary may corrupt training features xi 7→ x′i , training labels yi 7→ yi′ , and the test sample xte 7→ x′te , but may not insert or delete training examples. We model corruption constraints along four axes. The first axis constrains the number of corrupted examples in the training set. The remaining axes constrain per-example feature or label corruptions in terms of a feature-space distance function dX or a label space distance function dY . The adversary’s capability is thus parameterized by the pair (dX , dY ) together with a threat vector ρ = (mp , εf , εl , εte ). Define I(w, w′ ) := {i ∈ [n] : (xi , yi ) ̸= (x′i , yi′ )}. The threat vector fixes the constraints (1) |I| ≤ mp , (2) maxi∈I dX (xi , x′i ) ≤ εf , (3) maxi∈I dY (yi , yi′ ) ≤ εl , (4) dX (xte , x′te ) ≤ εte . These constraints determine the perturbation set Bρ (w) := {w′ ∈ W : constraints (1)–(4) hold}. Decoupling the budget into four independent axes allows us to recover the threat models of several prior works as special cases [Rosenfeld et al., 2020, Jia et al., 2021, Zhang et al., 2022], as well as to generalize to several previously unconsidered threat models (e.g., mp < ∞ with dX = ∥·∥p for p ̸= 0). Usually we will take dY discrete and dX ≡ ∥·∥p for some 0 ≤ p ≤ ∞.

3.3

Certified robustness

We seek to provably defend against attacks within our threat model under the following definition. Definition 3.1 (ρ-Robustness). Let g : W → Y be a deterministic hard predictor. We say that g is ρ-robust at w ∈ W if g(w) = g(w′ ) for all w′ ∈ Bρ (w). Existing certified poisoning defenses typically report robustness as a scalar radius specifying the tolerable corruption magnitude along a single axis (e.g., mp or εf ) [Rosenfeld et al., 2020, Levine & Feizi, 2021, Zhang et al., 2022]. Instead, we are interested in characterizing the full certified region directly. For fixed g, define the robustness region R(w) := {ρ : g is ρ-robust at w}. Defining the robustness region R encodes the idea that varying one threat parameter (e.g., εte ) can affect robustness against other parameters (e.g., εf ), and we study the entire object holistically.

4

Methodology

Our goal is to develop a general defense for training classifiers that handles the threat models from Section 3 and admits an efficient certification procedure proving robustness.

4.1

Robust learning procedure

Robust training via randomized smoothing We design a certifiably robust training procedure following the methods of Randomized Smoothing [Lecuyer et al., 2019, Li et al., 2019, Cohen et al., 2019], initially introduced for certified robustness against evasion attacks. The main idea behind randomized smoothing is to transform a pre-existing base learner (in our case, the joint training-inference procedure G) into a provably robust smoothed classifier GM . The f to the inputs smoothed classifier GM is obtained by applying a randomized smoothing mechanism M : W → P(W) and lifting the base classifier G to a classifier on the space of distributions over the joint input space according to the aggregation rule: GM (w) := Ew∼M(w) [G(w)]. e GM is a deterministic soft classifier whose associated hard classifier e is gM (w) = arg maxy GM (w)y . Randomized mechanism The smoothing mechanism M should be chosen in a way to “wipe away” any influence the corruptions might have on the prediction. We design a multi-step randomization procedure that consists of a data subsampling phase followed by a feature and label noising phase. The resulting probability measure takes the form of a mixture distribution whose components correspond to the samples retained during the subsampling phase.

3

Each component of the mixture follows structurally identical randomization behavior, but is instantiated with different parameters. For a training set S = ((xi , yi ))ni=1 and sample-index sequence U = (u1 , . . . , uk ) ∈ [n]k , define SU := ((xui , yui ))ki=1 . Let Π ∈ P([n]∗ ) be a subsampling distribution over retained sample indices U , ϕX (·) a feature noise mechanism (e.g., ϕ(x) = N (x, σ 2 I)), and ϕY (·) a label noise mechanism (e.g., ϕ(y) = (1 − γ)δy + γ Unif([C])). Our smoothing mechanism M := MΠ,ϕX ,ϕY is generated by the following procedure. (1) Draw retained indices U ∼ Π. (2) Apply per-example noise to features and labels: For each i ∈ [|U |], independently sample x ei ∼ ϕX (· | xui ) and |U | e x yei ∼ ϕY (· | yui ). Construct Se := ((e xi , yei ))i=1 . (3) Sample x ete ∼ ϕX (· | xte ). 2 (4) Output (S, ete ). We make a few observations on the distributions resulting from the smoothing mechanism M. By construction, sampling from M is efficient. M can be written as a mixture distribution whose components are product measures parameterized by a subsample of S. M has |supp Π| components, which is generally quite large (e.g., nk for bagging with replacement). This makes evaluating the density (or mass) at a point a priori intractable. For a large number of norm-based smoothing mechanisms (e.g., Gaussian), the product to a well-understood Qnmeasure induced by ϕX reduces measure over the full dataset space identified with Rnd (e.g., i=1 N (0d , σ 2 Id ) ∼ = N (0nd , σ 2 Ind )). Concrete instantiations We motivate our smoothing scheme with a few concrete instantiations. Natural choices of Π are bagging (with or without replacement) or Poisson subsampling. Natural choices for ϕX include Gaussian, Laplace, Uniform, or discrete noise, but we can also accommodate more exotic noises such as the norm-based noises of Yang et al. [2020]. Most often ϕY will be a flipping distribution ϕ(y) = ϕflip γ,K (y) = (1 − γ)δy + γUnif([K]) for some alphabet size K, but we can also accommodate structured noises ϕY (y) = Myey for a Markovian transition matrix M . The smoothing mechanisms of several prior works can be recovered for suitable choices of Π, ϕX , ϕY . RAB [Weber et al., 2023] takes Π as a point mass on the original dataset (no subsampling) and sets ϕ(x) = N (x, σ 2 Id ). Jia et al. [2021] take Π as bagging with replacement with no feature or label noise. BagFlip [Zhang et al., 2022] considers Nd flip bagging with replacement and coupled feature-label noise ϕX (x) = j=1 ϕflip γ,K (xj ) and ϕY (y) = ϕγ,K (y), where notably the feature and label alphabets are the same size and use the same flipping probability.

4.2

Certifying predictions: overview

Core challenges The main technical challenge we face is how to certify robustness for such a large class of general smoothing methods against the adversaries defined in Section 3.2. Prior works applying randomized smoothing to data poisoning or backdoor attacks [Weber et al., 2023, Jia et al., 2021, Zhang et al., 2022] apply techniques introduced by Cohen et al. [2019], who frame certification as a hypothesis testing problem and construct Neyman–Pearson tests to derive tight certificates. Unfortunately, this path is only accessible for simple smoothing schemes and threat models, and does not scale to our setting: the likelihood ratio structure of M is complicated due to its combinatorial mixture structure and is typically only directly tractable for simple distributions such as the discrete noises of Zhang et al. [2022]. Furthermore, changing the mechanisms Π, ϕX , ϕY or the threat model dX , dY , ρ a priori requires a laborious new derivation of the certification condition by hand. What we desire instead is a generic way to automatically construct the certification conditions given the threat model dX , dY , ρ and the smoothing mechanism Π, ϕX , ϕY . All relevant information can be derived for each component independently, and different combinations can be composed automatically with basic computational rules. It turns out that such a procedure is possible if we turn to a certain dual formulation of Randomized Smoothing, first considered by Dvijotham et al. [2020] for the evasion setting in the language of f -divergences. We start by introducing some preliminaries.

4.3

Certification via convex optimization

Define a specification as a bounded measurable ψ : Ω → R, and call it robustly certified at ν ∈ P(Ω) w.r.t. D ⊆ P(Ω) if Eν ′ [ψ] ≥ 0 for every ν ′ ∈ D (Definition A.1). For convex f with f (1) = 0 (a generator), the induced f ′ := Eν [f (dν ′ /dν)] (Definition B.1). Given generators f1 , . . . , fm with bounds τi ≥ 0, define divergence T is′ Df (ν ∥ν) ′ := DF i {ν : Dfi (ν ∥ν) ≤ τi } (Definition A.2). We use the following result of Dvijotham et al. [2020], stated in full in Theorem A.2. Let θa , θb denote lower and upper bounds on the majority and runner-up predicted probabilities from GM (w), respectively, and write θ = 2We couple train and test noise mechanisms for simplicity; decoupling them is conceptually straightforward.

4

(θa , θb , 1 − θa − θb ). Then, every specification consistent with θa , θb is robustly certified w.r.t. DF iff the solution to the following problem is non-negative: inf ζa − ζb

ζ∈R3+

s.t.

ζa + ζb + ζc = 1,

Dfi (ζ∥θ) ≤ τi , i = 1, . . . , m.

(1)

Robustness certification in the sense of Definition A.1 is related to our own robustness notion (Definition 3.1). Writing c := gM (w) and taking specifications ψc,c′ (w) e := G(w) e c − G(w) e c′ , c ∈ arg maxy GM (w′ )y for all w′ ∈ Bρ (w) iff ′ every ψc,c′ with c ̸= c is robustly certified at M(w) w.r.t. Dw,ρ := {M(w′ ) : w′ ∈ Bρ (w)}. We state and prove the formal statement in Theorem D.1. In working with Equation (1), it suffices to choose any τi ≥ Dfi (ν ′ ∥M(w)) for every ν ′ ∈ Dw,ρ , with the tightest choice being τf⋆ (w, ρ) := sup Df (M(w′ )∥M(w)). (2) w′ ∈Bρ (w)

One can use any f -divergence for which an upper bound on Equation (2) is available. The most interesting cases are the hockey-stick divergences, due to their characterization of tight certificates (Theorem A.3), and the Rényi divergences, due to their nice tensorization properties (Lemma B.6).

4.4

Computing divergence bounds

Under Theorems A.2 and D.1, the problem of certifying robustness for GM at w ∈ W reduces to establishing a bound τf (w, ρ) ≥ τf⋆ (w, ρ) for suitable f . The technical challenge is grappling with the complex structure of M: subsampling through Π induces a mixture with combinatorially many components, and noising through ϕ makes each component a product measure. Our analysis proceeds in two steps: first, we reduce the combinatorial structure of the mixture distribution to a lower-dimensional problem, and second, we analyze divergences between paired product components. Bounding divergences for mixtures The first key observation for bounding divergences is that the components of any M(w′ ) and M(w) share mixing weights when paired by subsample, which interact nicely with Df (M(w′ )∥M(w)). Moreover, despite a combinatorial number of components, the components can often be grouped together, which gives us the following bound: PN PN Theorem 4.1 (Reorganized Joint Convexity Bound). Let µ = i=1 θi µi and ν = i=1 θi νi be mixtures with shared Fk mixing weights θi . Suppose there is a partition of indices [N ] = i=1 Si and a sequence of nonnegative real numbers Pk (δi )ki=1 such P that for all i ∈ [k] and all j ∈ Si , Df (µj ∥νj ) ≤ δi . Then one has Df (µ∥ν) ≤ τf for τf := i=1 βi δi , where βi := j∈Si θj . We prove Theorem 4.1 in Appendix D, along with an analogue for Rényi divergences (Corollary D.1). Theorem 4.1 does not depend on the specific geometry of the feature or label noise and only uses pairing of components and joint convexity of Df . The grouping of components is important computationally, as it reduces the sum to a tractable number of terms. For our noises, the component bound depends on U only through the number s(U ) of corrupted indices. Grouping by s leaves only a few terms, e.g., k + 1 for bagging and min(k, mp ) + 1 for bagging without replacement. This trick can be viewed as an extension to f -divergences of earlier techniques that partition the output space into regions of constant likelihood ratio [Lee et al., 2019, Bojchevski et al., 2020, Zhang et al., 2022].

4.5

Bounding component divergences

It remains to find the bounds δj . Consider a fixed corruption w′ of w, and apply Theorem 4.1. Writing zU := ′ ′ (SU , xte ) for an un-noised subsampled input, we obtain the component pairs (ϕ(zU ), ϕ(zU )) with zU determined ′ ′ by w . A small complication is that the zU are coupled through w , so we relax the problem slightly and take δj ≥ supz′ Df (ϕ(z ′ )∥ϕ(z)) over all corruptions z ′ of z that are feasible given group j (for example, a component might correspond to U with s corrupted examples). This is tight when some w′ attains every component supremum simultaneously.

5

Adjacency parameters The supremum supz′ Df (ϕ(z ′ )∥ϕ(z)) is natively over a high-dimensional space. However, for sufficiently symmetrical noises, the divergence between (x, x′ ) depends only on a low-dimensional adjacency parameter θ(x, x′ ), in the sense that every f -divergence can be written in the form Df (ϕ(x′ )∥ϕ(x)) = δf (θ(x, x′ )) for some δf depending on f . One way to see this is by the invariance of f -divergences under bimeasurable bijections (Lemma B.3). As a concrete example, for Gaussian noise any f -divergence depends only on the ℓ2 separation r = ∥x − x′ ∥2 /σ. Table 1: Divergence bounds derived in Appendix G. Here θ is the adjacency parameter of Definition G.1 and ∆ := x−x′ . Notation p+ , p0 , p− , κα (t), dβ , and Pd are defined in Appendix G. Noise Unif(γ)

Adjacency θ 1−

Q

|∆i |
i 1 − 2γ +

N (·, σ 2 I) r = ∥∆∥2 /σ Lap(·, b)

t = |∆|/b

ϕflip γ,C

s = ∥∆∥0

DR,α (µ∥ν)

DHS,β (µ∥ν)

1 α−1 log(1 − θ) 2

min(1, β) θ

Φ r2 − logr β − βΦ − r2 − logr β − (1 − β)+   √ −t/2 (1 − βe )+ − (1 − β)+ +
P
1−α α α 1−α −d s log p p + p p + p 1 − β(p Pd 0 + /p− ) + − − d≥d + α−1

αr /2 P j κα (tj )

β

Worst-case pairs A priori, Equation (2) admits a different maximizer for each f . In most cases, this is fortunately not the case. Write (µ′ , ν ′ ) ⪯ (µ, ν) when Df (µ′ ∥ν ′ ) ≤ Df (µ∥ν) for every generator f . We show that ⪯ is entirely determined by the Hockey-stick envelope (Lemma G.1): (µ′ , ν ′ ) ⪯ (µ, ν) iff DHS,β (µ′ ∥ν ′ ) ≤ DHS,β (µ∥ν) for all β > 0. In such cases, a single (µ⋆ , ν ⋆ ) generates every τf⋆ simultaneously. This property also composes nicely under product measures (Lemma G.2), which is useful for combining feature and label flipping. We show that such a pair exists for Gaussian and Uniform noise under all ℓp norms, for flipping noise under ℓ0 , and for Laplace noise under ℓ1 and ℓ∞ norms. For 1 < p < ∞ For Laplace noise under ℓ2 , the behavior is more complicated, requiring special treatment (Appendix G.4). Worst-case pairs, when they exist, reduce divergence bound computation to optimizing the adjacency parameter. For Gaussian noise this corresponds to maximizing the ℓ2 perturbation, which is easy. For Uniform noise the problem is nontrivial, and we must resort to a loose relaxation (Appendix G.3). Composition under products Our framework involves applying independent noise (between features and labels within an example, and independence between examples), which requires us to understand f -divergences between product measures. Rényi divergences are attractive here due to their nice tensorization properties (Lemma B.6) and can be computed immediately from components. We show in Lemma G.3 how to compute Hockey-stick divergences e HS,β (µ∥ν) = Eµ [D e HS,β/Λ (µ2 ∥ν2 )]. This is especially DHS,β (µ1 ⊗ µ2 ∥ν1 ⊗ ν2 ) in closed form via the formula D 1 1 useful for modeling dirty-label adversaries, where the corresponding noise ϕ can be written as a product of a label 2 flipping measure µ1 = ϕflip γ,C and a continuous noise µ2 (e.g., N (x, σ I)). Numerical computation Gaussian, flipping, and Uniform noise have hockey-stick profiles computable in closed-form once their worst-case adjacency parameter is known. For Laplace noise the profile involves repeated self-convolution of the log likelihood ratio distribution (which has no nice closed form), so we compute it with numerical integration techniques. Worked example Consider X = Rd , Y = [C], and S =P((xi , yi ))ni=1 . Let Π be bagging with replacement of k samples, and let ϕX (x) = N (x, σ 2 Id ), so that M(S) = U ∈[n]k n−k N (SU , σ 2 Idk ) has nk components. Under √ an ℓ2 adversary, a component with s corrupted samples has adjacency parameter r = ∥SU − SU′ ∥2 /σ ≤ εf s/σ, which is attained at maximal corruption magnitude. Since s ∼ Binom(k, mp /n) under Π, Theorem 4.1 gives Pk √ τf = s=0 Binom(s; k, mp /n)δf (εf s/σ), where δf depends on f (e.g., δTV (r)p= 2Φ(r/2) − 1; see Table 1). If we also model a backdoor trigger, we can replace ε2f s by ε2f s + ε2te to give δf ( ε2f s + ε2te /σ) in the sum. For label-flipping adversaries and randomized labels, we can use Lemma G.3 to compute δβ as a weighted sum of Gaussian hockey-stick values at thresholds β(p+ /p− )−d (Theorem G.5).

6

5

Evaluation

We present several applications of our framework to data poisoning and backdoor poisoning attacks. Our experiments focus on image classification on the MNIST [Lecun et al., 1998] and CIFAR10 [Krizhevsky, 2009] datasets, in addition to the class-subsampled variants MNIST-17 and CIFAR10-02 [Zhang et al., 2022, Weber et al., 2023]. We train ensembles of size N = 10, 000 and N = 1, 000 for MNIST and CIFAR10, respectively. We use confidence level α = 0.001.

ℓp feature adversaries

5.1

0.8 0.6 0.4 0.2 0.0

1.0 gaussian laplace uniform bagging only RAB

0.8 0.6 0.4 0.2 0.0

0.0

0.5

1.0

1.5

2.0

certified accuracy

1.0 gaussian laplace uniform bagging only RAB

certified accuracy

certified accuracy

1.0

gaussian laplace uniform bagging only RAB

0.8 0.6 0.4 0.2 0.0

0.0

0.5

1.0

1.5

2.0

poisoning amount R (%)

poisoning amount R (%)

(a) ℓ1 adversary, εf = 1.

(b) ℓ2 adversary, εf = 1.

0.0

0.5

1.0

1.5

2.0

poisoning amount R (%) (c) ℓ∞ adversary, εf = 1/28.

Figure 1: Certified accuracies on MNIST for clean-label triggerless attacks under different ℓp adversaries. The budget in each case is calibrated to correspond to the same ℓ2 budget, which has the effect that Gaussian noise certifies the same radius across all curves.

Setup We consider a setting in which the attacker corrupts at most mp training examples, each by at most ∥x − x′ ∥p ≤ εf . The test sample and labels are not corrupted. We instantiate Π as bagging and compare Gaussian, Laplace, and Uniform feature noise. We also evaluate pure bagging [Jia et al., 2021] and Gaussian noise without subsampling [Weber et al., 2023] as baselines. No prior method makes effective use of both the mp and εf constraints. For example, Jia et al. [2021] only subsample and pessimistically assume that a single retained poison compromises the learner, while Weber et al. [2023] do not subsample data. Zhang et al. [2022] use discrete noise that only works under an ℓ0 constraint, and cannot certify more than bagging in ℓp : while ℓp constraints can be converted into (looser) ℓq constraints for p, q > 0, they cannot convert into nontrivial ℓ0 constraints. For p > 0, we compare with the certificate obtainable from the RAB defense [Weber et al., 2023], which adds Gaussian noise to the entire training set without bagging. RAB’s certificate can be used in our threat model by computing the maximum admissible ℓ2 perturbation under our threat model. In particular, an ℓp bound can be converted into an ℓ2 √ (∞) (2) (1) (2) bound by taking εf ≤ εf or εf ≤ dεf , respectively, and with mp poisoned examples we obtain the full dataset √ (2) ℓ2 bound mp εf . Findings We make several observations on the clean-label poisoning robustness reported in Figure 1. First, pure bagging always attains a higher non-robust certified accuracy, which makes sense since adding noise to data should only reduce classifier accuracy. Second, uniform noise is competitive only for ℓ1 and for moderate poisoning amounts (< 1.2%). This finding corroborates Yang et al. [2020], who find in the evasion setting that Gaussian noise yields the largest certified accuracies for ℓ2 and ℓ∞ , whereas Uniform noise works best for ℓ1 . Laplace noise is only competitive for ℓ1 adversaries at high poisoning rates, where it marginally beats Gaussian noise for R ≥ 1.5. We show the dependence on εf for MNIST, MNIST-17, CIFAR10, and CIFAR10-02 in Figure 2 when training under Gaussian noise. In this case, the advantage of constraining εf deteriorates quickly: on MNIST, the certified radius is substantially larger for εf = 1, but by εf = 2 the certificate nearly matches that at εf = ∞ (corresponding to the bagging certificate of Jia et al. [2021]).

7

5.2

Label flipping and backdoor adversaries

Setup We study the impact of different threat models on certifiable robustness. We consider two main attacker settings: joint feature-label attacks and joint train-test (backdoor) attacks. In both settings, the adversary can corrupt at most mp training examples and, for each corrupted sample, modify features up to εf distance in ℓ2 . In feature-label attacks, the adversary can additionally corrupt the label. In backdoor attacks, the adversary also corrupts the test sample with test budget εte = εf . Findings We report the robustness tradeoffs for different datasets. The label-flipping adversary is reported in Table 2, and the backdoor adversary is reported in Table 3. Our method significantly outperforms RAB under backdoor adversaries. On MNIST-17, while RAB reaches trivial certified accuracy after R = 0.5%, our method retains over 45% certified accuracy at R = 2%. The improvement is due to bagging: with high probability, we retain only a small number O(k · mp /n) of poisoned samples, whereas RAB √ retains all poisoned samples. For RAB to certify comparable poisoned radii, it would need to train with σ = O(εf mp ), p which would destroy predictive performance, whereas for our method σ = O(εf mp k/n) still yields large certificates. Table 2: Robustness tradeoff for joint feature & label adversaries at poisoned fractions R, with εl = 1 and ℓ2 budget εf = 1 (MNIST, MNIST-17) or 0.5 (CIFAR10, CIFAR10-02). Bag sizes k and noise scales σa < σb are fixed per dataset (Table 7). Label noise retains the true label with p = 0.9. MNIST R (%) Bagging

MNIST-17

0 0.5 1 1.5 0 1 82.3 56.8 31.9 12.0 99.1 98.0

Ours, σa 81.2 50.0 23.5 Ours, σb 78.7 44.8 17.9

5.1 3.7

CIFAR10

2.5 0.0

CIFAR10-02

3.5 0 0.05 0.1 0.15 0 0.8 1.6 2.4 0.0 32.5 14.7 5.3 1.1 78.3 64.4 40.2 2.4

98.7 96.6 48.6 0.0 22.3 98.8 93.0 35.3 5.3 16.7

9.8 6.4

3.3 1.7

0.6 0.1

66.9 48.5 26.6 0.6 64.2 45.4 27.5 3.4

Table 3: Robustness tradeoff for clean label backdoor adversaries on MNIST, MNIST-17, CIFAR10, and CIFAR10-02 at different poisoned fractions R. The ℓ2 constraint is εf = εte = 1 on MNIST and MNIST-17 and εf = εte = 0.5 on CIFAR10 and CIFAR10-02. σa , σb are as in Table 7. RAB trains on the full training set. MNIST

Ours, σa Ours, σb

0.1 0.0 0.0

MNIST-17 1 0 0.0 95.9 0.0 94.7

0.5 0.0 0.0

1 0.0 0.0

CIFAR10 2 0.0 0.0

48.6 42.2 20.5 5.0 92.9 88.0 76.6 41.8 41.9 36.6 17.8 6.2 91.3 86.1 76.1 45.4

0.6 0.4 0.2 0.0

0.8 0.6 0.4

"f = 1 "f = 2 "f = 4 "f = 1

0.2 0.0

0.0

0.5

1.0

1.5

2.0

poisoning amount R (%)

(a) MNIST

CIFAR10-02

0 0.02 0.06 0.1 0 18.4 0.0 0.0 0.0 63.5 19.3 0.0 0.0 0.0 67.5 6.8 8.7

5.6 7.9

3.8 6.5

0.2 0.0 0.0

0.0

0.5

1.0

1.5

2.0

poisoning amount R (%)

0.6 0.4 0.2

"f = 0:5 "f = 1 "f = 2 "f = 4 "f = 1

0.8 0.6 0.4 0.2 0.0

0.06

0.12

0.18

poisoning amount R (%)

(b) MNIST-17

0.6 0.0 0.0

1.0 "f = 0:5 "f = 1 "f = 2 "f = 4 "f = 1

0.8

0.0 0.00

0.4 0.0 0.0

2.5 40.9 34.4 27.5 20.2 5.3 54.0 51.4 48.7 45.8

1.0

certified accuracy

1.0 "f = 1 "f = 2 "f = 4 "f = 1

0.8

certified accuracy

1.0

certified accuracy

0.5 0.0 0.0

certified accuracy

R (%) 0 RAB, σa 74.1 RAB, σb 66.5

(c) CIFAR10

0.24

0.0

0.3

0.6

0.9

1.2

poisoning amount R (%)

(d) CIFAR10-02

Figure 2: Certified accuracy versus poisoning fraction R at each per-example budget εf , under an ℓ2 adversary with Gaussian feature noise. σ = 0.5 for MNIST and σ = 0.35 for CIFAR10.

When is more noise useful? Aggressive noise erases corruptions, which corresponds to larger certified radii via smaller divergence bounds, but also degrades the base learner, lowering the vote confidence. In general, two training8

data noising strategies exist: either we use aggressive plain bagging (hoping to throw away bad examples), or we try to recover performance from retained bad examples by adding additional noise to them. It is therefore important to understand how different noises affect the resulting certificates. As a simple example, consider ℓ2 corruptions with Gaussian noise. To keep the component divergences small, the noise level σ must grow with the adversary budget εf . If σ becomes large, the input becomes impossible to classify, and the base learner accuracy will drop dramatically. In this regime, it is preferable to use no feature noising at all and rely on pure bagging to provide certificates. Label noising is especially delicate (Table 2): we only observe improvements over the plain bagging method for binary classification datasets MNIST-17 and CIFAR10-02. This is intuitive: whereas features can be noised individually while still preserving high information content taken over the full input, the label serves as the only supervision signal for the learning task, so noising it is especially destructive. Still, label flipping can be effective for sufficiently easy tasks: on MNIST-17, we observe certified radius out to 3.5% of the training dataset achieved by aggressive feature and label noising compared with the plain bagging baseline.

5.3

Comparison with prior works

Certified radius (%)

Our method recovers the exact certificates of Zhang et al. [2022] under all threat models and smoothing strategies they consider (Appendix E.3, Figure 3), and those of Jia et al. [2021] for replacement adversaries (Appendix E.2). Another useful finding is that, by writing down the hockey stick divergences in 6 ours, s = 1 ours, s = 2 closed-form, we are able to implement certification for a fixed εf bound in a much 5 ours, s = 4 2 2 3 2 2 ours, s = 8 more efficient O(k εf ) compared with BagFlip’s O(d + k d ) preprocessing cost 4 BagFlip when εf ≪ d. Notably, we depend on d only through εf . Our formulation is also 3 amenable to parallelized precomputation across all desired εf , whereas the linear 2 recurrence of Zhang et al. [2022] is not. 1 Because BagFlip couples the feature space to the label space, it can only certify 0 0.6 0.8 0.9 0.99 0.999 dirty-label attacks when |X | = |Y| and when labels are flipped with the same distripredicted-class probability pA bution as features. This in particular means it cannot certify dirty-label attacks in the multi-class setting if the features are binary. Our framework, in contrast, handles both Figure 3: Tightness of our cerof these cases directly. We are able to compute certificates in a setting where the label tificate with BagFlip’s. noise differs from the feature flipping noise, or where the number of distinct feature values differs from the number of classes.

6

Conclusion

We provide a randomized smoothing framework for certified robustness against backdoor and data poisoning attacks. Our framework decomposes the threat model into independent axes bounding corruption magnitudes, and applies composite noise comprising data subsampling, feature noising, and label flipping. We reduce certification in this regime to a convex program over f -divergence constraints and show how to compute the corresponding constraint sets. Our constraint computation leverages reorganized joint convexity to efficiently handle the mixture structure induced by subsampling and uses general, composable principles to accommodate a wide range of smoothing measures. We demonstrate this generality by certifying, for the first time, ℓ1 , ℓ2 , and ℓ∞ adversaries on models trained with Gaussian, Laplace, Uniform, and discrete noise. Limitations and open questions Our method trains thousands of base learners for sound prediction estimation. We mitigate this cost with an efficient parallelized training implementation, but future methods might seek efficient closedform solutions such as those considered in prior work [Rosenfeld et al., 2020, Weber et al., 2023]. Our method does not exploit properties specific to the dataset or base learner. Future work should consider whether using such information can yield stronger certificates. An interesting remaining challenge is to precisely characterize the structural properties of optimal noising schemes for complex backdoor poisoning threat models. For example, we do not understand the tradeoff between subsampling and data noising very well. Finally, learner-based robustness properties (such as data-smoothness) might be leveraged to obtain even tighter certificates.

9

Acknowledgments This work was supported by NSF awards CNS-2312875 and CNS-2331081, the U.S. Army Combat Capabilities Development Command Army Research Laboratory (DEVCOM ARL) under Cooperative Agreement Number W911NF24-2-0115, and by a grant from Good Ventures Foundation.

References Hojjat Aghakhani, Dongyu Meng, Yu-Xiang Wang, Christopher Kruegel, and Giovanni Vigna. Bullseye polytope: A scalable clean-label poisoning attack with improved transferability. In 2021 IEEE European Symposium on Security and Privacy (EuroS&P), pp. 159–178, 2021. doi: 10.1109/EuroSP51992.2021.00021. Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 274–283. PMLR, July 2018. URL https://proceedings.mlr.press/v80/athalye18a.html. Borja Balle and Yu-Xiang Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 394–403. PMLR, July 2018. URL https://proceedings.mlr.press/v80/balle18a.html. Aleksandar Bojchevski, Johannes Gasteiger, and Stephan Günnemann. Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 1003–1013. PMLR, July 2020. URL https://proceedings.mlr.press/v119/b ojchevski20a.html. Ruoxin Chen, Zenan Li, Jie Li, Junchi Yan, and Chentao Wu. On collective robustness of bagging against data poisoning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 3299–3319. PMLR, July 2022. URL https://proceedings.mlr.press/v162/c hen22k.html. C. J. Clopper and Egon S. Pearson. The use of confidence or fiducial limits illustrated in the case of the binomial. Biometrika, 26(4):404–413, December 1934. ISSN 0006-3444. doi: 10.1093/biomet/26.4.404. URL https: //doi.org/10.1093/biomet/26.4.404. Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1310–1320. PMLR, June 2019. URL https://proceedings.mlr.press/v97/cohen19c.html. Imre Csiszár and Paul C. Shields. Information theory and statistics: A tutorial. Foundations and Trends in Communications and Information Theory, 1(4):417–528, November 2004. ISSN 1567-2190. doi: 10.1561/0100000004. URL https://doi.org/10.1561/0100000004. Samuel Drews, Aws Albarghouthi, and Loris D’Antoni. Proving data-poisoning robustness in decision trees. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2020, pp. 1083–1097, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450376136. doi: 10.1145/3385412.3385975. URL https://doi.org/10.1145/3385412.3385975. Krishnamurthy (Dj) Dvijotham, Jamie Hayes, Borja Balle, Zico Kolter, Chongli Qin, Andras Gyorgy, Kai Xiao, Sven Gowal, and Pushmeet Kohli. A framework for robustness certification of smoothed classifiers using f-divergences. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id= SJlKrkSFPH.

10

Jonas Geiping, Liam H Fowl, W. Ronny Huang, Wojciech Czaja, Gavin Taylor, Michael Moeller, and Tom Goldstein. Witches’ brew: Industrial scale data poisoning via gradient matching. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=01olnfLIbD. Lukas Gosch, Xichuan Chen, Yan Scholten, and Stephan Günnemann. Certifying graph neural networks against label and structure poisoning. In Forty-third International Conference on Machine Learning, 2026. URL https: //openreview.net/forum?id=kQuvO5gaNr. Tianyu Gu, Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg. Badnets: Evaluating backdooring attacks on deep neural networks. IEEE Access, 7:47230–47244, 2019. doi: 10.1109/ACCESS.2019.2909068. Zayd Hammoudeh and Daniel Lowd. Provable robustness against a union of ℓ0 adversarial attacks. Proceedings of the AAAI Conference on Artificial Intelligence, 38(19):21134–21142, March 2024. doi: 10.1609/aaai.v38i19.30106. URL https://ojs.aaai.org/index.php/AAAI/article/view/30106. Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong. Intrinsic certified robustness of bagging against data poisoning attacks. Proceedings of the AAAI Conference on Artificial Intelligence, 35(9):7961–7969, May 2021. doi: 10.1609/ aaai.v35i9.16971. URL https://ojs.aaai.org/index.php/AAAI/article/view/16971. Jinyuan Jia, Yupei Liu, Xiaoyu Cao, and Neil Zhenqiang Gong. Certified robustness of nearest neighbors against data poisoning and backdoor attacks. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9):9575–9583, June 2022. ISSN 2159-5399. doi: 10.1609/aaai.v36i9.21191. URL http://dx.doi.org/10.1609/aaai. v36i9.21191. Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009. Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998. doi: 10.1109/5.726791. Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geambasu, Daniel Hsu, and Suman Jana. Certified robustness to adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pp. 656–672, 2019. doi: 10.1109/SP.2019.00044. Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial robustness for randomly smoothed classifiers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper_files/paper/2019/file/fa2e8c4385712f9a1 d24c363a2cbe5b8-Paper.pdf. Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defenses against general poisoning attacks. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id= YUGG2tFuPM. Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.ne urips.cc/paper_files/paper/2019/file/335cd1b90bfa4ee70b39d08a4ae0cf2d-Paper .pdf. Friedrich Liese and Igor Vajda. On divergences and informations in statistics and information theory. IEEE Transactions on Information Theory, 52(10):4394–4412, 2006. doi: 10.1109/TIT.2006.881731. Shijie Liu, Andrew C. Cullen, Paul Montague, Sarah M. Erfani, and Benjamin I. P. Rubinstein. Enhancing the antidote: Improved pointwise certifications against poisoning attacks. Proceedings of the AAAI Conference on Artificial Intelligence, 37(7):8861–8869, June 2023. doi: 10.1609/aaai.v37i7.26065. URL https://ojs.aaai.org/i ndex.php/AAAI/article/view/26065.

11

Yuzhe Ma, Xiaojin Zhu, and Justin Hsu. Data poisoning against differentially-private learners: Attacks and defenses. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 4732–4738. International Joint Conferences on Artificial Intelligence Organization, July 2019. doi: 10.24963/ijcai.2019/657. URL https://doi.org/10.24963/ijcai.2019/657. Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263–275, 2017. doi: 10.1109/CSF.2017.11. Jerzy Neyman and Egon Sharpe Pearson. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London, Series A: Containing Papers of a Mathematical or Physical Character, 231(694-706):289–337, February 1933. ISSN 0264-3952. doi: 10.1098/rsta.1933.0009. URL https://doi.org/10.1098/rsta.1933.0009. Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge University Press, 2025. Keivan Rezaei, Kiarash Banihashem, Atoosa Chegini, and Soheil Feizi. Run-off election: Improved provable defense against data poisoning attacks. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 29030–29050. PMLR, July 2023. URL https: //proceedings.mlr.press/v202/rezaei23a.html. Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to label-flipping attacks via randomized smoothing. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8230–8241. PMLR, July 2020. URL https://proceedings.mlr.press/v119/rosenfeld20b.html. Mahalakshmi Sabanayagam, Lukas Gosch, Stephan Günnemann, and Debarghya Ghoshdastidar. Exact certification of (graph) neural networks against label poisoning. In Y. Yue, A. Garg, N. Peng, F. Sha, and R. Yu (eds.), International Conference on Learning Representations, volume 2025, pp. 25663–25691, 2025. URL https: //proceedings.iclr.cc/paper_files/paper/2025/file/401aa72e0e3be680348a5b0ffd b1a5aa-Paper-Conference.pdf. Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash. Hidden trigger backdoor attacks. Proceedings of the AAAI Conference on Artificial Intelligence, 34(07):11957–11965, April 2020. ISSN 2159-5399. doi: 10.1609/aaai.v34i07.6871. URL http://dx.doi.org/10.1609/aaai.v34i07.6871. Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang. Provably robust deep learning via adversarially trained smoothed classifiers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceedings.neurips.cc/paper_files/paper/201 9/file/3a24b25a7b092a252166a1641ae953e7-Paper.pdf. Aman Saxena, Jan Schuchardt, Yan Scholten, and Stephan Günnemann. Provable robustness against backdoor attacks via the primal-dual perspective on differential privacy, May 2026. URL https://arxiv.org/abs/2605.21780. Ali Shafahi, W. Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein. Poison frogs! targeted clean-label poisoning attacks on neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https://proceedings.neurips.cc/paper_files/paper/201 8/file/22722a343513ed45f14905eb07621686-Paper.pdf. Philip Sosnin, Mark Niklas Mueller, Maximilian Baader, Calvin Tsay, and Matthew Robert Wicker. Certified robustness to data poisoning in gradient-based training. Transactions on Machine Learning Research, 2025. ISSN 2835-8856. URL https://openreview.net/forum?id=9WHifn9ZVX. Hossein Souri, Liam Fowl, Rama Chellappa, Micah Goldblum, and Tom Goldstein. Sleeper agent: Scalable hidden trigger backdoors for neural networks trained from scratch. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 19165–19178. Curran

12

Associates, Inc., 2022. doi: 10.52202/068431-1393. URL https://proceedings.neurips.cc/paper_f iles/paper/2022/file/79eec295a3cd5785e18c61383e7c996b-Paper-Conference.pdf. Jacob Steinhardt, Pang Wei Koh, and Percy S Liang. Certified defenses for data poisoning attacks. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https://proceedings.neurips.cc /paper_files/paper/2017/file/9d7311ba459f9e45ed746755a32dcd11-Paper.pdf. Wenxiao Wang, Alexander J Levine, and Soheil Feizi. Improved certified defenses against data poisoning with (deterministic) finite aggregation. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 22769–22783. PMLR, July 2022. URL https://proceeding s.mlr.press/v162/wang22m.html. Stanley L. Warner. Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309):63–69, 1965. doi: 10.1080/01621459.1965.10480775. URL https://www.tandfonline.com/doi/abs/10.1080/01621459.1965.10480775. PMID: 12261830. Maurice Weber, Xiaojun Xu, Bojan Karlaš, Ce Zhang, and Bo Li. RAB: Provable robustness against backdoor attacks. In 2023 IEEE Symposium on Security and Privacy (SP), pp. 1311–1328, 2023. doi: 10.1109/SP46215.2023.10179451. Chulin Xie, Yunhui Long, Pin-Yu Chen, Qinbin Li, Sanmi Koyejo, and Bo Li. Unraveling the connections between privacy and certified robustness in federated learning against poisoning attacks. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, CCS ’23, pp. 1511–1525, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400700507. doi: 10.1145/3576915.3623193. URL https://doi.org/10.1145/3576915.3623193. Greg Yang, Tony Duan, J. Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 10693–10705. PMLR, July 2020. URL https://proceedings.mlr.press/v119/yang20c.html. Yuhao Zhang, Aws Albarghouthi, and Loris D' Antoni. BagFlip: A certified defense against data poisoning. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 31474–31483. Curran Associates, Inc., 2022. URL https://proceeding s.neurips.cc/paper_files/paper/2022/file/cc19e4ffde5540ac3fcda240e6d975cb-P aper-Conference.pdf. Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 4782–4817. PMLR, March 2022. URL https://proceedings.mlr.press/v151/zhu22c.html.

A

Extended Background on Randomized Smoothing

A.1

Tightness of Randomized Smoothing

Historically, several analytical approaches have been applied to derive sound robustness guarantees under randomized smoothing procedures. Originally, the differential privacy guarantees of mechanisms like adding Gaussian noise were used to derive sound but slack bounds on the certified radius [Lecuyer et al., 2019]. Other, tighter, but still slack bounds were derived by analyzing connection between Renyi divergence and certified robustness Li et al. [2019]. Cohen et al. [2019] were the first to derive provably optimal robustness certificates by analyzing the connection between robustness certification and hypothesis testing. Salman et al. [2019] derived the same tight certificate as a consequence of a nonlinear Lipschitz continuity property of Weierstrass transforms.

13

Dvijotham et al. [2020] extend the results of Li et al. [2019] to formulate general robustness certification as a convex optimization problem. This optimization problem involves bounding various statistical divergences between noised versions of the clean and corrupted algorithm inputs. The general formulation not tight under most choices of divergence. However, Dvijotham et al. [2020] demonstrate a connection with hockey-stick divergences which can recover optimal certificates in the general case. Moreover, hockey-stick divergences are connected to differential privacy (specifically, (ε, δ)-approximate differential privacy), thereby connecting privacy, convex optimization and hypothesis testing together as tools for randomized smoothing certification.

A.2

f -Divergences

In this section we present the certified robustness framework of Dvijotham et al. [2020], based on convex programming. Dvijotham et al. [2020] present three main results important for our work. The first result, Theorem A.1, characterizes robustness of a specification under f -divergence constraints in terms of a convex program. The second result, Theorem A.2, characterizes the robustness over a broader space of specifications, aligning with the more typical certified robustness setting. The third results, Theorem A.3, demonstrates that under the setting of Theorem A.2, the Hockey-stick divergences of all orders are sufficient to recover tight certificates in the original primal certification problem. Definition A.1 (Specification; robust certification). A specification is a bounded measurable function ψ : Ω → R. We say ψ is robustly certified at ν with respect to D if Ew∼ν ′ [ψ(w)] ≥ 0 for all ν ′ ∈ D. Definition A.2 (f -divergence constraint set). For convex f : R+ → R with f (1) = 0, the f -divergence from ν to ν ′ is Df (ν ′ ∥ν) := Eω∼ν [f (dν ′ (ω)/dν(ω))]. Given a collection F of functions f each defining an f -divergence, and to each f an associated bound τf ≥ 0, define the F-constraint set as T DF := f ∈F Df = {ν ′ ∈ P(Ω) : Df (ν ′ ∥ν) ≤ τf for all f ∈ F}. (3) Theorem A.1 (Dvijotham et al. [2020]). Let DF ,τ be as in Definition A.2. For λ = (λ1 , . . . , λM ) ∈ RM + , define PM fλ (u) := i=1 λi fi (u) and denote its convex conjugate by fλ∗ . A specification ψ is robustly certified at ν with respect to DF ,τ (in the sense of Definition A.1) if and only if the optimal value of the convex program sup λ∈RM + ,κ∈R

κ−

M X

λi τi − E [fλ∗ (κ − ψ(w))] w∼ν

i=1

(4)

is non-negative. Theorem A.2 (Dvijotham et al. [2020]). Let DF ,τ be as in Definition A.2, and let θa , θb ≥ 0 satisfy θa + θb ≤ 1. Define the specification class    Pr [ψ(w) = +1] ≥ θa  w∼ν G(θa , θb ) := ψ : W → {−1, 0, +1} . (5)  Pr [ψ(w) = −1] ≤ θb  w∼ν

Every ψ ∈ G(θa , θb ) is robustly certified at ν with respect to DF ,τ if and only if the optimal value of the convex program inf

ζa ,ζb ,ζc ≥0

s.t.

ζa − ζb (6)

ζa + ζb + ζc = 1, Dfi (ζ∥θ) ≤ τi ,

i = 1, . . . , M

is non-negative, where θ = (θa , θb , 1 − θa − θb ) and ζ = (ζa , ζb , ζc ) are interpreted as probability distributions. Theorem A.3 (Dvijotham et al. [2020]). Let θa , θb , µ, D, S be as in Definition A.1. Define τβ := supν∈D DHS,β (ν∥µ) for all β ≥ 0 and let βa⋆ , βb⋆ be defined as βa⋆ , βb⋆ = arg max βa ≥βb ≥0

1 − βa (1 − θa ) − βb θb − (τβa + [1 − βa ]+ ) − (τβb + [1 − βb ]+ ).

14

(7)

Define the constraint set ( DHS :=

ν ∈ P(X )

DHS,βa⋆ (ν∥µ) ≤ τβa⋆

)

DHS,βb⋆ (ν∥µ) ≤ τβb⋆

.

(8)

Then, S is information-limited robustly certified at µ with respect to D if and only if S is information-limited robustly certified at µ with respect to DHS . Thus, the optimal information-limited certificate in this case can be obtained by applying the information-limited certificate of Theorem A.2 to DHS . In our setting µ = M(w) and D = Dw,ρ , so the quantity in Theorem A.3 is the hockey-stick profile τβ⋆ :=

B

sup

DHS,β (M(w′ ) ∥ M(w)),

β ≥ 0.

(9)

w′ ∈Bρ (w)

Background on f -divergences

In this section we formally define f -divergences and state some useful facts for computing with them. We state here only the most essential results for understanding our derivations; a more complete treatment can be found in, e.g., Csiszár & Shields [2004], Liese & Vajda [2006] or Polyanskiy & Wu [2025, ch. 7]. Additionally, we state and prove a few additional useful lemmata. Definition B.1 (f -divergence). Let f : R+ → R be convex with f (1) = 0, and take by convention f (0) := lim f (x), x↓0

f ′ (∞) := lim xf (1/x), x↓0

0 · f ′ (∞) := 0.

Let µ, ν be two probability measures on a measurable space (Ω, A). If µ ≪ ν then the f -divergence from ν to µ is defined as h  i Df (µ∥ν) := Eν f dµ (10) dν where dµ dν is a Radon–Nikodym derivative. More generally, let λ be any common dominating measure. Then, writing dν := dλ p := dµ , we may define dλ and q   Z p(x) Df (µ∥ν) := q(x)f dλ + f ′ (∞)µ(q = 0). (11) q(x) q>0 Equation (11) does not depend on the choice of common dominating measure λ, and moreover when µ ≪ ν gives the same result as Equation (10). We call the function f the generator of the f -divergence Df . dν := dλ . Table 4: f -divergences and associated generators and integral form, with p := dµ dλ and q

f -Divergence

Regime

Total variation DTV (µ∥ν) Hockey-stick DHS,β (µ∥ν)

β≥0

Kullback–Leibler DKL (µ∥ν) Squared Hellinger DH2 (µ∥ν) Hellinger DH,α (µ∥ν)

α ∈ (0, 1) ∪ (1, ∞)

Generator f (u)

Integral form

1 |u − 1| 2

1 2

R

(u − β)+ − (1 − β)+

R

(p − βq)+ dλ − (1 − β)+

u log u 1 √ ( u − 1)2 2

p log pq dλ R√ 1− pq dλ R α 1−α 1 ( p q dλ − 1) α−1 R (p−q)2 dλ q R (p−q)2 dλ p

uα −1 α−1

Pearson Dχ2 (µ∥ν)

(u − 1)2

Neyman Dχ2 (µ∥ν)

(u−1)2 u

P

N

|p − q| dλ

R

Unnormalized hockey-stick divergences We write Z e HS,β (µ∥ν) := (p − βq)+ dλ = DHS,β (µ∥ν) + (1 − β)+ = sup µ(A) − β ν(A). D A

15

(12)

f -divergences from likelihood ratios

If we define the likelihood and log-likelihood ratios

Λ := p/q ∈ [0, ∞],

L := log Λ ∈ [−∞, +∞],

(13)

we can rewrite Equation (11) in the form Df (µ∥ν) = Eν [f (Λ)] + f ′ (∞)µ(Λ = 0).

(14)

α

−1 Rényi divergences and the Hellinger integral The generator fα (x) := xα−1 is convex for every α ∈ (0, 1) ∪ (1, ∞), and defines the Hellinger divergence of order α, DH,α (µ∥ν) := Dfα (µ∥ν). The Hellinger integral of order α is Z Zα (µ∥ν) := pα q 1−α dλ = 1 + (α − 1) DH,α (µ∥ν), (15)

with the convention that Zα = ∞ if α ≥ 1 and µ ̸≪ ν. The Rényi divergence of order α is related via the monotone transformation: 1 1 DR,α (µ∥ν) := log Zα (µ∥ν) = log (1 + (α − 1)DH,α (µ∥ν)) . (16) α−1 α−1 Note Zα is not, strictly speaking, an f -divergence, since x 7→ xα does not vanish at 1. Writing L := log dµ dν for the  (α−1)L  log-likelihood ratio, Zα (µ∥ν) = Eµ e , which is the moment generating function of Z under µ evaluated at α − 1. By taking limits, one may also define the Rényi divergences at orders α ∈ {0, 1, ∞}: DR,0 (µ∥ν) := − log ν({p > 0}), DR,1 (µ∥ν) := DKL (µ∥ν),

p = dµ/dλ,

DR,∞ (µ∥ν) := log ess supν dµ dν . In general, it is more convenient to state the associated Rényi divergence DR,α rather than the raw Hellinger divergence DH,α , due to the nice tensorization and continuity properties of DR,α (see Lemma B.6). Special cases The most useful f -divergences are the hockey stick divergences (due to their association with tight certificates via Theorem A.3) and the Rényi divergences (due to their attractive computational properties; see, e.g., Lemma B.6). Moreover, several of the divergences in Table 4 can be expressed in terms of a hockey stick or Rényi divergence of an appropriate order. We have the following relationships: DTV = DHS,1 , DH,2 = Dχ2P , DH2 = 12 DH,1/2 = 1 − Z1/2 . Practical considerations Practically speaking, the relationships between divergences in Table 4 mean we should utilize the Hockey-stick divergences directly whenever possible, and otherwise simply compute the Rényi divergences of all orders (which is useful when tight Hockey-stick divergences are inaccessible). Other specific divergences, like DH2 and Dχ2P , restate information already encoded in the Rényi divergences of the appropriate orders. Definition B.2 (Perspective function). Let f be a generator as in Definition B.1 with the usual conventions for f (0) and f ′ (∞). The perspective of f is the function gf : R+ × R+ → R ∪ {+∞} given by   bf (a/b) b > 0, gf (a, b) := af ′ (∞) b = 0, a > 0, (17)   0 a = b = 0. Lemma B.1 (Properties of perspective functions). gf is jointly convex and positively homogeneous, i.e., gf (ta, tb) = tgf (a, b) for every t > 0. Consequently gf is subadditive: gf (a1 + a2 , b1 + b2 ) ≤ gf (a1 , b1 ) + gf (a2 , b2 ).

(18)

Moreover gf admits the representation gf (a, b) =

sup [sa − f ∗ (s)b] s∈dom f ∗

where f ∗ is the convex conjugate of f , and for b > 0 the supremum is attained exactly at those s ∈ ∂f (a/b). 16

(19)

Definition B.3 (Convex Conjugate). For a function f : R → R, its convex conjugate is defined by f ∗ (u) := supv (uv − f (v)). Lemma B.2 (Basic properties of f -divergences). Let µ, ν, ρ be probability measures and f a generator as in Definition B.1. (i) (Nonnegativity.) Df (µ∥ν) ≥ 0. If f is strictly convex at 1, then Df (µ∥ν) = 0 if and only if µ = ν. (ii) (Reversal.) With the conjugate generator f (x) := xf (1/x), one has Df (µ∥ν) = Df (ν∥µ). (iii) (Cancellation of common parts.) Df (µ ⊗ ρ∥ν ⊗ ρ) = Df (µ∥ν). (iv) (Joint convexity.) Let 0 < λ < 1 and suppose µ = λµ0 + (1 − λ)µ1 and ν = λν0 + (1 − λ)ν1 for probability measures µi , νi . Then Df (µ∥ν) ≤ λDf (µ0 ∥ν0 ) + (1 − λ)Df (µ1 ∥ν1 ). R (v) (Perspective representation.) Df (µ∥ν) = gf (p, q) dλ for common dominating λ. (vi) (Variational representation.) With f ∗ the convex conjugate of f ,   ∗ Df (µ∥ν) = sup E[g] − E[f ◦ g] . g : Ω→dom(f ∗ )

µ

ν

Lemma B.3 (Data-processing inequality). Let K be a Markov kernel from (Ω, A) to (Ω′ , A′ ), and write Kµ for the R pushforward A 7→ K(ω, A) µ(dω). Then for every generator f , Df (Kµ∥Kν) ≤ Df (µ∥ν).

(20)

Equality holds whenever K is induced by a bimeasurable bijection T : Ω → Ω′ , so that Df (T# µ∥T# ν) = Df (µ∥ν), and more generally whenever K is a sufficient statistic for {µ, ν}. Lemma B.4 (Reversal of Hockey-Stick divergences). Fix µ, ν probability measures on (Ω, A), and β > 0. Define the dual parameter β := 1/β, extended to β ∈ {0, ∞} in the usual way. Then one has the following relationship: e HS,β (µ∥ν) = β D e HS,β̄ (ν∥µ) + 1 − β, D

DHS,β (µ∥ν) = β DHS,β̄ (ν∥µ).

(21)

In particular, the TV distance DTV is symmetric since it corresponds to the self-dual β = 1. Moreover, the Hockey-Stick profile for (µ, ν) over 0 ≤ β ≤ 1 is entirely determined by the profile of the reversed pair (ν, µ) for β ≥ 1. Lemma B.5 (Integral representation by Hockey-stick divergences). Let f be a generator as in Definition B.1, finite on ′ (0, ∞), and let ρ denote the Lebesgue-Stieltjes measure of its right derivative f+ , that is, the unique Borel measure on ′ ′ (0, ∞) with ρ((a, b]) = f+ (b) − f+ (a) for 0 < a < b < ∞. Then for all µ ≪ ν, Z Df (µ∥ν) = DHS,β (µ∥ν) ρ(dβ). (22) (0,∞)

Nn Nn Lemma B.6 (Tensorization Properties for Qnf -Divergences). For product measures µ = i=1 µi and ν = i=1 νi on Pnthe same product space, Zα (µ∥ν) = i=1 Zα (µi ∥νi ) for every α ∈ (0, 1) ∪ (1, ∞). Furthermore, DR,α (µ∥ν) = i=1 DR,α (µi ∥νi ). As a result of Lemma B.6, the divergences of Table 4 obtained by manipulating a Rényi-type divergence themselves possess nice tensorization properties. We document these and more tensorization properties in Table 5. In addition, one has upper bounds on product measures for Hockey-stick and TV divergences, although these bounds are not tight in general.

17

Table 5: Tensorization of f -divergences under product measures. Throughout, µ = product measures on a common product space. Divergence

Tensorization Zα (µ∥ν)

Hellinger integral

DR,α (µ∥ν)

Rényi

DKL (µ∥ν)

Kullback–Leibler

Pearson χ

2

Neyman χ

B.1

P

Dχ2 (µ∥ν) N

Hockey-stick

DHS,β (µ∥ν)

Total variation

DTV (µ∥ν)

=

Qn

α ∈ (0, 1) ∪ (1, ∞)

=

Pn

α ∈ [0, ∞]

=

Pn

i=1 Zα (µi ∥νi ) i=1 DR,α (µi ∥νi )

i=1 DKL (µi ∥νi )

Nn

i=1 νi are

case α = 1 above

= 1 − i=1 1 − DH2 (µi ∥νi )
Q = n (µi ∥νi ) − 1 i=1 1 + Dχ2 P
Q = n (µi ∥νi ) − 1 i=1 1 + Dχ2 N
Q ≤1− n i=1 1 − DHS,βi (µi ∥νi )
Q ≤1− n i=1 1 − DTV (µi ∥νi )

Dχ2 (µ∥ν)

2

1 µi and ν =

Notes

Qn

DH2 (µ∥ν)

Squared Hellinger

Nn

case α = 1/2 above case α = 2 above Lemma B.2(ii) w/ Dχ2 P Q β = i βi , βi ≥ 1

Additional lemmata

In this section we state and prove some additional useful lemmata regarding various f -divergences. Lemma B.7 (f -divergence between measures with shared components). Let µ, ν be probability measures on (Ω, A), let λ be any dominating measure, and write p := dµ/dλ and q := dν/dλ. Define the overlap S := {p > 0} ∩ {q > 0} (up to a λ-null set). Suppose µ(E) = ν(E) for every measurable E ⊆ S. Then, denoting m := µ(S c ) = ν(S c ), one has m = DTV (µ∥ν) and moreover for every generator f as in Definition B.1, Df (µ∥ν) = (f (0) + f ′ (∞))m = (f (0) + f ′ (∞))DTV (µ∥ν). Proof. Taking E = S gives µ(S) = ν(S) and hence µ(S c ) = ν(S c ). Set Sµ := {p > 0, q = 0},

Sν := {p = 0, q > 0},

N := {p = q = 0}

so that Ω = S ⊔ Sµ ⊔ Sν ⊔ N with µ(N ) = ν(N ) = 0. Evaluating the divergence via Lemma B.2(v) gives Z Z Z Z Df (µ∥ν) = gf (p, q) dλ + gf (p, 0) dλ + gf (0, q) dλ + gf (0, 0) dλ S

Sµ

Z =

Z qf (1) dλ +

S ′

Sν

pf ′ (∞) dλ +

Sµ

N

Z qf (0) dλ + 0 Sν

= f (∞)µ(Sµ ) + f (0)ν(Sν ). To conclude, note µ(Sµ ) = ν(Sν ) = m, and take f (u) = 12 |u − 1| for which f (0) = f ′ (∞) = 12 . Corollary B.1 (Hockey-stick envelope for measures with common component). In the setting of Lemma B.7, for every β ≥ 0, DHS,β (µ∥ν) = min(1, β)m, where m = µ(S c ) = ν(S c ). In particular, DHS,β (µ∥ν) = DTV (µ∥ν) = m whenever β ≥ 1, independently of β. Proof. The generator fβ (u) = (u − β)+ − (1 − β)+ has fβ (0) = −[1 − β]+ and fβ′ (∞) = limx↓0 xfβ (1/x) = 1, so fβ (0) + fβ′ (∞) = 1 − [1 − β]+ = min(1, β). The significance of Lemma B.7 is that for distributions exhibiting “simple” likelihood ratio behavior, the TV distance encodes the entire hockey stick envelope (indeed, any f -divergence), and in particular this means via Theorem A.3 that the information-limited certificate is strictly a function of the TV distance between those distributions.

18

C

Detailed Comparison with Prior Work

C.1

Threat model and mechanism comparison

Table 6 expresses the threat model and smoothing mechanism of several prior certified poisoning defenses in our notation and describes whether our framework recovers their certificate. RAB RAB bounds a single aggregate ℓ2 perturbation applied to the entire training dataset. Strictly speaking, our threat model of Section 3.2 does not capture theirs, since in RAB an adversary may spread their corruption over all training examples. Given our threat model with mp corrupted examples and ℓ2 budget εf , an outer RAB approximation √ may be obtained by taking the aggregate bound εf mp . In the case of backdoor attacks we can arrive at a similar bound. This is how we use their bound in Section 5. Under their own threat model, our certification procedure still recovers their certificate if we compute the divergences directly: the noise induces a single Gaussian pair (Definition G.3) at distance ∥∆∥2 /σ with closed form hockey-stick divergence (Theorem G.2). This certificate reduces to the closed form of Cohen et al. [2019]. Bagflip BagFlip’s adversary is mostly recoverable under our threat modeling. The only nuance is in their treatment of label-flipping adversaries. First, they require that the finite label space and feature space coincide, X = Y = [K]. Then, they treat the label as an extra feature and reduce certification to the feature-only case. In particular, a single budget is shared between the features and label. In this case, we can technically recover their threat model by taking ρ = (mp , s, 0, εte ) on the “merged” feature-label space. If we start with our label-flipping threat model, ρ = (mp , εf , 1, εte ), we might ask how the resulting certificate compares to BagFlip’s (which would take s = εf + 1). First, observe that ρ is more restrictive in the sense that our adversary must place one of its corruptions on the label, or not at all, whereas BagFlip’s adversary could reallocate a label corruption into an extra feature corruption. Despite this, it turns out that the resulting certificates are identical. Since features and labels share the alphabet [K] and the flipping kernel, the divergences depend only on the number of changed coordinates (Theorem G.4), and both worst cases corrupt εf + 1 coordinates. This simplification fails if X ̸= Y or if the feature and label noises differ (for example, to enable stronger noise on features than labels), in which case our framework can still compute tight certificates and is notably more general than Zhang et al. [2022]. Table 6: Threat models and smoothing mechanisms of prior randomized smoothing works expressed in the notation of Sections 3 and 4 Work

Threat vector ρ

Mechanism (Π, ϕX , ϕY )

Certificate

Jia et al. [2021] Rosenfeld et al. [2020] Zhang et al. [2022] Weber et al. [2023]

(mp , ∞, 1, 0) (mp , 0, 1, 0) (mp , s, εl , εte ) aggregate ℓ2 on S

bagging, none, none full set, none, flipping bagging, flipping, flipping full set, Gaussian, none

identical (Theorem E.1) tighta identical (Theorem E.2) identicalb

a We can obtain provably tight certificates, but must estimate the vote probabilities with an ensemble. Rosenfeld

et al. [2020] give an efficient, loose closed form for learners trained with linear regression. b Under their threat model, the certificate reduces to the standard Gaussian certificate of Cohen et al. [2019],

which is already understood in Dvijotham et al. [2020].

C.2

Comparison with Saxena et al. [2026]

Saxena et al. [2026] develop a randomized smoothing-based backdoor defense from the DP perspective. They view the joint train-inference procedure as a randomized mechanism composed of a stack of two private algorithms. We note several differences between our works. We do not make any assumptions about properties of the learner, like privacy, instead placing assumptions on, and then noising, the input data. It is these data noising schemes we analyze in this work, using techniques to handle subsampling, noise products, and then the individual noise factors. In contrast, the analysis of Saxena et al. [2026] is placed on understanding the composition of DP mechanisms. Our threat modeling is more expressive in its per-example budgets for replacement adversaries, handling arbitrary ℓp constraints and label

19

corruptions, whereas Saxena et al. [2026] focuses primarily on symmetric set distance adversaries (corresponding to the standard adjacency relation notion in DP), with one notable exception being a special case for ℓ2 feature adversaries and Gaussian noise. One interesting connection between our work and the methods of Saxena et al. [2026] is in the use of the hockeystick profile, also called the privacy profile in the DP literature, to characterize the robustness condition. Whereas Saxena et al. [2026] use the language and tools of DP, we formulate our results here in the language of f -divergences and convex optimization. To demonstrate the connection, we derive one of the results of Saxena et al. [2026] in our language. Saxena et al. [2026] consider a “randomized DPA” mechanism (motivated by [Levine & Feizi, 2021]) which works as follows. DPA assigns each training record to one of N buckets by some fixed rule (e.g., index or hashing) and trains one model per bucket. In the randomized view, the mechanism samples one bucket uniformly at random and trains a model on it. In our notation, this means taking Π to be uniform over N disjoint buckets with no feature or label noise, and the test input to be noised by kernel ϕX . Theorem C.1 (DPA with test-time noise; Theorem D.4 of Saxena et al. [2026]). Let Π be uniform over pairwise disjoint index buckets U1 , . . . , UN . Let noise ϕX be applied only to the test sample. Suppose the corruption changes records in at most r buckets, and let τβte ≥ DHS,β (ϕX (x′te )∥ϕX (xte )) for all admissible test corruptions. Then, for every β > 0, DHS,β (M(w′ )∥M(w)) ≤ Nr min(1, β) + (1 − Nr )τβte

(23)

Equality holds if exactly r buckets are changed, the test perturbation attains τβte , and the sub-datasets SU1 , . . . , SUN and SU′ j (for corrupted j) are pairwise distinct. Proof. Apply Theorem 4.1 with two groups corresponding to corrupted and uncorrupted buckets. For an uncorrupted bucket, the component divergence reduces to divergence between test components τβte (Lemma B.2(iii)). For a corrupted bucket, the component pair is singular and its hockey stick is simply min(1, β). Combining these terms with the mixing weights Nr and 1 − Nr gives the bound. If the equality conditions hold, the component supports are disjoint, and the bound is attained by Corollary E.1. The advantage of the randomized DPA mechanism is that, because the partition size N is small, and because no feature or label noise is added to training data, the training can be done once for all buckets and re-used for arbitrarily many certifications (inference on a sampled model must still be performed). Another interesting observation is that DPA can be used to obtain bounds for symmetric set difference adversaries who can add or remove training samples. For example, if bucket assignment is performed by hashing the training example (as done in Levine & Feizi [2021]), one has r ≤ min(2mp , N ) for mp replaced training examples.

D

Deferred proofs

D.1

Equivalence of robustness conditions

Theorem D.1 (Robustness characterization). Fix base learner G, smoothing mechanism M, input w ∈ W, and threat f → R by ψc,c′ (w) vector ρ. Write c := gM (w). For each c′ ∈ Y, define the specification ψc,c′ : W e := G(w) e c − G(w) e c′ . Then the following are equivalent: 1. c ∈ arg maxy∈Y GM (w′ )y for every w′ ∈ Bρ (w). 2. For every c′ ̸= c, the specification ψc,c′ is robustly certified at M(w) with respect to Dw,ρ := {M(w′ ) : w′ ∈ Bρ (w)}. In particular, either condition implies ρ-robustness of gM at w whenever the certified margins are strict. Proof. Fix w′ ∈ Bρ (w) and c, c′ ∈ Y. By linearity of expectation together with the definition of the smoothed classifier, E

′) w∼M(w e

[ψc,c′ (w)] e = =

E

[G(w) e c − G(w) e c′ ]

E

[G(w) e c] −

′) w∼M(w e ′) w∼M(w e

= GM (w′ )c − GM (w′ )c′ . 20

E

′) w∼M(w e

[G(w) e c′ ] (24)

Suppose (1) holds; that is, for every w′ ∈ Bρ (w), we have that c ∈ arg maxy∈Y GM (w′ )y . Then for every c′ ̸= c we ′ ) [ψc,c′ ] ≥ 0. Since every element of Dw,ρ is of the form have GM (w′ )c ≥ GM (w′ )c′ , so by Equation (24) Ew∼M(w e M(w′ ) for some w′ ∈ Bρ (w), it follows that each ψc,c′ is robustly certified at M(w) with respect to Dw,ρ . On the other hand, suppose (1) does not hold. Then there exists some w′ ∈ Bρ (w) and c′ ̸= c with GM (w′ )c′ > ′ ) [ψc,c′ ] < 0, so that ψc,c′ is not robustly certified in the sense of GM (w′ )c . Then Equation (24) gives Ew∼M(w e Definition A.1 and condition (2) fails. Finally, if the certified margins are strict, i.e., GM (w′ )c > GM (w′ )c′ for all c′ ̸= c and all w′ ∈ Bρ (w), then c is the unique maximizer of y 7→ GM (w′ )y , and we recover robustness in the desired sense of Definition 3.1.

D.2

Proof of Theorem 4.1

Proof. The result follows by applying joint convexity of Df (Lemma B.2(iv)) and rearranging terms according to the partition: Df (µ∥ν) ≤

N X

θi Df (µi ∥νi ) =

i=1

≤

k X X

θj Df (µj ∥νj )

i=1 j∈Si

k X X

θj δi =

i=1 j∈Si

k X

δi

i=1

X

θj =

j∈Si

k X

βi δ i .

i=1

Corollary D.1 (Rényi mixture bound). With the setting in Theorem 4.1, the Rényi divergence DR,α (µ∥ν) satisfies the following LogSumExp bound: ! N   X 1 θi exp((α − 1)DR,α (µi ∥νi )) (25) DR,α (µ∥ν) ≤ α−1 log i=1

for all α ∈ (0, 1) ∪ (1, ∞). Moreover, given βi and δi in the setting of Theorem 4.1, we have the reorganized bound ! k   X 1 DR,α (µ∥ν) ≤ α−1 log βi exp((α − 1)δi ) . (26) i=1

Proof. We first note that Equation (26) follows straightforwardly from Equation (25) due to monotonicity of log and exp. We prove Equation (25) for the cases 0 < α < 1 and α > 1 separately. Case 1: 0 < α < 1 The Rényi divergence is related to the f -divergence generated by f (u) = 1−uα by DR,α (µ∥ν) = 1 ( α−1 ) log(1 − Df (µ∥ν)), where in particular joint convexity of Df and monotonicity of log((1 − ·)−1 ) give the bound  !−1  N   X 1  DR,α (µ∥ν) ≤ log  1 − θi Df (µi ∥νi ) 1−α

i=1

=



1 α−1



log 1 −

N X

! θi Df (µi ∥νi ) .

i=1

Using the fact that Df (µi ∥νi ) = 1 − exp((α − 1)DR,α (µi ∥νi )), we get 

DR,α (µ∥ν) ≤

1 α−1



log 1 −

N X

! θi (1 − exp((α − 1)DR,α (µi ∥νi )))

i=1



=

1 α−1



log

N X

! θi exp((α − 1)DR,α (µi ∥νi ))

i=1

where the final step follows since

P

i θ = 1.

21

Case 2: α > 1 The Rényi divergence is related to the f -divergence generated by f (u) = uα − 1 by DR,α (µ∥ν) = 1 ( α−1 ) log(1 + Df (µ∥ν)), where in particular joint convexity of Df and monotonicity of log(1 + ·) give the bound DR,α (µ∥ν) ≤



1 α−1



log 1 +

N X

! θi Df (µi ∥νi ) .

i=1

Using the fact that Df (µi ∥νi ) = exp((α − 1)DR,α (µi ∥νi )) − 1, we get 

DR,α (µ∥ν) ≤

1 α−1



log 1 +

N X

! θi (exp((α − 1)DR,α (µi ∥νi )) − 1)

i=1



=

1 α−1



log

N X

! θi exp((α − 1)DR,α (µi ∥νi ))

i=1

where the final step follows since

E

P

i θi = 1.

Tightness of certificates

Since Cohen et al. [2019] proved optimality of their certificate for Randomized Smoothing with Gaussian noise, it has been customary to pair derivation of certified guarantees with an analysis of the tightness of the resulting certificate. In the ideal case, one can prove that a given Randomized Smoothing certificate is tight in the following precise sense. Given an input w ∈ W, the certification procedure determines a robustness region R at which the input w is robust (g(w) = g(w′ ) for all w′ ∈ Bρ (w) where ρ ∈ R). We can say that the region R is tight if, for any ρ ∈ / R, there exists a “worst-case” input w′ ∈ Bρ (w) and base algorithm G (subject to some constraints determined by evaluating G at w) with the property that g(w′ ) ̸= g(w). In the information-limited setting of Theorem A.2, G is constrained by the aggregated vote probabilities 0 ≤ θb ≤ θa ≤ 1. In the full-information setting of Theorem A.1, more information about the vote distribution can be used. Turning to our framework, our analysis introduces slack at two key steps. First, we replace the induced constraint set of Dw,ρ of Theorem D.1 by a convex outer approximation DF . Second, we replace the exact divergence bounds τf⋆ = supw′ ∈Bρ (w) Df (M(w′ )∥M(w)) by analytical upper bounds of Theorem 4.1. 3 The first source of slack corresponds to the convex relaxation itself, and is already reasonably well-understood. By Theorem A.3, if the exact Hockey-stick profile τβ⋆ (see Equation (9)) is available at all orders β ≥ 0, then the resulting certificate is tight in the information-limited setting. This means no procedure that observes only the vote statistics θa , θb can certify a larger region without further assumptions on the base learner G. Thus, to understand the tightness of our certificates, we should the error introduced by Theorem 4.1 P understand P and how it affects certification. For mixture distributions µ = i θi µi and ν = i θi νi on a shared space, define the joint-convexity slack N X Ef (µ, ν; θ) := θi Df (µi ∥νi ) − Df (µ∥ν) ≥ 0. (27) i=1

In this appendix, we seek to understand the second source of slack arising from our use of the joint convexity bound Theorem 4.1, and how it affects the resulting certificates generated by our framework. This analysis can be broken into several steps. Appendix E.1 characterizes Ef exactly as the information gained by releasing the mixture component labels along with the noised observation. In particular, the joint convexity bound is exact in precisely the cases when the mixture component label can be recovered from the noised observation. Appendices E.2 and E.3 show that the smoothing schemes of two prior works, Jia et al. [2021] and Zhang et al. [2022], satisfy this hypothesis, and thus we recover their certificates exactly. 3 To be precise, slackness could also enter through the reorganization process of Theorem 4.1. However, in the cases we consider, this reorganization

is exact.

22

E.1

Joint-convexity slack from label recovery

PN PN Throughout this subsection fix mixtures µ = i=1 θi µi and ν = i=1 on (Ω, A) with common weights θi > 0, let λ be a common dominating measure for {µi , νi }N i=1 , and write pi := dµi /dλ and qi := dνi /dλ. Sampling from µ is a two-stage process: first, draw index i ∼ θ, then, draw ω ∼ µi . The mixture µ reflects the law of ω marginalized over i. For purposes of understanding the slack Ef , it is useful to also define the labeled pair (i, ω): Definition E.1 (Labeled mixture). The labeled mixtures of µ and ν are the probability measures on [N ] × Ω µ b :=

N X

θi (δi ⊗ µi )

νb :=

i=1

N X

θi (δi ⊗ νi )

i=1

We write π : [N ] × Ω → Ω, π(i, ω) = ω for the projection onto the observation ω. Note that π is a deterministic Markov kernel with π# µ b = µ and π# νb = ν. Lemma E.1 (Additivity of labeled mixtures). For every generator f as in Definition B.1, Df (b µ∥b ν) =

N X

θi Df (µi ∥νi ).

(28)

i=1

b and νb, with densities (i, ω) 7→ θi pi (ω) and (i, ω) 7→ θi qi (ω). By Proof. The measure λ′ := count ⊗ λ dominates µ the perspective representation (Lemma B.2(v)) and positive homogeneity of gf (Lemma B.1), Df (b µ∥b ν) =

N Z X

gf (θi pi , θi qi ) dλ =

i=1

N X

Z θi

gf (pi , qi ) dλ =

i=1

N X

θi Df (µi ∥νi ).

i=1

Combining Lemma E.1 with the data-processing inequality (Lemma B.3) applied to π recovers Theorem 4.1: Df (µ∥ν) = Df (π# µ b∥π# νb) ≤ Df (b µ∥b ν) =

N X

θi Df (µi ∥νi ).

i=1

In particular, Ef = Df (b µ∥b ν ) − Df (µ∥ν).

(29)

Equation (29) states that the slack Ef is precisely the difference in f -divergence between labeled and unlabeled mixtures. In our setting the index is the retained index sequence U ∼ Π. Corollary E.1 (Exactness for identifiable mixtures). If the sets Ωi := {pi > 0} ∪ {qi > 0} are pairwise disjoint up to PN λ-null sets, then Df (µ∥ν) = i=1 θi Df (µi ∥νi ) for every generator f , that is, Ef = 0. Proof. Let ι(ω) := i for ω ∈ Ωi and arbitrary elsewhere, and define T (ω) := (ι(ω), ω). Each µi , νi is supported only on Ωi , so T# µ = µ b and T ν = νb. Applying Lemma B.3 to T and to π gives Df (b µ∥b ν ) ≤ Df (µ∥ν) ≤ Df (b µ∥b ν ). The PN # right hand side is i=1 θi Df (µi ∥νi ) by Lemma E.1.

E.2

Tightness of pure subsampling

We use these results to recover the bagging certificate of Jia et al. [2021] as a special case of our framework. Take ϕX (· | x) = δx and ϕY (· | y) = δy as the feature and label smoothing mechanisms (that is, no noise is added to features or labels). Call an input w = (S, xte ) and corruption w′ ∈ Bρ (w) record-distinct if the records of S are pairwise distinct, the corrupted records (x′i , yi′ ), i ∈ I(w, w′ ), are pairwise distinct, and the clean and corrupted records are disjoint. Theorem E.1 (Exactness for pure subsampling). Let M subsample without noise and let w′ ∈ Bρ (w) be record-distinct. Write m(w, w′ ) := PU ∼Π [∃j. uj ∈ I(w, w′ )] for the probability that the subsample retains a corrupted record. Then, for every generator f , X
Df (M(w′ )∥M(w)) = Π(U )Df δSU′ δSU = (f (0) + f ′ (∞)) m(w, w′ ). U

23

So Theorem 4.1 is exact, and the Hockey-stick profile is DHS,β (M(w′ )∥M(w)) = min(1, β)m(w, w′ )

β ≥ 0.

(30)

Proof. If U does not contain a corrupted index, then SU′ = SU . Otherwise, SU′ contains at least one corrupted record, so SU′ ̸= SV for every V . By record-distinctness, it follows that SU ̸= SV and SU′ ̸= SV′ for U ̸= V . Therefore, the component supports TU := {SU , SU′ } of the component pairs are pairwise disjoint, and exactness follows from Corollary E.1. For Equation (30), observe that the mixtures agree on their intersection {U : U ∩ I = ∅}, and so we may apply Lemma B.7 with overlap mass 1 − m(w, w′ ). Corollary E.2 (Recovery of bagging certificate). In the setting of Theorem E.1, write m⋆ρ := supw′ ∈Bρ (w) m(w, w′ ). Then G(θa , θb ) is robustly certified at M(w) with respect to Dw,ρ if and only if θa − θb ≥ 2m⋆ρ .

(31)

For ρ constraining only mp , m⋆ρ = 1 − (1 − mp /n)k under size-k sampling with replacement and m⋆ρ = 1 −

n−mp n −1 without replacement. k k Proof. Substituting τβ = min(1, β)m⋆ρ into the objective of Theorem A.3, we get βa⋆ = βb⋆ = 1 whenever θa > m⋆ρ and θb + m⋆ρ < 1, giving optimal value of θa − θb − 2m⋆ρ in Equation (6). A noteworthy condition for our tightness proof was record-distinctness. In the usual randomized smoothing setting [Cohen et al., 2019, Jia et al., 2021, Zhang et al., 2022] this is a mild assumption, as the certificates are derived without using additional information about the input. If record-distinctness does not hold (either due to repetition in S or impossibility of choosing an appropriate w′ ), we cannot directly apply Lemma B.7 to obtain the worst-case τβ (although it remains a valid upper bound).

E.3

Recovering BagFlip’s certificate

In Appendix E.2, we exploited Corollary E.1 to obtain a tight certificate based on the TV distance in the case of pure bagging. Once feature or label noise is introduced, the mixture components are no longer identifiable. Thus, in principle, the slack Equation (27) is nontrivial. However, it turns out that Zhang et al. [2022] compute the certificate only for the label-released mixture (see Zhang et al. [2022, Appendix A]), and thus Corollary E.1 does apply to the setting actually considered by BagFlip. This means two things. First, the certificates obtained within our framework match the certificates of Zhang et al. [2022] exactly in the analytical sense. Second, the certificate of Zhang et al. [2022] may not be tight in the sense that base learners that do not use the mixture component label (which is true of BagFlip’s learners) are actually more robust than the certificate guarantees. Theorem E.2 (Recovery of BagFlip certificate). Consider the BagFlip instantiation taking X = [K]d , Y = [K], Π \ M(w \′ ) denote the labeled uniform on [n]k , and ϕX , ϕY the flipping measures of Definition G.5 with rate γ. Let M(w), mixture of M as in Definition E.1. Then the bound of Theorem 4.1, applied with partition of [n]k by the number c of retained corrupted examples, evaluates to k   X
m \′ ) M(w) \ = τβ = DHS,β M(w Binom(c; k, np )δβ c(εf + εl ) + εte ,

(32)

c=0

where δβ (s) := DHS,β (ϕγ (y)∥ϕγ (y ′ )) for any y, y ′ with ∥y − y ′ ∥0 = s, given in closed form by Equation (65). Consequently, the certificate obtained by applying Theorem A.3 to the profile given by Equation (32) coincides with the radius of Zhang et al. [2022, Thm. 5.1]. Proof. Conditioned on the sampled indices U , the pair (µU , νU ) consists of two flipping measures on [K]kd × [C]k × [K]d whose parameters disagree in exactly c(εf + εl ) + εte coordinates, where c = |{j : uj ∈ I(w, w′ )}|. By Theorem G.4 the component divergence is determined as a function of c, so the regrouping step preserves the exact joint convexity bound. Thus, we recover the exact Hockey-stick envelope τβ , β ≥ 0, and via Theorem A.3 the optimal information-limited certificate. 24

F

Methodology Details

F.1

Training

Datasets We train models on MNIST, CIFAR10, as well as binary classification tasks derived from them. MNIST-17 uses the MNIST digits 1 and 7, and CIFAR10-02 uses the CIFAR10 classes 0 and 2 (airplane and bird). The training and test sets have 60,000 and 10,000 examples on MNIST, 13,007 and 2,163 on MNIST-17, 50,000 and 10,000 on CIFAR10, and 10,000 and 2,000 on CIFAR10-02. We report certified accuracy on the full test set. Pixel values are divided by 255, which puts every feature in [0, 1], and we apply no further normalization or standardization. d = 784 on MNIST and d = 3072 on CIFAR10. Architectures On MNIST datasets, the base learner is a small convolutional network consisting of two 5 × 5 convolutions with 16 and 32 channels, respectively, each followed by ReLU activation and 2 × 2 average pooling, then a hidden layer of width 64 with ReLU, and finally a linear output layer. We use dropout of 0.25 and 0.5 before each linear layer. On the CIFAR10 datasets, we use the ResNet-20 of Jia et al. [2021] modified to use group normalization (at most eight groups) and weight-standardized convolutions. These modifications are due to our parallel training implementation which does not support the running statistics of batch normalization. Networks in all experiments are trained from random initializations. Optimization All training uses the Adam optimizer with learning rate 10−3 and runs for 200 epochs with batch size 16. We use weight decay of 2 · 10−3 on MNIST and 10−4 on CIFAR10. On CIFAR10, the learning rate is multiplied by 0.1, 0.01, 0.001, and 0.0005 from epochs 80, 120, 160, and 180, following BagFlip [Zhang et al., 2022]. Models trained on the full training set (for the RAB baseline) use 20 epochs with batch size 128 on MNIST and MNIST-17, and 10 epochs with batch size 64 on CIFAR10 and CIFAR10-02. Augmentation On MNIST, we use random translations of up to 2 pixels and 8 × 8 cutout. On CIFAR10, we use random translations of up to 4 pixels and horizontal flips. In addition, each training batch receives Gaussian noise whose standard deviation is drawn uniformly from [0, 1], motivated by the augmentation of Zhang et al. [2022], and disabled for plain bagging experiments on CIFAR10 and CIFAR10-02.

F.2

Mechanisms and configurations

Mechanisms All ensembles use bagging with replacement. The feature noise scale σ is√calibrated to a constant 2 coordinate-wise √ √ standard deviation: Gaussian noise N (0, σ ), Laplace noise Lap(0, σ/ 2), and uniform noise Unif([− 3σ, 3σ]). The feature noise is Gaussian unless stated otherwise. In the joint feature and label experiments, label noise keeps the original label with probability 1 − γ + γ/C = 0.9, with γ = 19 on MNIST and CIFAR10 and γ = 15 on MNIST-17 and CIFAR10-02. The backdoor experiments do not use label noise. Ensembles Every ensemble uses m = 10,000 base models on MNIST and MNIST-17, and m = 1,000 base models on CIFAR10 and CIFAR10-02. ℓp feature adversaries The experiments of Section 5.1 use k = 100 and σ = 0.5 on MNIST and MNIST-17, k = 1000 and σ = 0.35 on CIFAR10, and k = 200 and σ = 0.35 on CIFAR10-02. In Figure 1, the Gaussian, Laplace and uniform curves use this configuration, the bagging curve uses k = 100 with no noise, and RAB uses σ = 0.5 on the full training set. Figure 2 uses the configuration of each dataset. Label flipping and backdoor adversaries Table 7 lists the bag sizes and noise scales of Tables 2 and 3. In Table 2, bagging uses the same k as our method. In Table 3, RAB uses the σa and σb of our method on the full training set.

F.3

Confidence intervals

Certification in our framework requires high-confidence bounds on teh vote probabilities of the smoothed classifier. We estimate them from N votes of an ensemble using the following confidence interval.

25

Table 7: Bag sizes and noise scales of Table 2 and Table 3. Joint feature & label

Backdoor

Dataset

k

σa

σb

k

σa

σb

MNIST MNIST-17 CIFAR10 CIFAR10-02

30 30 200 25

0.25 0.5 0.2 0.35

0.5 1.0 0.35 0.5

300 100 1000 100

0.75 0.75 0.5 0.35

1.0 1.0 0.75 0.5

Algorithm 1 T RAIN U NDER M ECHANISM Input: Training set S = ((xj , yj ))nj=1 , learning algorithm A, mechanism (Π, ϕX , ϕY ), number of models N Output: Base models g1 , . . . , gN 1: for i = 1, . . . , N do 2: Sample Ui = (u1 , . . . , uk ) ∼ Π
k 3: Sample Sei ← (e xj , yej ) j=1 with x ej ∼ ϕX (· | xuj ) and yej ∼ ϕY (· | yuj ) 4: gi ← A(Sei ) 5: end for 6: return g1 , . . . , gN

Lemma F.1 (Clopper–Pearson Interval [Clopper & Pearson, 1934]). Let Z1 , .P . . , ZN be independent, identically N distributed Bernoulli random variables with mean p ∈ [0, 1], and let SN := i=1 Zi . Fix a failure probability ζ ∈ (0, 1), and let Q(q; α, β) denote the q-quantile of the Beta distribution with shape parameters α, β. Define   (33) p := Q ζ2 ; S, N − S + 1 ,   p := Q 1 − ζ2 ; S + 1, N − S , (34) with the conventions p := 0 when SN = 0 and p := 1 when SN = N . Then, with probability at least 1 − ζ, p ∈ [p, p]. In particular, the one-sided upper confidence bound p + := Q(1 − ζ; S + 1, N − S) satisfies Pr[ p ≤ p + ] ≥ 1 − ζ. More precisely, we use SimuEM as in Jia et al. [2021], which applies a Bonferroni correction over all C classes and the e test points. Each bound thus has failure probability α/(eC) and the full test-set failure probability is bounded by α via the union bound.

F.4

Algorithms

Algorithms 1 and 2 follow Jia et al. [2021, Algorithm 1] and Weber et al. [2023, Algorithms 1 and 2]. We perform certification following Dvijotham et al. [2020, Algorithm 2] with hockey-stick constraints of all orders.

G

Bounding divergences

The core technical challenge of our method is to derive the divergence bounds τf (w, ρ) ≥ τf⋆ (w, ρ) =

sup w′ ∈B

Df (M(w′ )∥M(w))

(35)

ρ (w)

for various inputs w, smoothing mechanisms M, threat models ρ, and generators f . Via Theorem 4.1, the problem reduces to bounding divergences between the paired components of the mixture induced by M. Fixing mixture component U , this decomposes into two steps. The first step is to argue that the maximum attainable divergence is exhibited by some worst-case perturbation of the subsampled input x = SU , so that we may write sup Df (ϕ# x′ ∥ϕ# x) = Df (µ⋆ ∥ν ⋆ ) x′ ∈B(x)

26

(36)

Algorithm 2 C ERTIFY Input: Base models g1 , . . . , gN , test examples x1 , . . . , xe , feature noise mechanism ϕX , per-example budgets (εf , εl , εte ), confidence level 1 − α Output: Predicted label and certified number of corrupted examples for each test example 1: for x in x1 , . . . , xe do 2: Sample x e(i) ∼ ϕX (· | x) for i = 1, . . . , N ▷x e(i) = x if the test input is not noised PN (i) 3: counts[y] ← i=1 1[gi (e x ) = y] for y ∈ [C] 4: c, c′ ← top two indices in counts 5: θa , θb ← S IMU EM(counts, α/e) 6: m⋆ ← B INARY S EARCH(θa , θb ) ▷ find largest mp with p > p 7: Output c and m⋆ , or A BSTAIN if no mp ≥ 0 is certified 8: end for for some pair of probability measures µ⋆ , ν ⋆ , where ϕ is the joint feature-and-label noising mechanism. 4 Note that x and B(x) do not necessarily correspond exactly with the joint input w and constraint set Bρ (w); for example, B(x) likely depends on U . For reasons we will describe later, the two main desiderata are that the same pair µ⋆ , ν ⋆ works for every f , and that such pairs compose across the factors of ϕ. We handle this step in Appendix G.1. The second step is to compute the full set of divergences for µ⋆ , ν ⋆ . This is typically straightforward once µ⋆ , ν ⋆ are known. We handle this step in Appendix G.2, where we work out closed-form divergences for Uniform, Flipping, Gaussian, and Laplace measures by hand. We also show how to construct product measures using these measures as building blocks, and reduce divergence computation to a one-dimensional numerical computation. Together, the above steps are sufficient to derive bounds for Uniform, Gaussian, and Flipping measures, as well as product combinations of them, under all (ℓp , ℓ0 ) feature-label constraints. In some cases the procedure does not work so cleanly. Informally speaking, if the smoothing geometry does not mesh with the perturbation geometry, no single pair µ⋆ , ν ⋆ need exist. This arises for Laplace feature noise under general ℓp norms with p ̸= 1, which we treat separately in Appendix G.4.

G.1

Finding worst-case adjacent distributions

Adjacency parameters The left side of Equation (35) optimizes over a high-dimensional set. In many cases the divergence depends only on some lower-dimensional “sufficient statistic” computable from x, x′ , motivating the following definition. Definition G.1 (Adjacency parameter). Let ϕ be a noising mechanism over space X . An adjacency parameter is a map θ : X × X → Θ such that, for every generator f , there exists a function δf : Θ → R+ such that Df (ϕ# x′ ∥ϕ# x) = δf (θ(x, x′ )) for all x, x′ ∈ X . Writing ΘB (x) := {θ(x, x′ ) : x′ ∈ B(x)}, Equation (35) becomes sup Df (ϕ# x′ ∥ϕ# x) = x′ ∈B(x)

sup δf (θ),

(37)

θ∈ΘB (x)

which is often simpler when Θ is low-dimensional. How low-dimensional Θ can be is governed by symmetry of the constraint set under the noise ϕ. By Lemma B.3, Df is invariant to invertible transformations. So, if T is a transform with T# ϕ(x) = ϕ(T x) for every x ∈ X , the divergence can only depend on those qualities of the pair x, x′ invariant under T . Taking Gaussian measures as an example, T can be taken to be any Euclidean isometry, leaving θ(x, x′ ) = ∥x − x′ ∥2 . Worst-case pairs Equation (37) may have a different maximizer for each f . Ideally, however, this is not the case. Define the binary relation (µ′ , ν ′ ) ⪯ (µ, ν) if and only if, for every generator f , Df (µ′ ∥ν ′ ) ≤ Df (µ∥ν). Similarly, call θ⋆ a worst-case for Θ′ ⊆ Θ if supθ∈Θ′ δf (θ) = δf (θ⋆ ) for every f . It can be convenient to characterize worst-case measures through their likelihood ratios. We have the following lemmata, which will become useful later. 4 This is similar to the concept of a dominating pair [Zhu et al., 2022] in the privacy literature.

27

Lemma G.1 (Hockey-stick characterization of ⪯). Let µ ≪ ν and µ′ ≪ ν ′ be measures on the same space. Then (µ′ , ν ′ ) ⪯ (µ, ν)

DHS,β (µ′ ∥ν ′ ) ≤ DHS,β (µ∥ν) for every β > 0.

⇐⇒

(38)

Proof. Each fβ is itself a generator, which gives the forward implication. Conversely, ρ is nonnegative in Lemma B.5, so a uniform bound on DHS,β (µ′ ∥ν ′ ) is preserved into Df (µ′ ∥ν ′ ). Lemma G.2 (Product composition of worst-case pairs). For each j = 1, . . . , k, let µj , µ′j , νj be measures on (Ωj , Aj )

N ′ N N N ⋆ with µj , µ′j ≪ νj and (µ′j , νj ) ⪯ (µj , νj ). Then j µj , j νj ⪯ j µj , j νj . In particular, if θj is a worst ⋆ ⋆ case parameter for each j, then (θ1 , . . . , θk ) is worst case for the product measure. Proof. Replacing µ′j by µj one index at a time forms a sequence from µ′ to µ. Thus, by transitivity of ⪯, it suffices to prove the case where the two products differ only in a N single factor (WLOG, the first): µ′j = µj for all j ̸= 1. N Group the factors µ>1 := j≥2 µj and ν>1 := j≥2 νj , and let Λ>1 denote their likelihood ratio. Applying Lemma G.3 with µ>1 as the first factor and using Equation (38), we have h i e HS,β (µ′1 ⊗ µ>1 ∥ν1 ⊗ ν>1 ) = E D e HS,β/Λ (µ′1 ∥ν1 ) D >1 µ>1 h i e HS,β/Λ (µ1 ∥ν1 ) = D e HS,β (µ1 ⊗ µ>1 ∥ν1 ⊗ ν>1 ). ≤ E D >1 µ>1

Since β > 0 was arbitrary, the claim follows from Lemma G.1.

G.2

Bounds between adjacent smoothing measures

In this appendix we derive Hockey-stick and Rényi divergences for the distributions arising in our analysis. General Strategy We show how to compute Df (µ∥ν) when µ and ν are adjacent measures. In these computations, ν may be interpreted as the clean distribution, and µ the corrupted one. Each computation proceeds by writing down the distribution of Λ = p/q under ν and evaluating Equation (14). Lemma G.3 (Hockey-stick for product measures). Let µ = µ1 ⊗ µ2 and ν = ν1 ⊗ ν2 and write Λ1 and Λ2 for the likelihood ratios under (µ1 , ν1 ) and (µ2 , ν2 ), respectively. Then, for every β > 0, h i h i e HS,β (µ∥ν) = E Λ1 D e HS,β/Λ (µ2 ∥ν2 ) = E D e HS,β/Λ (µ2 ∥ν2 ) . D (39) 1 1 ν1

µ1

Proof. Using (λu − β)+ = λ(u − β/λ)+ for λ > 0, we have h i e HS,β (µ∥ν) = E [(Λ − β)+ ] = E E [(Λ1 Λ2 − β)+ ] = E Λ1 D e HS,β/Λ (µ2 ∥ν2 ) . D 1 ν

ν1 ν2

ν1

The final equality holds since Eν1 [Λ1 h(Λ1 )] = Eµ1 [h(Λ1 )]. N N Corollary G.1. Suppose µ = j µj , ν = j νj , and that Λj takes finitely many values for j < k. Let V be set of Q values of Λ<k := j<k Λj , and let Pλ := Pµ1 ⊗···⊗µk−1 [Λ<k = λ]. Then for every β > 0, X e HS,β (µ∥ν) = e HS,β/λ (µk ∥νk ). D Pλ D (40) λ∈V

e HS,β (µ∥ν) = Moreover, if µk = νk , then D

P

λ>β (1 − β/λ)Pλ .

Proof. Apply Lemma G.3 with the first factor µ1 ⊗ · · · ⊗ µk−1 and take the sum over the values of Λ<k . The final e HS,β/λ = (1 − β/λ)+ . claim holds by taking µk = νk to be a point mass, so D Corollary G.1 allows us to fully understand the hockey stick profile of any measure constructed from discrete factors combined with a factor whose entire profile is known. The relevant application below is to construct joint feature-and-label noises which combine discrete label flipping with continuous feature noise (e.g., Definition G.6)). The convolution in Equation (40) in general can be computationally expensiveQif many factors are tensored together. The number of discrete likelihood ratio values is upper-bounded by the product j |Vj |. Thankfully, for the noises we consider, the likelihood ratio values collapse onto a lattice, greatly simplifying the computation. 28

Smoothing measures

We now catalog the smoothing measures used in our work and their associated divergences.

Definition G.2 (Uniform measure). Let m ∈ N and γ ∈ R+ . Given x ∈ Rm , the associated Uniform measure is the product measure m O µ := Unif(xi − γ, xi + γ). (41) i=1 m

We say that two Uniform measures on R

with the same γ and data x, x′ are θ-adjacent if θ =1−

m  Y i=1

|xi − x′i | 1− 2γ

 .

(42)

+

Theorem G.1 (Divergences for adjacent uniform measures). Let µ, ν be θ-adjacent Uniform measures on Rm . Then 1 log(1 − θ), for α ∈ (0, 1), else ∞, DR,α (µ∥ν) = α−1

(43)

DKL (µ∥ν) = ∞,

(44)

DHS,β (µ∥ν) = min(1, β)θ,

(45)

DTV (µ∥ν) = θ.

(46)

Proof. µ and ν have densities p, q which evaluate to (2γ)−m on their supports and 0 everywhere else. Thus the likelihood ratio Λ satisfies the hypotheses of Lemma B.7, so we may write Df (µ∥ν) = (f (0) + f ′ (∞))DTV (µ∥ν) for any generator f . The overlap region defining Λ = 1 can be seen to be of length (2γ − |xi − x′i |)+ on each coordinate, |x −x′ | which has mass under ν of (1 − i2γ i )+ . Thus Λ = 1 with probability 1 − DTV (µ∥ν) = 1 − θ, completing the proof. Definition G.3 (Gaussian measure). Let m ∈ N and σ ∈ R+ . Given x ∈ Rm , the associated Gaussian measure is the standard isotropic Gaussian measure: µ := N (x, σ 2 Im ). (47) We say that two Gaussian measures on the same space Rm and same parameter σ with data x and x′ , respectively, are ′ ∥2 r-adjacent if ∥x−x = r. σ Theorem G.2 (Divergences for adjacent Gaussian measures). Let µ = N (x, σ 2 Im ) and ν = N (x′ , σ 2 Im ) be r-adjacent Gaussian measures on Rm . Then αr2 2 r2 DKL (µ∥ν) = 2

DR,α (µ∥ν) =

DHS,β (µ∥ν) = Φ

DTV (µ∥ν) = 2Φ

(48) (49)

log β r 2 − r

r 2







− βΦ − 2r − logr β − (1 − β)+

−1

(50) (51)

Proof. Equations (48) to (51) are well-known; see Mironov [2017] for Equation (48) and Balle & Wang [2018] for Equation (50). Equation (49) follows by taking the limit α → 1 in Equation (48), and Equation (51) follows by taking β = 1 in Equation (50) and applying the identity Φ(−x) = 1 − Φ(x). Definition G.4 (Laplace measure). Let m ∈ N and b ∈ R+ . Given x ∈ Rm , the associated Laplace measure is the product measure dµ µ := Lap(x, b)⊗m , (z) = (2b)−m exp(−∥z − x∥1 /b). (52) dz We say that two Laplace measures on the same space Rm and same parameter b with data x and x′ , respectively, are t-adjacent if t = (|x1 − x′1 |, . . . , |xm − x′m |)/b ∈ Rm (53) ≥0 , taken in nonincreasing order. 29

Theorem G.3 (Divergences for adjacent Laplace measures). Let µ, ν be t-adjacent Laplace measures on Rm . For notational convenience, for α ∈ (0, 1) ∪ (1, ∞) and t ≥ 0 define the quantities α α−1 −αt e(α−1)t + 2α−1 e , ζα (t) := 2α−1

1 log ζa (t), κα (t) := α−1

where we define by the limit ζ1/2 (t) = e−t/2 (1 + t/2). Under ν, the likelihood ratio factorizes as Λ = Qm e−∥t∥1 j=1 Vtj where each Vtj is independent and P[Vt = 1] =

1 , 2

dP dv

= (1,e2t )

1 −3/2 v , 4

P[Vt = e2t ] =

1 −t e . 2

(54) Qm

j=1 Λj =

(55)

Then, we have that DR,α (µ∥ν) =

P

(56)

DKL (µ∥ν) =

P

(57)

j κα (tj ) −tj − 1). j (tj + e

If t = te1 has a single nonzero coordinate, then for all β > 0, h i p DHS,β (µ∥ν) = (1 − βe−t/2 )+ − (1 − β)+ , +

DTV (µ∥ν) = 1 − e−t/2 .

(58) (59)

For general t, the Hockey-stick divergence can be obtained numerically by convolving m copies of the distribution in Equation (55). Proof. We first exhibit the likelihood ratio structure from Equation (55). That the likelihood ratio factorizes into Λj is clear from the product measure structure of µ, ν. WLOG we can assume b = 1, x = 0, and x′j = tj ≥ 0. Write pj , qj for the densities of µj , νj , respectively. Each coordinate j has   x ≤ 0, exp(−tj ), pj (x) Λj (x) = = exp(−|x − tj | + |x|) = exp(2x − tj ), 0 ≤ x ≤ tj ,  qj (x)  exp(tj ), x ≥ tj . We would like to understand the distribution of the variable Vtj := exp(tj )Λj under ν. On the endpoints we see that Z 0 Pν [Vtj = 1] = 1/2 exp(−|x|) = 1/2 Z∞ ∞ Pν [Vtj = e2tj ] = 1/2 exp(−|x|) = e−t /2, t

recovering the first and last identities in Equation (55). For the points x ∈ (1, e2tj ), we note that the map f (x) = e2x is differentiable with differentiable inverse f −1 (v) = 12 ln(v), so we may apply the change of coordinates formula to arrive at the density 1 −1/2 q(f −1 (v)) dP 2v = = = 14 v −3/2 . dv ′ −1 2tj |f (f (v))| 2v (1,e ) Q tj Qm ∥t∥1 Noting that j e = e , we recover Λ = e−∥t∥1 j=1 Vtj . Rényi and KL divergences

Evaluating the Hellinger integral Zα for a single coordinate via Equation (55) gives −αtj Zα (µj ∥νj ) = E[λα E[Vtαj ]. j] = e ν

ν

Computing the latter expectation gives Z e2t

1 α−3/2 dv + 12 e−tj +2αtj 4v 1 1 (e(2α−1)t − 1) + 12 e−tj +2αtj = 12 + 4α−2 1 1 = ( 12 − 2(2α−1) ) + ( 12 + 2(2α−1) )e(2α−1)tj

E[Vtαj ] = 21 + ν

α−1 α = ( 2α−1 ) + ( 2α−1 )e(2α−1)tj .

30

Multiplying through by e−αtj recovers the Rexpression Zα (µj ∥νj ) = ζα (t). The case for α = 1/2 follows by 1 recomputing the integral directly and noting v −1 = ln(v). Finally, taking DR,α (µj ∥νj ) = α−1 log Zα (µj ∥νj ) and summing over coordinates (applying Lemma B.6) yields Equation (57). It can be verified that taking the limit α → 1 yields Equation (57). Hockey-stick divergence Suppose t = te1 . Cancelling identical factors (Lemma B.2(iii)), we need only compute DHS,β (µ1 ∥ν1 ). By Equation (55) for Λ1 , we see that x 7→ Λ1 (x) is nondecreasing in x with range [e−t , et ]. Hence, for β ∈ (e−t , et ), we have the set xβ := 12 (t + log β) ∈ (0, t).

Eβ := {Λ1 ≥ β} = (xβ , ∞), Integrating over these regions gives R∞ 1

exp(−|x|) dx = 21 e−xβ , xβ 2 R∞ µ(Eβ ) = xβ 12 exp(−|x − t|) dx = 1 − 12 e−(t−xβ ) . ν(Eβ ) =

Using exβ =

√

βet/2 , we compute the (unnormalized) hockey-stick directly as p p p e HS,β (µ∥ν) = µ(Eβ ) − βν(Eβ ) = 1 − 1 βe−t/2 − 1 βe−t/2 = 1 − βe−t/2 . D 2 2

e HS,β (µ∥ν) = 0. When β ≤ e−t , we have Λ1 ≥ β everywhere and When β ≥ et , Λ1 ≤ β everywhere and D e DHS,β (µ∥ν) = 1 − β. Combining all three cases (and re-normalizing) yields Equation (58). Taking β = 1 yields Equation (59). Definition G.5 (Flipping Measure). Let C ≥ 2 be an integer alphabet size, y = (y1 , . . . , ym ) ∈ [C]m , and γ ∈ [0, 1]. We define the flipping measure m O ϕγ (y) := ((1 − γ)eyi + γ Unif([C])) . (60) i=1

We say that two flipping measures on the same space [C]m are s-adjacent if ∥y − y ′ ∥0 = s Theorem G.4 (Divergences for Adjacent Flipping Measures). Let µ = ϕγ (y)

and

ν = ϕγ (y ′ )

be s-adjacent flipping measures on [C]m . For notational convenience define the quantities p+ := 1 − γ + Cγ , and

$ dβ :=

p0 := (C−2) C γ

p− := Cγ ,

(61)

% log β p+ log p

β≥1

(62)

1−α α log(pα + p1−α + p− + p− + p0 )

(63)

+1

−

Then DR,α (µ∥ν) =



s α−1



+ DKL (µ∥ν) = s(1 − γ) log pp− s   X + −d DHS,β (µ∥ν) = 1 − β( pp− ) Pd d=dβ

DTV (µ∥ν) =

s  X

 + −d 1 − ( pp− ) Pd

d=1

31

(64) (65)

(66)

where Pd is the distribution defined by Pd := Pye∼µ [∥e y − y ′ ∥0 − ∥e y − y∥0 = d]   X s n n = p++ p−− pn0 0 n , n , n + − 0 n +n +n =s +

−

(67) (68)

0

n+ −n− =d ⌊(s−d)/2⌋

=



X

 s pl+d pl ps−2l−d l + d, l, s − 2l − d + − 0

l=max(0,−d)

(69)

Proof. loss of generality, we may coordinates so that yi ̸= yi′ for i ∈ [s], and yi = yi′ otherwise. Write NWithout Nm Nrelabel Nm m m µ = i=1 µi = i=1 ϕγ (yi ) and ν = i=1 νi = i=1 ϕγ (yi′ ) By definition, µi assigns mass p+ = 1 − γ + γ/C to yi and mass p− = γ/C to every other symbol. νi is defined similarly, swapping yi for yi′ . Tensorizing Divergences First, we point out that the Rényi divergence Equation (63) follows from Tensorization (Lemma B.6) since µ and ν decompose as product measures. In particular, we needP only understand the component-wise s divergences DR,α (µi ∥νi ) for 1 ≤ i ≤ s, and we may recover DR,α (µ∥ν) = i=1 DR,α (µi ∥νi ). For 1 ≤ i ≤ s, ′ yi ̸= yi , and so writing down the likelihood ratio for a single component takes one of three values:  p+ / p− yei = yi µi (e y)  (70) = p− / p+ yei = yi′  νi (e y)  1 otherwise. We can then compute the expectation over yei ∼ µi : " α−1 #  α−1  α−1 µi (e y) + E = p+ pp− + p− pp− + p0 + y ei ∼µi νi (e y) 1−α 1−α = pα + pα + p0 + p− − p+

from which it follows DR,α (µi ∥νi ) =



=



1 α−1



1 α−1



 log

 E

y ei ∼νi

µi (e y) νi (e y)

α−1 

1−α α log(pα + p1−α + p− + p− + p0 )

allowing us to conclude DR,α (µ∥ν) =

s X

DR,α (µi ∥νi )

i=1

=



s α−1



1−α α log(pα + p1−α + p− + p− + p0 ).

Computing DKL (µ∥ν) proceeds similarly by using Equation (70) and evaluating i h (e y) DKL (µi ∥νi ) = E log µνii(e y) y e∼µ

+ = p+ log pp− + p− log pp− +

p+ = (p+ − p− ) log p− + = (1 − γ) log pp− .

Using tensorization of KL gives the identify from Equation (64).

32

Hockey Stick Divergence To compute the Hockey Stick Divergence we must understand the entire likelihood ratio distribution µ/ν holistically. For ye ∼ ν, define the random distances δ ′ := ∥e y − y ′ ∥0 ,

δ := ∥e y − y∥0 (s)

δs := ∥e y

−y

(s)

′

∥0

(s)

δ := ∥e y

−y

′(s)

(71) ∥0

(72)

where ye(s) and y (s) are the respective projections onto the first s coordinates. Define the signed random difference d := δ ′ − δ. Notably, since y and y ′ only disagree in the first s coordinates, the difference d is determined entirely by the projection of y, y ′ , and ye onto the first s coordinates. That is, d = δ ′ − δ = δ ′(s) − δ (s) . For any given ye ∈ [C]m , we can write n Y 1[e y =y ] 1[e y ̸=yi ] δ µ(e y) = p+ i i p− = pn−δ + p−

ν(e y) =

i=1 n Y

1[e y =yi′ ] 1[e y ̸=yi′ ]

p+ i

p−

′

′

= pn−δ pδ− +

i=1

Thus the likelihood ratio µ(e y )/ν(e y ) is given by  d ′ ′ µ(e y) δ δ ′ −n −δ ′ + = pn−δ p− = pδ+ −δ pδ−δ = pp− . + p− p+ − ν(e y)

(73)

d takes values in {−s, . . . , 0, . . . , s}, and so there are exactly 2s + 1 = O(s) distinct likelihood ratio value regions. Now, from Equation (73), we would like to understand the law for d under ν. We start by expressing d as the result of a biased random walk: X d d= di , (74) i

  1 i.i.d. di ∼ 0   −1

with prob. p+ with prob. p0 with prob. p− .

(75)

We can understand the law for d using the theory of probability generating functions (PGFs). If X is a discrete integer-values random variable taking values in {−B, . . . , B} with mass function p(x), the PGF for X is defined as GX (z) := E [z x ] = x∼X

b X

p(x)z x .

x=−b

The PGF for di is thus Gi (z) = p− z −1 + p0 + p+ z. The PGF for a sum of independent random variables is simply a product the PGFs for the variables, and thus the PGF for d is given by G(z) =

s Y

Gi (z) = (p− z −1 + p0 + p+ z)s .

(76)

i=1

e by extracting the coefficient of the z d term, in this case computed as We recover the probability Pd = Pye∼ν [d = d]   X s n n de [z ]G(z) = p++ p−− pn0 0 (77) n , n , n + − 0 n +n +n =s e

+

−

0

n+ −n− =d

where the inner probability corresponds to choosing n+ choices of p+ , n− choices of p− , and n0 choices of p0 in the random walk. Knowing the law for d under ν, we recover O(s) regions of constant likelihood ratio, one for each d, and each of which has likelihood ratio (p+ /p− )d . To compute the Hockey Stick divergence, we must also understand the law for d under µ, defined by e Qd := Pye∼µ [d = d]. (78) 33

Luckily, moving from ν to µ under a given ye is straightforward to understand. Using the same random walk formulation gives inverted step probabilities, and pushing through the PGF H gives H(z) = G(1/z). Extracting coefficients, we see that Qd = P−d . (79) Moreover, Pd itself admits a certain multiplicative symmetry simplifying the expression further. For a fixed n+ , n− satisfying n+ − n− = −d, we have   n+   n− n n p− + p++ p−− pn0 0 = pp− p− p pn0 0 (80) + p+  n+ −n− n n + (81) = pp− p−+ p+− pn0 0  −d n n + = pp− (82) p−+ p+− pn0 0 . From Equation (82) we can simply swap the labels of n− and n+ to get the constraint n+ − n− = d, and plugging into Equation (68) and combining Equation (79) gives us the identity Qd = P−d  −d + = pp−

(83) 

X

s n n p + p − pn0 n+ , n− , n0 + − 0

n+ +n− +n0 =s n+ −n− =d

=



p+ p−

−d



Pd .

(84)

(85)

All that remains is to integrate the divergence loss µ − βν over the region Ωβ := {ỹ ∈ [C]n : µ(e y ) > βν(e y )}. Defining the sets Ωd := {e y ∈ [C]n : δ ′ − δ = d} for each −s ≤ d ≤ s, we see that {Ωd }sd=−s partitions the outcome space, and in particular integrating µ − βν over Ωβ can be done by integrating over each Ωβ ∩ Ωd and taking the sum. Since the likelihood ratio is constant on each Ωd , this amounts to isolating the d satisfying (p+ /p− )d ≥ β and summing the corresponding masses. We see that log(β) log(p+ /p− )   log(β) ⇐⇒ d ≥ + 1. log(p+ /p− )

(p+ /p− )d > β ⇐⇒ d >

Defining dβ := ⌊log(β)/ log(p+ /p− )⌋ + 1, we conclude DHS,β (µ∥ν) =

s X

(Pd − βQd )

(86)

d=dβ

=

s  X

 + −d 1 − β( pp− ) Pd

(87)

d=dβ

TV Distance

The TV distance follows directly from setting β = 1 in Equation (65) and observing that dβ = 1.

The Flipping Measure of Definition G.5 has an interesting history. It is essentially a C-ary randomized response [Warner, 1965], well-studied in both the DP and randomized smoothing literatures [Mironov, 2017, Lee et al., 2019, Bojchevski et al., 2020, Dvijotham et al., 2020, Zhang et al., 2022]. Mironov [2017] computes the s = 1, C = 2 case; see Table II in that work. The general Rényi divergence Equation (63) appears in Appendix A.10 of Dvijotham et al. [2020], but they do not derive the corresponding DHS,β divergence which can yield tighter certificates via Theorem A.3. Lee et al. [2019] and Zhang et al. [2022] both operate implicitly with the Hockey Stick divergences by way of the Neyman-Pearson Lemma characterization of optimal certificates, although these works elude an efficient closed-form expression and instead compute with a runtime-suboptimal partitioning algorithm with runtime O(d3 + k 2 d2 ) (the practical impacts of which are discussed in [Dvijotham et al., 2020]). Bojchevski et al. [2020] consider flipping measures and identify the O(s) likelihood ratio partition structure that allows us to obtain the closed-form Equations (65) and (66), but do not explicitly write down the closed-form divergence. 34

Definition G.6 (Gaussian–Flipping Measure). Let m, n ∈ N, an integer alphabet size C ≥ 2, σ ∈ R+ , and γ ∈ [0, 1]. For j ∈ [C], define the flipping measure ϕγ (j) := (1 − γ)ej + γ Unif([C])

(88)

on [C]. Given x ∈ Rm and y ∈ [C]n , the associated Gaussian–Flip measure is the product measure on Rm × [C]n µ := N (x, σ 2 Im ) ⊗

n O

ϕγ (yi ).

(89)

i=1

We say that two Gaussian–Flip measures on the same space Rm × [C]n and same parameters σ, γ, with data (x, y) and (x′ , y ′ ), respectively, are (r, s)-adjacent if ∥x−x′ ∥2 =r σ

∥y − y ′ ∥0 = s.

and

(90)

The Gaussian–Flipping measure of Definition G.6 has two main applications within our framework. First, it allows joint smoothing of features and labels for dirty-label data poisoning adversaries. Second, it allows smoothing over feature spaces that combine continuous feature representations with discrete ones, for example of the form X = Rm × K n for some discrete space K. In such a setting a data sample can be noised by applying continuous noise (e.g., Gaussian) to the continuous features and discrete noise (e.g., flipping) to the categorical features. Theorem G.5 (Divergences for Adjacent Gaussian–Flipping Measures). Let µ = N (δ, σ 2 Im ) ⊗

n O

ν = N (δ ′ , σ 2 Im ) ⊗

ϕγ (yi ),

i=1

n O

ϕγ (yi′ )

i=1

be (r, s)-adjacent Gaussian–Flip measures on Rm × [C]n . Define p+ := 1 − γ + Cγ , p− := Cγ , p0 := (C−2) C γ. For −s ≤ d ≤ s, let Pd be the law of Equation (68) and define the tilted threshold βd := β



p+ p−

−d

,

β > 0.

(91)

Then s αr2 1−α α + p1−α + log(pα + p− + p− + p0 ) 2 α−1 r2 + DKL (µ∥ν) = + s(1 − γ) log pp− 2 s      X DHS,β (µ∥ν) = Pd Φ 2r − logrβd − βd Φ − 2r − logrβd − (1 − β)+ DR,α (µ∥ν) =

DTV (µ∥ν) =

d=−s s X

    −d   + + + Pd Φ 2r + dr log pp− − pp− Φ − 2r + dr log pp−

(92) (93) (94)

(95)

d=−s

Proof. Rényi and KL divergences. Applying tensorization (Lemma B.6), the result follows by adding the Gaussian values of Theorem G.2 and the flipping values of Theorem G.4. Hockey-stick divergence. Apply Lemma G.3 with the flipping block as the first factor. Under the flipping factor of µ,
e HS,β (µ∥ν) = P Pd D e HS,β N (x, σ 2 Im )∥N (x′ , σ 2 Im ) , the likelihood ratio equals (p+ /p− )d with probability Pd , so D d d log βd log βd r r where the Gaussian term is Φ( 2 − r ) − βd Φ(− 2 − r ). Subtracting (1 − β)+ gives Equation (94). TV Divergence. The TV Divergence bound follows from taking β = 1 in Equation (94).

G.3

Worst-case Uniform parameters

In this appendix we derive the worst-case Uniform noise adjacency parameter under different ℓp constraints. Luckily, Q |x −x′ | Uniform noise admits a low-dimensional adjacency parameter θ = 1 − i (1 − i2γ i )+ (Definition G.2). By the 35

proof of Theorem G.1, Df (µ∥ν) = (f (0) + f ′ (∞))θ for every generator f , which is nondecreasing in θ. Hence, the optimization problem Equation (37) is always maximized at the maximum attainable θ. This reduces the problem to maximizing θ under an ℓp constraint. Write ∆ := x − x′ . For a budget ∥∆∥p ≤ ε, write ti := |δi |/(2γ) and η = ε/(2γ). Define the quantity g(t) := − log(1 − t) for t < 1,

g(t) := ∞ for t ≥ 1. (96) Pm Pm Pm so that − log(1 − θ) = i=1 g(ti ). Evidently θ is nondecreasing in i=1 g(ti ), so we seek to maximize i=1 g(ti ) subject to the constraint ∥t∥p ≤ η. If η ≥ 1, the adversary can shift one coordinate by 2γ, in which case the supports are disjoint, in which case θ = 1 for every p. We therefore assume η < 1. Theorem G.6 (Worst-case Uniform parameter). Let η < 1, and write θp⋆ := sup{θ(x, x′ ) : ∥x − x′ ∥p ≤ ε} for Uniform measures on Rm with radius γ. Define Φp := − log(1 − θp⋆ ). Then θp⋆ = 1 − e−Φp , where 1. Φ1 = g(η), attained at t = ηe1 ; 2. Φ∞ = mg(η), attained at t = η1; 3. for 1 < p < ∞ and m ≥ 2, we have m1−1/p η ≤ Φp ≤ m1−1/p η + mmax(0,1−2/p)

η2 . 2(1 − η)

(97)

Proof. We start with the case p = 1. Since g is convex with g(0) = 0, for any a, c with a + c < 1, we have a c g(a) ≤ a+c g(a + c) and g(c) ≤ a+c g(a + c), so that g(a) + g(c) ≤ g(a + c). In particular, if t is nonzero in more than one coordinate, we can obtain a larger objective sumi g(ti ) by merging coordinates. Via inductive argument, the objective is maximized at t = ηe1 . The corresponding maximum is g(η). Now, the case when p = ∞. This case is easy, since g is increasing in each coordinate, we need only maximize each coordinate independently to obtain g(t) = mg(η). P Finally, the case when 1 < p < ∞. For 0 ≤ t < 1, we have the series representation g(t) = j≥1 tj /j, which P gives the bound g(t) ≤ t + 12 j≥2 tj = t + t2 /(2(1 − t)). Every coordinate satisfies ti ≤ ∥t∥ ≤ η, so m X

g(ti ) ≤ ∥t∥1 +

i=1

∥t∥22 . 2(1 − η)

By Hölder’s inequality, ∥t∥1 ≤ m1−1/p ∥t∥p and ∥t∥2 ≤ mmax(0,1/2−1/p) ∥t∥p , giving the upper bound. For the lower bound, we can take ti = ηm−1/p so that ∥t∥p = η. We conclude that m X

g(ti ) = mg(ηm−1/p ) ≥ m1−1/p η,

i=1

where the final inequality uses that g(s) ≥ s.

G.4

Worst-case Laplace parameters

To bound worst-case divergences for Laplace noise, we must solve Equation (37) applied to Theorem G.3. Unlike other noises like Gaussian or Uniform, the adjacency parameter for Laplace noise is the list-valued t in Equation (53). Concretely, in this appendix we attempt to solve (or bound)  τf⋆ (ε, p) = sup Df (µt ∥ν) : t ∈ Rm η := ε/b. (98) ≥0 , ∥t∥p ≤ η , Throughout this appendix we write ν := Lap(0, b)⊗m and µt for the measure centered at bt, and take b = 1. We summarize our findings here. The ℓ1 and ℓ∞ cases are solvable exactly for all f -divergences. For ℓ∞ , the argument is straightforward: every divergence is monotone in each coordinate t, so is maximized at t = η1. The result for ℓ∞ is stated in Theorem G.7. For ℓ1 , the divergence is maximized when the adversary concentrates their perturbation in a single coordinate. The result for ℓ1 is stated in Theorem G.8. 36

Technical lemmas We first present some technical lemmas which will help us understand the structure of Laplace noise. Lemma G.4 (Coordinate-wise monotonicity). For 0 ≤ t ≤ t′ , (Lap(t, 1), Lap(0, 1)) ⪯ (Lap(t′ , 1), Lap(0, 1)). In particular, (µt , ν) ⪯ (µt′ , ν) whenever t ≤ t′ coordinate-wise. profiles at every β > 0, which are determined by Proof. By Equation (38) it suffices to compare the Hockey-stick √ Equation (58) as DHS,β (Lap(t, 1)∥ Lap(0, 1)) = [(1 − βe−t/2 )+ − (1 − β)+ ]+ . By inspection, this quantity is nondecreasing in t for every β, which gives the first claim. The second claim follows from the first by applying Lemma G.2 for each coordinate. The following technical lemma characterizes the Hockey-stick behavior under an ℓ1 constraint when the adversary splits the perturbation between two coordinates. Lemma G.5. Let s, t > 0 and write η := s + t. Let µ(s,t) , ν be (s, t)-adjacent Laplace measures on R2 . Then, for every β ∈ (e−η , eη ), p β e HS,β (µ(s,t) ∥ν) = 1 − βe−η/2 (1 + ∆), D ∆ := 21 min{ℓ, s, t, η − ℓ}, ℓ := η+log , (99) 2 e HS,β (µ(s,t) ∥ν) = 1 − β for β < e−η and 0 for β ≥ eη . In particular, ∆ ≥ 0, so D e HS,β (µ(s,t) ∥ν) ≤ while D −η η e HS,β (µηe ∥ν) for every β > 0, with equality if and only if β ∈ D / (e , e ). 1

/ (e−η , eη ), the corresponding results hold since |log Λ| ≤ η almost surely by Theorem G.3. Proof. First, when β ∈ −η η Fix β ∈ (e , e ), and write µs := Lap(s, 1) and µt := Lap(t, 1) for the marginals of µ(s,t) , ν0 := Lap(0, 1) for the common marginal of ν, and Λt for the likelihood ratio of (µt , ν0 ). Applying Lemma G.3 to µ(s,t) , ν (with µt as the first factor), we have e HS,β (µ(s,t) ∥ν) = E [D e HS,β/Λ (µs ∥ν0 )], D t µt

where by Equation (58),   Λt ≤ βe−s , 0, p −s/2 e DHS,β/Λt (µs ∥ν0 ) = 1 − β/Λt e , βe−s ≤ Λt ≤ βes ,   1 − β/Λt , Λt ≥ βes .

(100)

Since Λt ∈ [e−t , et ], the branches of Equation (100) entering into the expectation depend on s and t. The first line applies exactly when βe−s ≥ e−t ; that is, ℓ ≥ s, and the third exactly when βes ≤ et ; that is, ℓ ≤ t. By Theorem G.3, we have Λt = e−t Vt , so under ν0 , it follows that Λt is distributed with mass 12 at e−t , mass 12 e−t t at e , and density 14 e−t/2 λ−3/2 on (e−t , et ). Integrating the measure gives, for x ∈ (e−t , et ], Pν0 [Λt ≥ x] = 12 e−t/2 x−1/2 , E [Λt ; Λt ≥ x] = 1 − 12 e−t/2 x1/2 ,

ν0

1/2

E [Λt ; Λt < x] = e−t/2 ( 12 + 14 log(xet )),

ν0

1/2

E [Λt ] = Z1/2 (µt ∥ν0 ) = ζ1/2 (t).

ν0

We have four meaningful cases depending on the ordering of s, t, ℓ. Case t ≤ ℓ ≤ s

In this case only the second line of Equation (100) applies, so p p −s/2 −t/2 p e HS,β (µ(s,t) ∥ν) = 1 − βe−s/2 E [Λ1/2 D βe e (1 + 2t ) = 1 − βe−η/2 (1 + 2t ). t ]=1− ν0

In this case min{ℓ, s, t, η − ℓ} = t.

37

Case ℓ ≥ max(s, t)

In this case the first line of Equation (100) applies on {Λt ≤ βe−s } and the second on the rest, so p −s e HS,β (µ(s,t) ∥ν) = E [Λt ; Λt ≥ βe−s ] − βe−s/2 E [Λ1/2 ] D t ; Λt ≥ βe ν0 ν0 p −η/2 = 1 − βe (1 + 12 (η − ℓ)).

In this case min{ℓ, s, t, η − ℓ} = η − ℓ. Case ℓ ≤ min(s, t)

In this case the third line of Equation (100) applies on {Λt ≥ βes } and the second on the rest, so p s s e HS,β (µ(s,t) ∥ν) = 1 − βe−s/2 E [Λ1/2 D t ; Λt < βe ] − βP[Λt ≥ βe ] ν0 p = 1 − βe−η/2 (1 + 2ℓ ).

In this case min{ℓ, s, t, η − ℓ} = ℓ. Case s ≤ ℓ ≤ t In this case µ(s,t) and µ(t,s) are related by swapping coordinates. By Lemma B.3 both sides of Equation (99) are symmetric in s and t, so we can reduce to the case t ≤ ℓ ≤ s handled above. In all four cases ∆ √ > 0 since s, t > 0 and 0 < ℓ < η. For the final comparison, Equation (58) with t = η gives e HS,β (µηe ∥ν) = 1 − βe−η/2 for β ∈ (e−η , eη ). This is Equation (99) when ∆ = 0. D 1 The property that ultimately allows us to characterize Laplace noise for ℓ1 adversaries is Schur convexity. Recall that we say t is majorized by t′ , written t ≺ t′ , if the two have equal sums and every prefix sum of the coordinates of t when listed in nonincreasing order is at most the corresponding sum for t′ . If the prefix-sum condition holds but the sums of t and t′ may differ, we say t is weakly submajorized by t′ , written t ≺w t′ . Lemma G.6 (Schur convexity in Laplace parameter). For every generator f , the map t 7→ Df (µt ∥ν) is Schur convex. In particular, if t ⪯ t′ , then (µt , ν) ≺ (µt′ , ν). Proof. Suppose t ≺ t′ . As a property of the majorization relation, it holds that there exists a sequence t = t(0) ≺ (k) (k) t(1) ≺ · · · ≺ t(n) = t′ such that each adjacent pair differs only a single pair of coordinates i, j and with ti + tj = (k+1)

(k+1)

+ tj ti . Thus, it is sufficient to prove the result only for the case when t, t′ differ in a single coordinate pair with ti + tj = t′i + t′j and min(ti , tj ) ≥ min(t′i , t′j ). Applying Equation (99) on the two swapped coordinates for t and t′ , with η = ti + tj and fixed β, we see that ∆ ≥ ∆′ because ∆ is nondecreasing in min(·, ·). In particular, the pair (ti , tj ) generates a smaller Hockey-stick divergence under Lemma G.5. Finally, applying Lemma G.2, we conclude that (µt , ν) ⪯ (µt′ , ν). ℓ∞ constraints Theorem G.7 (Worst-case ℓ∞ Laplace parameter). Let t ∈ Rm ≥0 with ∥t∥∞ ≤ η. Then (µt , ν) ⪯ (µη1 , ν), and the t maximizing Equation (98) is t⋆ = η1 and τf⋆ (ε, ∞) = Df (µη1 ∥ν) for every generator f . In particular ⋆ τR,α (ε, ∞) = mκα (η),

(101)

⋆ and τHS,β (ε, ∞) is obtained by convolving m copies of the distribution in Equation (55) at t = η and evaluating Equation (14).

Proof. The constraint ∥t∥∞ ≤ η is exactly t ≤ η1 coordinate-wise. By Lemma G.4, we have (µt , ν) ⪯ (µη1 , ν). Equation (101) follows by evaluating Equation (56) at t = η1. ℓ1 constraints Theorem G.8 (Worst-case ℓ1 Laplace parameter). Let t ∈ Rm ≥0 with ∥t∥1 ≤ η. Then, (µt , ν) ⪯ (Lap(bη, b), Lap(0, b)). In particular, the t maximizing Equation (98) is t⋆ = ηe1 and, for every β ≥ 1,   p ⋆ ⋆ τHS,β (ε, 1) = 1 − βe−ε/2b , τR,α (ε, 1) = κα (η), (102) +

with β < 1 determined by Lemma B.4. 38

Proof. Suppose first that ∥t∥1 = η exactly. Then t ≺ ηe1 , since the two have equal sums and the largest partial sum of ηe1 is η, which dominates every partial sum of t. Lemma G.6 therefore gives (µt , ν) ⪯ (µηe1 , ν). If instead ∥t∥1 = η ′ < η, apply the above to obtain (µt , ν) ⪯ (µη′ e1 , ν) and then Lemma G.4 in the single coordinate to obtain (µη′ e1 , ν) ⪯ (µηe1 , ν). Since µηe1 and ν agree in all coordinates but the first, canceling common factors (Lemma B.2(iii)) identifies the pair (µηe1 , ν) with the scalar pair (Lap(bη, b), Lap(0, b)), proving the first claim. Equation (102) then follows from Equations (56) and (58) evaluated at t = ηe1 . ℓp constraints For 1 < p < ∞, no single t maximizes the Hockey-stick divergences of all orders simultaneously. We instead bound every admissible t by a dominating parameter, which concentrates the perturbation into as few coordinates as the budget allows. 1−1/p Theorem G.9 (Dominating ℓp Laplace parameter). Let 1 < p < ∞ and t ∈ Rm ⌉ ≥0 with ∥t∥p ≤ η. Let K := ⌈m ⋆ := ⋆ ⋆ ⋆ and t η (1K , 0m−K ). Then (µt , ν) ⪯ (µt , ν). In particular, τf (ε, p) ≤ Df (µt ∥ν) for every generator f , and the right-hand side is obtained by convolving K copies of the distribution in Equation (55) at t = η. For p = 2, √ K = ⌈ m ⌉.

Proof. Every coordinate satisfies tj ≤ ∥t∥p ≤ η, and by Hölder’s inequality ∥t∥1 ≤ m1−1/p ∥t∥p ≤ Kη. Listing t in nonincreasing order, the sum of its j largest coordinates is therefore at most jη for j ≤ K and at most Kη for j > K. These are exactly the prefix sums of t⋆ , so t ≺w t⋆ . As a property of weak majorization, there exists u with t ≤ u coordinate-wise and u ≺ t⋆ . Lemma G.4 gives (µt , ν) ⪯ (µu , ν), and Lemma G.6 gives (µu , ν) ⪯ (µt⋆ , ν).

39

Related documents

• A Certified Robustness Framework for Backdoor Poisoning Attacks using $f$-Divergences#1458088
• Adversarial Benchmarks and BenchDoor Attacks: Exploiting Benchmark Incentives for Backdoor Attacks#1403329
• Adversarial Benchmarks and BenchDoor Attacks: Exploiting Benchmark Incentives for Backdoor Attacks#1394167
• Dataset Security for Machine Learning: Data Poisoning, Backdoor Attacks, and Defenses#1317996
• CertMoE: Robustness Certification for Mixture-of-Experts LLMs via Routing-Aware Smoothing#1414000