Safety Guarantees for Neural Network Dynamic Systems via Stochastic Barrier Functions
Authors: Rayan Mazouz
Karan Muvvala
Akash Ratheesh Babu
Luca Laurenti
Morteza Lahijanian
Venue: NeurIPS 2022 Accept (2022)
Keywords: Safety Certificate
Neural Networks
Stochastic Dynamical Systems
Barrier Functions
Convex Optimization
Robotics and Control

Abstract: Neural Networks (NNs) have been successfully employed to represent the state evolution of complex dynamical systems.  Such models, referred to as NN dynamic models (NNDMs), use iterative noisy predictions of NN to estimate a distribution of system trajectories over time. Despite their accuracy, safety analysis of NNDMs is known to be a challenging problem and remains largely unexplored.  To address this issue, in this paper, we introduce a method of providing safety guarantees for NNDMs.  Our approach is based on stochastic barrier functions, whose relation with safety are analogous to that of Lyapunov functions with stability.  We first show a method of synthesizing stochastic barrier functions for NNDMs via a convex optimization problem, which in turn provides a lower bound on the system's safety probability.  A key step in our method is the employment of the recent convex approximation results for NNs to find piece-wise linear bounds, which allow the formulation of the barrier function synthesis problem as a sum-of-squares optimization program.  If the obtained safety probability is above the desired threshold, the system is certified.  Otherwise, we introduce a method of generating controls for the system that robustly minimize the unsafety probability in a minimally-invasive manner.  We exploit the convexity property of the barrier function to formulate the optimal control synthesis problem as a linear program.  Experimental results illustrate the efficacy of the method. Namely, they show that the method can scale to multi-dimensional NNDMs with multiple layers and hundreds of neurons per layer, and that the controller can significantly improve the safety probability.

Safety Guarantees for Neural Network Dynamic Systems via Stochastic Barrier Functions
Rayan Mazouz Karan Muvvala' Akash Ratheesh', Luca Laurenti', Morteza Lahijanian
Department of Aerospace Engineering Sciences, University of Colorado Boulder, USA
2 Delft Center for Systems and Control, Delft University of Technology, The Netherlands
rayan mazouz, karan.
mwwvalu. karan.muvvala.
akash. waw.herrthheehhhhhoom maatteeeai lahi jawiaaannnoloonnannnaeeo edu
11 laurenti wwtlllrruuleer..
Equal Contribution
Abstract
Neural Networks (NNs) have been successfully employed to represent the state evolution of complex dynamical systems. Such models, referred to NN dynamic models (NNDMs), use iterative noisy predictions of NN to estimate a distribution time. Despite their accuracy, safety analysis of NNDMs
of system trajectories is known to be a challenging problem and remains largely unexplored. To address this issue, in this paper, we introduce method of providing safety guarantees for NNDMs. Our approach is based on stochastic barrier functions, whose relation with safety are analogous that of Lyapunov functions with stability. We first show method of synthesizing stochastic barrier functions for NNDMs via a convex optimization problem, which in turn provides a lower bound on the system's 's safety probability. A key step in our method is the employment of the recent convex approximation results for NNs to find piece-wise linear bounds, which allow the formulation of the barrier function synthesis problem as sum-of-squares optimiza- tion program. If the obtained safety probability above the desired threshold, the system is certified. Otherwise, we introduce method of generating controls for the system that robustly minimize the unsafety probability in a minimally-invasion manner. We exploit the convexity property of the barrier function to formulate the optimal control synthesis problem as a linear program. Experimental results illustrate the efficacy of the method. Namely, they show that the method can scale to multi dinleiidmmesionnll NNDMs with multiple layers and hundreds of neurons per layer, and that the controller can significantly improve the safety probability.
1 Introduction
Safety is major concern for autonomous dynamical systems, especially in safety-critical applications. Examples include UAVs, autonomous cars, and surgical robots. To this end, various methods are developed to provide safety guarantees for such systems [+3 Most of these methods, however, assume (simple) analytical models, which are often unavailable or too expensive to obtain due to complexity (nonlinearities) in real-world systems (4) This has given rise to recent efforts to harvest the representational power of neural networks (NNs) to predict how the state of a system evolves over time, referred to as NN dynamic models (NNDMs) 6) Despite their efficient and accurate representation of realistic dynamics, it has been difficult to make formal claims about the behavior of NNDMs over time. This poses a major challenge safety-critical domains: how to provide safety guarantees for NNDMs?
In this paper, we propose a framework to provide safety certificates for NNDMs. The approach is based on stochastic barrier functions 7 g] whose role for safety is analogous to that of Lyapunov functions for stability, and which can guarantee forward invariance of a safe set. Specifically,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

show a method of synthesizing barrier functions for NNDMs via an efficient convex optimization method, which in turn provides lower bound on the safety probability of the system trajectories. The benefit of our approach is that it does not require unfolding of the NNDM to compute this probability; instead, we base our reasoning on non- non-negative super-martingale inequalities to bound the probability of leaving the safe set. The key to this is to utilize the recent convex approximation results for NNs to obtain piece-wise linear bounds, and a formulation of the optimization problem that enables the use of efficient solvers. If the obtained safety probability is above a desired threshold, the system can be certified. For the cases that such safety certificates cannot be provided, we introduce a method of generating controls for the system, which robustly maximizes the safety probability in momimally-invasiin manner. We exploit the convexity property of the barrier function to formulate the control synthesis problem using state-of-thh-arr RI. techniques [1 illustrate the efficacy of the method. Namely, they show that the method can scale to multi-dimensional models with various layers and hundreds of neurons per layer, and that the controller can significantly improve the safety probability.
linear program. Experimental results on various NNDMs trained
In summary, this paper makes the following main contributions: (i) method of computing lower bound for the safety probability of NNDMs via stochastic barrier functions and efficient nonlinear optimization, thereby providing safety guarantees, (ii) a correct-by-constructie framework for NNDMs to ensure safety while being maiimmlll--invasivee i.e., intervening only when needed, (iii) demonstration of the efficacy and scalability of the framework in benchmarks on various NNDMs with multiple architectures, i.c., multiple hidden layers and hundreds of neurons per layer.
control synthesis
Related Work In recent years, NNs have been successfully employed to model complex dynamical systems [5] 6 Such models use iterative noisy predictions of an NN to estimate the distribution of the system over time. They provide means of predicting state evolution of the systems that have no analytical form, c.g., soft roboties [1]. In addition, because of their ability to quickly unfold trajectories, NNDMs have been used to enhance controller training in Reinforcement Learning (RL) frameworks p I. In these works, specifically, a NNDM of the system is trained in closed-loop with an NN controller, which can be concatenated in single NN representing the dynamics of the closed-loop system. Despite their popularity and increased usage, little work has gone to safety analysis of NNDMs. This paper aims to fill this gap.
Barrier functions provide formal methodology to prove safety of dynamical systems K The sfate-of-the-art to find stochastic barrier functions is arguably to rely on Sum-of-S
(SOS)
optimization [8]. Barrier certificates obtained via SOS optimization have been studied for determin- istic, uncontrolled nonlinear systems (15), and control -fffine stochastic systems [6 [8. as well as for hybrid models [13 14). In addition, the control synthesis formulation in this paper relaxes the
limitations of the existing SOS methods, which generally leads to non-convex optimization problem
g by reducing it to simple linear program.
Many recent studies have focused on the verification of NNs. However, most of them only aim to provide certification guarantees against adversarial examples 17). with approaches ranging from SMT [8]. and convex relaxations [19] to linear programming 20) Such methods, because of their local nature, cannot be directly employed to perform safety analysis on the entire state space and over the trajectories as required for NNDMs. Another line of work focuses on infinite time horizon safety of Bayesian neural networks (21). or the verification of neural ODEs with stochastic guarantees
22 They consider neural network controllers with known dynamics 23 Other methods have been employed for trajectory-level properties of NNs based on solution of the Bellman equations
24 formal (finite) abstractions [25). and mixed integer programming (26). which do not support noisy dynamics. In contrast, our approach supports additive noise and only requires to check static properties on the NN by showing that there exists function whose composition with the NN forms a stochastic barrier function.
2 Problem Formulation
In this work, we are interested in providing safety guarantees for dynamical systems that are described by NNs. Specifically, we consider the following discrete-time stochastic process whose time evolution is given by iterative predictions of an NN
X = f (xx) + VR.
k N, Xg. V2 E R
(1)

---

where f is a trained, fully- colly-oonnected. feed-forward NN with general continuous activation functions, and represents the maximum likelihood weights. Term Va is random variable modelling an additive noise of stationary Gaussian distribution with zero mean and covariance matrix R E IR IR i.e, the probability density function of V3 is (T |0, R).
Remark 1. System ① can be viewed as a closed-loop system, where f is the composition of NNDM (that represents the open-loop system) with an NN controller. NNDMs such as the one in System D are increasingly employed in robotics for both model representation and NN controller training. These models are often obtained by state-of-the (9 or perturbutions (slep response) of the actual system (e.g., (/2)).
model-bused RL techniques (e.g..
The evolution of System ①T) can characterized by the predictive posterior distribution Px(# xx), which describes the probability density of Xk+1 when X2 is induced by noise Vi. and hence is Gaussian with mean f")()) and covariance R. i.c. Px x) = Na (z), R).. For a subset of states X C I2" and (initial) state call T(X 2) = Jx (x æ)dž the stochastic kernel of System (I). From the definition of T follows that, for given initial condition X, Zy R", X is a Markov process with a well-defined probability measure Pr uniquely generated by the stochastic kernel T (27] Proposition 7.45]. For Xo, Xx IR, this probability measure is inductively defined as
E R". This distribution
R., we
Pr|xo Xo] 1x, (2o),
Pr|x Xx X =] = Ix),
where indicator function 1 1x, (zo) = if E Xo, otherwise O. The definition of Pr allows one to make probabilistic statements over the trajectories of System (T). In this work, we are particularly interested in main problems: safety certification and safe controller synthesis for System (
Problem 1 (Safety Certificate). Let X, C R and Xo S Xg be basic closed semi-algebraic seis representing respectively the safe set and the set of initial states. Denote the probability that the system initialized in Xo remains in the safe set in the next N E N20 steps by
Pa(Xs, No, 10 Pr[Voo E Xo, Vk S N, E X.).
(2)
Then, given threshold 6g E [0, provide a safety certificate for System by proving that XX, 2 8g.
Problem Problemssecke seeks to compute the probability that x2 remains within a safe set, c.g., it avoids obstacles or any undesirable states. Computation of this probability is particularly challenging because System (I) stochastic and NN (f"") is generally a non-convex function. The assumption that X, and X₂ are basic closed semi-algen alii-aleebracc sets is not limiting, as these sets are defined an intersection of finite number of polynomial inequalities and, for instance, include convex polytopes and spectrahedra (28)
In the case that safety certificate cannot be generated, are interested in synthesizing controller that by-design guarantees safety. To this end, we extend System 11 with an affine input
X = fth (xx) + gu, + Vk-
(3)
where g R > RR is given, U1 E U C IR.S is a control action, and U is bounded. Our goal is to synthesize feedback controller æ R U such that un = x (xx) guarantees safety of System (3)
Problem 2 (Safe Control Synthesis). Let X2 C Rn and X₂ C Xg be basic closed semi remi-algebraic sets representing respectively the safe set and the set of initial states, and N E N>u time horizon. Then, given threshold 8n, synthesize a feedback controller v such that Px(X,, , Xn, N, T) 2 82, where (x(X,, Xo, N,T) π) is the safety probability obtained for control-affine System
Remark 2. There may exist many possible controllers that are solutions to Problem 2 Since System ① represents closed-loop system with a given controller, one may want specifically synthesize a safety controller that is "minimally invaiiveevvvve i.e., it minimally intervenes to guarantee safety. In Section
we elaborate on this notion and introduce methods of generating such controllers. 3
Overall Approach Our approaches to Problems I and 2 are based on (stochastic) barrier functions. Specifically, we aim to synthesize barrier functions that can serve as a safety certificate by providing lower bound for P.. To achieve this, we rely on recent results for local convex relaxation of an NN to find piece-wise linear over- and under-approximations of f" This allows us to formulate the problem of finding stochastic barrier function for System I as SOS optimization problem.
3

---

Our saanimalll-invasivee control synthesis method (Problem 2 focuses on injecting controls to System (3) only in the regions of the state space that potentially contribute unsafety the system. To this end, we exploit two main properties of the barrier function: the required (super-) martingale property and the convexity property of SOS polynomials. The former allows us to design a method of identifying the "unsafe" regions, and the latter enables us to formulate a Linear Programming (LP) optimization problem to find controllers that robustly minimize the probability of unsafety.
Remark 3. For ease of presentation, g in (3) is taken be constant, however, note that the proposed approach can also handle g being a continuous function of z. or even a NN. For the latter, introduce an interval bound propagation approach in Section 4.7 that allows the computation of upper and lower bounds on g(x), which in turn can be incorporated in the LP optimization formulation in Section for control synthesis (Problem in straightforward manner.
3
Preliminaries
In this section, we provide brief background stochastic barrier functions and non-negative polynomials, which are central components of our framework.
3.1 Stochastic Barrier Functions
Consider stochastic process X F(xg. Vk), where Xx X C V R is well- defined stochastic process, and F X x V + X is a locally Lipschitz continuous function. Then, given initial Xo X, safe set X, X, and unsafe set Xn X, a twice differentiable function B : X + I is called a stochastic barrier function or simply barrier function if the following conditions hold for a 2 1 and 3, E [0, 1]:
B(x) 20 0
Vo X
(4a)
B(x) 5
Vz Xo
(4b)
B(x) 21
Yr Xn E[B(F(z, e)) x] s B(x)/a+
(4c)
Vz E X,
(4d)
If such B exists, then for any N E N20, it follows, assuming a without loss of generality, that
Pr|vk < N, X E X, xo Xo] 2 1 (1) + BN).
(5)
Intuitively, Conditions 4ap-44 (4 allow one to use non-negative super-martingale inequalities bound the probability that the system reaches the unsafe region. This results in the probability bound in (5) (see (29 Chapter 3, Theorem 3)). A major benefit of using barrier functions for safety analysis is that
while Conditions (4b)- (4d) are static properties, they allow one to make probabilistic statements on the time evolution of the system without the need to evolve the system over time.
3.2
Non-negative Polynomials
Synthesis of barrier functions can be formulated as a nonlinear optimization problem. To solve it efficiently via convex programming, we formulate the problem using SOS polynomials, which is sufficient condition for polynomial non-negativity 30 This formulation allows the use of efficient semidefinite programming solvers, which have polynomial worst-case complexity BI].
Ofai-urr-Ssurs (SOS) E IR" if there exists some polynomials X i = 1,...,V, for some r E N, such that M(x) -E X (x)) If (xx) is an SOS, then X(x) 2 0 for all E RD. The set of all SOS polynomials is denoted by A.
Definition 1 (SOS Polynomial). A multivariate polynomial A(x) is
Now, consider a basic closed semi- semi-algebraic set X {x E R" h2(x) 2 0 Vi (1..... .......33 (},, which defined as the intersection of polynomial (hx( inequalities. Then, Proposition I Jallows one to enforce nog-negay on these semi- algebricc sets.
Let X C Rn be a compact basic semi-algebraic defined as = (x E Rn he(x) 2 0 Vi E (1....,1}} where hx(x) is polynomial. Then, polyno-
Proposition 1 (Putinar's Certificate, (32
mial 7x)) is non-negative on X if. for some do (o(z), >x(x) E A. 7(x) = >o(x)) + + (x(x))a(x))

---

Corollary 1. Let 7(x) be a non-negative polynomial on X E (I.....I} I, and h(z) be an I-dimensional vector of palynomials with hz(z) as its i-th dimension for allie E (T....1)). Further, let L be an l-dimensional vector of SOS polynomials, i.e, the i-th element is (1)) E A. Then, it holds that 7(x) L h(()) E A.
h,(2) 2000 vi e
4 Barrier Functions for Neural Network Dynamical Models
In this section, we introduce formulation for synthesizing a barrier function that guarantees safety of System ① Our approach relies on the local convex relaxations of f which we use to formulate an SOS optimization problem that generates a valid barrier function for System
4.1 Local Convex Relaxation of NNDMs
Our approach uses convex relaxation of f Specifically, we utilize the recent relaxation results for NNs [19] to compute piece-wise linear functions that under- and over-approximate f The advantage of this method is that it is computationally efficient and produces tight bounds for small neighborhoods. To this end, we first partition X, to finite set of regions Q = {21, ..... 2 qQq) ). where S X, for all i E {I..... } is a basic (closed) semi-algebraic set. Such a decomposition can be obtained using, e.g., a grid or half-spaces. Then, for every q Q, we compute linear bounds
Fz(x) = Agt + by such that Vx E
[(x)= ff S (x) (6)
The above linear functions can be produced in several ways. One method is to forward propagate the bounds the input domain of (zx) using Interval Bound Propagation (IBP) based approaches
33 34.
These approaches are efficient but generally lead to loose approximations. Another method
Linear Relaxation based Perturbation Analysis (LiRPA) algorithms. which perform a symbolic back propagation followed by a forward evaluation of the bounds [35] 36 19]. Such LiRPA based algorithms produce tighter bounds but can be slow. our implementation, we use the off-the-sheii
toolbox
36
compute F, (z) and f (I) in (6) for its trade-off between speed and accuracy.
4.2 Barrier Function (Certificate) Synthesis
With the above local linear bounds for f", Condition (4d) can be redefined over the partitioned regions in Q. That is,
Recall that a valid barrier function (xx) must satisfy Conditions 4b
4d
Condition (dd) can be replaced with the following constraints: for each E Q.
BI (z) 2] S B(x)/a + 3 and
(z) S f (x) < fx(
VI q.
In this formulation, f2((x) ) is (free) variable that is bounded by two linear functions, avoiding the non-convexity of f (z)). Consequently, an efficient evaluation of the constraint becomes feasible.
Remark 4. Note that there are in fact three constraints in 7 (one saper-martingale condition B and two bounds on f (x)). If they are treated separately, it leads to a conservative barrier function because each constraint needs to hold for all x E q separately. A less conservative approach is to pose all constraints for the same x at the same time. In Theorem 7 we show how this can be achieved.
As commonly practiced in the literature, e.g., 15 class of polynomial functions. Then, the degree of the polynomial becomes a design parameter. In the following lemma, we show that the degree of the polynomial must be at least for the polynomial to be a valid candidate barrier function for System []. That is, there does not exist a linear function satisfying Conditions 4b4-44)) for 1) < 1, which implies that the lower bound in (5) is trivially 0.
8 37.. restrict search for B(x) to the
Lemma 1. For k E R" and c E R. consider linear function B(x) kT x + Then, B(x) satisfies Conditions (bb) iff 0 and
Proof. There are two cases to consider: (i) k = 0: in this case B(x) c, which satisfies Conditions (4)--44) iff e = n = 1. (ii) o 0: in this case, due to the linearity of B(x), there always exists
such that B(x') < O, violating Condition 4a)
5

---

Having established that the polynomial degree must be at least 2, we further restrict (xx) to SOS polynomials. Theorem shows a formulation of the barrier function synthesis problem as an SOS program, which can be solved in polynomial time. In particular, the theorem shows how to formulate Conditions (b)- and (7 as SOS constraints.
Theorem 1 (NNDM Barrier Certificate). Consider SOS polynomial function B(x), and safe set X, {ar E 1n ha 2 0}, initial set Xo = {a R" ho 0}, unsafe set Xu IR X₃ {o E R (r) 2 0}, and partition region = {x E I (a(2) 2 0f for all E Q. Let (x)x), Co(x) and C,(x) be vectors of SOS polynomials with the same dimensions as hg. hg, and has respectively. Likewise, let Lxxx(z) and (z) be vectors of SOS polynomials with the same dimension as hyg Then, a stochastic barrier certificate (zx) for System 41 with time horizon N E No0 can be obtained by solving the following SOS optimization problem for n,. B E [0, 1]:
min 8,7
17 1 B+NN
3N
subject to:
B(x) EA,
(8a)
B(x) C (c)) +
(8b)
B(x) (x) -
(8c)
- B b) x) + +B())/a + B CT (z) (1) w)(u - (x)( EA
V4 E Q
(8d)
which guarantees safety probability Pa(X,, N) 2 11+3NN
Proof. It suffices to show that if B satisfies Constraints Sa
8d then Conditions 4a 4d are
satisfied. As Constraint (8a) guarantees that B is SOS polynomial, hence non-negative by definition, Condition (4a) holds. By Corollary it holds that if Constraints (8b)-(8) hold, then is respectively smaller that 7 in X, and greater than 1 in X.. What is left to show is that Constraint &d guarantees the satisfaction of Condition (4d). This can be done as follows. For every region E Q. the expectation term in Condition (4d) can be expressed as EIB(y +v) æi], where y is bounded by under-approximation f. (1r) and over-approximation [1((x) of f"(x) in System (T) for all x q- Then by Corollary [ Constraint (8d) is obtained for each Note that B(x) is polynomial, so if B[ v) x] also a polynomial, the condition is valid SOS constraint. Given that y + is linear, BB + v) xr] is sum of monomials in terms of y and expectation moments E(vd), where d 2 0. Since, random variable v has normal distribution, E E/e""] is constant. Therefore, By + v) x is a polynomial only in terms of (components of) y.
Remark 5. We note that Condition (&d) uses linear equations in (6 to bound (x) for all x E q. Removing the dependence on by replacing the equations for Fz(2) and f((x) with their extreme values in region q relaxes the optimization problem and results in speed-up. It is however an additional pveraapprximmation and hence the obtained safety probability bound is strictly smaller than the one generated by using the actual linear equations for fa(z) and (z). This is the classical "efficiency versus accuracy" trude-off. In our implementation, we compare the two approuches.
(x)
5 Minimally-invasive Barrier Controller Synthesis
Here, we focus on Problem 2 The assumption is that a barrier function B(x) is synthesized for System ( via Thcorem [ which has a safety probability that is lower than threshold 6g. Hence, our goal is to design feedback controller for System 2 that guarantees safety. Idcally, this controller is minimal in the interruptions causes to the system evolution. Below, we first provide a definition for minimally-invaste controller, and then show how it can be synthesized.
Recall that a feedback controller π R + U is a function that assigns a control value each state. Let Xx C X2 be the set of states, to which assigns non-zero control values, i.e., x (xr) A 0 for all E X,. Further, we denote by V(X) the volume of set X C RR. Then, we say a feedback controller is minimally-invasing if it minimizes V(X=). Moreover, we say is e-mininully-invasive if controller with an arbitrary small e. To this end, we make the observation that if the discretization of X₃ discussed in Section 4.]
v(X=) - ming V(X,') S e. In this work, we seek c-minimally-invatte

---

is uniform, ((xx) for given x is directly proportional to the number of discrete regions in Q to which x applies a non-zero control. We denote by Q- the set of such regions. Then, a feedback controller л that minimizes [Q~1 is pemiiiimlll-iinasivve.. and as the discretization becomes finer, monotonically approaches zero. Therefore, given barrier function B(x),, our first goal is to identify the minimal number of regions in Q that require non-zero controller to guarantee safety. Recall that, given B(x), we require the safety probability to be 1--1--10 (77 + B.) 2 dg. While 1j is related to the value of B(x) in the initial set, 3 is compensation needed to turn a sub-martingale inequality to a super-martingale inequality (Condition (d or (4d). We can compute this compensation for each region q E Q by evaluating Condition (8d) or 4d Let 3g denote the computed compensation term
for region q. Then, region requires a non-zero controller if 3g > (1 - 6g 7)
We now turn our attention to designing a controller that reduces S. In our approach, we tap directly into the convex nature of the SOS polynomial ((x) (SOS-convex). Lemma eshwa that a controller that drives System to point closest to the minimum point of (xx), also robustly minimizes 8qg
Lemma 2. Given B(x), let x² arg ming Bxx), x' f0))) gu + v as in System 33, and Bg 2 E[B(r') x]] B(x) for all x in region q C Xg. Then, the controller that minimizes 1 xx" II where J' = -xx()) + gu, also robustly minimizes By. i.e., minimizes an upper bound of Byg
Proof. Given that B is polynomial and x' is affine both u and v, we can write E B(x)) x]] B(E[2' =1)) + S. where a, called Jensen's gap (38). is non-negative polynomial of x, u, and moments Elud), where 2 S d S m is an even integer. This polynomial can always be upper bounded by a constant & 2 0 for bounded x and u. Then, with H' = E[x',, the min Bg is upper bounded by
min Bg S min max (B(#' x)) Bxx) + +) - min max B x)) min Bxx) +.. zēq
=Eq
zEq
The second inequality holds because B is non-negative function resulting from a SOS optimization,
and is thus SOS-convex (39] Since (ā²) monotonically decreases as 5' xx, maxxc9 B(i' xx)
is minimized by arg min, (x) + gu x= Vr E q.
We note that, in the proof of Lemma 2 the moments (0)) appear in every monomial of polynomial & (Jensen's gap). Hence, for with variance less than 1, Jensen's 's gap is very small and vanishes as the variance becomes smaller, making the controller in the lemma optimal. Furthermore, even though Lemma 2 Juses L, norm for || xx" II the statement also holds for L2 and Lxx norms. We
specifically use L, norm to be able to compute the controller via an LP as stated in Theorem 2
Theorem 2 (Controller Synthesis), Consider convex barrier function B(x) and its minimum argument x² as specified in Lemmal and linear bounds f, (z) and F for
for f (x) in region q S F" as in (
A controller that robustly minimizes B, for System (3) is the solution to the following LP optimization problem, where 0- = (01, (0,,02.... .a....,,,, E 20 and the vector inequality relations are element-wise:
min Σ9. 02 subject to: 0 2.
i=1
y x² S 0 x² y S 0
(10a)
y fz) (2)++0 gu
(10d)
(10b)
[z) + +gu
(10c)
= = z' - z"
(10c)
2'-² 2 E u UEU (10f)
Proof. By Lemma 2 it holds that robustly minimizes Bg. it suffices to minimize || I|1- This norm is the sum of n absolute values, each of which can be set to 0 with linear Constraints (10a) and (TOb). Hence, the minimization of || - 2=1| is equivalent
minimization of Σ. 0,
subject to (I0a) and (10b). The bounds on the dynamics of System 33 can be expressed as linear Conditions (10hp and (10e), each of which has to hold for all = E g, i.e., is free variable. To turn the optimization into an LP, z is expressed as the difference of two non-negative decision variables z' and z in Constraint (10c).
Remark 6. Note that the controller obtained via the LP is a vector of scalars for each region q. This leads to feedback controller over the regions q E Q. It is possible to express u SOS polynomials, which would be a feedback controller over x. That could potentially provide a tighter bound for Bg at the cost of extra computation since SOS optimization is more expensive than LP.
7

---

5.1 Control Synthesis Algorithm
Our framework for computing a barrier certificate as well as minimally-invasiin controllers for NNDMs is outlined in Algorithm[] T First, the safe set X is uniformly partitioned into finite set of regions [Q], and bounds of f are computed as piece-wise linear functions per Section [.1 Then, for given polynomial degree m 2, barrier certificate along with its corresponding safety probability bound are computed in accordance with Theorem [ If this probability is greater than or equal to 6g. the NNDM certified, and the algorithm terminates. Otherwise, it iteratively searches for e-minially-invasivee controllers. In each iteration, upper bound 7j set on vi (initially with its largest possible value 1 6g and then reduced by An > 0). and new barrier function is computed with this bound, where the objective function is minimization of 3 to ensure e-minimally invvasvv controllers. Then, for each E Q. B, checked against the threshold. If exceeding, controller computed for q in accordance with Theorem 2 This process repeats until a satisfactory Pa is obtained or < O.
We highlight two important properties of this algorithm: it clearly terminates in finite time, and if P. 2 8, the synthesized controller is correct-by correct-yy-constructinn constructoo..
Algorithm I: NNDM Controller Synthesis
Input NN fw, initial set Xg. safe set X,. noise covariance R. polynomial degree m. threshold &,, and step size Ar)
Output: feedback controller ,, and safety probability bound Pa
Q, L. - PARTTTONANTCCOOPPTTBBBOOOODSS,, ("), & ++0
77 B(x) + COMPUTEBARRIENCERTIIICCC
R)
Il Theorem
while < 6, and > 0 do
77 4- [6, k&v)). k ++1
set upper bound on yj I/ T/Thoremm
3, Bxx) COMPUTTRARRRIRCTTTRCCTTTTT J. R. R,m,))
for q E Q do
7
π 6 (g. 0)
8
if 8, > (1 - 6, n then
π < (g, (gg) + COMPUTECONTROLL(rg min B(x), q, J.. U) // Theorem
9
B + OPPATEBETA(B(E)...)
evaluate Condition (dd]
Pg 1-11
(n + N max 97))
12 return n. Pa
6 Case Studies
We demonstrate the efficacy of our framework on several case studies. We first show that our verification method able produce non-trin non-trivial safety guarantees for NNDMs trained using imitation learning techniques (40) from data gathered by rolling out an RL agent trained with state-of-the-an RL techniques [1 We then show that our control approach significantly increases the safety probability,
Models We trained the Pendulum (2D), Cartpole (4D), and Acrobot (6D) agents from the OpenAI gym environment, as well 4D and 5D Husky robot models. For the OpenAl models, we collected input-output states of the system under an expert controller, either as a look-up table or an NN controller. We picked the best controller available for the agents from the OpenAl Leaderboard (4T). The Husky models were trained to move from one point to another while staying within lane. We initially trained NNDM along with an NN controller on the trajectory data generated from PyBullet (physics simulator (42)) as outlined in [9]. We then used these NNs to generate input-output data and trained closed-loop NNDMs specified above. In total, trained 10 fully-connected multi-layer perceptron NNDM architectures with up to 5 hidden layers and 512 neurons per layer, each with ReLU activation function. The dimensionality and architecture information is provided in Table []]
The state space of the Pendulum consists of the pole angle 0 and angular velocity ò, with the safe set defined as |- 15, // 15) x 1], and the initial set as 6g E [-T/36, π //66.. For the Cartpole, the state space consists of the cart position z, velocity á pole angle 6, and angular velocity Å. The safe sets for cart position are defined as E [-1,1] and E [-> (LTT/12 15, π n/15], with the initial set On E [-x/36, T/ /36]. For the 4D Husky, the states are position and orientation 0, and linear velocity v. The task of the controller to keep the robot within a lane, and hence the safe set y E [-1, and the initial set is defined as any position (I, y) that is within a radius of 0. from the

---

Table 1: Benchmark results for barrier certificate and control synthesis on various NNDMs. Threshold control synthesis. Architecture h x [r] denotes a
5. 0.95 was used for the minimally-inven NNDM with hidden layers, each with r neurons. n the dimensionality of the system.
Verificttion
Control
Model
bxx [e]
[22
Interval Bounds
Linear Bounds
Interval Bounds
Linear Bounds
Time (min)
Time (min)
(mii6)
Time (min)
120
0.531
0.468
0.06
0,005
0.995
0.09
10
0,999
0.04
[64]
240
0.440
0.569
0.005
10-3
0.998
480
0.145
0.851
0.36
0.005
0.995
0.43
10-3
0.999
0.32
120
0.355
0.424
0.05
0.196
0.783
0.06
10
0.999
0004
16
0.00
0.05
2 [64]
240
0,480
0.556
0.14
0.157
0.841
0.15
10
0.997
0,11
10
0.998
0.13
Pendulum
450
0.998
0.32
10-4
120
0.674
0.320
0.05
0.388
0.597
0.06
10
0.394
0.06
10
0.955
0.05
x [644]
240
0.534
0.161
0.14
0.293
0.703
0.17
10
0.995
0.11
10-6
0.996
0.12
480
0.356
0.636
0.41
0.211
0.788
0.51
10-3
0.999
0.39
10-4
0.993
0.47
0.968
0.827
0.907
10-6
0.951
5 [64]
950
0.722
0.229
1.55
0.692
0.259
1.67
10
0.909
1.42
10-9
0.951
1.61
1920
0.505
0.448
5.82
0:458
0.492
6.28
10
0:911
5.33
10-6
0.951
5.39
966
1.001
D.625
10-3
0:877
12.43
10-4
0.998
x [126]
1920
1.000
57,83
0.417
65.15
10
0.900
31.31
0,993
35,09
Curpole
3840
0.796
0.193
216.92
0.385
0.5 0.599
224.70
10-2
0,979
158.51
10-4
0.985
164.41
9921
1.00
0000
17.50
0.779
0.172
18:19
10
0.815
11:38
T0
01951
14:02
(1226
1920
0.773
10-4
31.98
3840
0.878
0,101
228.78
0.666
0.331
225.42
10
0.980
148.49
10-1
0.997
160.46
900
0.672
0.200
14:25
0.691
0.299
16,50
10
0.872
11:22
10
0.951
11.71
1 [256]
1800
0.667
$2.70
0.673
0.278
58.76
10
0.878
33.27
10-
0.951
35.10
2250
69.12
0.368
81.32
10
42.01
0.951
Husky
4800
0.622
0.331
500.10
0.347
0.539
345, 84
10
0.951
20%. 71
10
0.933
302.5
1800
1:00
0.00
64.61
0.544
0.010
74.02
10
0.749
30:44
10
0,500
34.99
1256)
22.50
1.001
0:502
10-6
0.951
$2,02
4800
0.845
0.415
400.88
10
0.908
205.75
0.951
274.94
432
1.00
0.00
12:43
1.00
0.00
1T.82
10
0.750
7.21
10
0.349
9:03
Husky
[
1080
1,00
0.00
51.59
1.00
0.00
57.65
10
0.829
49.38
10
0,950
$1.76
1728
168.39
1.00
171.35
153.59
10-4
0,951
161.04
Acrobot
1 [512]
288
144
1.00
1.00
0.00
0.00
25,01
11.10
0.863
1.00
0.088
0.00
25.62
12.02
10
10
0.951
0.951
11.55
4.44
10-
10
0.951
0.951
11.78
4,93
origin. For the 5D Husky, the additional state over the 4D model is the angular velocity w;; the task, the safe set, and the initial set remain the same. Finally, for the Acrobot, the state space consists of the cosines and sines of 01 and 0z, and angular velocities 0 and 6z. Here 82 and 0g are the pole angle of the first link and the angle of the second link relative to the first link, respectively. The task is for the tip of the second link to reach a height of at least beyond y 1.2. Thus, the safe set is defined sin(0:) E [-0.6, 0.6) and sin(02) [-0.6, 0.6]. and the initial set is any point within a radius of 0.1 around the origin in the first 4 dimensions.
1, with a safety constraint to never reach
We implemented our algorithms in Python and Julia (code available in 443 ). For collecting data and training, we used the TensorFlow framework
Implementation and Experimental Setup:
44
To compute the linear approximations of the NNDMs, we utilized a-CROWN 36) For the
optimization, we used Julia's 's SumOfSquares, jll package 45] 46). The optimizations are all performed
single-threaded on a computer with 3.9 GHz 8-Core CPU and 64 GB of memory.
To the best of our knowledge, there is no other work on safety verification of NNDMs, against which we can compare. Hence as a bascline, we compare our approach based on linear under and over approximation of the NNDM against interval bounding approaches cf. Remark 5) The interval bounding approach results in a relaxed optimization problem at the cost of more conservative safety probabilities. The results are shown in Table T The computation times indicate the time to synthesize the barrier and the controller using Theorems T [2 respectively. The barrier degree is 4 for all the case studies. Below, we provide brief discussion on the results. For more in-depth discussions and details on the discretization and hyperparameters, see Appendix A
Benchmarks:
As expected, the safety probability always increases with [Q] (finer partitions), since the linear and interval bounds for f become more accurate. This behavior is encountered in all the systems and architectures, regardless of the number of hidden layers or neurons per layer. However, it is also observed that this trend of finer discretizations and increased safety probability consistently comes at the cost of an increased computation time. This due to the fact that the number of partitions directly dictate the number of constraints in the optimization problems. Note that the probability of safety using interval bounds strictly worse than linear approximations for all the experiments. Using either linear or interval bounds, we are able to compute non-trivial probability of safety for all the case-studies and observe the discretization vs accuracy trend. Take for instance, the 1 llaayer Cartpole model, where an increase in |Q] from 960 to 3840 causes increase in P. from
Verification:
9

---

02
(a) [ = 120, certificate
(h) [Q] = 240, certificate (c) Q 480, certificate
-22
-01
4.1
02
(d) [Q| 120, control
(c) [Q]
240, contral
(f) [Q] = 480, control
Figure 1: Comparison of Bg values for the Pendulum NNDM with 2 layers and 64 neurons per layer
before and after applying the controller for various [Q) Shade of gray correspond to the values of 8q-
0.375 to 0.599, at the expense of an increased computation time of more than 12 times. This behavior also true for the 4D Husky model, where increasing [Q] from 1800 to 4800 for the 2-layer model, increases Ps from 0.010 0.384 at the price of more than 5-fold increase in the computation time.
When the certification probability below 6, 0.95, the control strategy is utilized to increase the probability of safety. Using interval bounds, controllers had to be synthesized for all case-studies, which illustrates the looseness of the bounds. In fact, in several case studies, the controller was not able to meet the desired threshold. For the linear bounds, observe that for all except two NNDMs, whose Ps < 6g. the controller synthesis algorithm was able to produce P. > &,, showing the effectiveness of our control method. The first exception is for the 4D Husky model with 2-hidden layers and Q = 1800, where the controller increases P3 from 0.010 to 0,800 (73-fold increase) yet cannot meet the 0.95 threshold. Similarly, for the I-layer 5D Husky model with [ = 432, the controller increases Pa from 0.00 to 0,949, but the 0.95 threshold cannot be reached. Nonetheless, for all the linear bound cases, the controller reduces 3 to 10
Control Synthesis:
Figure T illustrates the minimally-invasive aspect of the controllers. shows the 9g values for the Pendulum NNDM with 2 layers before and after the application of the controllers with three different sizes of (Q). For [Q] = 120, all the regions require controllers, but for IQ] = 240 and 480, respectively, only 69.2% and 23.75% of the regions require controllers; hence, the minimally-invasii controller focuses specifically on those regions and does not affect those with already-small 8yy
7 Conclusion
In this work, we introduced a methodology providing safety guarantees for NNDMs using stochastic barrier functions. We showed that the problem of finding stochastic barrier function for a NNDM can be relaxed to an SOS optimization problem. Furthermore, we derived novel framework for synthesis of an affine controller with the goal of maximizing the safety probability in a minimally-invan manner. Experiments showcase that, along with a minimally-invasio controller, guarantee safety for various standard reinforcement learning problems.
bottleneck to our approach is the discretization step, which is required obtain piece-wise linear under- and over-approximation of the neural network, and can be expensive for higher dimensional spaces. Future directions should focus on mitigating this curse of dimensionality.
Acknowledgments and Disclosure of Funding
This work was supported in part by the NSF grant 2039062 and NASA COLDTech Program under grant #80NSSC2IK1031.
10

---

References
[1] Christel Baier and Joost-Piette Katoen. Principles of model checking. MIT Press, 2008.
[2] Morteza Lahijanian, Sean B Andersson, and Calin Belta. Temporal logic motion planning and control with probabilistic satisfaction guarantees. IEEE Transactions on Robotics, 28(2):396- 409, 2011.
[3] Luca Laurenti, Morteza Lahijanian, Alessandro Abate, Luca Cardelli, and Marta Kwiatkowska. Formal and efficient synthesis for continuous-time linear stochastic hybrid processes. IEEE Transactions on Automatic Control, 2020.
[4] Calin Belta and Sadra Sadraddini. Formal methods for control synthesis: An optimization perspective. Annual Review of Control, Robotics, and Autonomous Systems, 2:115-140, 2019.
[5] Maziar Raissi, Paris Perdikaris, and George E. Karniadakis. inyssce-informeed neural networks:
A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Compulational physics, 378:686-707, 2019.
[6] John Cristian Borges Gamboa. Deep learning for time-series analysis. arXiv preprint arXiv:170.001887, 2017.
[7] Stephen Prajna, Ali Jadbabaie, and George J Pappas. A framework for worst-case and stochas- tic safety verification using barrier certificates. IEEE Transactions on Automatic Control, 52(8):1415-1425 2007.
[8] Cesar Santoyo, Maxence Dutreix, and Samuel Coogan. A barrier function approach to finite-time stochastic system verification and control. Automatica, 125:109439, 2021.
[9] Anusha Nagabandi, Gregory Kahn, Ronald S Fearing, and Sergey Levine. Neural network dynamies for model-based deep reinforcement learning with model-free fine-tuning. 2018 IEFE International Conference on Robotics and Automation (ICRA), pages 4063-4069. IEEE, 2017.
[10] Ricky TQ Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. Neural ordinary differential equations. Advances in neural information processing systems, 31, 2018.
[11] Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in handful trials using probabilistic dynamics models. In Advances in Neural Information Processing Systems, pages 4754-4765, 2018.
[12] Keene Chin, Tess Hellebrekers, and Carmel Majidi. Machine learning for soft robotic sensing and control. Advanced Intelligent Systems, 1900111,,,,, 2020.
[13] Aaron D. Ames, Samuel Coogan, Magnus Egerstedt, Gennaro Notomista, Koushil Sreenath, and Paulo Tabuada. Control barrier functions: Theory and applications. 2019 18th European Control Conference (ECC), pages 3420-3431,
[14] Stephen Prajna and Ali Jadbabaie, Safety verification of hybrid systems using barrier certificates. In International Workshop Hybrid Systems: Computation and Control, pages 477-492. Springer, 2004.
[15] Stephen Prajna, Ali Jadbabaie, and George Pappas. A framework for worst-case and stochas- tie safety verification using barrier certificates. IEEE Transactions on Automatic Control, 12(5):1415-1428, 2007.
[16] Aaron D Ames, Jessy W Grizzle, and Paulo Tabuada. Control barrier function based quadratic programs with application to adaptive cruise control. 53rd IEEE Conference on Decision and Control, pages 6271-6278. IEEF, 2014.
[17] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. CoRR, abs/1412.6572, 2015.

---

[18] Guy Katz, Clark Barrett, David L Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pages 97-117. Springer, 2017.
[19] Huan Zhang. Tsui-Wei Weng, Pin-Yu Chen, Cho-Jui Hsieh, and Luca Daniel. Efficient neu- ral network robustness certification with general activation functions. Advances in neural information processing systems, 31, 2018.
[20] Ruediger Ehlers. Formal verification of piece-wise linear ferd-forward neural networks. In International Symposium on Automated Technology for Verification and Analysis, pages 269- 286. Springer, 2017.
[21] Mathias Lechner, Dorde Zikelić, Krishnendu Chatterjee, and Thomas Henzinger. Infinite time horizon safety of bayesian neural networks. Advances in Neural Information Processing Systems, 34, 2021.
[22] Sophie Gruenbacher, Ramin M. Hasani, Mathias Lechner, Jacek Cyranka, Scott A. Smolka, and Radu Grosu. On the verification of neural odes with stochastic guarantees. In AAAI, 2021.
[23] Charles Dawson, Sicun Gao, and Chuchu Fan. Safe control with learned certificates: A survey of neural Iyapunov, barrier, and contraction methods, arXiv preprint 220. 11762, 2022.
[24] Matthew Wicker, Luca Laurenti, Andrea Patane, Nicola Paoletti, Alessandro Abate, and Marta Kwiatkowska. Certification of iterative predictions in bayesian neural networks. Uncertanity in Artificial Intelligence (UAI), 2021.
[25] Steven Adams, Morteza Lahijanian, and Luca Laurenti. Formal control synthesis for stochastic neural network dynamic models. IEEE Control Systems Letters, 2022.
[26] Tianhao Wei and Changliu Liu. Safe control with neural network dynamic models. In Learning for Dynamics and Control Conference, pages 739-750. PMLR, 2022.
[27] Dimitir P Bertsekas and Steven Shreve. Stochastic optimal control: the discrete-time case. Athena Scientific, 2004.
[28] Murray Marshall. Positive polynomials and sums of squares. American Mathematical Soc., 2008.
[29] Harold J Kushner. Stochastic stability and control. Technical report, Brown Univ Providence RI, 1967.
[30] Hilbert. Ueber die darstellung definiter formen als summen von formenquadraaten. Mathematis- che Annalen, 32:342-350, 1888.
[31] Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM review, 38(1):49-95. 1996.
[32] Gilbert Stengle. A nullstellensatz and positivstellensatz in semialgebraic geometry. Mathema- tische Annalen, 207:87-98, 1974.
[33] Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Efficient formal safety analysis of neural networks. In Advances in Neural Information Processing Systems, pages 6367-6377, 2018.
[34] Shiqi Wang, Kexin Pei, Justin Whitehouse, Junfeng Yang, and Suman Jana. Formal security analysis of neural networks using symbolic intervals. 27th USENIX Security Symposium (USENIX Security 18), pages 1599-1614, 2018.
[35] 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 robustness verification. Advances in Neural Information Processing Systems, 34:29909-29922 2021.
12

---

[36] Kaidi Xu, Huan Zhang. Shiqi Wang, Yihan Wang, Suman Jana, Xue Lin, and Cho-Jui Hsieh. Fast and complete: Enabling complete neural network verification with rapid and massively parallel incomplete verifiers. International Conference on Learning Representations, 2020.
[37] Jacob Steinhardt and Russ Tedrake. Finite-time regional verification of stochastic non-linear systems. The International Journal of Robotics Research, 31(7):901-92) -2000099922--- 2012.
[38] JG Liao and Arthur Berg. Sharpening jensen''s 's inequality. The American Statistician, 2018.
[39] Amir Ali Ahmadi and Raphaël M. Jungers. Sos-convex Iyарunov functions with applications to nonlinear switched systems. In Proceedings of the IEEE Conference on Decision and Control, 2013.
[40] Steven L Brunton and J Nathan Kutz. Data-driven science and engineering: Machine learning, dynamical systems, and control. Cambridge University Press, 2022.
[41] Gym leaderboard.
[42] Erwin Coumans and Yunfei Bai. Pybullet, a python module for physics simulation for games, robotics and machine learning. htttp://pybullet.orrg 2026-2021.
[43]
Github code: NeuralNecCootro/Barrier. httpg::/ggtaabb.cc/arraaaastttt NeuralleeCControlBatiiee
[44]
Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg Corrado, Andy Davis, Jeffrrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jía, Rafal Jazefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng. TensorFlow: Large- scale machine learning on heterogeneous systems, 2015. Software available from tensorflow.org.
[45] Tillmann Weisser, Benoît Legat, Chris Coey, Lea Kapelevich, and Juan Pablo Vielma. Polyno- mial and moment optimization in julia and jump. In JuliaCon, 2019.
[46] Benoît Legat, Chris Coey, Robin Deits, Joey Huchette, and Amelia Perry. Sum-of-squares optimization in Julia. In The First Annual JuMP-dev Workshop, 2017.
[47] Husky urdf httpp:///hhh..cooooooooooo/a/aa/ data/husky/husky urdf
[48] Giuseppe Paolo, Jonas Gonzalez-Billandon, Albert Thomas, and Balázs Kégl. Guided safe shooting: model based reinforcement learning with safety constraints. arXiv preprint 294402300 2022.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See the paragraph above Related Work in Section
(b) Did you describe the limitations of your work? [Yes] See Section 7
(c) Did you discuss any potential negative societal impacts of your work? [No] Our work is motivated by providing safety guarantees for NNDMs in safety-critical applications, especially when deploying these NNDMs in real-world scenarios. This line of work meant to contribute society in positive way. Potential negative societal impacts have hence not been a part of the discussion is this paper.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All main theorems, lemmas and assumptions have been outlined in the paper. Theorems [ as well as Lemmas
form the core of this paper. The discussion regarding all of these has been detailed to describe our approach as clear as possible to the reader.
(b) Did you include complete proofs of all theoretical results? [Yes] The proofs for Lemmas as well as Theorems are included in the main body of the paper.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material included the supplementary material as a docker file, including detailed instructions on how to reproduce the experimental results. This code can also be found on Github, see 43 Note, a Mosek license is required to run the optimizations, which can be obtained from httpp::/wwat mosek. com
URL)? [Yes] The code is
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section[Jand Appendix
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 6
4. If you using existing assets code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] State-of-the-art linear approximates of NNs have been used existing assets. The main takeaways of these assets used in this research work have been captured in Section [4.] (Auto-
Toolbox). Further, we use the model-based model-free RL approach mentioned in Section 6 to train NNDM model in PyBullet (Physics Simulator). Naturally, the necessary citations have been provided to credit the creators. At last, the Mosek toolbox has been utilized for optimization. While not directly cited in the text, this toolbox has been given credit in our online available code.
(b) Did you mention the license of the assets? [Yes] See the supplementary material.
(c) Did you include any assets either in the supplemental material new framework has been provided related to the work of the paper. This code is included supplementary material, and Github (see (3)).
URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] This discussion is not part of this paper. The
14

---

included material does not contain personally identifiable information or offensive content, the best of our knowledge.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "hfqQfCPk863", "reviewer": "Reviewer_crLS", "summary": "This paper considers the safety guarantees of the neural network dynamic models (NNDMs). Specifically, the authors use stochastic barrier certificate to verify if a given NNDM satisfy the safety in a probabilistic way, which provides a lower bound on the system's safety probability. If the safety probability is below the desired threshold, then the authors propose to directly modify the output of the NNDM that robustly minimize the unsafety probability in a minimally-invasive manner. The authors applied the proposed method on three different control problems.", "questions": "1. In line 15, the authors claim they introduce a method of generating controls for the system. What is the control of the system? The authors just directly modify the system state in the form of equation (3). This is not the real control of the system.\n\n2. It is hard to justify the contribution of this paper since the authors just modify the output of a NNDM (equation (3)) to satisfy the safety probability.\n\n3. In line 112, the authors claim that ``Computation of this probability is particularly challenging because system (1) is stochastic and NN is generally non-convex'' ? I do not think this is a reasonable motivation.\n\n4. In line 118, I do not think u_k is the ``real'' control action of the system. It is just a variable to change the output of a NNDM.\n\n5. In equation (4b), what is $\\eta$? Could it be negative?\n\n6. The right hand side of (5) is very likely to be negative. The authors should justify this.\n\n7. In Proposation 1, what is $\\lambda_0(x)$? Moreover, in Corollary 1, the conclusion is equivalent to state that $\\lambda_0(x)$ is a SOS polynomial following the last equation of Proposation 1. This is really confusing.\n\n8. In line 181, can we always partition $X_s$ to a finite set of regions, in which each region is a basic semi-algebraic set?\n\n9. In theorem 1, what are the domains of $\\beta$ and $\\eta$? Moreover, in theorem 2, is this optimization always feasible? For example, what if $\\theta$ is negative? The authors should clearly define the domain of a variable before using it.\n\n10. In experiments, there are no comparisons with other approaches that consider safety guarantees. Therefore, it is hard to justify the contribution of this work. Moreover, the authors did not explain why there is an exception in Husky, in which case the safety probability is 0.800 (cannot meet the 0.95 threshold).\n", "limitations": "The authors just modify the output of a NNDM to satisfy a given safety probability. This approach does not generate a ``real'' control for the system. Therefore, it does not apply to dynamical systems.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis paper combines stochastic barrier certificate and convex relaxation of a neural network in a good way.\n\nWeaknesses:\n\nThe contibutions of this paper are not clear. There are some related works, and the authors have not compared their method with other approaches, especially in the experiments.  There is one important notation that is misleading. When the safety probability is below the desired threshold, the authors just modify the output of the NNDM, instead of generating controls for the system as claimed by the authors. The ``control'' of a system should not be considered in the form of equation (3). The equation (3) just directly modify the output of the NNDM. For example, if the state x denotes the system's position that is controlled by the system's acceleration, the authors just modify the position to satisfy the safety probability instead of changing the acceleration. In order to model the real control of a system, the authors should consider the control in the $f^w$. In other words, the control is an input to the NNDM.  ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "bgmsKfEUNnh", "reviewer": "Reviewer_JTrX", "summary": "The paper introduces a safety-guaranteeing controller distillation method for neural network dynamic models (NNDM). The approach is based on the stochastic barrier functions. The introduced algorithm works in two phases. In the first phase, a convex approximation results are applied to obtain piecewise linear bounds for the NNDM on the domain discretized into square regions. In the second step, a synthesis of a minimally invasive (according to the provided definition) controller is carried out using the linear programming approach.", "questions": "* There is no baseline presented for the experimental section, which makes the presented results incomparable, and  hard to evaluate the impact of the algorithm being introduced;\n* It would be very nice if authors use at least one example, in which an analytical model is not available or is more complicated than a nonlinear ODE/hybrid system, appearing in the classical applications of barrier function certificates to closed-form models, maybe one of the  MuJoCo standard environments should do a good job here;\n* the experimental setting is not clearly introduced in the main part, e.g. the safety certification sets used for the barrier function computation are not provided;\n* l. 309, the Husky models used for the experimental evaluation are not standard, haven't seen them being used in RL literature, please explain and provide an appropriate reference;\n* regarding the implementation, what is the rationale in having part of the code (i.e. NeuralNetControlBarrier) written in Julia, as opposed to having the code fully written in Python ?\n\n## Minor remarks\n* l. 261, elaborate and provide a reference for 'called Jensen’s gap, is a non-negative polynomial of x, u, and moments E[vd]';\n* l. 217 the difference between $L_q(x)$ and $L_{q,x}(x) $ is not explained;", "limitations": "The limitations related especially to the scalability issue have been appropriately addressed in the paper.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper introduces a novel approach for a problem of large importance in safe machine learning, i.e. synthesis of safe controllers for NNDM's. For instance, NNDM's are widely encountered in model-based reinforcement learning approaches, and a synthesis of a safe controller given NNDM has a large potential for practical applications. \n\nThe paper aims at bringing the tool of barrier functions previously widely studied in control theory approaches for closed-form models (restricting practical applications in ML) into the world of NN-based models. I have not verified the claim that this is in fact the first paper demonstrating such an approach, but if yes then the paper would constitute a major result. \n\nThe approach is reasonable and is clearly presented. The formal presentation is supported by theoretical results, i.e. lemmas and theorems. The layout makes it easy to follow and understand the algorithm construction. The overall approach seems to be sound. The formal presentation is supported by experimental case studies (Sec. 6). \n\nI am happy with the formal presentation but have some objections to the experimental evaluation. My main critique, see also questions below, is lack of proper presentation of the setup in the main paper. I would rethink if all of the plots in Fig. 1 are crucial for presentation, and perhaps replace some of them with more illuminating text. The examples, confirm that the approach works in a desirable way (large safety certificate probability/ small $\\varepsilon$ of the minimally invasive controller) , however, those results are not compared to a single baseline, which makes them harder to appreciate. The third is the scalability issue, it is actually noted by the authors that the bottleneck is the discretization step. In fact, it is hard to think how such an approach would scale up to larger systems, given that the phase space needs to be discretized into square-like subregions, resulting in an exponential explosion of the number of subregions. Without overcoming this issue the approach may not have a significant impact in reliable ML community, and I would like the authors to at least provide a convincing argument for that there exists a path towards relaxing the restrictive discretization step.\n\nWeighting positives and negatives, I think the paper is a valuable contribution to the reliable machine learning field of research, and I am leaning toward accepting it. \n I am voting for weak accept at present, but I am open to increasing my score in case the authors satisfactorily address my remarks for the experimental section of the work, i.e., will provide some baseline method evaluation, will improve the presentation of the experimental results in the main part and will discuss how the restrictive discretization step could be circumvented..", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WVdIfnyWnfg", "reviewer": "Reviewer_D3ig", "summary": "This work provides probabilistic safety guarantees for dynamical systems. Noticing the safety issues in neural network based dynamical systems, this paper utilizes stochastic barrier function generated by SOS optimization and propose a safety probabilistic certificate for discrete step system. In the control synthesis problem, the paper also provides a lower bound of safety probability by local convex relaxation.", "questions": "1. I’m a bit concerned on the comparison metrics in the experiment, see my detailed question 1,2.\n\n2. The computational time could be an issue for high dimensional system and finer partitions, but this is not a deal-breaker since the target is certification.", "limitations": "1. Algorithm 1 has safe set as input, how to determine unsafe/safe region for each application? If that requires additional prior knowledge, then it might be unfair to compare the safety probability to safe region between synthesis controller and baseline model from imitation learning, since the former one already “knows” where the boundary is.\n\n2. As for the verification comparison itself, I’m concerned why use the model from imitation learning as baseline instead of the expert controller. If the imitation learned model only saw the trajectory generated from an expert controller during training, then it’s reasonable it cannot handle corner cases. In line 311, it seems like your synthesis controller has been exposed to new data, then this is again not fair comparison. Feel free to correct me if I misunderstood your approach.  \n\n3. In the verification results, I’m curious why larger architecture leads to worse Ps? \n\n\n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. Introducing the stochastic function into dynamical system learning is novel.\n\n2. The narrative structure is clear.\n\n3. It’s interesting to see many tricks in this paper to reformulate the problems.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept