Certified Robustness to Data Poisoning in Gradient-Based Training
Authors: Philip Sosnin
Mark Niklas Mueller
Maximilian Baader
Calvin Tsay
Matthew Robert Wicker
Venue: Accepted by TMLR ()

Abstract: Modern machine learning pipelines leverage large amounts of public data, making it infeasible to guarantee data quality and leaving models open to poisoning and backdoor attacks. Provably bounding the behavior of learning algorithms under such attacks remains an open problem. In this work, we address this challenge by developing the first framework providing provable guarantees on the behavior of models trained with potentially manipulated data without modifying the model or learning algorithm. In particular, our framework certifies robustness against untargeted and targeted poisoning, as well as backdoor attacks, for bounded and unbounded manipulations of the training inputs and labels. Our method leverages convex relaxations to over-approximate the set of all possible parameter updates for a given poisoning threat model, allowing us to bound the set of all reachable parameters for any gradient-based learning algorithm. Given this set of parameters, we provide bounds on worst-case behavior, including model performance and backdoor success rate. We demonstrate our approach on multiple real-world datasets from applications including energy consumption, medical imaging, and autonomous driving.

Published in Transactions on Machine Learning Research (09/2025)
Certified Robustness to Data Poisoning in Based Training
Philip Sosnin
p. 0..osninn25@kkmmriill..cc uk
Deportment of Computing, Imperial College London, United Kingdom
Mark N. Müller
mark.waeller Dinf ethzz.ck
Department of Computer Science, ETH Zurich, Swilzerland
LogicStar.oa ni, Switzerland
Maximilian Baader
mbuader@inf ethe..ck
Department of Computer Science, ETH Zurich, Switzerland
Calvin Tsay'
c. c.tsaay@tmmerrill.ccc uk
Department of Computing, Imperial College London, United Kingdom
Matthew Wicker
m.uscckr@@impriial.ccm uk
Department of Computing, Imperial College London, United Kingdom The Alan Turing Institute, United Kingdom
Reviewed on OpenReview: https: openreview. net/ forum? id= fWHf
Abstract
Modern machine learning pipelines leverage large amounts of public data, making it infea- sible to guarantec data quality and leaving models open to poisoning and backdoor attacks. Provably bounding the behavior of learning algorithıns under such attacks remains an open problem. this work, we address this challenge by developing the first framework pro- viding provable guarantees on the behavior models trained with potentially manipulated data without modifying the model or learning algorithm. In particular, our framework cer- tifies robustness against untargeted and targefed poisoning, for bounded and unbounded manipulations of the training inputs and labels. Our method leverages convex relaxations to over-approximate the set of all possible parameter updates for a given poisoning threat model, allowing us to bound the set of all reachable param- eters for any gradient-based learning algorithm. Given this set of parameters, we provide bounds on worst-case behavior, including model performance and backdoor success rate. We demonstrate our approach on multiple real-world datasets from applications including energy consumption, medical imaging, and autonomous driving.
well backdoor attacks,
1 Introduction
To achieve state-of-the-art performance, modern machine learning pipelines involve pre-training on massive, uncurated datasets; subsoquently, models finc-tuned with task-specific data to maximize downstream performance (Han et al. 2021). Unfortunately, the datasets used in both steps are potentially untrustworthy and of such scale that rigorous quality checks become impractical.
Yet, adversarial manipulation, i.e, poisoning allacks, affecting even a small proportion of data used for either pre-training or fine-tuning can lead to catastrophic model failures (Carlini et al. 2023). For instance, Yang et al. (2017) show how popular recommender systems on sites such as YouTube, Ebba, and Yelp can be easily manipulated by poisoning. Likewise, Zhu al. (2019) show that poisoning even 1% of training data
"Equal contribution

---

Published in Transactions on Machine Learning Research (09/2025)
can lead models to misclassify targeted examples, and Han et al. (2022) use poisoning to selectively trigger backdoor vulnerabilities in lane detection systems to force critical errors.
Despite the gravity of the failure modes induced by poisoning attacks, counter-measures are generally attack- specific and only defend against known attack methods (Tian et al.) 2022.. The result aptack-specific defenses an effective "arms race" between attackers trying to circumvent the latest defenses and counter- measures being developed for the new attacks. In effect, even best practices, i.e, using the latest defenses, provide no guarantees of protection against poisoning attacks. To date, relatively few approaches have sought provable guarantees against poisoning attacks. These methods are often limited in scope, e.g., applying only to linear models (Rosonfeld et al. 2020; Steinhardt et al. 2017). only providing approximate guarantees (Xie et al. 2022), or only working for some limited poisoning settings (Rosenfeld et al. 2020). Other approaches partition datasets into hundreds or thousands of disjoint shards and then aggregate predictions such that the effects of poisoning are provably limited (Levine & Feizi 2020 Wang et al., 2022). In contrast, our
goal in this work is not to produce a robust learning algorithm, but to efficiently analyze the sensitivity of (un-modified) algorithms. We provide an extensive díscussion of related works in Appendix A
This Work: General Certificates of Poisoning Robustness. We present an approach for computing sound certificates of robustness to poisoning attacks for any model trained with first-order optimization methods, e.g., stochastic gradient descent or Adam (Kingma & Ba 2014 Unlike prior works we highlight that our guarantees of robustness apply lo general poisoning adversaries, i.e,, adversaries able to arbitrarily and adaptively modify a bounded number of training data and labels. Our analysis applies to given model and training algorithm (without need for modification) and therefore can be used to analyze and investigate the poisoning robustness of various proposed defenses and benchmarks. The proposed strategy begins by treating various poisoning attacks as constraints over an adversary's perturbation 'budget' in input and label spaces. Following the comprehensive taxonomy by Tian al. (2022), we view the objective of each poisoming attack as an optimization problem. Though our framework general we explicitly consider three objectives: (i) untargeted attacks: reducing model performance to cause denial-of-service, (ii) targeted attacks: compromising model performance on certain types of inputs, and (iii) backdoor attacks: leaving the model performance stable, but introducing a trigger pattern that causes crrors at deployment time. Our approach then leverages convex relaxations of both the training problem and the constraint sets defining the threat model to compute a sound (but potentially incomplete) certifionte that bounds the impact of the poisoning attack. In summary, this paper makes the following key contributions:
A framework for soundly bounding the reachable parameter space of gradient-trained models under poisoning attacks.
An instantiation of our framework based on hound-propagatte including a novel extension of the CROWN algorithm to the interval-parameter setting.
Based on the above, series of formal proofs that allow us to bound the effect of poisoning attacks with respect to arbitrary attack goals.
An extensive empirical evaluation demonstrating the effectiveness of our approach.
2 Background: Poisoning Attacks
This section describes the capabilities of the poisoning attack adversaries that we seek to certify against. We consider two distinct threat models of bounded and unbounded poisoning attacks, which we define below. Typical threat models additionally specify the adversary's 's system knowledge; however, we aim to upper bound a worst-case adversary, so assume unrestricted access to all training information inchuding model architecture and initialization, data, data ordering, hyper-parameters, etc.
Notation. We denote a machine learning model as a parametric function f with parameters 0, feature space x E RMin, and label space y y. The label space y may be discrete (e.g. classification) or continuous (e.g. regression). We operate in the supervised learning setting with a dataset D = {(x(), yy))) We denote the parameter initialization 0' and training algorithm M as M(S 0', D), ie.. given model,
2

---

Published in Transactions on Machine Learning Research (09/2025)
Algorithm 1 ABSTRACT GRADIENT TRAINING FOR COMPUTING VALID PARAMETER-SPACE BOUNDS
input: f model, 8' init. params., dataset, epochs, a learning rate, allowable dataset perturbations (poisoning adversary), optional clipping parameter.
2: output: 0 nominal SGD parameter, [0z.0r] valid parameter space bound on the influence TT
3: 0 -8;; 0v), + 0")
// Initialize nominal perameter and interval bounds.
4: for E-many epochs do
5: for each batch B C D do
6:
A
Clip VoL (F))
// Compute nominal SGD porameter update (clipping optional).
B
(E.))EB
7:
a00
// Update the nominnal parameter.
8:
AO
Σ (0.9)EB
Clip
V&L (f(()) [ T(B). (02, 0u)
1/ Define the set of descent
B
directions under T.
9: Compute A02, AlU s.t. AlL - 20 v Adu
AΔO Ao
1/ Bound possible descent directions under T.
10: 0z. + Or. adtu; By + 0u aL0,
// Update parameter interval reachable under T.
11: end for
12:
end for
13: return 10z, 0v]
initialization, and data, the training function M returns a "trained" parameterization 0. Finally, we assume the loss function is computed element-wise from the dataset, denoted as ((fx)())))))))
Bounded Poisoning Attacks. In a bounded attack setting, an adversary is permitted to perturb subset of the training data in both the feature and label spaces, with the perturbation constrained by a given norm. Specifically, the adversary may select up to data-points, modifying their features by most in the ny-norm and their labels by at most v in the fy-norm. In classification setting, label-flipping attacks can be considered under this attack model by setting v = 1,4 = 0. Given a dalaset D and an adversary (n, e, 4) we denote the set of potentially poisoned datasets as T (n.c.p.a))) (D).
Unbounded Poisoning Attacks. It may not always be realistic to assume that the effect of poisoning adversary is bounded. A more powerful adversary may be able to inject arbitrary data-points into the training data set, for example by exploiting the collection of user data. In this "unbounded" attack setting, we use T denote the set of all possible datasets derived from nominal dataset D by adding and/or removing up to n data-points.
To simplify our exposition below, we use denote cases where either the bounded or unbounded adver- saries may be applied. We refer to T interchangeably as either the poisoning adversary, or set of potentially poisoned datasets.
Poisoning Attack Goals. Following the taxonomy of poisoning attacks from Tian al. (2022), attacks can be broadly classified into three categories based on adversarial goals. Untargeted poisoning aims to degrade the overall performance of the model, potentially causing denial-of-service by corrupting training data, such flipping sample labels injecting noise into feature representations. In contrast, targeted poisoning attacks focus on manipulating the model's behavior for specific inputs while maintaining normal performance on others, effectively forcing misclassification of particular samples. A more advanced form of targeted poisoning is backdoor attacks, where adversaries implant hidden triggers in training data that activate only when specific patterns appear in test inputs, making the attack harder detect. For cach attack goal, one can formulate an adversarial objective function, which we aim to bound using our certification procedure. We discuss potential formulations and their certification in Appendix B
3

---

Published in Transactions on Machine Learning Research (09/2025)
3 Methodology
This section introduces novel approach for certifying robustness against poisoning attacks by deriving sound bounds on the set of model parameters that can be reached under a given attack. We begin by demonstrating how robustness can be certified using such parameter-space bounds. Next, we present a general algorithm that bounds the effect of adversarial manipulations on model parameters, yiclding an interval that encompasses all reachable training parameters. Finally, we instantiate our framework with novel formulation of CROWN-style bounds, enabling the sound computation of the necessary quantities.
3.1 Parameter-Space Certificates of Robustmess
The key concept behind our framework is to bound the parameters obtained via the training function M(f,0', given the adversary T(D). Before detailing the method, we first formalize our definition of parameter-space bounds and how they can be translated into formal, provable guarantees poisoning robustness.
Definition 3.1 (Valid parameter-span bounds). An interval over parameters [0",00] is a valid parameter- space bound on a poisoning ad adversary, T(D), if:
0 O', D) 10 0")
VD T(D)
(1)
where the interval domain is interpreted element-wise.
Definition 3.1 captures a super-set of all the parameters the learning algorithm can reach given the inter- vention of an adversary defined by T(D). Next, we assume the existence of an objective function J that the adversary attempts to maximize; we give concrete realizations of J for well-studied adversarial goals including backdoor attacks in Appendix B Regardless of the form of J we have that:
Theorem 3.2. Let [0,,00] be valid parameler-space bound for poisoning adversary T. Then, for given adversarial gool J, one can compute sound upper bound (t.e. certificate) by optimizing over the parameler space, rolher than dalaset space:
J (FMULUDD)) DET
max (f").
max
(2)
0010"
Theorem 3.2 cnables us to translate our bounds on parameter-space bounds directly to bounds on the adversarial goals. Unlike the intractable maximization over datasets (left hand side of Equation (2), the maximization over parameter space (right hand side of Equation (2) can be efficiently upper-bounded using popular certification techniques (Adams et al. 2023 Wicker et al.) 2020 2023). The final result is a guarantee that there does not erist a poisoning adversary who is more successful than the bound in Theorem 3.2
3.2 Abstract Gradient Training for Valid Parameter Space Bounds
In this section, we provide a high-level framework, which we term Abstract Gradient Training (AGT), for computing parameter bounds that respect Definition 3.1 Our framework applicable to any first-order training algorithn[] but here choose to focus vanilla SGD to ease exposition. We consider the standard SGD update step:
- 0
a
VoL(F
(3)
B
where B C D is the sampled batch at the current iteration. The function M 0', D), in the simplest case, iteratively applies the update (3) for fixed, finite number of iterations starting from 0 = 0'. Therefore, to bound the effect of a poisoming attack, iteratively apply bounds update (3). In Algorithm D we present a general framework for computing parameter-space bounds for SGD given a poisoning adversary T, and observe the following:
Including those based on momentum or adaptive moments.
4

---

Published in Transactions on Machine Learning Research (09/2025)
1. Lines 6-7 compute the standard SGD update rule.
2. Lines 8-10 compute bounds on the SGD update rule, taking into account poisoning of the current batch and all previously seen batches.
Starting from 0 = g =',, the reachable parameter interval is maintained over every iteration of the algorithm, giving us the following result:
Theorem 3.3. Algorithm | returns valid parometer-spaee bounds (D) poisoning adversary for stochas- tic gradient descent training procedure Mff, ,
Algorithm alllws us bound the effect of a bounded adversary without modifying the original training procedure. On the other hand, consider unbounded adversaries we must include the additional clipping operation, highlighted in purple. This limits the maximum contribution of any arbitrarily added or perturbed data-points, which is a requirement for computing closed bounds.
3.3 Bounding the Descent Direction.
The main challenge of Algorithm is in bounding the set AO, which is the set of all possible descent directions at the given iteration under 'T. In particular, B E T (B) represents the effect of the adversary's perturbations on the current batch, while the reachable parameter interval Ó E [0+,0U] represents the worst- case effect adversarial manipulations to all previously seen batches. Exactly computing the set Ae is not computationally tractable, so we instead soek over-approximate element wisc bounds that can be computed efficiently within the training loop.
Notationally, we will refer to per-sample gradient terms as 866) = v (z()), g()),, and use the symbols 8(0 and 6 to represent sound bounds on these terms (we handle the computation of these terms Section 3.4 We seek to soundly aggregate these per-sample gradient bounds to obtain an interval over-approximation [A0", A of the descent direction A0, which in turn is combined with the parameter interval [Ø', 0"1 each training iteration. The exact aggregation mechanism depends on the form of the poisoning adversary. Below we present an efficient over-approximation of the descent direction for the bounded adversary in the following theoren
Theorem 3.4 (Bounding AO for bounded adversary). Tet B = (())), be a batch of size b, and let the model parameters 0 lie within the interval [04 0. Given bounded adversary specified by (n, P. v, a), the SGD porameter update A Σ VoL (f (z(1),, ((0) is bounded element-wie above and below by
B
AQ 1
SEMax
(1))
+
(4)
i=1
AO
SEMin b
(5L)
(()
+
L
(5)
n2
i=1
for any batch B E Timep.n (B). Here,
and ((i) are sound bounds capturing the effect of previous adversariol manipulations, satisfying
(1)
L < 8 < 51 for all 5 in the set
(V (f)
y10) v(0) 10 10t 0un).
(0".0")
(6)
8 and b10) are bounds on the combined effect of previous poisoning and the worst-case adversarial
perturbations of the i-th data-point in the current batch, satisfying 2()) 3 s 80) for all 8 in
E [0t. 807 [|x(() lp S
V&C (F(3),
(7)
( و0ا
2The analogous theorem for the unbounded adversary can found Appendix D
5

---

Published in Transactions on Machine Learning Research (09/2025)
The operations SEMax, and SEMin, correspond to taking the sum of the element-wits top/bottom-a ele- ments over each index of the input vectors This theorem, and its constituent operations, are discussed in more detail in Appendix F.4
The update rule in Theorem 3.4 accounts for past poisoning via gradient bounds (0 o06' valid for all reach- able 0. We then bound the impact of current-batch adversarial attacks by selecting the n points exhibiting the worst-case gradient bounds under poisoning (6%) "6"). To soundly bound the descent direction for all parameters, this update is applied independently to each parameter index. This approach, while computa- tionally efficient for propagating interval enclosures, introduces a potentially loose over-approxinatio,, as the n worst-case points for one parameter index are unlikely to be the same for all indices.
3.4 Computation of Sound Gradient Bounds
This section presents a novel algorithm for bounding optimization problems of the form
i E [ 04]
max & min VoL (0). s.t. 2.0.0
|x x p I y U
(8)
Bounds on these optimization problems are exactly the per-sample gradient bounds dU, de required by Theorem 3.4 Noting that problems of the form (6) can be recovered by setting v = 0, we focus solely on this more general case in this section.
Computing the exact solution to 8 is, in general, a non-convex and NP-hard optimization problem (Katz jet al. 2017 However, we require only over-approximate solutions; while these can introduce (potentially significant) looseness to the reachable parameter set, they will always maintain soundness. Future work could invostigate exact solutions, c.g., via mixod-integer programming (Huchette ct al., 2023 Tsay et al., 2021). Owing to their tractability, our discussion focuses on the novel linear bound propagation techniques we develop for abstract gradient training. We present only brief overview of our approach in this section; full details can be found in Appendix
Neural Networks. While the algorithm presented in $3.2 is general to any machine learning model trained via stochastic gradient descent, we focus our discussion on neural network models for the remainder of the paper. We first define neural network model f R Ro with K layers and parameters
0 (W)),80)) as:
((k] = ((k) b(), (b)) = (3(A)
where 200) xr, (z) 2(K), and is the activation function, which we take to be ReLU.
Cortification of Ncural Networks. Solving problems of the form min f. || øI, S c} for noural net- works has been well-studied in the context of adversarial robustness certification. However, optimizing over inputs, labels and parameters, e.g,, min 1 E (04,0%), ||x - øllp S,, loyllyy1 راl S S²} is much less well- studied, and to-date similar problems have appeared primarily in the certification of probabilistic neural networks WWicker et al. 2020). Our approach decomposes (8) into forward and backward passes through the neural network. We first compute bounds on the network's 's output for given input, label, and parameter domain, then back-propagate these bounds to obtain gradient bounds.
Interval Arithmetic. For ease of exposition, we will represent interval matrices with bold symbols i.e., A [Ar, Au ] R=,, We define @, @ O to represent interval matrix addition, matrix multiplication and element-win wise multiplication, respectively, such that
A B E A +
B YAE A, B B,
x B E A Ø
B
AA A B & B,
Ao B E
A
O
BJ
VA A, B E B.
We assume that b. b, we take SEMin / Max with respect to min (b, m) instead.

---

Published in Transactions on Machine Learning Research (09/2025)
We denote interval vectors as (aL, au] with analogous operations. We note that all matrix operations involving intervals can be computed using standard interval arithmetic techniques in at most 4x the cost of a standard matrix operation, for example using Rump's algorithm Rump (1999). Interval arithmetic is commonly applied as a basic verification or adversarial training technique by propagating intervals through the intermediate layers of neural network (Gowal et al. 2018).
Forward Pass Bounds. Mirroring developments in robustness certification of neural networks, we provide novel, explicit extension of the CROWN algorithm (Zhang et al., 2018) to account for interval-boudedd weights. The standard CROWN algorithm bounds the outputs of the m-th layer of a neural network by back-propagating linear bounds over each intermediate activation function to the input layer. We extend this framework to interval parameters, where the weights and biases involved in these linear relaxations are themselves intervals. We note that linear bound propagation with interval parameters has been studied previously in the context of floating-poin sound cortification (Singh et al.) 2019). In the interest of space, we present only the upper bound of our extended CROWN algorithm here, with the full version presented in Appendix C
Proposition 3.5 (Explicit upper bounds of neural net f with interval parameters). Given m-layer neural network function f R R whose unknown parameters lie in the intervals b(8) ((0) and ((k) E w(k) for k = 1, ,,.... m, there exists an erplicil funclion
81/ (0,)) A (1:m), b(1=)) = = x +
(1) (B(K) + +
(9)
k=1
such that Vo E æ
fz(x) S max { (-) (() E A b* b(t)
(10)
where x is a closed imput domain and A (0rm), A (1im) are the equivalent weights and biases of the linear upper bounds, respectively. The bias term A (1am) is explicitly computed based on the linear bounds on the activation functions. The weight A (0mm) lies in an interval A (0rm) which is computed in an analogous way to standard, non-interval CROWN.
Given the upper bound function f,(() (-) defined above and intervals over all the relevant variables, we can compute the following closed-form global upper bound:
7 = max
A
Σ (R) + A
In the above, bold symbols are used to denote interval domains, with @ and @ being interval matrix multiplication and addition, respectively. Interval arithmetic, and its application to our CROWN-style bounds, is discussed in detail in Appendix
Backward Pass Bounds. Given bounds on the forward pass of the neural network, we can bound the backward pass (the gradients) of the model. We do this by extending the interval arithmetic based approach of Wicker et al. 2202)) (which bounds derivatives of the form OC (k)) to additionally bound the derivatives w.r.t. the parameters. In the below, we assume that sound bounds on the output logits g(K) of the network have been obtained, e.g. using our CROWN-style bounds.
First, we back-propagate intervals over 3" (the label) and {(K) (the logits) to compute an interval over (k))g(K), the gradient of the loss w.r.t. the logits of the network. The procedure for computing this interval is described in Appendix C for selection of loss functions. We then use interval bound propagation to back-propagate this interval through the network to compute intervals over all gradients:
12 = (W(4)) T &
Oc
ac
OC
OC
H
(k) L
(k)
0g(k)'
0g(h)
=
(2(k)
0C
OC
(k-
(k- (k-1)) 2
1)
OC
OC
@W(k)
(*())
ab(k)
02(k)
7

---

Published in Transactions on Machine Learning Research (09/2025)
R- 200
0.15
50
0.05
(a) Features only (e= 0.01, oc, x= 0=
(b) Festures ouly (rx = 10. v= 0,g=0)
(c) Labels only 10= 0, 0c, 1,
(d) Labels features (e = p=o.,=....
Figure 1: Regions where our certification holds for classifier trained on the halfmoons dataset. The white line shows the decision boundary the model, and each colored region indicates the area for which we cannot certify predictions for the given adversary.
where (-) is the Heaviside function, and @ is the (interval) element-wise product. The resulting gradient intervals suffice to bound all solutions to our original optimization problem (B). That is, the gradicnts of the network lie within these intervals for all ((k), W 6(*) b(4), || - x=1 p S e, and lly - y"11 S v. These bounds are exactly those required compute & dr, 8z, and 8y needed to bound the descent direction Theorem 3.4
3.5 Algorithm Analysis and Discussion
Figure ] visualizes the resulting worst-case decision boundaries for a simple binary classifier consisting of neural network with hidden layer of 128 neurons. In this classification selting, label poisoning results Jooser bounds than feature space poisoning, with
producing bounds of approximately the same width 200. This is due to the relatively large interval introduced by label flipping attack y E {0,1), 1}, compared to interval of width introduced in fealure-space allack. We also emphasise that Algorithm assumes at most poisoned points per batch, rather than per dataset. In regression settings, label poisoning is relatively weaker than feature poisoning for a given strength e v, since the feature-space interval propagates through both the forward and backward training passes, while the label only participates in the backward pass. This effect particularly pronounced in deep networks, since interval / CROWN bounds tend weaken exponentially with depth (Mao al. 2023 Sosnin & Tsay 2024
Computing Certificates of Poisoning Robustness. Algorithm ! returns valid parameter-space bounds (02, Gu] for given poisoning adversary. To provide certificates of poisoning robustness for specific query point x, we first. bound the model output (xx for all 0 E [0r,, 0vl using the bound-propagation procedure described above. In classification settings, the robustness of the prediction can then be certified by checking if the lower bound on the output logit for the target class is greater than the upper bounds of other classes (i.e. (=)] 2 (=) j). If this condition satisfied, then the model always predicts class j at the point x for all parameters within our parameter-space bounds, and thus this prediction is certifiably robust poisoning. Details on computing bounds on other adversary goals can be found in Appendix B
Comparison to Interval Bound Propagation. The CROWN algorithm in $3.4 not strictly tighter than interval bound propagation (IBP). Specifically, the non-associativity of Couble-interwee matrix multi- plication leads to significantly different interval sizes depending the order in which the multiplications are performed: IBP performs interval matrix multiplications in a 'orwards'' ordering, while CROWN uses a 'backwards' ordering. Empirically, we observe that CROWN tends to be tighter for deeper networks, while IBP may outperform CROWN for smaller networks. In our nunerical experiments, we compute both CROWN and IBP bounds and take the element-wise tightest bound.
Combined Forward and Backward Pass Bounds. The CROWN algorithm can be applied to any composition of functions that can be upper- and lower-bounded by linear equations. Therefore, it is possible
8

---

Published in Transactions on Machine Learning Research (09/2023)
Feature poison (e 0.01)
Feature poison (n 1000)
Label poison (2== 0.05)
Label poison (n 1000)
0.6
10000
0.05
10000
2
0.2
0.4
5000
0,02
5000
0.1
MSE + Cortified Bounds
0.2
0.0
Depth (d)
Width (ar)
Batch Size (8)
Learning Rate (a)
0.6
256
100
0,02
0.4
1000
10
64
10000
0.005
0.2
0.0
50
100
150
100
150
0
50
150
100
150
Training Iteration
Figure 2: Mean squared error bounds the UCT-houseelectric dataset for a bounded adversary. Top: Effect of adversary strength. Bottom: Effect of model/training hyperparameters (with = 100, 0.01, 0). Where not stated, p q = co, d 1, w 50, b = 10000, 0.02.
to consider both the forwards and backwards passes in a single combined CROWN pass for many loss functions. However, linear bounds on the gradient of the loss function tend to be relatively loose, e.g., linear bounds on the softmax function may be orders-of-magnitude looser than constant [0, 1] bounds (Wei et al. 2023). As a result, we found that the tightest bounds were obtained using IBP CROWN on the forward pass and TBP on the backward pass.
Computational Complexity. The computational complexity of Algorithm depends on the method used to bound the gradients. In the simplest case, IBP can be used to compute bounds on the gradients in 4x the cost of standard forward and backward pass. Likewise, most 4 times the cost of the original CROWN algorithm. For an m layer network with neurons per layer and n outputs, the time complexity of the original CROWN algorithm is Omm2n²) Zhang et al. 2018 We further note that the SEMin/ / SEMax operations can be computed in ((b) for each index and in practice can be efficiently parallelized using GPU-basod implementations. In Appendix G we observe that AGT typically incurs a runtime of less than 2x standard training. In summary, Abstract Gradient Training using TBP has time complexity equivalent to standard neural network training (O(bmn?) for each batch of size b), but with our tighter, TROWN-based. bounds the complexity is O(bm²n²) per batch.
CROWN bounds admit a cost of at
Limitations. While Algorithm is able to obtain pardmearreettr space bounds for any gradient- based training algorithun, the tightness of these bounds depends on the exact architecture, hyperparameters and training procedure used. In particular, bound-propagation between successive iterations of the algorithm assumes the worst-case poisoning at each parameter index simultaneously, which not realizable by any practical poisoning attack. Therefore, obtaining non-vacuous guarantees with our algorithm often requires training with larger batch-sizes and/or for fewer epochs than is typical. Additionally, certain loss functions, such as multi-class cross entropy, have particularly loose interval relaxations. Therefore, AGT obtains relatively weaker guarantees for multi-class problems when compared to regression or binary classification settings. We hope that tighter bound-propagation approaches, such as those based on more expressive abstract domains, may overcome this limitation in future works.
4 Experiments
In this section we experimentally validate the effectiveness of our proposed approach. We provide complete details of hyper-parameters and run-times of our experiments in Appendix G For classifica- tion tasks, we report the certified accuracy, which is our certified lower bound on the accuracy of any model poisoned with the given attack; likewise, certified mean squared error refers to upper bound

---

Published in Transactions on Machine Learning Research (09/2025)
the loss in regression tasks. A code repository to reproduce experiments can be found at: wwwphsssnnoosonnnnnnooooooo.osis psssssin/nnnnoo Alstriattrradienn
UCI Regression (Houschold Power Consumption). We first consider a relatively simple regression model for the household electric power consumption ("howsellccriee) dataset from the UCI repository (He-- brail Berard 2012) with fully connected neural networks and MSE loss function. Figure 2 (top) shows the progression of the nominal and worst/bester MSE (computed for the test set) for 1x50 neural network and various parameterizations of poisoning attacks. As expected, we observe that incrcasing cach of n, e, and results in looser performance bounds. We nole that the setting of 10000 corresponds to 100% of the dataset being potentially poisoned.
Figure 2 (bottom) shows the progression of bounds on the MSE (computed for the test set) over the training procedure for a fixed poisoning atlack (n 100, e = 0.01) and various hyperparameters of the regression model. In general, we observe that increasing model size (width or depth) results in looser performance guarantees. As expected, increasing the batch size improves our bounds, the number of potentially poi- soned samples remains fixed and their worst-case effect is 'diluted'. Increasing the learning rate accelerates both the model training and the deterioration of the bounds.
Comparison of CROWN vs IBP. To evalu- ate the tightness of our proposed CROWN-based bounds relative standard interval bound propa- gation, we use the UCI dataset setting described above to train models of varying sizes. We apply Algorithm 1 with either IBP or CROWN-based for- ward pass bounds and compare the resulting pa- ramoter space intervals. Figure 3 reports the av- erage bound width at the end of training, computed as [8] ( 0.)). We find that our CROWN- based bounds yield tighter parameter intervals than IBP for deeper models. However, as previously dis- cussed, CROWN is not strictly tighter in this setting and we observe that IBP can outperform CROWN for shallower but wider architectures. Accordingly, in all other experiments, we compute both sets of bounds at each training iteration and take their element-wist minimum to obtain the tightest parameter intervals.
CROWN
IBP
Avg. Bound Widsh
10
10"
10-
10 5
10
6
d=1
1
d- d- 3
64
128 87
256
Model Depth (d)
Model Width (w)
Figure 3: Comparison of AGT with CROWN vs IBP bounds for various model sizes trained on the UCI dataset (d = and w 64 where not stated).
Baseline Comparison. We compare our ap- proach with DPA Levine & Feizi (2020) and ran-
1.0
domized smoothing (RS) Rosenfeld et al. (2020) on
Certified Accuracy
MNIST. To make the approaches comparable, we only consider label-flippigg attack (g 0, 1) on the MNIST dataset. In label-only poisoning set-
0.8
ACT (x- eo)
ACT (x- 0.2)
0.6
ACT (x- 0.1)
0.4
RS (g 0.05)
tings, it is common to use unsupervised learning ap- proaches on the (assumed clean) features prior to training classification model (e.g. SS-DPA (Levine & Feizi (020)): Therefore, we first project the data into a 32-dimensional feature space using PCA. Fig- ure | illustrates the certified accuracy using this methodology. Before discussing the quantitative comparison, we highlight the significant qualitative differences between the baselines and our approach. Randomized smoothing only applies to linear mod- cls and the label flipping regime whereas our ap- proach is general. DPA applies to generalized poisoning adversaries, but requires both substantial overhead (relative to AGT) and modification of the learning algorithm. In Figure 4 DPA ensemble of 3000
0.2
DPA (A 3000)
0.0
50
100
150
200
# Label Flips (n)
Figure 4: Certified accuracy the MNIST dataset under label-fiipping attack. Curves for Deep Par- tition Aggregation (DPA) and Randomized Smooth- ing (RS) reproduced from Figures 1 of Levine & Feixi (2020) and Rosenfeld et al. (020 respectively.
10

---

Published in Transactions on Machine Learning Research (09/2025)
Feature Polsoning (Bounded Adversary)
Label Poisoning (Bounded Adversary)
Festure + Label Polsoning (Unbounded Adversary)
Feature Poisoning
(Bounded Adversary)
Certifed Accuracy
1.00
Backdoox Accuracy
1.00
0.75
0.75
0.01
0.50
0.02
0.1
0.008
Ine tuned accuracy Prodininel menurmey
0.000
0.00
0.00
0
200
400
6000
200
400
600
0
200
400
600
0
200
400
600
Attack Size (n)
Attack Size (n)
Attack Size (n)
Attack Size (n)
Figure 5: Certified accuracy (left) and backdoor accuracy (right) for a binary classifier fine-tuned on the Drusen class of OCTMNIST for an attack size up to 10% poisoned data per batch (b = 6000, = 00, 0,v = 1). Dashed lines show the nominal accuracy of each fine-tuned model.
models thus incurring 3000 times the space costs compared to normal training. Quantitatively, AGT can outperform randomized smoothing, but only for small number of label flips. However, there is no setting in which AGT outperforms DPA.
MedMNIST Image Classification. Next, we consider fine-tuning classifier trained on the retinal OCT dataset (OCTMNIST) (Yang et al. 2021), which contains four classes-onc normal and three abnormal. The dataset is unbalanced, and we consider the simpler normal vs abnormal binary classification setting. We consider the 'small' architecture from Gowal et al. 2018), comprising two convolutional layers of width 16 and 32 and a dense layer of 100 nodes, and the following fine-tuning scenario: the model is first pre-trained without the rarest class (Druson) using the robust training procodure from Wicker ct al. (2022), so that the resulting model is robust to feature perturbations during fine-tuning. We then assume Drusen samples may be poisoned and add them as new abnormal class to fine-tune the dense layer, with mix of 50% Drusen samples (b = 6000 with 3000 Drusen) per batch.
Figure shows how increasing the strength of the potential poisoning attack worsens the bound on prediction accuracy. With feature-only poisoning, a poisoning attack greater than c = 0.02 over n R 500 samples produces bounds worse than the prediction accuracy of the original pre-trained model. With an unbounded label and feature poisoning adversary, the bounds are weaker, as expected. Higher certified accuracy can be obtained by increasing the clipping parameter K, at the cost of nominal model accuracy (Figure) 5 center right). With label-only poisoning, the certificates are relatively stronger, as the training procedure requires approximately n 2 600 poisoned samples for the prediction accuracy bound to reach the original pre-trained model's accuracy. The setting of n = 600 corresponds to 20% of the Drusen data per batch being mis-labeled.
Finally, we consider a backdoor attack setting where the c used at training and inference times is the same. The model is highly susceptible to adversarial perturbations at inference time even without data poisoning, requiring only e 0.009 to reduce the certified backdoor accuracy to 50%. As the strength of the adversary increases, the accuracy that we are able to certify decrcases. We note that tighter verification algorithms can be applied at inference time to obtain stronger guarantees.
Fine- Fine-Tuning PilotNet. Finally, we fine-tune model that predicts steering angles for autonomous driving given an input image (Bojarski et al., 2016). The model contains convolutional layers of 24, 36, 48, and 64 filters, followed by fully connected layers of 100, 50, and 10 nodes. The fine-tuning setting is similar to above: first, we pre-train the model on videos 2-6 of the Udacity self-driving car datasel We then fine-tune the dense layers on vidco 1 (challenging lighting conditions) assuming potential label poisoning.
Figure 6 shows the bounds on mean squared error for the video data and visualizes how the bounds translate to the predicted steering angle. We again see that fine-tuning improves accuracy on the new data,
11

---

Published in Transactions on Machine Learning Research (09/202))
Pre-tzained
Fine-Suned
0.04
0.05
Certified MSB
X- 0.02
0.03
True lahel
Fine-tuned
0.02
Pre-trained
200
400
600
Labels Poisoned (n)
Figure 6: Left: Fine-tuning PilotNet on unseen data with a bounded label poisoning attack (q oc). Right: We plot the stecring angle prediction before and after fine-tuning (n 300, g 00, 0.01). The angle of the lines indicates the predicted steering angle.
but also that the MSE bounds deteriorate as the number of potentially poisoned samples increases (Figure left). The rate of deterioration depends strongly on poisoning strength v.
5 Conclusions
We proposed a mathematical framework for computing sound parameter-space bounds on the influence of poisoning attack for gradient-based training. Our framework defines generic constraint sets represent general poisoning attacks and propagates them through the forward and backward passes of model training. Based the resulting parameler-space bounds, we provided rigorous bounds the effects of various poison- ing attacks. Finally, demonstrated our proposed approach to be effective tasks including autonomous driving and medical image classification.
References
Steven Adams, Andrea Patane, Morteza Lahijanian, and Luca Laurenti. Ban-dp: robustness certification of bayesian neural networks via dynamic programming. In International Conference on Machine Learning, pp. 133-151 PMLR, 2023.
Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp- 2154 2156, 2018
Battista Biggio, Konrad Rieck, Davide Ariu, Christian Wressnegger, Igino Corona, Giorgio Giacinto, and Fabio Roli. Poisoning behavioral malware clustering. In Proceedings of the 2014 workshop on artificial intelligent and securily workshop, pp. 27 36, 2014.
Mariusz Bojarski, Davide Del Testa, Daniel Dworakowski, Bernhard Firner, Beat Flepp, Prasoon Goyal, Lawrence Jackel, Mathew Monfort, Urs Muller, Jiakai Zhang, et al. End to end learning for self-driving cars. arXiv preprint orXiv:1604.077. 07316 2016.
Elena Botoeva, Panagiotis Kouvaros, Jan Kronqvist, Alessio Lomuscio, and Ruth Misener. Efficient verifi- cation of relu-based neural networks via dependency analysis. Tn Proceedings of the AAAT Conference on Artificial Intelligence, volume 34, pp. 3291 3299, 2020.
Rudy R Bunel, llker Turkaslan, Philip Torr, Pushmeet Kohli, and Pawan K Mudigonda. A unified view of piccewise lincar neural network verification. Advances Neural Information Processing Systems, 31, 2018.
Nicholas Carlini, Matthew Jagielski, Christopher Choquette-Choo, Daniel Palcka, Will Pcarce, Hyrum Anderson, Andreas Terzis, Kurt Thomas, and Florian Tramèr. Poisoning web-scale training datasets is practical. Xixiv preprint Xrxiv2230 10X1:22302.10144 2023.
12

---

Published in Transactions on Machine Learning Research (09/2025)
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song. Targeted backdoor attacks on deep learning systems using data poisoning. Xiv preprind orXie 712.05526, 2017.
Timon Gehr, Matthew Mirman, Dana Maacsler-Coheen Petar Tsankov, Swarat Chaudhuuri and Martin Vechev. Ai2: Safety and robustness certification of neural networks with abstract interpretation. In 2018 IEEE symposium on security and privacy (SP), pp. 3-18. IEEE, 2018.
Lukas Gosch, Mahalakshmi Sabanayagam, Debarghya Ghoshdastidar, and Stephan Günnemann. Prov- able robustness of (graph) neural networks against data poisoning and backdoor attacks. arXiv preprint arXiv:2407.10867, 2024.
Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust. models. arXiv preprint 1rx: 12715, 2018.
Tianyu Gu, Brendan Dolan-Gavite and Siddharth Garg. Badnets: Identifying vulnerabilities in the machine learning model supply chain. arXiv preprint wrXYc:1708.066733 2017.
Xingshuo Han, Guowen Xu, Yuan Zhou, Xuehuan Yang, Jiwei Li, and Tianwei Zhang. Physical backdoor attacks to lane detection systems in autonomous driving. In Proceedings of the 30th ACM International Conference on Multimedia, pp. 2957 2968, 2022.
Xu Han, Zhengyan Zhang, Ning Ding, Yuxian Gu, Xiao Liu, Yuqi Huo, Jiezhong Qiu, Yuan Yao, Ao Zhang, Liang Zhang, et al. Pre-trained models: Past, present and future. AI Open, 2:225-250, 2021.
Georges Hebrail and Alice Berard. Individual Household Electric Power Consumption. UCI Machine Learning Repository, 2012. DOI: http:///d0ii.r//102444333 222442//58KKK4. C58K54.
Sanghyun Hong, Varun Chandrasekaran, Yigitcan Kaya, Tudor Dumitras, and Nicolas Papernot. On the effectiveness of mitigating data poisoning attacks with gradient shaping. arXiv preprint ar arXiv:2002.14497, 2020.
Hanxun Huang, Xingjun Ma, Sarah Monazam Erfani, James Bailey, and Yisen Wang. Unlearnable examples: Making personal data unexploitable. arXiv preprinl ar Xrxv:21001.4480 2021.
Jocy Huchette, Gonzalo Muñoz, Thiago Scrra, and Calvin Tsay. When deep learning meets polyhedral theory: A survey. arXiv preprint ar arXiv:2305.00241 2023.
Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smi solver for verifying deep neural networks. In Computer Aided Verification: 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part T 30, pp- 97-117. Springer, 2017.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv:1412.60 6980, 2014.
arXiv preprinl
Alexander Levine and Soheil Feizi. Deep partition aggregation: Provable defense against general poisoning attacks. Xix preprint or arXi::2006.144 14768, 2020.
Suyi Li, Yong Cheng, Wei Wang, Yang Liu, and Tianjian Chen. Learning to detect malicious clients for robust federated learning. arXiv preprint arXim:2002.0021 2020.
Yuhao Mao, Mark Niklas Müller, Marc Fischer, and Martin T. Vechev. Understanding certified training with interval bound propagation. CoRR,
10426, 2023. doi: 10.48550/ARXIV 10466. URL
https://doi. org/ 10. 1115:10...55534.4 (tt/500/arxiv..oo www.aa.wwww.......... 2306. 10426
Mark Niklas Müller, Franziska Eckert, Mare Fischer, and Martin Vochev. Certified training: Small boxes are all you need. arXiv preprinl arX1v22210004871,, 2022.
Luis Muñoz-Gonzáler Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamce, Emil C Lupu, and Fabio Roli. Towards poisoning of deep learning algorithms with fack-gradien optimization. In Proceedings of the 10th ACM workshop on artificial intelligence and securily, pp. 27 33, 2017.
13

---

Published in Transactions on Machine Learning Research (09/2025)
James Newsome, Brad Karp, and Dawn Song. Paragraph: Thwarting signature learning by training mali- ciously. In Recent Advonces in Intrusion Delection: 9th International Symposium, RAID 2006 Hambury, Germany, September 20-22, 2006 Proceedings 9, pp. 81 105. Springer, 2006.
Keivan Rezaci, Kiarash Banihashem, Atoosa Chegini, and Soheil Feizi. Run-off election: Improved provable defense against data poisoning allacks. In International Conference on Machine Learning, pp- 29030 29050. PMLR, 2023.
Elan Rosenfeld, Fara Winston, Pradeep Ravikumar, and Zico Kolter. Certified robustness to label-flipping attacks via randomized smoothing. In International Conference Machine Learning, pp. 8230 8241. PMLR, 2020.
Siegfried M Rump. Fast and parallel interval arithmetic. BIT Numerical Mathemalics, 39:534 554, 1999.
Gagandeep Singh, Timon Gehr, Markus Püschel, and Martin Vechev. An abstract domain for certifying neural networks. Proc. ACM Program. Long., 3(POPL) jan 2019. doi: (0.1145/3290354.
Philip Sosmin and Calvin Tsay, Scaling trollers using bounds tightening, aiviv preprint arXiv:2403.110 17874, 2024.
programming for certification of neural network con-
Jacob Steinhardt, Pang Wei W Koh, and Percy S Liang. Certified defenses for data poisoning attacks. Advances in neural information processing systems, 30, 2017.
Zhiyi Tian, Lei Cui, Jie Liang, and Shui Yu. A comprehensive survey on poisoning attacks and countermea- sures in machine learning. ACM Computing Surveys, 55(8):1-35, 2022.
Calvin Tsay, Jan Kronqvist, Alexander Thebelt, and Ruth Misener. Partition-based formulations for mixed- integer optimization of trained relu neural networks. Advances in neural information processing systems, 14:3068-3088 2021.
Wenxiao Wang, Alexander Levine, and Soheil Feizi. Improved certified defenses against data poisoning with (deterministic) finite aggregation. In International Conference on Machine Learning, pp. 22769-22783. PMLR, 2022.
Dennis Wei, Haoze Wu, Min Wu, Pin- Yu Chen, Clark Barrett, and Eitan Farchi. Convex bounds on the softmax function with applications to robustness verification, 2023.
Matthew
Wicker, Xiaowei Huang, and Marta Kwiatkowska. Feature-guided black-box safety testing of deep neural networks. In Tools and Algorithms for the Construction and Analysis of Systems: 24th International Conference, TACAS 2018, Held Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, Thessaloniki, Greece, April 14-20, 2018, Proceedings, Part 24, pp. 408-426. Springer, 2018
Matthew Wicker, Luca Laurenti, Andrea Patane, and Marta Kwiatkowska. Probabilistic safety for bayesian neural networks. In Conference on uncertainty artificial intelligence, pp. 1198- PMI.R, 2020.
Matthew Wicker, Juyeon Heo, Luca Costabello, and Adrian Weller. Robust explanation constraints for neural networks. arXie preprint wrXi::2212.08500 2022.
Matthew Wicker, Andrea Patane, Luca Laurenti, and Marta Kwiatkowska. Adversarial robustness certifica- tion for bayesian neural networks. aixiv preprint arXiv:236. 13614, 2023.
Chulin Xie, Yunhui Long, Pin-Yu Chen, and Bo Li. Uncovering the connection between differential privacy and cortified robustness federated learning against poisoning attacks. arXiv preprint arXiv:2209.0400 2022.
Guolei Yang, Neil Zhenqiang Gong, and Ying Cai. Fake co-visitation injection attacks recommender systems. In NDSS, 2017.
14

---

Published in Transactions on Machine Learning Research (09/2025)
Jiancheng Yang, Rui Shi, and Bingbing Ni. MedMNIST classification decathlon: A lightweight AutoML benchmark for medical image analysis. In IEEF 18th International Symposium on Biomedical Imaging (ISBI), pp. 191- 195, 2021.
Huan Zhang, Teu Weng, Pin-Yu Chen, Cho-Jui Hsich, and Luca. Daniel. Efficient neural network robust- ness certification with general activation functions. Advances in neural information processing systems, 31, 2018.
Chen Zhu, W Ronny Huang, Hengduo Li, Gavin Taylor, Christoph Studer, and Tom Goldstein. Transferable clean-label poisoning atlacks deep neural nets. In Internalional conference machine learning, pp- 7614-7623. PMLR, 2019.
15

---

Published in Transactions on Machine Learning Research (09/2025)
A Related Works
Data Poisoning. Poisoning attacks have existed for nearly two decades and are a serions security concern Biggio & Roli 2018 Biggio el al. 2014 Newsome et al., 2006). In Gonzzler el al. (017 the authors formulate a general gradient-based attack that generates poisoned samples that corrupt model performance when introduced into the dataset (now termed, untargeted attack). Backdoor attacks manipulate a small proportion of the data such that, when specific pattern is seen at test-time, the model returns a specifie,
erroneous prediction [Chen et. al.
(2017); Gu et al. (2017); Han et. al. (2022); Zhu et al. (2019) Popular defenses are attack specific, c.g., generating datasets using known attack strategics to classify and reject
potentially poisoned inputs [Li et al. 2020 Alternative strategies apply noise or clipping to mitigate
certain attacks (Hong et al.) 2020).
Poisoning Defenses. General defenses to poisoning attacks seek provide upper-bounds on the effec- liveness of any atlack strategy. In this area, Steiihaartt et al. (2017) provide such upper-bounds for linear models trained with gradient descent. Rooenfeld et al. (2020) present certified upper-bound the ef- fectiveness of &2 perturbations on training labels for linear models using randomized smoothing. [ie et al. (2022) observe that differential privacy, which usually covers addition or removal of data points, can also provide statistical guarantees in some limited poisoning settings.
Certified Poisoning Robustness Relative to inference-time adversarial robustness (also referred as evasion attacks), less attention has been devoted to provable guarantees against data poisoning adversarics. Existing methods for deterministie certification of robustness to poisoning adversaries involve design of learning process with careful partitioning and ensembling such that the resulting model has poisoning robustness guarantees (Levine & Feizi, 2020 Wang et al. 2022 Rezaci et al.) 2023). We refer to these methods as "aggregation" methods. In contrast, our approach is method for analysis and certification of standard, unmodified machine learning algorithms. Aggregation approaches have been shown to offer strong guarantees against poisoning adversaries albeit at a substantial computational cost including: storing and training thousands of models on (potentially disjoint) subsets of the dataset and the requirement to evaluate each of the potentially thousands of models for each prediction; additionally, these methods require that one have potentially thousands of times more data than is nocessary for training single classifier. By designing algorithrs to be robust to poisoning adversaries aggregation based approaches are able Lo scale to larger models than are considered in this work (Levine & Feizi 2020 Wang et al. 2022 Rezaei et al., 2023). Yet, the computational cost of our approach, in the simplest case, is only four times that of standard training and inference and we do not require that one has access to enough data to train multiple well-performing models. Furthermore, our approach enables reasoning about backdoor attacks, where these partitioning approaches cannot. We finally highlight that the method presented in this paper is orthogonal ortiogonal/complemennee complementaryy to the partitioning approach, and thus future works may be able to combine the two effectively.
A concurrent work (Gosch et al. 2024p also develops certificates for neural networks under data poisoning by leveraging the Neural Tangent Kernel to establish an equivalence of a neural network with Support Vector Machine. In contrast to this work, the certificates presented in (Gosch et al.) 2024] are deterministic only under the assumption of infinite-width networks, and can only handle a restricted set of threat models compared to those described in Scction 2
Certified Adversarial Robustness. Sound algorithms (i.e., no false positives) for upper-bounding the effectiveness of inference-time adversaries well-studied for trained models (Gehr et al. 2018 and training
models for robustness (Gowal et al. 2018 Müller et al. 2022). These approaches typically utilize idcas from
formal methods (Kalz el al.) 2017 Wicker el al.) 2018)) or optimization (Boloeva et al. 2020 Bunel et al., 2018 Huchette et al. 2023). Most related to this work are strategies that consider intervals over both model inputs and parameters (Wicker et al. 2020). as well as some preliminary work on robust explanations that bound the input gradients of a model Wicker et al. (2022). Despite these methodological relationships, none of these methods directly apply to the general training setting studied here.
16

---

Published in Transactions on Machine Learning Research (09/2025)
B Poisoning Attack Goals and Certified Bounds
In this appendix, we define common poisoning attack objectives and demonstrate how our certification procedure can be used to bound the success of such attacks. We focus on the three primary objectives introduced in Section 2 and note that this is not exhaustive list of adversarial goals.
B.1 Poisoning Attack Goals
Untargeted Poisoning. Untargeted attacks aim to prevent training convergence, leading to an unusable model and denial of service (Tian et al. 2022). We formulate the goal with respect to some dataset of interest {(x(*) " )- In the case of denial of service, this is usually taken to be the training dataset, or some subset therein. The denial of service attack objective can thus be written as
max D'ET
Σ (x!)))
(11)
where L is taken to be the training loss function. We can certify robustness to this kind of attack using sound upper bound on this optimization problem.
Targeted Poisoning. Targeted poisoning is more task-specific and is typically evaluated over the test dataset. Rather than simply attempting to increase the loss, the adversary seeks to make model predictions fall outside 'safe' set outputs, S(x(1, ))) In the simplest case, this can the defined as the set of predictions matching the ground truth. The safe can be more specific however, i.c., mistaking a lanc marking for person safe, but not vice versa. The adversary's 's objective is given by:
k
max Σ D'ET I
((M()0))"))))) & ((x(0) ())
(12)
As before, sound upper bound 12 bounds the success rate of any targeted poisoning attacker. Note that with h = 1 we recover the pointwise certificate setting studied by Rosenfeld et al. (022)). This setting also covers 'unlearnable examples', such as the attacks considered by Huang et al. (2021).
Backdoor Poisoning. Backdoor attacks deviate from the above attacks by assuming that test-time data can be altered, via a so-called trigger manipulation. By assuming that the trigger manipulation(s) are bounded (x) (e.g,, an foo ball around the input), one can formulate the backdoor attack's goal producing predictions outside safe set 5(x(0), ()) (defined as before) for manipulated inputs:
k 1 13xx* e V(x()) s.t. MM (M $ (0.0,00)
max D'ET
(13)
K
Backdoor attacks typically aim to leave the model performance on 'clean' data unchanged, which can be modeled via the dependep safe set S. Any sound upper bound to the above is a sound bound on the success rate of any backdoor attacker.
B.2 Bounding Poisoning Attack Goals
In this soction, we describe procedure for computing bounds on each the poisoning adversary's objectives. We recall from Theorem 3.2 that optimization problems with respect to an adversary T can be equivalently bounded by optimizing valid parameter space bound [0L, 007 returned from Algorithm 1
17

---

Published in Transactions on Machine Learning Research (09/2025)
Given test set ((x0) y we will write the poisoning objectives above in the following form,
J
max D'ET K
9 (MUCSD
D') ,0
(14)
i=
max DE
(00 10,00,000 2111)
(15)
k max
9 (50, (19 x00) (/10)
(16)
DE DE 000
where the function g(-) is the adversary objective for single sample. The first inequality holds by The- orem 3.2 and the second holds by relaxing the maximization over the summation. Thus, to bound the
original poisoning objectives [11], 112 and [3), it suffices to compute bounds the required quantity for each test sample independently.
Certified Predictions and Backdoor Robustness. Computing an bounds on
max 0rE(00,001
1 (z(1) & S)
(17)
corresponds to checking if 1 (x) lies within the safe set for all 0 E [0L,0%) As before, we first compute bounds fリ on f (x(()) using our CROWN-based bounds. Given these bounds and assuming multi-
class classification setting, the predictions not reachable by any model within [05,0%] are those whose logit upper bounds lie below the logit lower bound of any other class. That is, the set of possible predictions S is given by
5' fit.. 1 $t
(18)
If S' S, then max 1( (z) & S) = O.
Backdoor atlack robustness is computed in an analogous way, with the only difference being the logit bounds f" being computed over all æ E (z) and or 00, This case is also computed via our CROWN- basod bound propagation.
Denial of Service. In the case of denial of service, it suffices to bound the training loss, such the cross entropy and mean-squared-crro losses. For cross entropy loss, one compute the loss over the worst-case logits given bounds on the neural network output (from our CROWN algorithm). For mean squared error, valid upper bound is obtained by computing the loss with respect the point in the output bounds that is furthest from the true label. Bounding these loss functions is discussed in more detail in Appendix C
C Bound Propagation in Abstract Gradient Training
In this appendix, we provide a comprehensive overview of the bound-propagation procedure used to obtain gradient bounds in A bstract Gradient Training. We recall our aim of bounding which we state explicitly for neural networks below:
max or min g.g. W(.K) (CC:K)
(e)(((E),)
(k)
1. S (R) < W (k)
s.t.
U
k
K
b < (00) by (K)
k
K
g(k) W()) (k- ((k)
k
K
=(k) (3(0),
k
K
(19)
| #I,p S 6,
1y Øl1, <
f(x) (K)
2 (0)
18

---

Published in Transactions on Machine Learning Research (09/2025)
where the min maximization problem is considered element-wise. To efficiently bound this problem, we start by decomposing it into distinct sub-problems, which we bound independently. In particular, we first aim to bound the forward pass variables z(6) using our CROWN-style bounds, and then prop-ggoe these bounds using interval propagation. Each sub-problem considers only a sub-set of constraints, so the resulting bounds are valid over-approximation of the solutions to 19
In the remainder of this section, we first provide an introduction to interval matrix arithmetic, which forms the foundation of our instantiation of AGT. We then present our novel CROWN- bounds for bounding the forward pass through the neural network. Finally, describe the interval bound propagation method used to back-propagate these bounds and compute the required gradient bounds.
C.1 Interval Matrix Arithmetic
Here provide basic introduction to interval matrix arithmetic, which forms the basic building block of our CROWN-style bounds. For case of exposition, we will represent interval matrices with bold symbols i.c., A = [Ar, Av C R=1xx2, We denote interval vectors as a = (ar,, av) with analogous operations.
Definition C.1 (Interval Matrix Arithmetic). Let A = [Az, Au] and B = [Br, Bu] be intervals over matri- oes. Let (D; 0 2 represent interval matrix addition, matrix multiplication and elementwise multiplication, such that
A+ B E A BJ Ax B E A 3 B
YΑE A, B
AΛ A, B E B, A,EABEE B.
Ao E A O
B)
These operations can be computed using standard interval arithmetic techniques in at most 4x the cost of a standard matrix operation, for example using Rump's algorithm Rump (1999). Interval arithmetic is commonly applied as a basic verification or adversarial training technique by propagating intervals through the intermediate layers neural network (Gowal et al. 2018
C.2 Forward pass bounds: CROWN with Interval Parameters
In this section, we present our full extension of the CROWN algorithm ZZang et al. 2018 for neural networks with interval parameters. The standard CROWN algorithm bounds the outputs the m-th layer of neural network by back-propagating linear bounds over each intermediate activation function to the input layer. We extend this framework to interval parameters, where the weights and biases involved in these linear relaxations are themselves intervals. We note that linear bound propagation with interval parameters has been studied previously in the context of peating-poine sound certification (Singh et al. 2019).
Here, we present an explicit instantiation of the CROWN algorithm for interval parameters, which we recall from Section 3.4 in its complete form.
Proposition 3.5 (Explicit output bounds of neural network with interval parameters). Given an m-layer
neural network function f R - Rou whose unknown parameters lie in the intervals ((8) E (b) and ((k) E (k) for = I,..., m, there ezist two explicit functions
m
8 (z, (2(0m)) @(1m)) b(1:m)) 12
+
(b(t) + =6!²) 2!10) 1.:
(20)
14/ (a, (00m)) A (1:m) s(mm) A
(k) (B(0) +1!1))
(21)
such that Vr x
[x(x) 2 min {1g (I, ((0m), (1:m)) (amm),((lmn) b((lm)) ) (2(()) E (2()), 6² b0s)
fz) max {1% (2, (0.m) A (1mm) b(l=m) A119) E A .² b
19

---

Published in Transactions on Machine Learning Research (09/2025)
where a is closed input domain and (00m) A (1mm), (1mm),2((0m)) ()1m)) are the equivalent weights and biases of p
the upper and lower linear hounds, respectäuely. The bias terms A11m) @(:mm) are explicilly computed based on the linear bounds on the activation functions. The weights A A10mm) (2(0m)) lie in intervals A A00sm), S2 (0:m) which are computed in an analogous way to standard (non-interval) CROWN.
Computing Equivalent Weights and Biases. Our instantiation of the CROWN algorithm in Proposi- tion 3.5 relies on the computation of the equivalent bias terms A (1mm), (1:m)) and interval enclosures over the equivalent weights ((0m)) A (0:m), This proceeds similarly to the standard CROWN algorithm but now accounting for intervals over the parameters 6(1mm), ((1mm) of the network.
The standard CROWN algorithm bounds the outputs of the m-th layer of a neural network by back- propagating linear bounds over each intermediale activation function to the input layer. In the case of interval parameters, the sign of particular weight may be ambiguous (when the interval spans zero), mak- ing it impossible to determine which linear bound to back-propagate. In such cases, we propagate concrete bound for that neuron instead of its linear bounds.
When bounding the m-th layer of a neural network, we assume that we have pre-activation bounds ((k) E [200) [ on all previous layers on the network. Given such bounds, it is possible to form lincar bounds on any non-linear activation function in the network. For the r-th neuron k-th layer with activation function (2); we define two linear functions
(R) (x p(..) h (=) = a.r
(k) 10. (2) oUr 2 + (U.r)
such that (=) < a(2) < (z) Vz E
(K) (1,00 ur
The coefficients Uirr L,rt S (()) E R are readily (Zhang et al., 2018).
(k) (R)
computed for many common activation functions
Given the pre-activation and activation function bounds, the interval enclosures over the weights Q(0mm) (00m) are computed via. back-propagation procedure. The back-propagation is initialisod with
Q A (m) _mm, [m]] and proceeds as follows:
(R) QU
if k # 0
A (k+1) W(++1)
1.
(R) a L,
if
02 0 kf
(k+11) w
A (k-1) = (A @ wr()) @ ((1-1),
100
3.
0
kf
(k+1) 2 w(++1)
1
aLi
(R)
05
n (++)) w(++1)
3.5
(8)
i
2(++1)
W(++1)
1) (k) @ w()) o (1-11)
aua
w
3.8
0
0E
S (k+1)
W(++1
1
i 0.
where we use 0 < [] and 0 2 [1] to denote that an interval is strictly positive or negative, respectively.
Finally, the bias terms A (R) (1) for all le < m can be computed as
(k) U
if 0 < A (k+1) w(++1)
((k)
if 0 <
2 (k+1)
@ W(++1)
L1
54
1
(k)
i
A (1+1) W(++1)
(R)
(k)
ir0>
((++1) W(++1)
1j
5
(k)
A (k+1) @ W(++1)
(())
if
(k+11) W(++1)
with the m-th bias terms given by )(m)) (m)
0.
20

---

Published in Transactions on Machine Learning Research (09/2025)
Closed-Form Global Bounds. Given the two functions (), 19 (:) as defined above and intervals over all the relevant variables, we can compute the following closed-form global bounds:
2 min
0 = 1j
max A (0) J:
where min / max are performed element-wise and return the lower upper bounds of each interval enclosure. Then, we have oo S (x) S <y for all x E æ, (1k) E (()) and W E w((), which suffices to bound the output of the neural network as required to further bound the gradient the network.
C.3 Bounding the Backward Pass: Interval Bound Propagation
Turning to the backward pass, we first show how to bound the first partial derivative of the loss function given bounds from the forward pass. We then provide an interval back-propagation procodure for computing intervals over all gradients of the model.
Loss Function Bounds. Here we present the computation of bounds on the first partial derivative of the loss function required for Algorithm problem via interval arithmetic:
In particular, we consider bounding the following optimization
y'1la min max (OC (v",'') .3)) /0y" ly E "u".""].Ilv" - sv}
for some loss function L where iy" y are bounds on the logits of the model (obtained via the bound- propagation procedure), ye is the true label, and y' is the poisoned label.
Mean Squared Error Loss. Taking C (vv", = llv" -/112 to be the squared error and considering the 0o norm, the required bounds are given by:
a (y- - yy- -
St 2 (v" - vv'+
The loss itself can be upper-bounded by 10 = max ((r -1²) (v" y²)²} and lower bounded by
if y E [v4.8²] otherwise
14
(22)
min -/)) (v" 4/
Cross Entropy Loss. To bound the gradient of the eross entropy loss, we first bound the output proba- bilities p. 1Σ, exp (yj vf]] obtained by passing the logits through the softmax function:
Σ exp exp - w1)
Σ exp (w} -2²)
d =
P
The categorical cross entropy loss and its first partial derivative are given by
OC (v*.,))
L (v v') = Σ vl log
1f"
Oy*
where y is one-hot encoding of the true label. Considering label flipping attacks (g 10=0 = 1), we can bound the partial derivative by
[ - [a1%] p.¹ -
In the case of targeted label flipping attacks (c.g- only applying label flipping attacks to / from specific classes), stronger bounds can be obtained by considering the bounds only on the indices y affected by
the attack. The cross entropy loss itself is bounded by 1- E, vt logpl p 1d = v/ log
21

---

Published in Transactions on Machine Learning Research (09/2025)
Interval Back- fack-Propagation. We extend the interval arithmetic based approach of Wicker et al. (2022) which bounds derivatives of the form OC/0z(8), to additionally compute bounds on the derivatives w.r.t. the parameters. First, we back propagaee intervals over y" (the label) and g( (the logits) to compute an interval over 0c/0g(K), the gradient of the loss w.r.t. the logits of the network. The procedure for computing this interval described in Appendix C for selection of loss functions. We then use interval bound propagation back-propagate this interval through the network to compute intervals over all gradients:
0z(k-1) OL
Oc
(W)))) dc
dc &
0g(k)
02(k)
ac
11
(k) 1T
11
2
(k)
0z(k)
ac
T (1-11) (=---))) (=
0c
0c
@W())
(2(k)
kb(k)
0k(k)
where H(- is the Heaviside function, and is the element-wise product. The resulting gradient intervals
suffice to bound all solutions to our original optimization problem
(8. That is, the gradients of the network
lie within these intervals for all W E W(k), ((h) E b(kk, || x* S and 11 v0lla S v.
D Bounding the Descent Direction for an Unbounded Adversary
Theorem D.1 (Bounding the descent direction for unbounded adversary). Given nominal batch B (xx10 y/1) ) with batchsize b, porameter set (04,00] and clipping level k, the clipped SGD parameter update A Σ Clip, [oo (s (z(0), ,5(0)]] is bounded element-wise by
B
AOL = SEMin { (((0) b-n [.:m i=1 -msla) ABU =1
(SEMMax b-n
[00) i=1
nsld
(23)
for any poisoned batch B derived from B by substituting up to n. data-points with poisoned data and any [9th,0"], The terms 8() 816 are sound bounds that account for the worst case effect of additions/ /removall additions/remouals in any previous ileralions. That is, they bound the gradient given any parameter 0* E |0L, 000 in the reachable
set, i.c. for all i= 1,....,, we have 66 I 8((( 2 for any
gl0) E {Clip [ool (5 (2(1)) ( [ 10",8U1}
(24)
The operations SEMax, and SEMin, correspond to taking the sum of the element-wine top/bottom-a ele- ments over each index of the input vectors. Therefore, the update step in (23) corresponds substituting the elements with the largest / smallest gradients (by taking the sum of only the min max b-n gradients) with the minimam / mazimum possible gradient updates (-K, respectively, due to the clipping operation). Since we wish to soundly over-approxinate this operation for all parameters, we perform this bounding op- eration independently over each index of the parameter vector. This is certainly a loose approximation, as the n points that maximize the gradient at a particular index will likely not maximize the gradient of other indices. Note that without clipping, the min / max effect of adding arbitrary data points into the training data is unbounded and we cannot compute any guarantees.
Comparison with Empirical Attacks E
In this section, we compare the tightness of our bounds with simple heuristic poisoning attacks for both the CCI-houseelectric and OCT-MNIST datasets.
E.1
Visualising Attacks Parameter Space (UCI-houseelectric)
First, we investigate the tightness of our bounds parameter space via a feature poisoning attack. The
attack's objective is to maximize a given scalar function of the parameters, which we label ftarz(8). We then take the following poisoning procedure at each training iteration:
22

---

Published in Transactions on Machine Learning Research (09/202)
30
Training Iteration
Clean
Puisoned
Figure 7: Training trajectory for selected parameters under parameter-targeted feature poisoning with adversary of 0.02, 2000, p The coloured boxes show the bounds 00..0u] obtained at each training iteration using AGT.
Randomly sample subset n samples from the current training batch.
For each selected sample x(0) compute a poison v(0) such that 200 v(0) maximizes the gradient f /0x subject to || |p <.
Add the noise each of the sampled points to produce the poisoned dataset.
The noise in step 2 is obtained via projected gradient descent (PGD). To visualise the effect of our attack in parameter space, we plot the trajectory taken by two randomly selected parameters 0,,0; 0, from the network. We then run our poisoning atlack on a collection of poisoning objectives flarg, such as 0; + 0j. 0;, -0,, etc. The effect of our poisoning attack to perturb the training trajectory the direction to maximize the given objective.
Figure shows the result. of this poisoning procedure for random select ion of parameter training trajectories. We can see that the poisoned trajectories (in black) lie close the clean poisoned trajectory, while our bounds represent an over-approximation of all the possible training trajectorics.
E.2
Teature-Space Collision Attack (UCI-houseelectric)
100
7 200
T = 400
}]2
targes f (o t.tggget]
0.75
Clean
Poisoned
0.50
0.25
Training Iteration
Figure 8: Mean squared error the target point target sarget) in the UCI-houscelectrie dataset. Black lines show loss trajectories under the randomized feature-collision poisoning attack.
We now consider an unbounded attack setting where the adversary's goal is to prevent the model from learning particular training example tatarget ylarget). We again consider a simple randomized atlack setting, where the adversary first selects a subset of n samples from each training batch. The adversary then replaces the features of each of the n samples with target and assigns each one a randomly generated label. In this way, the adversary aims obscure the true target label and prevent the model from learning the pair (gtgtt yragget).
23

---

Published in Transactions on Machine Learning Research (09/2025)
Figure X shows the loss of the model on the target point at each training iteration. To investigate the tight of our loss lower bound, we also consider the case where the adversary replaces all of the sampled instances from the batch with the true (ztarget, yy yyarget), thus over-representing the sample within the batch and causing the model to fit the target point faster. The bounds (in red) are obtained from AGT with an unbounded adversary (N 0.05). We can see that although our bounds are not light to any of the atackk considered, they remain sound for all the poisoned training trajectories.
E.3 Randomized Label Flipping Attack (OCT-MNIST)
Here, we present the results of a label-flpping attack conducted on the OCT-MNIST dataset. Following the approach described in Section 4 we begin by pro-training a binary classification model to distinguish between two diseased classes and & healthy class. Next, we fine-tune the model's final dense layers on the 'Drusen' class, which we assume to be potentially compromised, using a training set composed of 50% clean data and 50% Drusen data, with 3000 samples from each category each batch. Given that the Drusen class is a minorily, we simulate scenario where a random subset of the Drusen data is incorrectly labeled the 'healthy' class. Figure 9 displays the model's accuracy when trained on the poisoned dataset. We can see that training on the mis-labelled data results in a significant decrease in model accuracy, though the poisoned accuracy remains within the bounds of certified by AGT.
0.8
Accuracy
0.6
Cettifled Accuracy
Clean Accuracy
0.2
...
Poisoned Accuracy
0
500
1000
Attack Size (m)
Figure 9: Accuracy on the OCT- MNIST dataset under a ran- dom label flipping attack on the Drusen class.
F Proofs
F.1 Proof of Theorem 3.2 (Bounding Adversary Goals via Parameter Space Bounds)
We begin the proof by writing out the form of the function we wish to optimize, J, for cach attack setting considered. Below the right hand side of the inequality is taken to be the function J, and each inequality is the statement we would like to prove.
For denial of service our bound becomes:
k (x(0),
max () < D'ET K
1
Σ
max
El 001
k
For certified prediction poisoning robustness our bound becomes:
k max Σ D'ET K
(2))) $ $5 S max
Σ 1(f (z(0) SS)
a* Elo S01 k
1m1
And for backdoor attacks our bound becomes:
k
k
E1(3r E V(x(0) s.t. (x)) S) k
Σ 1(3x E V(z(0) s.t. (x") E AU k
max D'ET
max
1=1
Proof. Without loss of generality, take the function we wish to optimize to be denoted simply by J. By definition, there exists parameter, 0 Mf, D') resulting from particular datasct D' E T(D) such that 0º provides a (potentially non-unique) optimal solution to the optimization problem we wish to bound, i.e, the left hand side of the inequalities above. Given a valid parameter space bound [0_, 8"1 satisfying Equation [ we have that necessarily, 8 E (84,8"") Therefore, the result of optimizing over [0L, 0") can provide at a minimum the bound realized by 8%: however, due to approximation, this bound might not be tight, so optimizing over [0L, .00 provides upper-bound, thus proving the inequalities above.
24

---

Published in Transactions on Machine Learning Research (09/2025)
F.2 Proof of Theorem 3.3 (Algorithm Correctness)
Proof. Here we provide proof of correctness for algorithm (i.e., proof of Theorem 3.3 detailed discussion of the operations therein.
well
First, we recall the definition of valid parameter space bounds (Equation in the main text):
0.
min M(J,0',)) D'); & M(S. 0' D); & max M(J,6',D), s 04 D'E((D)
D'E((D)
As well as the iterative equations for stochastic gradient descent:
+ 0 - as0, A
Σ
Vol (f)
B
(a,N)EB
For ease of notation, we assume fixed data ordering (one may always take the element-wise maxi- mums/min mommsmminiums over the entire dataset rather than each batch to relax this assumption).
Now, we proceed to prove by induction that Algorithm ! maintains valid parameter space bounds on each step of gradient descent. We start with the base case of gL = l valid parameter-space bounds. Our inductive hypothesis is that, given valid parameter space bounds satis- fying Definition 3.1 cach itcration of Algorithm (lines 4-8) produces new H and G that satisfy also Definition 31
according line 1, which are
First, we observe that lines 4 5 simply compute the normal forward pass. Second, we note that lines 6 compute valid bounds on the descent direction for all possible poisoning attacks within T(D). In other words, the inequality A0L < AO < AQU holds wise for any possible batch B E T(D). Combining this largest and smallest possible update with the smallest and largest previous parameters yields the following bounds:
0C a s - aAl s 00 aAoL
which, by definition, constitute valid parameter-space bounds and, given that these bounds are exactly those in Algorithm [1 have that Algorithm I provides valid parameter space bounds as desired.
F.3 Proof of Theorem D.1 (Descent Direction Bound for Unbounded Adversaries)
The nominal clipped descent direction for parameter 0 is the averaged, clipped gradient over training batch B, defined as
b
AO 1
Clip (00)
where each gradient term is given by 8(0) VoL (z)0)) ()). Our goal is to bound this descent direction for the case when (up to) n points are removed or added the training data, for any [0,,0v]. We begin by bounding the descent dircction for a fixed, scalar 8, then generalize to all [0z, ful and to the multi-dimennionall case (i.e., multiple parameters). We present only the upper bounds here; analogous results apply for lower bounds.
Bounding the descent direction for a fixed, scalar 0. Consider the effect of removing up to data points from batch Without loss of generality, assume the gradient terms are sorted in descending order, i.c., ((1) 2 g(2) 2 ... 2 8(6) Then, the average clipped gradient over all points can be bounded above by the average over the largest b terms:
b-n
A6 = b
1 Clip, [80]
1
Σ
Clip, (())
This bound corresponds removing the points with the smallest gradients.
25

---

Published in Transactions on Machine Learning Research (09/2025)
Next, consider adding arbitrary points to the training batch. Since each added point contributes at most due to clipping, the descent direction with up to n removals and additions is bounded by
b-n Clipx
Clip& 500)
(00)
S
nK +
Σ Clipx
[8(0]
where the bound now accounts for replacing the n smallest gradient terms with the maximum possible value of from the added samples.
Bounding the effect of variable parameter interval. We extend this bound to any 0 E [Oz, Ovl. Assume the existence of upper bounds o on the clipped gradients for each data point over the interval, such that
Clipx /or (1")))
vo' E 10r, Ovl.
Then, using these upper bounds, we further bound A as
AO
TIK +
Σ
Clip 6
where, before, assume 5 indexed in descending order.
Extending to the multi-dimensional case. To generalize to the multi-dimennional case, apply the above bound component-wise. Since gradients are not necessarily ordered for each parameter component, we introduce the SEMax, operator, which selects and sums the largest n terms al each index. This yields the following bound on the descent direction:
SEMax 100 i=1
AB S
nkld
which holds for any 0 E (0L.0y) and to n removed and replaced points.
We have established the upper bound on the descent direction. The corresponding lower bound can be derived by reversing the inequalities and substituting SEMax with the analagous minimization operator, SEMin.
F.4 Proof of Theorem 3.4 (Descent Direction Bound for Bounded Adversaries)
The nominal descent direction for a parameter the averaged gradient over a training batch B, defined as
A0
Σ 810)
where each gradient term is given by 800 VoL (z(()) ()). Our goal is to upper bound this descent direction when up n points from B are poisoned by up to in the feature space and label space. The bound is additionally computed with respect to any E [0z, Byl. We again begin by bounding the descent direction for fixed 0, then generalize to all 0 E [0r., 0v). We present only the upper bounds here, though corresponding results for the lower bound can be shown by reversing the inequalities and replacing SEMax with SEMin.
Bounding the descent direction for a fixed 0. Consider the effect of poisoning either the features or the labels of a data point. For a given data point, an adversary may choose to poison its features, its labels, or both. In total, at most n points may be influenced by the poisoning adversary. We assume that n otherwise take most min(n, b) points be poisoned.
Assume that have access to sound gradient upper bounds
8(0) < 700
45 E (Vo o (1a (z), 11 =llp < S,, (0) (0) - -llo S sv}
26

---

Published in Transactions on Machine Learning Research (09/2025)
where the inequalities are interpreted element-wise. Here, 81 corresponds to an upper bound on the maxi- mum possible gradient achievable at the data-point (x(*) yo through poisoning.
The adversary's 's maximum possible impact on the descent direction at any point is given by 80 8(). To maximize an upper bound on 20, we consider the n points with the largest possible adversarial contributions. Therefore, we obtain
AO- =
800 5
SEMax { -
-6
+ (0)
i=1
where the SEMax operation corresponds to taking the sum of the largest elements of its argument at each element. This bound captures the maximum increase in AO that adversary induce by poisoning up to n data points.
Bounding the effect of a variable parameter interval. Now, we wish to compute a bound on A for any 0 E Ov]. To achieve this, we extend our previous gradient bounds to account for the interval over our parameters. Specifically, we define upper bounds on the nominal and adversarially perturbed gradicnts that hold across the entire parameter interval:
Vg VorC (F )()))) o' E 100, 104,0%].
(z()),
S
= Vg E oor (f (i), O' E 8 1111 - =b1p S (1l08 - ~ll4 s v]
Thus, the descent direction is upper bounded by
AO < AB"
1 b
SEMax 16
b 1=1
+
for all / E (01, Oul, where the appropriate bounds with respect to the parameter interval have been substituted in.
F.5 Proof of Proposition 3.5
(CROWN bounds)
To prove Proposition
3.5
rely the following result which reproduce from Zhang et al. 2018
Theorem F.1 (Explicit output bounds of a neural network (Zhang et al. 2018 ). Göven an m-layer neural network function f "o TR there evists two explicil functions 1/. R + TR and sÿ To - IR such that Vj [nmm], Vx Bp (zo,e), the inequality ff(x) fz(x) S 14/ (x) holds true, where
{ (A (k-1)
if = m + 1;
()(x)= - 1000 x
(k) (b(K) +
(1))
(k-1)
j.
if k E [m].
m
if k m + 1;
(f(())
20
(k) js
((()) + +
o wfff
if k E [m]]
and V E [nx], we define four motrices (1)) (h),
(k) (()) E Rum
(k)
if + 0,A (I+1) A
W (++1) 0;
0 (1+)) ( 2 0;
(
L,
k 0, A
(K+1)
(k+1)
< 0;
w//
(K)
(it wilk < <0; 5.:
k.
k
B(k)
if + m, A (k+1)
(k+1)
((())
if + m, S2 n
(K+ 10+1 (k+1) 2 0;
2 0; Wi (k+1)
(K)
A
ih m,
(k+1)
:3
0;
(k)
TK m, m ((+1)) <0;
m.
i m.
and o is the Hadamard product and ej nm is standord unit vector at 3 th. coordinate.
27

---

Published in Transactions on Machine Learning Research (09/2025)
((k) The terms L, aua L and Pus represent the coefficients of linear bounds the activation functions, that is for the r-th neuron in k-th layer with activation function oxx), there exist two linear functions
(k) (R)
oir (x PL.r):
(N)
N.. (x) = ourr
(k) (x + (U.))
such that (x) S (x)) S h
U Vx E [14 ,( The terms [((]] ur are assumed to be sound bounds
(k))
on all previous neurons in the network. We first note that, for any ncuron r in the k-th layer, the linear (k)
bounds may be replaced with concrete bounds by substituting aL, = OUr 0 and $ ((k) . uh (k) Let S be index sets of tuples (i, k) indicating whether the lower and upper bounds (respectively) of the i-th neuron in the k-th layer should be concretized in this way. Then, the equivalent weights and biases take the following form:
(k)
(k)
if $ 5" k 0,A (k+1) ((++1) 0;
aya
(t, $ 5" # 0, 0,4 (k+1) (((+1)
A (K)
O LA
< <0;
(f,k) k= 0;
i((i,))
a (( 0, 12 (k+1) w>((kt))) 2 0;
(k)
QUN
(R)
((,,))55"
(k+t)
(k+1) (k+1)
0:
3,3
(1,
(00)
(1,)) ( 5/ m, A (k+1) ((+1)) (++1) 2 0:
A (K)
( * #,m, A.,A
(k+1)
W (k+1)
(
=m
i
(1, m, 2 (k- wr(Kt] 2 0:
(
PU.
(K)
( m, 1
(k W (k+1) < 0:
&
m;
(RK) if(i,k)
This is exactly the form described in Appendix C where SL and S are chosen to be the sets of neurons whose equivalent coefficient interval spans zero. Without this modification, the equivalent weights and biases of such neurons in the original formulation would be undefined. We now have bounds on the output of the neural network for which all operations are well-defined in interval arithmetic.
Replacing all operations in the computation of the equivalent weight terms by their interval arithmetic counterparts, we can compute sound, though over-approximated, intervals over A (0:m) and ([0m)) which satisfy
(R) E A (k) ((1m)) E W(1mm)
(aatsmm))((mmm) ((.mm) E (1:m)
(K)) (k) (1mm) ((1m)) ((1mm) E (1:m)
This is trivially true by the definitions of the interval arithmetic operations as given in Appendix C Turning to the upper bound (though analogous arguments hold for the lower bound), we have
m
p (x, A (0:m) A (1am) b(1=m)) A
(0) x
(k) (B(K) A() je
+
where A (0:m) are functions of the weights and biases of the network and A (1mm) are constants that depend the bounds the intermediate layers of the network. Thus, given parameter intervals (k)) ((()) the
28

---

Published in Transactions on Machine Learning Research (09/2025)
following result holds
f/ (z,A (0m)) A (1:m), ((am)) max { s3 (a, (0.m) A (1mm) blam))
W(1m) W-(1m))
b(lmm) E 6 (1:m)
A A(0m) b(lm)
E A (0:m)
max sy (I, de,.ll0m A (1:m) k((m))
(1:m)
for any of intervals A (0m) that satisfy {A(A) W E w( S A A Since our intervals A (0mm)
computed via interval arithmetic satisfy this property, have that any valid bound on this maximization
problem constitutes bound on the output of the neural nelwork [z( for any W(1m) E W and f(lm)) (1:m)
G Experimental Details and Runtimes
This section details the datasets and parr-paarmstesss used for the experiments detailed in Section I All experiments were run on server equipped with 2x AMD EPYC 9334 CPUs and 2x NVIDIA L40 GPUs using implementation of Algorithm written in Python using Pytorch.
Table shows run-time comparison of our implementation of Algorithm D with (un-certified) training in Pytorch. We observe that training using Abstract Gradient Training typically incurs modest additional cost per iteration when compared to standard training.
Time per iteration (seconds)
Dataset
Abstract gradient training
Un-certified training
UCI House-clectric
0.25
0.12
MNIST (inc. PCA projection)
1.6
1.1
OCT-MNIST
0.96
0.10
Udacity Self-Driving
53
42
Table Comparison of the run-time of AGT and standard model training in Pytorch.
Table details the datasets along with the number of epochs, learning rate (ar,, decay rate (n) and batch size (b) used for each. We note that standard learning rate decay of the form (a,, = a/(1+ mm) was applied during training. In the case of fine-tuning both OCT-MNIST and PilotNet, each batch consisted of mix 70% 'clean' data previously seen during pre-training and 30% new, potentially poisoned, fine-tuning data.
Datasct
#Samples
#Fcatures
#Epochs
1]
UCI House-electric
2049280
11
1
0.02
0.2
10000
MNIST
60000
784
3
5.0
1.0
60000
OCT-MNIST
97477
784
2
0.05
5.0
6000
Udacity Self-Drivin Driving
31573
39600
2
0.25
10.0
10000
Table 2: Datasets and Hyperparameter Settings
29


Reviews:
[{"review_id": "LaICJObPRa", "reviewer": "Reviewer_CbJE", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper studies a novel problem, that is to provide certified robustness against both bounded and unbounded data poisoning attacks. \n- The idea of using the reachable set is interesting.\n- The paper discusses many aspects of the algorithm, such as complexity, certifying a single query, and combining forward and backward pass.\n\nWeaknesses:\n- This algorithm has high complexity to have tight bound ($O(bm^2n^3)), which may not be practical for real-world applications. The experiments are only conducted on small-scale datasets and models. \n- Fig. 3 shows that the certified robustness is not quite high, and improving that trades off the nominal accuracy.\n- Fig. 4 implies that randomized smoothing consistently outperforms the proposed method when $n>50$, which is not unrealistic.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a method to certify the robustness of neural networks against data poisoning attacks, which perturb the feature or label of training data. In particular, the algorithm returns the upper bound of the worst-case adversary, such as the lowest accuracy or the highest MSE that the attack could achieve. Intuitively, this method leverages convex relaxation to bound the reachable set of all possible parameters that could be obtained by the training procedure and theoretically translates that bound to the adversary's objective. The experiments demonstrate the certified robustness on simple classification and regression problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "This work could be significantly improved if the experiments on large-scale datasets and large model are provided.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3Bex1FOjHX", "reviewer": "Reviewer_YK3j", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n1. This work provides a new framework for certified robustness by tracking the model parameters range during training. This framework is general and can be applicable for a wide range of poison attacks such as bounded attacks and unbounded attacks, untargeted and targeted poisoning, and backdoor attacks. \n\n2. Experiment results provide useful discussion to understand the framework performance and comparison to previous works. \n\n## Weaknesses\n1. Scalability. The bounds may be too loose as derived via relaxation in deeper networks or more epochs. This is already acknowledged  and discussed as limitations in this work on page 8. \n\na. scalability in model parameters. I wonder for the MNIST result, is the usage of PCA also due to this? How is the performance if without PCA?\n\n2. Assumption limitations.\n\na. If I understand correctly, this work assumes the input dataset to the framework to be clean instead of being poisoned, and then try to bound the model parameters space by solving an optimization problem allowing at most n samples to be corrupted at each gradient update. It seems to me that there is gap to this scenario and the motivated scenario where the input dataset is already poisoned like Zhu et al. 2019. If I understand correctly, other works like DPA could still provide the certified robustness to this motivated scenario.  \n\nb. data orderings.  The first paragraph of Section 2 states that this framework assumes unrestricted access to data ordering. I think this work do assume the data ordering by assume all poisoned samples in a batch or poisoned samples are concentrated in a few batches rather than uniformly distributed across the batches. Otherwise, I would expect the derived certified robustness to be more loose. \n\n3. Clarity.\n\na. This work instantiates a extension of the CROWN algorithm to the interval-parameter setting. And in page 7 for the comparison to interval bound, the numerical experiments compute both the CROWN bounds and IBP bounds and take the element-wise tightest bound. It would be better to include the ablation results to help understand the qualitative effect of the proposed extension.\n\nb, page 7 says \"at most $n$ poisoned points per batch, rather than per datasets\". Does this mean that there could be more than $n$ poisoned points per dataset in the presented experimental results?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the certified robustness of the neural networks by providing a framework to compute the valid parameter-space bounds $[\\theta_L, \\theta_U]$ and such that the all possible model parameters after training in this range, and optimizing in this range could provide the certified robustness of the model, though this may be potentially loose. This is because this estimation accumulates across steps and accumulates by element-wise summarization, and in practice the attacker may not have such ability to craft such poisoned data under the constraints. \n\nTo compute the bound $[\\theta_L, \\theta_U]$ at each gradient updates, this work provides an instantiation of CROWN (Zhang et al. 2018). As CROWN approximate the neural network by linearity approximation with upper bound and lower bound,  $\\theta_L$ could be tracked via the lower bound and $\\theta_U$ could be tracked via the upper bound. \n\nThis work also provides experiments to understand the certified performance of the proposed framework under different settings, feature poisoning, label flipping, feature+label poisoning.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please address my concerns in weaknesses.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "er90TVvDtE", "reviewer": "Reviewer_4DXp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n- The problem is interesting and the concept of certifying robustness without modifying the underlying learning algorithm is promising, providing generality and flexibility.\n\n- The approach tackles the challenge by trying to bound reachable parameter sets, a novel perspective compared to existing art.\n\n- Consideration of a variety of threat models (bounded and unbounded poisoning attacks) and attack goals (untargeted, targeted, backdoor attacks).\n\n**Weaknesses:**\n\n- The motivation and practicality for **bounding the model parameters** (i.e., maintaining an interval over θ) is not clearly established in the paper. I am not sure why one would track such bounds, especially since θ is not guaranteed to correlate with functional behaviour. More importantly, while in an adversarial robustness case (input manipulation at test time) the bounds on input perturbations make sense practically, in the poisoning case, supposing bounds on parameters does not seem neither intuitive, nor practically useful. \n- Besides, expectedly, the empirical results suggest that certified bounds weaken for deep models. I am really unsure about how practically useful these bounds would be, even though I have no fundamental concerns theoretically. \n- There is no clear statement of the loop invariant that after each iteration the parameter box [θ_L, θ_U] contains all parameters reachable under the adversary model. While it might be moinor, the mention of the “optional” clipping parameter κ is confusing—it is actually necessary for unbounded attacks and irrelevant otherwise. Without this clarification, it can confuse the reader into thinking the clipping is an unclear artifact. \n- These equations use symbols like δ_L and δ_U without clearly stating where they come from. This is confusing, especially since deriving such bounds is one of the main goals of the paper. Only later (Section 3.4 and Appendix C) do we learn that these are obtained using interval-CROWN and IBP. Earlier equations should reference this explicitly. Either change the structure, or mention this explicitly; it got me confused dropping these early without explanation. (similar comment on some proofs, including those in Appendix F (Theorem 3) and Theorem 1 (Appendix E), rely on assumptions or constructs defined in later sections or appendices, without making this dependency clear. This forces the reader to hunt around the paper to piece things together)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a novel framework designed to provide certified robustness guarantees against data poisoning in gradient-based learning algorithms. The proposed framework does not modify the underlying learning algorithm or model; instead, it leverages convex relaxations and bound-propagation techniques to define and track intervals of reachable parameters under various adversarial manipulations (both bounded and unbounded). This allows for certifying robustness in scenarios involving untargeted, targeted, and backdoor attacks, offering theoretical guarantees on the worst-case model performance and behavior under poisoning attacks", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see weaknesses, but mainly clarify the motivation and practical usefulness for parameter intervals, and improve readability of the theoretical structure.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)