Make Sure You're Unsure: A Framework for Verifying Probabilistic Specifications
Authors: Leonard Berrada
Sumanth Dathathri
Krishnamurthy Dj Dvijotham
Robert Stanforth
Rudy R Bunel
Jonathan Uesato
Sven Gowal
M. Pawan Kumar
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Verification
Safety
Optimization

Abstract: Most real world applications require dealing with stochasticity like sensor noise or predictive uncertainty, where formal specifications of desired behavior are inherently probabilistic.  Despite the promise of formal verification in ensuring the reliability of neural networks, progress in the direction of probabilistic specifications has been limited. In this direction, we first introduce a general formulation of probabilistic specifications for neural networks, which captures both probabilistic networks (e.g., Bayesian neural networks, MC-Dropout networks) and uncertain inputs (distributions over inputs arising from sensor noise or other perturbations). We then propose a general technique to verify such specifications by generalizing the notion of Lagrangian duality, replacing standard Lagrangian multipliers with "functional multipliers" that can be arbitrary functions of the activations at a given layer. We show that an optimal choice of functional multipliers leads to exact verification (i.e.,  sound and complete verification),  and for specific forms of multipliers, we develop tractable practical verification algorithms.
 
We empirically validate our algorithms by applying them to Bayesian Neural Networks (BNNs) and MC Dropout Networks, and certifying properties such as adversarial robustness and robust detection of out-of-distribution (OOD) data. On these tasks we are able to provide significantly stronger guarantees when compared to prior work -- for instance, for a VGG-64 MC-Dropout CNN trained on CIFAR-10 in a verification-agnostic manner,  we improve the certified AUC (a verified lower bound on the true AUC) for robust OOD detection (on CIFAR-100) from $0 \% \rightarrow 29\%$. Similarly, for a BNN trained on MNIST, we improve on the $\ell_\infty$ robust accuracy from $60.2 \% \rightarrow 74.6\%$. Further, on a novel specification -- distributionally robust OOD detection -- we improve on the certified AUC from $5\% \rightarrow 23\%$.

Make Sure You're Unsure: A Framework for Verifying Probabilistic Specifications
Leonard Berrada *
Sumanth Dathathri *
Krishnamurthy (Dj) Dvijotham"
Robert Stanforth
Rudy Bunel
Jonathan Uesato
Sven Gowal
M. Pawan Kumar 1
Abstract
Most real world applications require dealing with stochasticity like sensor noise predictive uncertainty, where formal specifications of desired behavior inherently probabilistic. Despite the promise of formal verification in ensuring the reliability of neural networks, progress in the direction of probabilistic specifications has been limited. this direction, we first introduce a general formulation of probabilistic specifications for neural networks, which captures both probabilistic networks (e.g., Bayesian neural networks, MC-Dropout networks) and uncertain inputs (distributions over inputs arising from sensor noise or other perturbations). We then propose a general technique to verify such specifications by generalizing the notion of Lagrangian duality, replacing standard Lagrangian multipliers with "functional multipliers" that can be arbitrary functions of the activations at a given layer. We show that an optimal choice of functional multipliers leads to exact verification (i.e., sound and complete verification), and for specific forms of multipliers, we develop tractable practical verification algorithms.
We empirically validate our algorithms by applying them to Bayesian Neural Networks (BNNs) and MC Dropout Networks, and certifying properties such adversarial robustness and robust detection of out-of-distribution (OOD) data. On these tasks are able provide significantly stronger guarantees when compared to prior work - for instance, for a VGG-64 MC-Dropout CNN trained on CIFAR- 10 in cerification-aanosti manner, we improve the certified AUC verified lower bound on the true AUC) for robust OOD detection (on CIFAR-100) from 0% + 29%. Similarly, for a BNN trained on MNIST, we improve on the foo robust accuracy from 60.2% > 74.6%. Further, on novel specification distributionally robust OOD detection we improve on the certified AUC from 5% > 23%.
Introduction
While neural networks (NNs) have shown significant promise in wide-range of applications (for e.g., [He et al. 2016 Yu and Deng 2014)). a key-bottleneck towards their wide-spread adoption in safety-critical applications is the lack of formal guarantees regarding safety and performance. In this direction, there has been considerable progress towards developing scalable methods that can provide formal guarantees regarding the conformance NNs with desired properties [Katz al.) 2017 Dvijotham et al., 2018b] Raghunathan et al. 2018) However, much of this progress has been in the setting where the specifications and neural networks do not exhibit any probabilistic behaviour, or is mostly specialized for specific probabilistic specifications [Weng et al. 2019 Wicker et al., 2020)
"Equal contribution. Authors listed in alphabetical order. Correspondance 1berradaeteeppindd.com sdathatth@deppmind com, dvij@cs washington. edu. DeepMindd London, United Kingdom.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In contrast, we introduce a general framework for verifying specifications of neural networks that are probabilistic. The framework enables us handle stochastic neural networks such as Bayesian Neural Networks or Monte-Carlo (MC) dropout networks, as well as probabilistic properties, such as distributionally robust -fttt---iitritttionn (OOD) detection. Furthermore, the specification can be defined on the output distribution from the network, which allows us to handle operations such as the expectation on functions of the neural network output.
Probabilistic specifications are relevant and natural to many practical problems. For instance, for roboties applications, there is uncertainty arising from noisy measurements from sensors, and uncertainty regarding the actions of uncontrolled agents (e.g. uncertainty regarding the behaviour of pedestrians for self-driving vehicle). Often these uncertainties are modelled using a probabílistic approach, where a distribution is specified (or possibly learnt) over the feasible set of events (Thrun al. 2005]. In such cases, we want to provide guarantees regarding the network's conformance to desired properties in the distributional setting (e.g. given model of the pedestrian's uncertain behaviour, guarantee that the probability of collision for the autonomous vehicle small). A more general problem includes scenarios where there is uncertainty regarding the parameters of the distribution used to model uncertainty. Here, in this general setting, we seek to verify the property that the network behaviour conforms with the desired specification under uncertainty corresponding to an entire set of distributions.
The key to handling the aforementioned complexity in the specifications being verified through our framework is the generalization of the Lagrangian duality. Specifically, instead of using the standard Lagrange duality where the multipliers are linear, we allow for probabilistic constraints (constraints between distributions) and use funetional multipliers to replace the linear Lagrange multipliers. This allows us to exploit the structure of these probabilistic constraints, enabling us to provide stronger guarantees and facilitates the verification of verification-agnosti networks (networks that are not designed to be verifiable). In our paper, we focus verification-agnosiic networks as this is desirable for many reasons, as noted in Dathathri et al. 2020). To summarize, our main contributions are:
We derive general framework that extends Lagrangian duality to handle a wide range of probabilistic specifications. Our main theoretical result (Theorem 1) shows that our approach (i) is always sound and computes
upper bound on the maximum violation of the specification being verified, and (ii) is expressive enough to theoretically capture tight verification (i.e. obtaining both sound and complete verification).
We develop novel algorithms for handling specific multipliers and objectives within our framework (Propositions 1 This allows us to apply our framework to novel specifications (such as distributionally robust OOD detection, where input perturbations are drawn from entire sets of distributions) by better capturing the probabilistic structure of the problem.
We empirically validate our method by verifying neural networks, which are verification- agnostic, on a variety of probabilistic specifications. We demonstrate that even with relatively simple choices for the functional multiplier, our method strongly outperforms prior methods, which sometimes provide vacuous guarantees only. This further points towards the potential for significant improvements to be had by developing tractable optimization techniques for more complex and expressive multipliers within our framework.
2 Probabilistic Specifications
2.1 Notation
Let us consider a possibly stochastic neural network ő: X - P()). where X' is the set of possible input values to the model, )/ is the set of possible output values, and P (2²) is the set of distributions over )/. We assume that ) is a subset of R (unless specified otherwise), where I is the number of labels, and the output of the model are logits corresponding to unnormalized log-confidence scores assigned to the labels {1.....
The model is assumed be sequence of K layers, each of them possibly stochastic. For kt {I...., K} }. T (I)) denotes the probability that the output of layer & takes value IG when its input value 1k-1. We write I& ~ Tr (xx-1) to denote that 2& is drawn from the distribution over outputs of layer le given input - to layer k. We further assume that each Te (x) has the form (@wx + b). where is non-lincar activation function (c.g., ReLU, sigmoid, MaxDut), and ö and b

---

are random variables. The stochasticity for layer тд is assumed to be statistically independent of the stochasticity at other layers. For a BNN, i and follow diagonal Gaussian distribution (i.e., Gaussian distribution with a diagonal covariance matrix), and for MC-Dropout network they follow a Bernoulli- distribution.
Given distribution po over the inputs X, we use ((po) to denote (with slight abuse) the distribution of the random variable (Xo), where Xo
2.2 Problem Formulation.
We now introduce the general problem formulation for which we develop the verification framework. Definition 1 (Probabilistic verification problem). Given (possibly stochastic) neural network @ X P ()), set of distributions over the input Po and a functional ab P (P)) + R, the
probabilistic verification problem to check that the following is true:
4 Po E Po, 1b (8 (po)) 0.
2.3 Examples of Specifications
Below we provide examples of probabilistic specifications which are captured by the above problem formulation, and that we further empirically validate our framework on. In Appendix [A] we provide further examples of relevant specifications (e.g.. ensuring reliable uncertainty calibration) that can be handled by our problem setup.
Distributionally Robust OOD Detection. We consider the problem of verifying that a stochastic neural network assigns low confidence scores to all labels for OOD inputs, even in the presence of bounded noise perturbations to the inputs. Given a noise distribution perturbing an OOD image Foods we require that the expected softmax is smaller than a specified confidence threshold Pmax for each label Since the precise noise distribution is most often unknown, we wish to consider an entire class Proise of noise distributions. Denoting by 8 the Dirac distribution around the problem is then to guarantee that for every Po Po {ōrrod + w w E P Pnossse and for each possible label i, vb(((p))) = ((p)) tsoftmas (y) Pmax < 0. Robust OOD detection under bounded loo. perturbations as considered in Bitterwolf et al.] [2020) is special case of this problem where Pnoise restricted to set of 8 distributions over points with bounded Loo norm.
Robust Classification. We also extend the commonly studied robust classification problem [Madry et al. 2017] under boundeeunded perturbations, to the setting of probabilistic neural networks (e.g. BNNs). Define Pu be the set of 5 input distributions centered at points within an e-ball of a nominal point Tnoms with label i E (1...., .I]: Po {Ō.. ||x Znom| S e). For every Po E Po. we wish to guarantee that the stochastic NN correctly classifies the input, i.e. for each (sof
(d((p))) = ( (sof tmax (v)) sof smax (y) S O. Note that it is important to take the
expectation of the softmax (and not logits) since this is how inference from BNNs is performed.
3 The Functional Lagrangian Framework
We consider the following optimization version:
OPT max sb (Ø (po)), PoEP.
Having OPT < O here is equivalent to satisfying specification ① However, solving problem directly to global optimality is intractable in general, because it possibly be challenging nonlinear and stochastic optimization problem. However, to only verify that the specification is satisfied, it may suffice to compute an upper bound on OPT. Here, we describe how the functional Lagrangian framework allows to derive such bounds by decomposing the overall problem into smaller, easier sub-problems.
3.1 General Framework
Let X denote the feasible space of activations at layer k, and let pk denote the distribution of activations at layer l when the inputs follow distribution po (so that pk o (po)).
3

---

Assumptions. In order to derive our verification framework, we make the following assumptions:
(A1): 3/ S Up E In such that for each input distribution Po E Po. Support (Po) _ Xo = 14. uo]-
(A2): Each layer is such that if x E Xx= = [k. Wk]. then Support (TH (z)) S Xx+1 = [I []++
Assumption (A1) is natural since the inputs to neural networks bounded. Assumption (A2) can be restrictive in some cases: it requires that the layer output is bounded with probability 1, which not true, for example, if we have a BNN with a Gaussian posterior. However, we can relax this assumption to requiring that the output is bounded with high probability, as in Wicker et al. 2020
Functional Lagrangian Dual. In order to derive the dual, we begin by noting that problem can be equivalently written in the following constrained form:
/ I (ylz) Pk (x) dx.
max PPP...P.....
+ (pk) AkE (O...., K 13, V E Re+1, Pk+1 (1) = Xx,
For the k-th constraint, let us assign Lagrangian multiplier A4+1 to each possible y E Ak+11 Note that A (y) chosen independently for each y, hence À is a functional multiplier. We then integrate over y, which yields the following Lagrangian penalty to be added to the dual objective:
f 1111
Au+1 (3) Pk+1 (y) dy +
A1+1 (1) Thk (y/zr) pk (x) dxdy.
We now make two observations, which are described here at a high level only and are available in more details in appendix B First, we these penalties over k and group terms by pu. it can be observed that the objective function decomposes additively over the ps: distributions. Second, for k (I,.... K 1). each Pk can be optimized independently (since the objective is separable), and since the objective is linear in pk the optimal pı is a Dirac distribution, which means that the search over the probability distribution ps can be simplified to a search over feasible values 24 E Xz. This yields the following dual:
max PK EPx
② (Px)
- dR (I) (x) dz)
K- Σ k=1
max ZEdi
(1
Ao+1 (3) TT (y ())x) dy A (z)
+ max PoEPo No (1)s An (O) (212z) (vlzz)
(z) dx,
(4)
where we define PK 2 (PP)). In the rest of this work, we refer to this dual as g (A), and we use the following notation simplify equation 4
K
g (A) = max Do (Po. A1) PoEPo
+
Σ
max gh (Tt, Ae. AR+1) + max gK AK). EX,
(5)
PREPR
The dual g (A) can be seen as a generalization of Lagrangian relaxation [Bertsekas] 2015 with the two key modifications: (i) layer outputs are integrated over possible values, and (ii) Lagrangian penalties are expressed as arbitrary functions >₃ (x) instead of being restricted linear functions.
Main Result. Here, we relate the functional Lagrangian dual the specification objective
Theorem 1. For any collection of functions X (A1,... .., AK) R. X ... R. we have that (A) 2 OPT. In particular. if a choice of X can be found such that (A) < O. then specification 1 is true. Further, when up (px) ) = Ey-px [c (y)), the dual becomes tight: g (A*) = OPT if X set to:
xx c
1.... 1), XI (x)
E (N(
[M (v)
Proof. We give brief sketch of the proof- - the details are in Appendix B The problem in constrained form is an infinite dimensional optimization with decision variables Po, .t,,,.....P and linear
constraints relating Pa and pE+1- The Lagrangian dual of this optimization problem has objective g (A). By weak duality, we have g(A) 2 OPT. The second part of the theorem easily observed by plugging in A in (X) and observing that the resulting optimization problem is equivalent to 2 L

---

Example. Let Po be the set of probability distributions with mean O, variance 1, and support [-1, 1], and let (a,i (H, o²) denote the normal distribution with mean j and variance o² with truncated support (a, bj. Now consider the following problem, for which we want to compute an upper bound:
OPT max 1x (exp((xx s.t. X1 ~ (o.) 1) and Xo ~ po- PoEPo
This problem has two difficulties that prevent us from applying traditional optimization approaches like Lagrangian duality [Bertsekas] 2015), which has been used in neural network verification
Dvijotham al. [2018b]. The first difficulty is that the constraint linking X1 to Xg is stochastic, and standard approaches can not readily handle that. Second, the optimization variable po can take any value in entire set of probability distributions, while usual methods can only search over sets of real values. Thus standard methods fail to provide the tools to solve such a problem. Since the probability distributions have bounded support, a possible way around this problem is ignore the stochasticity of the problem, and to optimize over the worst-case realization of the random variable However
X1 in order to obtain valid upper bound on OPT as: OPT I max this is an over over-pessinn pessimistic modeling of the problem and the resulting upper bound is loose. In contrast, Theorem shows that for any function À R E. OPT can be upper bounded by:
exp(-x1)
OPT
JT (0.10.)).PEE exp(-x1) ((a1 + Exp-oo [X X (X3. (X())
max
This inequality holds true in particular for any function À of the form Or where 0 R, and thus:
DPT S inf max exp(-x1) - o.. Exo-ro [x Xo [0x]]]-
(xX1))
OER [0
inf max exp(-21) Am1 AE X pp [xg1.
eER PoP
inf max exp(-xi) Oz1 + 0 ~ 0.37. OER 21
Here, our framework lets us tractably compute bound on OPT that is significantly tighter compared to the naive support-based bound.
3.2 Optimization Algorithm
Parameterization.
The choice of functional multipliers affects the difficulty of evaluating g (A). In
fact, since neural network verification is NP-hard [Katz et al., 2007], we know that computing g (A*) is intractable in the general case. Therefore in practice, we instantiate the functional Lagrangian framework for specific parameterized classes of Lagrangian functions, which we denote as A (6) =
{Ae (x)) A (x; 0z)) ] Choosing the right class of functions \(0) is a trade-off: for very simple classes (such as linear functions), g(A(0) easy to compute but may be loose upper bound on ( while more expressive choices lead to tighter relaxation of (2) at the cost of more difficult evaluation (or bounding) of g(X(O)).
Algorithm 1 Verification with Functional Lagrangians
Input: initial dual parameters ((0), learning-rate y, number of iterations T. for t 0,..., T 1 do (optimization loop)
for k 0 to K do (potentially in parallel)
dg (A) Vo
maxgi (Ik, Au, )k+1) (potentially approximate maximization) 22
end for
(1++1) (00) - E dfth (or any gradient based optimization)
end for
Return: Exact value or guaranteed upper bound on g(A(B(7))) (final evaluation|
Optimization. With some abuse of notation, for convenience, we write go (ro, Au, A1) = Io (Po. A1) and gK (Fx, Ag, Ax+1) 9K (PK,AR) with Xo >K-1 0. Then the problem of obtaining the best bound can written as: ming Σk= max,, 9& (Ik, Ae; A1+1), where the inner maximizations are understood to be performed over the appropriate domains (Po for Do. X for zk.
5

---

I 1=....., K- and Px for TK). The overall procedure is described in Algorithm 1 @ is minimized by gradient- based method in the outer loop; the inner loop. the decomposed maximization problems over the #& get solved, potentially in parallel. During optimization, the inner problems can be solved approximately as long as they provide sufficient information about the descent direction for 0.
Guaranteeing the Final Results. For the final verification certificate to be valid, do require the final evaluation to provide the exact value of g (((((())) or an upper bound. In the following section, we provide an overview of novel bounds that we use in our experiments to certify the final results.
3.3 Bounds for Specific Instantiations
The nature of the maximization problems encountered by the optimization algorithm depends on the verification problem as well as the type of chosen Lagrangian multipliers. In some easy cases, like linear multipliers on a ReLU layer, this results in tractable optimization or even closed-form solutions. In other cases however, obtaining non-trivial upper bound is more challenging. In this section, we detail two such situations for which novel results were required to get tractable bounds: distributionally robust verification and expected softmax-based problems. To the best of our knowledge, these bounds do not appear in the literature and thus constitute a novel contribution.
Distributionally Robust Verification with Linexp Multipliers. We consider the setting where we verify deterministic network with stochastic inputs and constraints on the input distribution Po E PPo In particular, we consider Po = {u + w w ~ Pnoise J. where Pnoise denotes a class of zero-mean noise distributions that all satisfy the property having sub-Gaussian tails (this is true for many common noise distributions including Bernoulli, Gaussian, truncated Gaussian):
Sub-Gaussian tail: Vi, vt TR, E (exp (tw))] exp (f²o2/2).
We also assume that each component of the noise is i.i.d. The functional Lagrangian dual g (A) only depends on the input distribution Pa via 9o, which evaluates to go (Po, A1) IF Pazeo [X] (a)). we choose X to be a linear quadratic function, then (A) only depends on the first and second moments of Po- This implies that the verification results will be unnecessarily conservative as they don't use the full information about the distribution po- To consider the full distribution it suffices to add an exponential term which evaluates to the moment generating function of the input distribution. Therefore we choose x (x) = a² + exp (7d x + x) and X (x) 3 x. The following result then gives a tractable upper bound on the resulting maximization problems:
Proposition 1. the setting described above, and with s as the element-wit function::
max 9o (po, \1) T (wp + 6) + exp (Ilw v12² 02 1 k)), PoEPo
91 (z, A1, xEX;
BT (w2z b2) a²x x exp (1 +
=EX2.==a(2)
The maximization in the second equation can be bounded by solving a convex optimization problem (Appendix C.3).
Expected Softmax Problems. Several of the specifications discussed in Section 2.3 (c.g..
distributionally robust OOD detection) require us to bound the expected value of linear Function of the softmax. For specifications whose function ab (pk) = Exppx [=)], by linearity of the objective w.r.t. the output distribution Pk. the search over the distribution pk can be simplified to search over feasible output values Fx:
be expressed as expected value:
-f
max bb (px) Pk Ex
Jxzx AK (x) (x) max c (xx) - dx (z). zE
Given this observation, the following lets certify results for linear functions of the sof tmax (z): Proposition 2. For affine λK. and c(x) with the following form c(z) n¹" softmani (x²), max c c(x) Ax (x) can be computed in time O(3d), where Xg C gd.

---

We provide a proof of this proposition and concrete algorithm for computing the solution in Appendix C.2 This setting is particularly important to measure verified confidence and thus to perform robust OOD detection. We further note that while the runtime is exponential in d, d corresponds to the number of labels in classification tasks which is constant value and does not grow with the size of the network or the inputs to the network. Further, the computation is embarassingly parallel and can be done in (1) time if 3d computations can be run in parallel. For classification problems with 10 classes (like CIFAR-IO and MNIST), exploiting this parallelism, we can solve these problems on the order milliseconds on a cluster CPUs.
Related Work
Verification of Probabilistic Specifications. We recall that in our work, Po refers to a space of distributions on the inputs x: to network Φ, and that we address the following problem: verify that Vp E Po. & (p) E Pout. where P Pout represents a constraint on the output distribution. In contrast, prior works by Weng et al. ( et al. [2019). and Miiman et al. [202T] study probabilistic
specifications that involve robustness to probabilistic perturbations of a single input for deterministic networks. This setting be recovered contain a single distribution p. Conversely, DDvijohhmm et al. [2018a] study specifications involving stochastic models, but can not handle stochasticity in the input space.
special case within our formalism by letting the class Po
Wicker et
20200 P Puwpw VV E X, Ow (x) E C 2 Pmin. where P' is the probability of any event, &w denotes the network with parameters w. Pwe denotes the distribution over network weights (e.g., a Gaussian posterior) and C is set of safe outputs, and this allows for computation of the probability that randomly sampled set of weights exhibits safe behaviour. However, in practice, inference for BNNs is carried out by averaging over predictions under the distribution of network weights. In this less restrictive and more practical setting, it suffices if the constraint is satisfied by the probabilistic prediction that averages over sampled weights: Var X, P Puu-p... (xx) E C) > Pminn where & (ar) denotes the distribution over outputs for x E X. Further, Wicker et al.) [2020] also observe that min x P Fumps (x) [ow()) E C] > 1 Wwoppe [vx E X, dw C.. making the second constraint less restrictive. Cardelli et al. [219]] and Michelmore et al. [2020] consider a similar specification, but
al.
define a notion of probabilistic safety for BNNs:
unlike the approaches used here and by Wicker al. 2020 these methods can give statistical
confidence bounds but not certified guarantees.
Wicker et al. [021] improve the classification robustness of Bayesian neural networks by training them to be robust based on an empirical estimate of the average upper bound on the specification violation, for fixed set of sampled weights. In contrast,
approach provides meaningful guarantees for BNNs trained without considerations to make them more easily verifiable, and the guarantees our framework provides hold for inference based on the true expectation, as opposed to fixed set of sampled weights.
Our work also generalizes Bitterwolf et al. 2020 which studies specifications of the output distribution of NNs when the inputs and network are deterministic. In contrast, our framework's flexibility allows for stochastic networks well. Furthermore, while [Bitterwoff al. [2020) are concerned with training networks to be verifiable, their verification method fails for networks trained in perification-agnese manner. In our experiments, provide stronger guarantees for networks that are trained in a verification-agnostie manner.
Lagrangian Duality. Our framework subsumes existing methods that employ Lagrangian duality for NN verification. In Appendix [.]]] we show that the functional Lagrangian dual instantiated with linear multipliers is equivalent to the dual from Dvijotham et al. [2018b]. This is also the dual of the LP relaxation [Ehlers 2017] and the basis for other efficient NN verification algorithms ([Zhang al. 2018 Singh al. 2018 for example), as shown in Liu et al.
[202T). For the case of quadratic
multipliers and a particular grouping of layers, we show that our framework is equivalent to the
Lagrangian dual of the SDP formulation from Raghunathan et al.
2018 (see Appendix D.2)
We also note that similar mathematical ideas on nonlinear Lagrangians have been explored in the optimization literature [Nedich and Ozdaglar 2008 Feizollahi et al. 2017 but only as theoretical construct this has not lead to practical algorithms that exploit the staged structure of optimization problems arising in NN verification. Further, these approaches do not handle stochasticity.
7

---

Table Robust OOD Detection: MNIST vs EMNIST (MLP and LeNet) and CIFAR-IO 10 CIFAR-
100 (VGG-*). BP: Bound-Pree Propagation (baseline); FL: Functional Lagrangian (ours). The reported times correspond to the median of the 500 samples.
Time (s)
GAUC (%)
OOD Task
Model
#ncurons
#params
AAUC (%)
BP
FL
BP
FL
0.01
40.1
+38.8
55.4
65.0
86.9
(EJMNIST
MLP
256
2k
0.03
40.1
+37.4
38.5
53.1
88.6
0.05
38.4
+36.2
18.9
36.1
88.8
0.01
53.2
+52.4
0.0
29.8
71.6
(EJMNIST
LcNet
0.3M
0.IM
0.03
52.4
+51.1
0.0
14.1
57.6
0.05
55.4
+54.1
0.0
3.1
44.0
VGG-16
3.0M
83k
0.001
50.8
+35.0
0.0
25.6
60.9
CIFAR
VGG-32
5.9M
0.2M
0.001
82.3
+40.9
0.0
25.8
64.7
VGG-64
11.8M
0.5M
0.001
371.7
+48.7
0.0
29.5
67.4
Experiments
Here, we empirically validate the theoretical flexibility of the framework and its applicability to across several specifications and networks. Crucially, show that framework permits verification of probabilistic specifications by effectively handling parameter and input stochasticity across tasks. For all experiments, consider layer decomposition of the network such that the intermediate inner problems can be solved in closed form with linear multipliers (See Appendix C.4). We use different bound- bound-propage propagation algorithms to compute activation bounds based the task, and generally refer to these methods as BP. Our code is available at htttt::///// /ttps:://ithub www.huu..ooooooooooommooo..e.eee wwt.ccmm///c/eeeeeeee (deepminddjaas jax_rriffy
5.1 Robust OOD Detection on Stochastic Neural Networks
Verification Task. We consider the task of robust OOD detection for stochastic neural networks under bounded &o inputs perturbation with radius e. More specifically, we wish to use threshold on the softmax value (maximized across labels) classify whether a sample is OOD. By using verified upper bounds on the softmax value achievable under c-perturbations, we can build a detector that classifies OOD images as such even under perturbations. We use the Area Under the Curve (AUC) to measure the performance of the detector. Guaranteed AUC (GAUC) is obtained with verified bounds on the softmax, and Adversarial AUC (AAUC) is based on the maximal softmax value found through an adversarial attack. We consider two types of stochastic networks: i) Bayesian neural networks (BNNs) whose posterior distribution re-use the MLP with two hidden layers of 128 units from Wicker et al. [220 (denoted MLP)
truncated Gaussian distribution. We
and truncate their Gaussian posterior distribution to three standard deviations, ii) we consider MC- Dropout convolutional neural networks, namely use LeNet (as in Gal and Ghahramani (2016]) and VGG-style models (Simonyan and Zisserman 2013). For MLP and LeNet, we use MNIST as training data, and EMNIST distr--iittiiuttio data. For the VGG models, training data, and CIFAR- 100 as duttr--distribution data.
CIFAR-10 as
Method. We use linear Lagrangian multipliers, which gives closed-form solutions for all intermediate inner maximization problems (Appendix C.4). In addition, we leverage Proposition to solve the final inner problem with the softmax specification objective. Further experimental details, including optimization nyper-parameters, are available in Appendix E. We compute activation bounds based an extension of Bunel al. [2020] to the bilinear case, referred to BP in Table [ The corresponding bounds are obtained with probability 1, and we were to relax these guarantees to only hold up some probability lower than note that the method of [Wicker et al. 20200) would offer tighter bounds.
The functional I Lagrangian (FL) approach systematically outperforms the Bound- Propagation (BP) baseline. We note that in particular, FI. significantly outperforms on dropout CNNs, where BP is often unable to obtain any guarantee at all (See Table [] As the size of the VGG
Results.

---

Table 2: Adversarial Robustness for different BNN architectures trained on MNIST from Wicker et al. [2020]. The accuracy reported for FL and LBP is the % of samples we can certify as robust with probability 1. For each model, we run the experiment for the first 500 test-set samples.
#layers
#neurons
LBP Acc. (%)
FL Acc. (%)
LBP Time (s)
FL Time (s)
128
67.0
77.2
16.7
+518.3
0.025
256
66.2
76,4
16.1
+522.8
512
60.2
74.6
16.0
+522,4
256
57.0
70.0
16.8
+516.5
2
0.001
512
79.6
87.4
17.0
4517.3
1024
39.4
42.4
17.1
4514.1
model increases, we can observe that the median runtime of BP increases significantly, while the additional overhead of using FL. remains modest.
5.2 Adversarial Robustness for Stochastic Neural Networks
Verification Task. For this task, we re-use the BNNs trained on MNIST (LeCun and Cortes 2010) from Wicker et al. [2000] (with the Gaussian posterior truncated to three standard deviations bounded). We use the same setting as Wiikker al. [2020] and study the classification robustness under &or perturbations for 1-layered BNNs and 2- layerd BNN at radii of = 0.025 and 0.001 respectively. We recall, as mentioned earlier in Section that the specification we study different from that studied in [Wicker et al. 2020).
Method We use the same solving methodology in Section 5.1 To compute bounds the activations, we use the bilinear LBP method proposed in Wicker et 2020
Results. Across settings (Table our approach is able to significantly improve on the guarantees provided by the LBP baseline, while also noting that our method incurs an increased compute cost.
5.3 Distributionally Robust OOD Detection
Verification Task. We bound the largest softmax probability across all labels for OOD inputs noisy perturbations of the input where the noise is drawn from a family distributions with only two constraints for each p Pooise: w E [-c, e] with prob. LEwop |exp (wt)) S exp (o²(/2). for given constraints E, o > 0. The first constraint corresponds to restriction on the support of the noise distribution, and the second constraint requires that the noise distribution is sub-Gaussian with parameter a. We note that no prior verification method, to the best of our knowledge, addresses this setting. Thus, as baseline, we use methods that only use the support of the distribution and perform verification with respect to worst-case noise realizations within these bounds.
Method. We use 3-layer CNN trained MNIST with the approach from Hein et al. 2019 (details in Appendix E.3). and we employ EMNIST as the out-of-distribution data to be detected. We functional multipliers of the form: A (x) = 0% for k: 1 and imeear-xxponentia multipliers for the input layer: \ (x) 8T x + exp (>/ K1) (method denoted by FL-LinExp). As baselines, we consider a functional Lagrangian setting with linear multipliers that only uses information about the expectation of the noise distribution (method denoted by FL.-Lin), and BP baseline that only uses information about the bounds on the support of the noise distribution ( (-c, c) (activation bounds computed using Bunel et al. (2020). The inner maximization of gl for K
k > 2 can be done in closed form and we use approaches described in Propositions! and to respectively solve 0.04, 0.1.
max go. max ΦI and max gk. We
Results. FL.-LinExp achieves the highest guaranteed AUC (See Table 3 showing the value of accounting for the noise distribution, instead of relying only on bounds on the input noisc.

---

Table 3: Guaranteed Area Under Curve (GAUC) values in distributionally robust setting. The
stochastic formulation of the Functional Lagrangian with Linear-Eaa Expeear-xxpnnntiall (LinExp) multipliers gets the highest guaranteed AUC.
GAUC (%)
Timing (8)
Model
#ncurons
BP
FL-Lin
FL.-LinExp
BP
FL-Lin
FL-LinEXp
CNN
9972
5.4
5.6
23.2
227.7
+661.8
+760.7
Conclusion
We have presented general framework for verifying probabilistic specifications, and shown significant improvements upon existing methods, even for simple choices of the Lagrange multipliers where we can leverage efficient optimization algorithms. We believe that our approach can be significantly extended by finding new choices of multipliers that capture interesting properties of the verification problem while leading to tractable optimization problems. This could lead to discovery of new verification algorithms, and thus constitutes exciting direction for future work.
Limitations. We point out limitations in the approach suggested by this work. First, the guarantees provided by our approach heavily depend on the bounding method used to obtain the intermediate bounds- this is consistent with prior work on verifying deterministic networks [Dathathri et al. 2020 Wang et al., 2021], where tighter bounds result in much stronger guarantees. Second, as noted Section 3.1 our approach can only handle probability distributions that have bounded support, and alleviating this assumption would require further work.
Broader Impact and Risks. Our work aims improve the reliability of neural networks in settings where either the model or its inputs exhibit probabilistic behaviour. In this context, we anticipate this work to be largely beneficial and do not envision malicious usage. However, the guarantees of our method crucially depend on having an accurate modeling of the uncertainty. Failing that can result in overestimation of the reliability of the system, which can have catastrophic consequences in safety-critionn scenarios. In this regard, we advocate special care in the design of the specification when applying our approach to real-worle cases.
10

---

References
Maksym Andriushchenko, Francesco Croce, Nicolas Flammarion, and Matthias Hein. Square attack: query-efficiiet black-box adversarial attack via random search. European Conference Computer Vision, 2020.
Dimitri Bertsekas. Convex optimization algorithms. Athena Scientific Belmont, 2015.
Julian Bitterwolf, Alexander Meinke, and Matthias Hein. Provable worst case guarantees for the detection of out-of-distribution data. Advances in Neural Information Processing Systems, 2020.
Rudy Bunel, Oliver Hinder, Srinadh Bhojanapalli, al. An efficient nonconvex reformulation of stagewise convex optimization problems. Advances in Neural Information Processing Systems, 2020.
Luca Cardelli. Marta Kwiatkowska, Luca Laurenti, Nicola Paoletti, Andrea Patane, and Matthew Wicker. Statistical guarantees for the robustness of bayesian neural networks. International Joint Conference on Artificial Intelligence, 2019.
Sumanth Dathathri, Krishnamurthy Dvijotham, Alexey Kurakin, Aditi Raghunathan, Jonathan Uesato, Rudy Bunel, Shreya Shankar, Jacob Steinhardt, lan Goodfellow, Percy Liang, et al. Enabling certification of verification -agnotoii networks via mnemory-efficiee semidefinite programming. Advances in Neural Information Processing Systems, 2020.
Krishnamurthy Dvijotham, Marta Gamelo, Alhussein Fawzi, and Pushmeet Kohli. Verification of deep probabilistic models. NeurIPS 2018 Workshop on Security in Machine Learning, 2018a.
Krishnamurthy Dvijotham, Robert Stanforth, Sven Gowal, Timothy A Mann, and Pushmeet Kohli. A dual approach to scalable verification of deep networks. Conference Uncertainty in Artificial Intelligence, 2018b.
Ruediger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. International Symposium on Automated Technology for Verification and Analysis, 2017.
Mahyar Fazlyab, Manfred Morari, and George Pappas. Probabilistic verification and reachability analysis of neural networks via semidefinite programming. Conference on Decision and Control (CDC), 2019.
Mohammad Javad Feizollahi, Shabbir Ahmed, and Andy Sun. Exact augmented lagrangian duality for mixed integer linear programming. Mathematical Programming, 2017.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. International Conference on Machine Learning, 2016.
Robert Grone, Charles R Johnson, Eduardo Sá, and Henry Wolkowiez. Positive definite
completions of partial hermitian matrices. Linear algebra and its applications, 1984.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. Computer Vision and Pattern Recognition, 2016.
Matthias Hein, Maksym Andriushchenko, and Julian Bitterwolf. Why relu networks yield high- confidence predictions far away from the training data and how mitigate the problem. Conference on Computer Vision and Pattern Recognition, 2019.
Guy Katz, Clark Barrett, David L. Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. International Conference on Computer Aided Verification, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. NIST, 2010.
Changliu Liu, Tomer Arnon, Christopher Lazarus, Clark Barrett, and Mykel Kochenderfer. Algorithms for verifying deep neural networks. Foundations and Trends in Optimization, 2021.
11

---

Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. International Conference on Learning Representations, 2017.
Rhiannon Michelmore, Matthew Wicker, Luca Laurenti, Luca Cardelli, Yarin Gal, and Marta Kwiatkowska. Uncertainty quantification with statistical guarantees in end-to-end autonomous driving control. International Conference Robotics and Automation (ICRA), 2020.
Matthew Mirman, Timon Gehr, and Martin Vechev. Robustness certification of generative models. International Conference on Programming Language Design and Implementation, 2021.
Angelia Nedich and Asuman Ozdaglar. A geometric framework for nonconvex optimization duality using augmented lagrangian functions. Journal of global optimization, 2008
Aditi Raghunathan, Jacob Steinhardt, and Percy S Liang. Semidefinite relaxations for certifying robustness to adversarial examples. Advances in Neural Information Processing Systems, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogmition. International Conference on Learning Representations, 2015.
Gagandeep Singh, Timon Gehr, Matthew Mirman, Markus Püschel, and Martin Vechev. Fast and effective robustness certification. Advances in Neural Information Processing Systems, 2018.
Scbastian Thrun, Wolfram Burgard, and Dieter Fox. Probabilistic Robotics (Intelligent Robotics and Autonomous Agents). The MIT Press, 2005.
Lieven Vandenberghe and Martin S Andersen. Chordal graphs and semidefinite optimization. Foundations and Trends Optimization, 2015.
Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and Zico Kolter. Beta- crown: Efficient bound propagation with per-neuron split constraints for complete and incomplete neural network verification. ICML 2021 Workshop on Adversarial Machine Learning. 2021.
Lily Weng, Pun-Yu Chen, Lam Nguyen, Mark Squillante, Akhilan Boopathy, Ivan Oseledets, and Luca Daniel. Proven: Verifying robustness of neural networks with probabilistic approach. International Conference on Machine Learning, 2019.
Matthew Wicker, Luca Laurenti, Andrea Patane, and Marta Kwiatkowska. Probabilistic safety for bayesian neural networks. Conference on Uncertainty in Artificial Intelligence, 2020.
Matthew Wicker, Luca Laurenti, Andrea Patane, Zhoutong Chen, Zheng Zhang, and Marta Kwiatkowska. Bayesian inference with certifiable adversarial robustness. International Conference on Artificial Intelligence and Statistics, 2021.
Dong Yu and Li Deng, Automatic Speech Recognition: A Deep Learning Approach. Springer, 2014.
Huan Zhang, Tsui-Wa Wei Weng, Pin- Yu Chen, Cho-Jui Hsieh, and Luca Daniel, Efficient neural network robustness certification with general activation functions. Advances in Neural Information Processing Systems, 2018.
12


Reviews:
[{"review_id": "siXs5HAGgd", "reviewer": "Reviewer_KLAd", "summary": "The paper targets the verification of probabilistic specifications of neural networks, e.g., where the specification to a deterministic network can be probabilistic, or for verifying deterministic specifications over a probabilistic neural network. The authors pose the probabilistic verification as an intractable stochastic optimization problem. They leverage functional lagrangian framework to solve the problem approximately. The framework enables the decomposition of the problem into smaller sub-problems which are relatively tractable to solve. The authors experimentally demonstrate the effectiveness of their approach on three specifications against Wicket et al. and obtain more precise results while remaining scalable.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Originality: The use of functional lagrangian optimization for probabilistic neural networks verification is an original contribution to the best of my knowledge. The authors develop tractable algorithms that exploit the structure of the verification problem for approximately solving the optimization problems. This enables them to verify novel specifications such as distributionally robust OOD detection not possible with prior work. \n\nQuality: The verification framework provided in this work is sound and the experimental results are convincing. In the experiments, the authors use a closed-form solution for the inner optimization problems by instantiating their framework with linear multipliers. This is shown to be equivalent to Dvijotham et al. It is not clear to me whether the closed-form solution is the best solution possible layerwise or an approximation when considering linear multipliers? The Lagrangian dual from Dvijotham et al. does not provide the best layerwise convex relaxation and more precise relaxations were achieved by [1,2].  \n\nClarity: The paper is well motivated and understandable. The authors demonstrate the instantiation of their framework well on an example. I believe that the high-level ideas of the paper should be accessible to a relatively wider audience. However, the authors do not provide details about the CPU cluster used for their experiments in Section 5.1. It is also not clear to me whether the experiments in Section 5.3 were performed on CPUs or GPUs. \n\nSignificance: There is relatively less work on verifying probabilistic specifications compared to the deterministic ones. The authors provide a generalized framework for verifying such specifications and show how the existing works can be seen as an instantiation of their framework. I believe that this is a significant contribution and may lead to more specialized verification algorithms with better scalability while maintaining sufficient precision in the future.\n\nMore questions:\n1. Is the formulation with functional lagrangian presented here the tightest possible or one can define non-decomposable lagrangians which might be more precise?\n\n2. The closed-form solution in C.4 assumes box constraints on x, therefore, processing each neuron independently. If instead, one considered polyhedral dependencies between the input neurons, will the bounds will improve even with linear multipliers?\n\n3. What is the dropout rate for VGG-x networks considered in the experiments?\n\n4. Will the source code of the verifier be publicly available?\n\nReferences:\n1. The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification.\n2. Beyond the Single Neuron Convex Barrier for Neural Network Certification.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors address these concerns adequately in their paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "k6u-rQvcBfN", "reviewer": "Reviewer_361J", "summary": "This paper presents a general formulation of probabilistic specifications for neural networks which can capture both probabilistic networks and uncertain inputs. The authors generalize the notion of Lagrangian duality by defining functional Lagrange multipliers that can be arbitrary functions of the activations at a given layer. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Strengths\n------------\n- Probabilistic specifications are an important yet underexplored area in neural network verification\n- The proposed general framework can handle stochasticity in both the specifications and the network architectures in a unified manner\n- The functional Lagrangian formulation is interesting \n- The results demonstrate gains over existing probabilistic verification methods for some properties\n\nWeaknesses\n-----------------\n- No clear demonstration of the relationship between the probabilistic guarantees and actual attack success rate using SOTA attacks.\n- It is not clear whether it is feasible for the framework to verify other types of property beyond the ones presented in the paper. \n\nThe authors propose a new probabilistic verification framework for neural networks that can handle stochasticity both in the input specifications as well as model architectures. The proposed functional Lagrangian formulation is interesting. The results seem to indicate gains over existing probabilistic verification methods. However, the implications of probabilistic verification in terms of attack success are not clear to me. What are the actual attack success rates for probabilistically verified networks? Are they lower than unverified ones? The authors did not provide any data. Moreover, it is not clear how generic the proposed framework is. The authors mention that in many cases obtaining a non-trivial upper bound is challenging. What are such cases? Beyond the properties presented in the paper, what other types of properties can be supported by the framework? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "YtmwIq9s4VE", "reviewer": "Reviewer_jAE7", "summary": "This paper proposes a general framework for probabilistic robustness verification, with both stochastic networks and probabilistic specifications. The core technique is based on the generalization of Lagrangian duality where the multipliers are functional multipliers and probabilistic constraints are allowed. Under the proposed framework, the paper demonstrates several applications, including robust OOD detection on stochastic NN, adversarial robustness verification for stochastic NN, and distributionally robust OOD detection. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Pros:\n* The framework this paper proposes is general one for probabilistic robustness verification, that supports both stochastic networks and probabilistic specifications. And the verification has certified guarantees.\n* There are empirical demonstrations for the proposed framework, which show the benefit of using functional Lagrangian.\n* The paper is clearly written on introducing the techniques, experiments, limitations and social impact. \n\nCons:\n* The proposed method seems slow (much slower than baseline).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper has discussed them in the last section.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "VMiZWrmqoOh", "reviewer": "Reviewer_XbVP", "summary": "The paper proposes a framework for giving mathematical guarantees on neural networks with probabilistic specifications, e.g. for robustness across distributions or for robustness of models with non-deterministic outputs. The authors first formulate the abstract framework in terms of functional lagrangians and then show how to apply these by using concrete applications and concrete function classes for the lagrangians.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Strengths:\nThe paper tackles an important problem and provides general framework from which further methods can be developed. The novel task of worst-case robustness with respect to a family of out-distributions is a valuable contribution. A fair number of examples for the application of the authors' proposed method is given. Implementing the method is technically non-trivial and thus a contribution (more so if the code is published).\n\nWeaknesses:\nAs the authors openly admit, their approach can only provide certificates for models with outputs that are bounded with probability 1 in each layer, which does pose a practical limitation. \nIt is not always clear from the experiments how tight the final bounds are. Table 1 computes an AAUC as upper bound on the worst-case AUC but in Table 3 it should also be possible to give an empirical upper bound on the worst-case AUC by empirically finding an adversarial noise distribution that produces a low AUC.\nBecause the models were trained in a certification agnostic way, some of the threat models (CIFAR in Table 1 and 2 layers in Table 2) are so small that they would not even allow for any change at all when pixel values are constrained to lie on i/255 for i in {0,...,255}. As such, these guarantees seem fairly meaningless in practice. Using an epsilon of at least 1/255 would help fix this.\n\nCorrectness:\nAs far as I verified (no proofs) the math seems correct.\n\nClarity:\nIt seems to me that line 109 has sloppy notation when defining distributionally robust OOD detection. omega is in the set of distributions, but $x_\\mathrm{ood}$ is in $\\mathbb{R}^d$. It is clear what the authors meant to convey but this should be improved.\nWhile the example starting in line 164 is simple and illustrative, I don't find it obvious how to actually write this in terms of probabilistic neural network layers as defined in Section 2.1. I think writing this explicitly (what is $\\pi(x_1|x_0)$ etc.) in the appendix would help make the paper more readable. \n\nRelation to prior work:\nThe relation to prior work is sufficiently discussed.\n\nReproducibility:\nUnfortunately, the authors did not provide code. However, the information in the appendix seems sufficient in order to implement their method.\n\nAdditional feedback:\nFormatting in Table headers. Shouldn't be all italic.\nLine 47: \"for e.g.\" = \"for for example\" \nFormatting of \"softmax\" in line 234 is inconsistent with formatting in lines 110, 118, 232.\nInconsistent capitalization of \"Section\" between main text and checklist.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the authors adequately address this.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers unanimously acknowledged the technical contributions in providing mathematical guarantees on neural networks with probabilistic specifications. The authors' responses also addressed the reviewers' concerns. It's a clear accept.
Decision: Accept (Spotlight)