DeGAS: Gradient-Based Optimization of Probabilistic Programs without Sampling Francesca Randone, Romina Doz, Mirco Tribastone, Luca Bortolussi Abstract We present DeGAS, a differentiable Gaussian approximate semantics for loopless probabilistic programs that enables sample-free, gradient-based optimization in models with both continuous and discrete components. DeGAS evaluates programs under a Gaussian-mixture semantics and replaces measure-zero predicates and discrete branches with a vanishing smoothing, yielding closed-form expressions for posterior and path probabilities. We prove differentiability of these quantities with respect to program parameters, enabling end-to-end optimization via standard automatic differentiation, without Monte Carlo estimators. On thirteen benchmark programs, DeGAS achieves accuracy and runtime competitive with variational inference and MCMC. Importantly, it reliably tackles optimization problems where sampling-based baselines fail to converge due to conditioning involving continuous variables. 1 Introduction Probabilistic programming languages (PPLs) extend general-purpose languages with probabilistic primitives. In recent years they have received significant attention, motivated by their ability to model and analyze inherently stochastic systems such as randomized algorithms [ 18 ] , probabilistic cyber-physical systems [ 22 ] , and machine-learning models [ 8 ] . Probabilistic programs (PPs) typically expose parameters that must be tuned to meet goals: maximize likelihood [ 10 , 5 ] , satisfy safety constraints [ 30 ] , calibrate uncertainty [ 13 ] , or optimize bespoke utilities [ 28 ] . Current practice relies on sampling—either Markov chain Monte Carlo (MCMC) [ 2 ] or variational inference (VI) [ 7 ] . While often effective, these methods can exhibit high-variance gradient estimates and brittle behavior on discontinuous objectives induced by branching and hard conditioning, frequently necessitating problem-specific reparameterization tricks [ 34 , 27 , 1 , 14 , 25 ] . This paper asks the following: Can we obtain gradients for PP objectives without sampling? We answer affirmatively by introducing DeGAS, a differentiable Gaussian-mixture approximate semantics that renders end-to-end evaluation differentiable, enabling optimization with off-the-shelf automatic differentiation (AD) and without Monte Carlo estimators. The key idea is a principled, vanishing smoothing of discrete and measure-zero constructs (e.g., point masses and Boolean predicates), which yields differentiable densities and path probabilities throughout a program’s execution. This delivers deterministic objective values and gradients with respect to the program parameters. DeGAS builds on the SOGA (second-order Gaussian approximation) semantics for a class of loop-free probabilistic programs [ 29 ] . With SOGA, each program state is represented as a Gaussian mixture (GM) and program constructs update mixtures analytically (affine transforms, products, and conditioning via truncation) to approximate the posterior over program variables. DeGAS smooths the discontinuities that arise under branching and conditioning by injecting small Gaussian noise where needed and relaxing predicates accordingly, while preserving closure under mixture operations. We prove differentiability of posterior distributions and path probabilities with respect to parameters, and we show that as the smoothing parameter tends to zero, the differentiable semantics converges to the unsmoothed SOGA semantics under mild regularity conditions. We implement DeGAS in PyTorch leveraging its AD capabilities to provide a sample-free gradient-based optimizer. Numerical experiments show that, on thirteen benchmark programs, DeGAS achieves accuracy and runtime competitive with VI and MCMC. More important, we show DeGAS is able to solve instances of optimization problems for which sampling baselines fail to converge due to the presence of constructs such as conditional statements depending on continuous variables. Structure of the paper. Section 2 reviews related work. Section 3 presents the syntax and defines the differentiable semantics. Section 4 states and proves our main properties (differentiability and convergence). Section 5 reports the experimental results. Section 6 concludes. 2 Related Work To the best of our knowledge, this is the first work that computes gradients of probabilistic programs without sampling. For deterministic programs, the idea of smoothing to achieve sample-free optimization via gradient-free methods has been explored in [ 11 , 12 ] , and successively adapted for automatic differentiation in [ 20 ] . However, as will be shown in Section 4 , the smoothing of deterministic programs does not trivially carry over to PPs. An attempt was made to extend the smoothing to PPs in Leios [ 21 ] . Leios takes as input a discrete or hybrid discrete-continuous PP and approximates it with a fully continuous one using smoothing. The authors notice that the relaxation parameters must be tuned to avoid collapsing any probability event to zero. For example, a variable initially distributed as a Bernoulli after smoothing becomes distributed as a mixture of two components, with means in 0 and 1 and small standard deviations. This implies that the probability of the event x==0 passes from 0.5 to 0 . To avoid this, Leios solves an optimization problem to replace all Booleans predicate depending on smoothed variables. Conceptually, we are close in spirit in that we tackle discontinuities by controlled smoothing. However, the goal is fundamentally different: similarly to the previously mentioned works, Leios aids sampling-based inference; instead, we enable sample-free optimization. For PPs, most of the work has focused on coupling AD with sampling-based inference, designing gradient estimators for discontinuous programs—either to improve MCMC and VI globally [ 34 , 27 , 1 , 14 , 25 ] or only on the discontinuous parts [ 35 , 32 , 23 ] . These approaches still estimate gradients via sampling and are used to run inference faster or more stably. In contrast, we compute deterministic gradients by evaluating a differentiable program semantics; no Monte Carlo appears in the optimization loop. This lets us optimize likelihood and non-likelihood probabilistic objectives directly (such as reachability), not just expected values under a sampler. Some methods start from an input program and compute a second program, whose expected return value is the derivative of the input program’s expected return value [ 3 , 26 ] ; the new program can then be sampled to obtain gradient estimations. We differ in both goal (optimization rather than derivative-estimation for inference) and mechanism: for our smoothing, we leverage the analytical properties of the SOGA/GM semantics [ 29 ] , that yield closed-form truncated moments and CDFs for every node, which we then backpropagate through analytically. 3 Syntax and Semantics SOGA was introduced in [ 29 ] as a semantics for a loop-free PPL that manipulates input variables distributed as GMs. SOGA makes the language closed under GMs, providing an analytical representation of the posterior that enables efficient computation of moments, cumulative distribution functions (CDFs), and probability density functions (PDFs). This semantics is the second-order approximation of a family of approximate semantics based on Gaussian Mixtures, guaranteed to convergence to the true one, and demonstrated high accuracy across a variety of programs. Here, we add the possibility of specifying parameters to be used for optimization. Notation. For a distribution D , let f_{D} denote its pdf. A normal random variable with mean \mu and covariance matrix \Sigma is denoted by \mathcal{N}(\mu,\Sigma) . A GM is a weighted sum of Gaussians, G_{\pi,\mu,\Sigma}=\sum_{i=1}^{c}\pi_{i}\mathcal{N}(\mu_{i},\Sigma_{i}) where c is the number of components and (\pi_{i})_{\{i=1,\ldots,c\}} is the vector of weights satisfying 0\leq\pi_{i}\leq 1 and \sum_{i=1}^{c}\pi_{i}=1 . A Dirac delta centered on x_{0} is denoted by \delta_{x_{0}} . Let x[x_{i}\to e] denote the vector with e as i -th component, and every other component equal to x_{j} . Let \textrm{Marg}_{y}(D) denote the marginal of distribution D with respect to subvector y . We denote with \mathbf{I}_{n} the identity matrix of dimension n and with \mathbb{I}_{A} the characteristic function of set A . We use \otimes for the product of probability measures: if D_{1},D_{2} are distributions on \mathbb{R} , D_{1}\otimes D_{2} is a distribution on \mathbb{R}^{2} whose marginal on the first coordinate is D_{1} and the marginal on the second coordinate is D_{2} . For a predicate b , P_{D}(b) denotes the probability of b under distribution D . D_{\mid b} denotes distribution D conditioned to b . 3.1 Syntax Variables. We consider programs defined over a vector of real variables x=(x_{1},\dots,x_{n}) and a set \Theta of parameters, \Theta=\{\theta_{i}=d_{i}\}_{i=1,\ldots,p} where \theta_{i} is the name of the parameter and d_{i}\in\mathbb{R} is an initial value. In addition, for each parameter an interval domain is specified. For instance, we can specify a standard deviation (std) as a parameter called \sigma , with initial value 1 , and interval domain (0,+\infty) . Expressions. Expressions over program variables can either be products between two variables or linear expressions on program variables, where the coefficients of the variables or the zero-th order term can either be constants or parameters: \mathbb{E}=\{x_{i}x_{j}\mid i,j=1\dots n\}\cup\{c_{1}x_{1}+\ldots+c_{n}x_{n}+c_{0}\mid c_{i}\in\mathbb{R}\cup\Theta\}\kern 5.0pt. Boolean predicates. Boolean predicates are true or false , or inequalities between a variable and a real number, which can either be a constant or a parameter: \mathbb{B}=\{true,false\}\cup\{x_{i}\bowtie c\mid c\in\mathbb{R}\cup\Theta,\,\bowtie\in\{<,\leq,==,\geq,>\}\} Boolean predicates in the guards of conditional (if) statements are restricted to \mathbb{B}_{\text{if}} with \bowtie\in\{<,\leq,\geq,>\} . The restrictions on expressions and Boolean predicates are inherited by SOGA and are motivated by the need to preserve closure of the Gaussian-mixture semantics under the supported operations. However, our grammar is expressive enough to encode general polynomial assignments and guards. Language. Our syntax uses the primitive {x}\sim{gm(\pi,\mu,\sigma)} for random assignments with GMs, where \pi=(\pi_{1},\ldots,\pi_{c}) , \mu=(\mu_{1},\ldots,\mu_{c}) , \sigma=(\sigma_{1},\ldots,\sigma_{c}) are vectors of weights, means and standard deviations, respectively, and \pi_{i},\mu_{i},\sigma_{i} can either be real constants or real parameters, with the restriction that \pi_{i},\sigma_{i}\geq 0 and \sum_{i}\pi_{i}=1 . The complete grammar of our programming language is: \displaystyle P::=~ \displaystyle\texttt{skip}\mid{x}~\texttt{:=}~{e} (deterministic assignments) \displaystyle{x}\sim{gm(\pi,\mu,\sigma)} (random assignment) \displaystyle\texttt{if}~{b}~\{~{P}~\}~\texttt{else}~\{~{P}~\} (test) \displaystyle\texttt{observe}~{b} (observe) \displaystyle{P};~{P} (sequential composition) The \texttt{observe}~{b} construct represents a hard observe, which conditions the program’s distribution on the event specified by b , effectively truncating the support of the resulting distribution to the states satisfying b . 3.2 Semantics We denote with \llbracket\cdot\rrbracket the operator for the exact semantics of the program,intended in the classic sense of Kozen’s Semantics 2 [ 19 ] ; instead, \llbracket{\cdot}\rrbracket^{S} denotes the Second Order Gaussian Approximation (SOGA) semantics operator as defined in [ 29 ] (both reported in Appedix 0.A for completeness), which closes the language under GMs. The closure is realized by replacing every distribution that would not be a GM in the exact semantics (for instance, when conditioning due to a branch) with a GM. The substitution is performed by a dedicated operator called the moment-matching operator , denoted by \mathcal{T}_{\textrm{gm}} , which approximates a density function with a GM by matching its first two moments. In particular, when \mathcal{T}_{\textrm{gm}} acts on a mixture, it acts on every component; when it acts on a single-component mixture, it maps it to a Gaussian having mean and covariance matrix matching the original distribution, denoted by \mu_{D} , \Sigma_{D} . Formally: \mathcal{T}_{\textrm{gm}}(D)=\begin{cases}\pi_{1}\mathcal{T}_{\textrm{gm}}(D_{1})+\ldots+\pi_{c}\mathcal{T}_{\textrm{gm}}(D_{c})&\text{if }D=\sum_{i=1}^{c}\pi_{i}D_{i}\\ \mathcal{N}(\mu_{D},\Sigma_{D})&\text{else.}\end{cases}\kern 5.0pt. (1) Notably, when acting on Gaussian mixtures, \mathcal{T}_{\textrm{gm}} leaves them unaltered [ 29 ] . Non-differentiability of SOGA semantics. By closing the semantics with respect to GMs, the general pdf of the distribution yielded by a program dependent on parameters \Theta can be shown to take the general form f_{\Theta}(x)=\sum_{i=1}^{C}\frac{\pi_{i}(\Theta)}{(2\pi)^{n/2}|\Sigma_{i}(\Theta)|^{1/2}}\exp\left(-\frac{1}{2}(x-\mu_{i}(\Theta))^{T}\Sigma_{i}^{-1}(\Theta)(x-\mu_{i}(\Theta))\right). Assuming that \pi(\Theta),\mu(\Theta) and \Sigma(\Theta) are differentiable in \Theta , f_{\Theta} can only be nondifferentiable in \Theta if a covariance matrix is singular, i.e., |\Sigma_{i}(\Theta)|=0 . x = gm([1.], [0], [1]); y = c; \pi=1,\quad\mu=\begin{bmatrix}0\\ c\end{bmatrix},\quad\Sigma=\begin{bmatrix}1&0\\ 0&0\end{bmatrix} (a) Assignment with a constant. x = gm([1.], [0], [1]); y = gm([0.5, 0.5], [0, 1], [0, 0]); \pi_{1}=0.5,\;\mu_{1}=\begin{bmatrix}0\\ 0\end{bmatrix},\;\Sigma_{1}=\begin{bmatrix}1&0\\ 0&0\end{bmatrix} \pi_{2}=0.5,\;\mu_{2}=\begin{bmatrix}0\\ 1\end{bmatrix},\;\Sigma_{2}=\begin{bmatrix}1&0\\ 0&0\end{bmatrix} (b) Assignment with a discrete distribution. x = gm([1.], [0], [1]); y = x + 1; \pi=1,\quad\mu=\begin{bmatrix}0\\ 1\end{bmatrix},\quad\Sigma=\begin{bmatrix}1&1\\ 1&1\end{bmatrix} (c) Deterministic function. x = gm([1.], [0], [1]); y = gm([1.], [0], [1]); observe(y == 0.5); \pi=1,\quad\mu=\begin{bmatrix}0\\ 0.5\end{bmatrix},\quad\Sigma=\begin{bmatrix}1&0\\ 0&0\end{bmatrix} (d) Observation of a constant value. Figure 1 : Nondifferentiability of SOGA semantics. Examples yielding singular covariance matrices. Figure 1 shows four minimal examples in which this may occur. In Figure 1(a) , y is assigned a constant value c , setting its variance to 0 ; in Figure 1(b) , y is assigned with a discrete (Bernoulli) distribution, yielding again 0 variance; in Figure 1(c) , y is assigned a deterministic function of x , so the distribution of y is completely determined by that of x ; reflected in the singularity of the covariance matrix. In Figure 1(d) , y is observed to take on a real value, having an effect analogous to a constant assignment. In order to deal with such cases consistently, we smooth the semantics. Smoothing will depend on a hyper-parameter \epsilon>0 that we assume fixed for the rest of this section. Intuitively, \epsilon represents the amount of smoothing applied to the program and corresponds to the standard deviation of the Gaussian perturbation applied to smoothed variables. Next, we discuss how we smooth Boolean predicates and the whole semantics separately. Throughout the section, we let V denote the set of program variables that have been smoothed. Smoothing operator for Boolean predicates. We define the following smoothing operator for Boolean predicates, that takes as input a predicate b and a set of smoothed variables V and returns a new predicate. \mathcal{B}_{\epsilon}(x\bowtie c,V)=\begin{cases}x>c+\delta_{\epsilon}&\text{if }\bowtie\text{ is }>,x\in V\\ x>c-\delta_{\epsilon}&\text{if }\bowtie\text{ is }\geq,x\in V\\ xc-\delta_{\epsilon})\wedge(x0 . The semantics of a valid program P is then defined as a mixture of the semantics of its path: \llbracket{P}\rrbracket^{\Delta,\epsilon}=\sum_{\begin{subarray}{c}\omega\in\Omega^{P}\\ \llbracket{\omega}\rrbracket^{\Delta,\epsilon}=(p,D)\end{subarray}}\frac{p\cdot D}{\sum_{\begin{subarray}{c}\omega^{\prime}\in\Omega^{P}\\ \llbracket{\omega^{\prime}}\rrbracket^{\Delta,\epsilon}=(p^{\prime},D^{\prime})\end{subarray}}p^{\prime}}. Let us go back to Figure 1 , to briefly discuss how \llbracket{\cdot}\rrbracket^{\Delta,\epsilon} avoids the discontinuities. For the program in Figure 1(a) , \llbracket{\cdot}\rrbracket^{\Delta,\epsilon} effectively assigns y with c+z , where z is a freshly defined variable, Gaussianly distributed with mean 0 and std \epsilon . This is equivalent to assigning y with \mathcal{N}(c,\epsilon) , and yields a non-degenerate covariance matrix \Sigma=\begin{bmatrix}1&0\\ 0&\epsilon^{2}\end{bmatrix} . For the program in Figure 1(b) , \llbracket{\cdot}\rrbracket^{\Delta,\epsilon} replaces components with zero std with non-degenerate components with std \epsilon . Therefore the assignment effectivaly performed would be y=gm([0.5,0.5],[0,1],[\epsilon,\epsilon]) , yielding \Sigma_{1}=\Sigma_{2}=\begin{bmatrix}1&0\\ 0&\epsilon^{2}\end{bmatrix} . For the program in Figure 1(c) , \llbracket{\cdot}\rrbracket^{\Delta,\epsilon} acts similarly as in the first case, y is a assigned with x+1+z , with z fresh Gaussian variable with mean 0 and std \epsilon . The covariance matrix then becomes \Sigma=\begin{bmatrix}1&1\\ 1&1+\epsilon^{2}\end{bmatrix} . Finally, for the program in Figure 1(d) , the variance of y after the observation is corrected and put equal to \epsilon , yielding \Sigma=\begin{bmatrix}1&0\\ 0&\epsilon^{2}\end{bmatrix} . To avoid unwanted changes in the behaviour of the probability mass due to the smoothing, \llbracket{\cdot}\rrbracket^{\Delta,\epsilon} uses the operator \mathcal{B}_{\epsilon} to interpret differently Boolean predicates when they involve smoothed variables, as reflected in the definition of the semantics of test and observe nodes. This has the effect of avoiding conditioning to zero probability events, since \llbracket{\cdot}\rrbracket^{\Delta,\epsilon} always acts on non-degenerate distributions and \mathcal{B}_{\epsilon}(b,V) always returns open sets. In the next section, we will prove that the semantics computed by \llbracket{\cdot}\rrbracket^{\Delta,\epsilon} is indeed differentiable in the program parameters and that by suitably choosing the value of \delta_{\epsilon} when applying \mathcal{B}_{\epsilon} \llbracket{\cdot}\rrbracket^{\Delta,\epsilon} will converge to to \llbracket{\cdot}\rrbracket^{S} . x\sim gm([1],[0],[\sigma]) if x<\theta then y:=-1 else y:=1 end if v_{0} entry v_{1} rnd x\sim gm([1],[0],[\sigma]) v_{2} test x<\theta v_{4} det y=-1 \textit{cond}(v)=\textit{false} v_{3} det y=1 \textit{cond}(v)=\textit{true} v_{5} exit Figure 2 : Example program P (left) and its cfg (right). Example 1. Consider the program P and its cfg in Fig. 2 , where \theta and \sigma are parameters with \theta\in(-\infty,+\infty) and \sigma\in(0,+\infty) . The exact semantics is: \llbracket P\rrbracket=\Phi(\theta/\sigma)\cdot(\mathcal{N}(0,\sigma)_{\mid x<\theta}\otimes\delta_{-1})+(1-\Phi(\theta/\sigma))\cdot(\mathcal{N}(0,\sigma)_{\mid x\geq\theta}\otimes\delta_{1}) In particular, the exact marginal over y is a discrete distribution putting \Phi(\theta/\sigma) probability mass on -1 and 1-\Phi(\theta/\sigma) on 1 . Therefore, the exact marginal over y is nondifferentiable (in fact, discontinuous) in the parameters. Using the SOGA semantics, closed with respect to GMs, yields: \llbracket{P}\rrbracket^{S}=\Phi(\theta/\sigma)\cdot\mathcal{T}_{\textrm{gm}}(\mathcal{N}(0,\sigma)_{\mid x<\theta}\otimes\delta_{-1})+(1-\Phi(\theta/\sigma))\cdot\mathcal{T}_{\textrm{gm}}(\mathcal{N}(0,\sigma)_{\mid x\geq\theta}\otimes\delta_{1}) However, the marginal over y remains unchanged, and therefore still nondifferentiable. When computing the differentiable semantics, not only is the moment-matching operator applied to close the semantics with respect to GMs, degeneracies are avoided by smoothing the assignments of y . This yields: \displaystyle\llbracket{P}\rrbracket^{\Delta,\epsilon} \displaystyle=\Phi(\theta/\sigma)\cdot\mathcal{T}_{\textrm{gm}}(\mathcal{N}(0,\sigma)_{\mid x<\theta}\otimes\mathcal{N}(-1,\epsilon))+ \displaystyle\hskip 113.81102pt+(1-\Phi(\theta/\sigma))\cdot\mathcal{T}_{\textrm{gm}}(\mathcal{N}(0,\sigma)_{\mid x\geq\theta}\otimes\mathcal{N}(1,\epsilon)) For any \sigma\in(0,+\infty) , the differentiable marginal over y is given by \Phi(\theta/\sigma)\cdot\mathcal{N}(-1,\epsilon)+(1-\Phi(\theta/\sigma))\cdot\mathcal{N}(1,\epsilon). Figure 3 : Marginal posterior densities of program P under different semantics. The orange lines highlight the different components of the mixtures. The marginal densities of the three semantics, computed for \sigma=1 and \theta=0 are represented in Fig. 3 , where the densities of the components of the mixtures are highlighted in orange and for DeGAS we fixed \epsilon=0.05 . 4 Properties of \llbracket{\cdot}\rrbracket^{\Delta,\epsilon} In this section we prove two properties of the DeGAS semantics operator \llbracket{\cdot}\rrbracket^{\Delta,\epsilon} , namely differentiability of \llbracket{P}\rrbracket^{\Delta,\epsilon} with respect to the parameters and convergence of \llbracket{P}\rrbracket^{\Delta,\epsilon} to \llbracket{P}\rrbracket^{S} as \epsilon\to 0 . Differentiability. First, we focus on the differentiability of the DeGAS semantics with respect to \Theta . For this reason, in this subsection we make the dependence of the programs on the parameters explicit, using the notation P(\Theta) . For instance, program P from Example 1 would be denoted as P(\theta,\sigma) . We assume that the parameters come with assigned initial values and interval domains and that they always take values in the interval domains. For instance, for P(\theta,\sigma) we could specify the initial values d_{\theta}=0 and d_{\sigma}=1 and the interval domains \theta\in(-\infty,+\infty) , \sigma\in(0,+\infty) . We say that a distribution D(\Theta) is differentiable in \Theta if its pdf is. For example, if D(\Theta) is a GM, D(\Theta) is differentiable in \Theta if, for i=1,\ldots,c (i) \pi_{i}(\Theta) , \mu_{i}(\Theta) and \Sigma_{i}(\Theta) are differentiable in \Theta ; (ii) \Sigma_{i}(\Theta) is non-singular for every value of \Theta that satisfies the constraints. Theorem 4.1 For any valid program P(\Theta) , \llbracket{P(\Theta)}\rrbracket^{\Delta,\epsilon} returns (p^{\prime}(\Theta),D^{\prime}(\Theta),V^{\prime}) such that p^{\prime}(\Theta) and D^{\prime}(\Theta) are differentiable in \Theta . This is the core theoretical result of the paper (proved in the Appendix), because it allows for a safe application of gradient-based optimization methods to PPs. Convergence. DeGAS adds an additional layer of approximation, through the Gaussian perturbation, to the already approximated semantics of SOGA \llbracket{\cdot}\rrbracket^{S} . We prove that this additional approximation tends to disappear when the perturbation becomes very small, i.e. in the limit for \epsilon\to 0 . Coupled with SOGA’s convergence result to the true semantics \llbracket\cdot\rrbracket , this offers a principled way of obtaining sample-free gradients for a class of PPs. DeGAS’ convergence proof (provided in the Appendix) is surprisingly subtle and deserves an intuitive explanation. When smoothing the predicates, the dependence of \delta_{\epsilon} on \epsilon can jeopardize the convergence. The following example motivates the introduction of an additional requirement, called consistency , that is needed to guarantee convergence. Example 1 We consider two example programs: \displaystyle P_{1}\colon \displaystyle{x}~\texttt{:=}~{0};{y}\sim{gm([1.],[0.],[1.])};\texttt{observe}~{x\geq 0}, \displaystyle P_{2}\colon \displaystyle{x}~\texttt{:=}~{0};{y}\sim{gm([1.],[0.],[1.])};\texttt{observe}~{x>0}. In SOGA we have \llbracket{P_{1}}\rrbracket^{S}=(1,\delta_{0}\times\mathcal{N}(0,1)) and \llbracket{P_{2}}\rrbracket^{S}=(0,\delta_{0}\times\mathcal{N}(0,1)) . In DeGAS, before the observe statement for both programs we have the output triple (1,D_{\epsilon},\{x\}) where D_{\epsilon}=\mathcal{N}(0,\epsilon)\times\mathcal{N}(0,1) . However, the predicates of the observe node are smoothed differently: \mathcal{B}_{\epsilon}(x\geq 0,\{x\})=x>-\delta_{\epsilon},\qquad\mathcal{B}_{\epsilon}(x>0,\{x\})=x>\delta_{\epsilon}. Consider P_{1} . To compute the differentiable semantics of the observe node we need to compute P_{D_{\epsilon}}(x>-\delta_{\epsilon}) and the moments of (D_{\epsilon})_{\mid x>\delta_{\epsilon}} , and we want them to tend to 1 and to the moments of \delta_{0}\times\mathcal{N}(0,1) , respectively. Here, we focus on the probabilities, since the convergence of the moments are proved using similar arguments. Letting \Phi denote the cdf of the standard Gaussian, then P_{D_{\epsilon}}(x>-\delta_{\epsilon})=1-\Phi\left(-\frac{\delta_{\epsilon}}{\epsilon}\right). For this quantity to tend to 1 we need \frac{\delta_{\epsilon}}{\epsilon}\to\infty . Intuitively, this limit forces \delta_{\epsilon} to decrease slower than the variance of x (in this case \epsilon ), so that as \epsilon tends to 0 more and more of the probability mass of D_{\epsilon} is inside \{x>-\delta_{\epsilon}\} . Moreover, it is clear that if \delta_{\epsilon} is a linear function of \epsilon or if it decreases faster than it, the limit cannot hold. Analogously consider P_{2} for which P_{D_{\epsilon}}(x>\delta_{\epsilon})=1-\Phi(\frac{\delta_{\epsilon}}{\epsilon}) . For it to tend to 0 we need again \frac{\delta_{\epsilon}}{\epsilon}\to\infty . This time the slower convergence of \delta_{\epsilon} to 0 allows a larger part of the probability mass of D_{\epsilon} to remain outside \{x>\delta_{\epsilon}\} . The previous example leads us to the following definition and theorem (we report the full proof in the Appendix). Definition 1 The operator \mathcal{B}_{\epsilon} is applied consistently if for every test and observe node with \textit{arg}(v)=x_{i}\bowtie c when \mathcal{B}_{\epsilon} is applied to compute \llbracket{v}\rrbracket^{\Delta,\epsilon}(p,D,V) and x_{i}\in V , \delta is chosen such that: \lim_{\epsilon\to 0}\delta_{\epsilon}(\epsilon)=0\qquad\text{ and }\qquad\lim_{\epsilon\to 0}\frac{\delta_{\epsilon}(\epsilon)}{\sqrt{\Sigma_{x_{i},x_{i}}(\epsilon)}}=+\infty for every \Sigma(\epsilon) covariance matrix of a component of D . The dependence of \Sigma from \epsilon is guaranteed by the fact that x_{i}\in V . Theorem 4.2 Suppose P is a valid program and \mathcal{B}_{\epsilon} is applied consinstently when computing \llbracket{P}\rrbracket^{\Delta,\epsilon} . Then \lim_{\epsilon\to 0}\llbracket{P}\rrbracket^{\Delta,\epsilon}=\llbracket{P}\rrbracket^{S} (where convergence for the distributions is intended in the sense of convergence in distribution ). We remark that, while in theory it is possible to let \epsilon tend to 0 to make the additional error vanish, in practice we want to use a value of \epsilon large enough to enable efficient gradient-based optimization, as will be discussed next. 5 Experimental Evaluation Setup. We evaluate DeGAS along two axes: (i) we optimize parameters of benchmark probabilistic programs taken from the literature comparing with Variational Inference (VI) and Markov Chain Monte Carlo (MCMC); (ii) we evaluate DeGAS on programs with discontinuities related to continuous variables, which, as we will show, make standard optimization methods inapplicable. In this case we consider classic models of cyber-physical systems (CPS), whose parameters are synthesized to optimize trajectory likelihoods or reachability properties. We implemented DeGAS in Pytorch, leveraging automatic differentiation for the gradient computation (cf. Appendix 0.C ) and employing Adam as optimizer. For all the experiments we set \delta_{\epsilon}=\sqrt{\epsilon} and report the results for \epsilon=0.001 . The choice of \delta_{\epsilon} is coherent for the consistency assumptions. Furthermore, we did not observe significant accuracy changes with respect to the SOGA approximation when varying \epsilon , as long as it stays below 0.1 , as reported in Appendix 0.D.1 . This is further confirmed by the results reported in Appendix 0.D.6 , pointing to the fact that the main source of error is that induced by SOGA, while \epsilon has a negligible empirical effect for the considered values. For a dedicated analysis of the SOGA error for inference tasks, including discussion on increasing the Gaussian approximation order, we refer the reader to [ 29 ] . We run all the experiments on a machine equipped with an Apple M2 processor with 8 cores running at 3.49 GHz and 8 GB RAM. For all the experiments we set a time-out threshold of 600 s. Comparison with VI and MCMC. We start by comparing DeGAS with Variational Inference (VI) and Markov Chain Monte Carlo (MCMC) as implemented in Pyro [ 5 ] on a set of 13 case studies taken from the PPL literature ( [ 10 , 15 , 16 ] ). As a standard benchmark optimization task, we also consider a Proportional Integral Derivative (PID) controller, described in Appendix 0.D.2 . For each case study, some of the significant variables are set as optimizable parameters while others as observables. For the observables a dataset D of size N=1000 is generated for the true value of the parameters. For the PID case study, data correspond to idealized representations of stable dynamics, maintaining the system at its equilibrium point. For each program, the posterior density computed by DeGAS is used to compute the negative log-likelihood l(\Theta)=-\log f_{\Theta}(x) of the dataset D ; then, we optimize to find \Theta^{*}=\text{argmin}_{\Theta}l(\Theta). For both VI and DeGAS, we report the results for the value of the learning rate chosen among \{0.001,0.005,0.01,0.05,0.1,0.2\} that achieves the minimum error. The optimization is stopped upon convergence within a tolerance of 10^{-8} with a patience of 30 iterations, with a maximum of 500 steps for DeGAS (except 1000 for the PID model) and 1000 for VI. For VI, we use the Trace_ELBO loss 1 1 1 https://docs.pyro.ai/en/dev/inference_algos.html . For MCMC, we run the NUTS kernel with 4 chains, initially running inference with 500 samples and 50 warm-up steps. If \hat{R} exceeds 1.05 , the procedure is repeated, increasing the number of samples by 500 and the warm-up steps by 50 when the total number of steps is between 2000 and 5000 , and by 100 thereafter, up to a maximum of 6000 total steps. All hyperparameter values are reported in Appendix 0.D.3 . Table 1 collects the results, where ‘time’ refers to the average runtimes (in s) out of 10 executions and ‘error’ refers to the average relative difference between the optimized value and the real value across all the optimizable parameters of the program. As the table shows, our approach generally achieves performance comparable to the baseline methods, and in several benchmarks it outperforms them in terms of accuracy. Two models particularly challenging for DeGAS are Grass and Burglary. Both models contain a large number of nested if statements, that give rise to a high number of components in the GM approximation. This problem is also known for SOGA and can be mitigated using a pruning strategy [ 29 ] , whose tuning is outside the scope of this paper. Model # Par. # Var. VI MCMC DeGAS Time Error Time Error Time Error Bernoulli 1 2 0.204 0.024 10.968 0.023 1.986 0.001 Burglary 2 7 3.244 0.913 13.014 0.141 14.347 1.686 ClickGraph 1 6 1.635 0.376 62.546 0.096 21.600 0.086 ClinicalTrial 3 6 1.055 1.980 120.492 2.536 17.070 0.657 Grass 4 6 3.077 0.306 58.151 0.015 317.582 0.036 MurderMistery 1 1 0.792 8.015 14.036 2.303 2.508 0.203 SurveyUnbiased 2 2 0.794 0.013 17.030 0.013 11.570 0.008 TrueSkills 3 6 2.056 0.003 t.o. t.o. 1.664 0.003 TwoCoins 2 1 0.095 0.864 49.120 0.873 3.410 0.688 AlterMu 3 5 1.007 1.043 t.o. t.o. 0.640 0.312 AlterMu2 2 3 0.718 0.556 384.730 0.139 0.618 0.096 NormalMixtures 3 3 1.061 0.909 345.409 0.053 2.941 0.386 PID 2 55 10.778 – nc nc 213 – Table 1 : Comparison of inference methods across models. Models highlighted in gray indicate cases where DeGAS outperformed both other methods in either accuracy or execution time. For the last model, PID, we are not able to quantify the error, as the true parameters are unknown, but we show the result of the optimization in Figure 7 . MCMC fails to converge for this case study ( \hat{R}\gg 1 .) Many benchmark programs include conditional statements with Boolean guards over discrete variables. When these conditions are enumerable, both VI v\sim gm([1],[\mu_{1}],[5]) if v>0 then y\sim gm([1],[\mu_{2}],[1]) else y\sim gm([1],[-2],[1]) end if MCMC can correctly perform inference through enumeration. 2 2 2 https://pyro.ai/examples/enumeration.html However, when the condition depends on continuous variables, the resulting model becomes discontinuous and nondifferentiable, breaking the smoothness assumptions of gradient-based VI and affecting the convergence of MCMC. This behavior is clearly visible in the program on the right inset adapted from [ 24 ] , where \mu_{1} and \mu_{2} are optimizable parameters and whose true value is 0.5 and 1 . Figure 4 shows that VI has oscillatory loss values (similarly, MCMC does not reach a value of \hat{R}<1.05 , indicating nonconvergence), while DeGAS optimizes successfully. This highlights the complementarity of DeGAS with existing methods: while it may incur longer runtimes on some benchmarks, it can also enable efficient optimization in challenging discontinuous settings, where VI and MCMC are known to struggle. 0 100 200 300 400 2{,}000 2{,}100 Iter. Loss DeGAS 0 200 400 4{,}500 4{,}550 Iter. Loss VI Figure 4 : Comparison of DeGAS and VI loss curves for the program in Section 5. Parameter synthesis for cyberphysical systems. We now consider models of cyber-physical systems (CPS) where control-flow branches depend on continuous random variables such that the previously described nondifferentiability issue arises. DeGAS, instead, provides an analytic form for the loss functions: we show examples of both data likelihoods and complex reachability objectives. We consider the following models taken from [ 31 , 11 ] and fully described in Appendix 0.D.4 : 1. Thermostat represents a thermostat maintaining fixed temperature by switching an heater on or off when the temperature crosses the thresholds t_{on} and t_{off} (optimizable parameters). The temperature evolves according to a first-order decay process with an added heating term when the heater is active and stochastic fluctuations due to noise. 2. Gearbox represents a car’s transmission system. We consider a model with three gears. The controller determines when to shift from one gear to the next, allowing only consecutive transitions. The thresholds s_{i} (optimizable parameters) specify the velocity at which gear i is released and gear i+1 engages. Additionally, gear shifts are not instantaneous: in our model, each transition lasts 0.3 seconds, during which the gearbox remains disengaged. The velocity grows linearly when the gear is engaged and decreases quadratically when disengaged. In both cases it is subject to stochastic fluctuations. 3. Controlled Bouncing Ball represents a ball dropped onto a platform with a spring and damper. The spring pushes the ball back with a force determined by the compliance C , and the damper slows the ball according to the coefficient R (both are optimizable parameters). When the ball reaches the platform, the system transitions to a reflection mode, returning to free fall once the height is positive. Parameter synthesis by data likelihoods. As in the previous case studies, the goal of the optimization is to maximize the negative log-likelihood with respect to a set of 100 trajectories generated from the models using the true parameter values. Table 2 and Figure 5 show that DeGAS consistently recovers parameter values close to the ground truth. The optimized mean trajectories (in red) accurately capture the behavior of the stochastic simulations (in grey), even when the initial trajectories (in blue) are far from the correct one. The normalized loss curves confirm convergence in all three cases. Table 2 : Results for the CPS optimization from trajectories Case Study Params lr Steps Time Init Target Result Thermostat t_{ON},t_{OFF} 0.1 40 61.964 (15,22) (17,20) (16.78,19.97) Gearbox s_{1},s_{2} 0.15 200 167.643 (8,12) (10,20) (8.69,19.24) Bouncing Ball R,1/C 0.8 100 500.621 (-1,450) (7,400) (5.27,408.99) 0 10 20 30 14 16 18 20 22 Time step Thermostat 0 10 20 10 20 30 Time step Gearbox 0 10 20 30 0 5 10 Time step Controlled Bouncing Ball 0 20 40 60 80 100 0 0.5 1 Epoch Loss Normalized Loss Functions T G B Figure 5 : Mean trajectories with one standard deviation (red) obtained using optimized parameters, compared to trajectories generated with initial parameters (blue). The gray trajectories represent the samples used for optimization. Synthesis by reachability A complementary synthesis objective consists in optimizing the parameters of the CPS to maximize the probability of reaching specific target states or satisfying certain behavioral constraints. We consider three such cases. Thermostat: the goal is to maximize the probability of reaching the region T(t)\in[T_{min},T_{max}]=[19.9,20.1] in mode "ON" at various time points (\tau_{1}=0.6,\tau_{2}=1.8\text{ and }\tau_{3}=2.4) ; gearbox: we maximize the probability of maintaining velocity below 16 across the whole trajectory; bouncing ball: we want to maximize the probability that the ball reaches H\geq 7 when falling after making one bounce. The optimizable parameters are the same as the ones in the previous section. We report the results in Table 3 and Figure 6 . The table reports the initial and final loss values, since the true optimal parameters are unknown. As shown in the figure, for all models the optimized trajectories (in red) satisfy the desired behavioral constraints, unlike the initial trajectories (in blue). The optimization curves further confirm convergence across all three models. Table 3 : Results for the CPS optimization from reachability properties Case Study lr Steps Time(s) Init Init Loss Result Fin. Loss Thermostat 0.1 100 2770 (16.5,22) -2e^{-12} (19.04,21.30) -5695 1Gearbox 0.5 40 52.642 (10,20) 1.000 (1.92,-1.57) 0.966 Bounc. Ball 0.2 50 184.264 (7,200) -0.002 (-3.87,210.14) -0.979 0 10 20 15 20 25 30 Time step Thermostat 0 10 20 10 20 Time step Gearbox 0 10 20 30 0 5 10 Time step Controlled Bouncing Ball 0 20 40 60 80 100 0 0.5 1 Epoch Loss Normalized Loss Functions T G B Figure 6 : Mean trajectories with one standard deviation (red) obtained by optimizing the target represented in gray are compared with initial trajectories (blue) 6 Conclusions We introduced DeGAS, a method to enable sample-free optimization of probabilistic programs via a differentiable program semantics. DeGAS smoothens SOGA, a semantics which represents a program evolution through Gaussian-mixture updates (affine maps, products, and truncated moments) that enable an analytic—but, in general, discontinuous, representation of the posterior distribution. We demonstrated the potential of DeGAS in tackling synthesis tasks that cannot be directly solved through classic optimization methods such as variational inference and Markov chain Monte Carlo, due to the presence of discontinuities hindering convergence. In principle, the main ideas behind DeGAS can be applied to any semantics that (i) represents program states in a tractable form, (ii) supports closed-form (or deterministic-quadrature) updates for transforms and conditioning, and (iii) admits a smooth relaxation of discrete or measure-zero constructs whose parameter \varepsilon\to 0 recovers the original semantics. We conjecture that under these conditions, all statements about differentiability hold for \varepsilon>0 , and convergence back to the unsmoothed semantics follows by similar arguments as for SOGA. Thus, an interesting direction for future work is to study other semantics such as probabilistic circuits, mixture of exponentials or general symbolic PPs that provide analytic or semi-analytic representations of distributions. Data Availability Statement DeGAS is publicly available on Github at https://github.com/frarandone/DeGAS . This paper was accompanied by an artifact for the replication of the experimental results which can be found at: https://zenodo.org/records/18197807 . Appendix Appendix 0.A Exact and SOGA semantics 0.A.1 Definition of SOGA semantics To define the SOGA semantics, as in [ 29 ] , first the exact control-flow graph (cfg) semantics from [ 19 ] is introduced. We use the same labelling used in Section 3 . The exact semantics of a node v is a function taking as input a pair (p,D) , and returning a pair (p^{\prime},D^{\prime}) of the same type. The only exception is the entry node which takes no input. We define the semantics of each node type as follows. • If v\colon\textit{entry} , then \llbracket v\rrbracket_{\omega}=(1,\mathcal{N}(0,\mathbb{I}_{n})). • If v\colon\textit{det} , then, letting D^{\prime} denote the distribution of x[x_{i}\to e] , \llbracket v\rrbracket_{\omega}(p,D)=\begin{cases}(\pi,D)&\text{ if }\textit{arg}(v)=\texttt{skip}\\ (p,D^{\prime})&\text{ if }\textit{arg}(v)={x_{i}}~\texttt{:=}~{e}.\end{cases} • If v\colon\textit{rnd} and \textit{arg}(v)={x_{i}}\sim{gm(\pi,\mu,\sigma)} , then \llbracket v\rrbracket_{\omega}(p,D)=(p,\textrm{Marg}_{x\setminus x_{i}}(D)\otimes G_{\pi,\mu,\sigma}). • If v\colon\textit{test} , letting \textit{arg}(v)=b : \llbracket v\rrbracket_{\omega}(p,D)=\begin{cases}(p\cdot P_{D}(b),D_{\mid b})&\textit{cond}(s_{\omega}(v))=\textit{true}\text{ and }P_{D}(b)\neq 0\\ (p\cdot P_{D}(\neg b),D_{\mid\neg b})&\textit{cond}(s_{\omega}(v))=\textit{false}\text{ and }P_{D}(\neg b)\neq 0\\ (0,D)&\text{else}.\end{cases} • If v\colon\textit{observe} , letting \textit{arg}(v)=b and I=\int_{\mathbb{R}^{n-1}}f_{D}(x[x_{i}\to c])d(x\setminus x_{i}) : \llbracket v\rrbracket_{\omega}(p,D)=\begin{cases}(p\cdot I,D_{\mid b})&b\text{ is }x_{i}==c\\ (p\cdot P_{D}(b),D_{\mid b})&b\text{ is }x_{i}\bowtie c\text{ and }P_{D}(b)\neq 0\\ (0,D)&\text{else}.\end{cases} • If v\colon\textit{exit} , \llbracket v\rrbracket_{\omega}(p,D)=(p,D) . The semantics of paths and valid programs is defined as for the differentiable semantics. 0.A.2 SOGA semantics The SOGA semantics is then defined for each node using the moment-matching operator \mathcal{T}_{\textrm{gm}} defined in Section 3 \llbracket{v}\rrbracket^{S}_{\omega}=\begin{cases}\llbracket v\rrbracket_{\omega}&v\colon\textit{entry},\textit{exit}\\ (\text{Id},\mathcal{T}_{\textrm{gm}})\circ\llbracket v\rrbracket_{\omega}&\text{else}.\end{cases} The semantics of paths and programs is defined as in the previous cases. Appendix 0.B Additional proofs 0.B.1 Proof of Theorem 1 Theorem 0.B.-1 For any valid program P(\Theta) , \llbracket{P(\Theta)}\rrbracket^{\Delta,\epsilon} returns (p^{\prime}(\Theta),D^{\prime}(\Theta)) such that p^{\prime}(\Theta) and D^{\prime}(\Theta) are differentiable in \Theta . Proof Since the semantics of a valid program is defined as \llbracket{P}\rrbracket^{\Delta,\epsilon}=\sum_{\begin{subarray}{c}\omega\in\Omega^{P}\\ \llbracket{\omega}\rrbracket^{\Delta,\epsilon}=(p,D)\end{subarray}}\frac{p\cdot D}{\sum_{\begin{subarray}{c}\omega^{\prime}\in\Omega^{P}\\ \llbracket{\omega^{\prime}}\rrbracket^{\Delta,\epsilon}=(p^{\prime},D^{\prime})\end{subarray}}p^{\prime}} and semantics of each path is defined as \llbracket{\omega}\rrbracket^{\Delta,\epsilon}=\llbracket{v_{n}}\rrbracket^{\Delta,\epsilon}_{\omega}\circ\ldots\circ\llbracket{v_{0}}\rrbracket^{\Delta,\epsilon}_{\omega} we can prove for each node v that if (p(\Theta),D(\Theta)) are differentiable in \Theta so is \llbracket{v}\rrbracket^{\Delta,\epsilon}_{\omega}(p(\Theta),D(\Theta),V) . Without loss of generality it is assumed that D(\Theta) is a Gaussian distribution with mean \mu(\Theta) and covariance matrix \Sigma(\Theta) , where \mu and \Sigma are differentiable functions of \Theta and \Sigma is non-singular for every \Theta . At node v , \llbracket{v}\rrbracket^{\Delta,\epsilon}_{\omega} outputs a p^{\prime}(\Theta) and D^{\prime}(\Theta) where D^{\prime} is possibly a GM. In this case we denote with \mu^{\prime}(\Theta) , \Sigma^{\prime}(\Theta) the mean and the covariance matrix of any component of D^{\prime}(\theta) . For each node type it is proved that p^{\prime}(\Theta) , \mu^{\prime}(\Theta) and \Sigma^{\prime}(\Theta) are differentiable in \Theta and that \Sigma^{\prime}(\Theta) is non-singular. The general case in which D(\Theta) (resp. D^{\prime}(\Theta) ) is a GM can be recovered by applying the same arguments componentwise. • v:\textit{det} . If \textit{arg}(v)=\texttt{skip} diffrentiability follows trivially from the differentiability of p(\Theta) and D(\Theta) . If \arg(v)={x_{i}}~\texttt{:=}~{e} , then \llbracket{v}\rrbracket^{\Delta,\epsilon}_{\omega}(p,D,V)=(p,D^{\prime},V) so we only need to prove differentiability of D^{\prime} . We distinguish three cases. \ast e is linear, x_{i} is not in e . Let x^{\prime} denote the subvector x\setminus x_{i} and consider the vector (x^{\prime},x_{i},z) . Before the assignment the vector is Gaussianly distributed with \mu(\Theta)=\begin{bmatrix}\mu(\Theta)_{x^{\prime}}\\ \mu(\Theta)_{x_{i}}\\ 0\end{bmatrix},\quad\Sigma(\Theta)=\begin{bmatrix}\Sigma_{x^{\prime},x^{\prime}}&\Sigma_{x^{\prime},x_{i}}&0\\ \Sigma_{x_{i},x^{\prime}}&\Sigma_{x_{i},x_{i}}&0\\ 0&0&\epsilon^{2}\end{bmatrix}. Let \alpha(\Theta) be the row vector representing the linear combination in e and \alpha_{0}(\Theta) the zero-th order term. Both \alpha(\Theta) and \alpha_{0}(\Theta) are differentiable in \Theta since the coefficient are either constant or parameters themself. Let A(\theta) be the blockmatrix A(\Theta)=\begin{bmatrix}\mathbb{I}_{n-1}&0&0\\ \alpha(\Theta)&0&1\\ 0&0&1\end{bmatrix}. After the assignment {x_{i}}~\texttt{:=}~{e+z} the distribution over program variables is Gaussianly distributed with mean \mu^{*}(\Theta) and covariance matrix \Sigma^{*}(\Theta) given by (we suppress dependence on \Theta at the r.h.s. for the sake of notation): \mu^{*}(\Theta)=\begin{bmatrix}\mu_{x^{\prime}}\\ \alpha\mu+\alpha_{0}\\ 0\end{bmatrix},\Sigma^{*}(\Theta)=A\Sigma A^{T}=\begin{bmatrix}\Sigma_{x^{\prime},x^{\prime}}&\Sigma_{x^{\prime},x_{i}}\alpha^{T}&0\\ \alpha\Sigma_{x_{i},x^{\prime}}&\alpha\Sigma_{x^{\prime},x^{\prime}}\alpha^{T}+\epsilon^{2}&\epsilon^{2}\\ 0&0&\epsilon^{2}\end{bmatrix}. When considering the marginal over x , by properties of the Gaussians [ 6 ] , we just need to consider the submatrices indexed by x=(x^{\prime},x_{i}) . Since \mu,\Sigma,\alpha and \alpha_{0} depend differentiably on \Theta so do \mu^{*}_{x} and \Sigma^{*}_{x,x} . However, to prove that the resulting pdf is differentiable in \Theta we still need to prove that \Sigma^{*}_{x,x} is non-singular. This can be done by computing the determinant using Schur complement [ 9 ] : |\Sigma^{*}_{x,x}|=\alpha\Sigma_{x^{\prime},x^{\prime}}\alpha^{T}+\epsilon^{2}-\alpha\Sigma_{x_{i},x^{\prime}}\Sigma_{x^{\prime},x^{\prime}}^{-1}\Sigma_{x^{\prime},x_{i}}\alpha^{T}=\epsilon^{2}>0. \ast e is linear, x_{i} in e . For this case the computations are analogous to the ones carried out above, except that the variable z is not needed. \ast e is non-linear, i.e. {x_{i}}~\texttt{:=}~{x_{j}x_{k}} . The differentiability with respect to \Theta of the mean and the covariance matrix after the assignment, follows from the fact that this quantities can be computed via Isserlis’s theorem [ 33 ] as polynomial functions of \mu(\Theta) and \Sigma(\Theta) . Again, to prove differentiability of the pdf we need to prove that the new covariance matrix \Sigma^{*}(\Theta) is non-singular. Let x^{\prime} denote the sub-vector x^{\prime}=x\setminus\{x_{i},x_{j},x_{k}\} . We prove that the covariance matrix of \tilde{x}=(x^{\prime},x_{j}x_{k}) is non-singular. For the vector (x_{j},x_{k},x_{k}x_{k}) the proof is analogous. These two facts together prove that \Sigma^{*} is non-singular. We proceed by contraddiction, supposing that the covariance matrix \tilde{\Sigma} of \tilde{x} is singular. Then exists a non-zero vector c such that c^{T}\tilde{\Sigma}c=0 . This means that the variance of c^{T}(\tilde{x}-\mathbb{E}[\tilde{x}]) is 0 . But this means that c^{T}(\tilde{x}-\mathbb{E}[\tilde{x}]) is deterministic, and in particular equal to its mean, 0 . Therefore, c can be partioned into a , b such that: a(x_{j}x_{k}-\mathbb{E}[x_{j}x_{k}])+b^{T}(x^{\prime}-\mathbb{E}[x^{\prime}])=0. (3) We now use a known property of Gaussian vectors: the conditional expectation of a component with respect to others is an affine function [ 6 ] . This means that \mathbb{E}[x^{\prime}|x_{j},x_{k}]=\alpha x_{j}+\beta x_{k}+\gamma for some vectors \alpha,\beta,\gamma . Therefore, conditioning ( 3 ) to x_{j} and x_{k} and taking the mean we find that exist constants \alpha,\beta,\gamma,\delta such that: \alpha x_{j}x_{k}+\beta x_{j}+\gamma x_{k}+\delta=0. If \alpha=0 the equality reduces to \beta x_{j}+\gamma x_{k}+\delta=0 , which would imply a degeneracy in the original covariance matrix \Sigma , causing a contraddiction. If \alpha\neq 0 we can rewrite x_{j}=\frac{-\gamma x_{k}-\delta}{\alpha x_{k}+\beta} . Since x_{k} is non degenerate by hypothesis, the denominator is different than zero a.e.. But by the property of Gaussian vectors, \mathbb{E}[x_{j}|x_{k}] must be an affine function, which is violated by the fact that x_{j} is a rational function of x_{k} . Therefore \Sigma^{*} cannot be singular. • v\colon\textit{rnd} . In this case the differentiability is guaranteed by the differentiability of D(\Theta) and of gm(\pi,\mu,\sigma) , which has never components with 0 std. • v\colon\textit{observe} . We distringuish the three cases. \ast b is x_{i}==c and x_{i}\not\in V . Differentiability follows from the differentiability of the pdfs of \mathcal{N}(c,\epsilon) and of D_{\mid b} , guaranteed by the fact that its moments are polynomials in \mu(\Theta) and \Sigma(\Theta) . In addition, if \Sigma(\Theta) is non-degenerate so is the covariance matrix of D_{\mid b} . \ast b is x_{i}\bowtie c in all the other cases. In this case the predicate is transformed into b^{\prime}=\mathcal{B}_{\epsilon}(x_{i}\bowtie c,V) . Since D is non-degenerate and all the conditions defined by \mathcal{B}_{\epsilon}(b,V) have positive measure P_{D}(b^{\prime}) is differentiable and different than 0 (it is computed using the cdf of D which is a differentiable function). The moments of the truncated distribution dist_{\mid b^{\prime}} are computed using the formulas in [ 17 ] as functions of \mu(\Theta) and \Sigma(\Theta) and of the extrema of the truncation ( -\infty and +\infty for all variables except for x_{i} , for which they involve c ). Since D is non-degenerate, the formulas in [ 17 ] are differentiable in their arguments. Therefore, the moments of dist_{\mid b^{\prime}} are be differentiable in \Theta . In addition, we need to prove that the new covariance matrix will be non-singular, but this follows from the fact that the initial covariance matrix is non-singular and the truncations are made on sets of positive measure. • v\colon\textit{test} . We let \textit{arg}(v)=b and b^{\prime}=\mathcal{B}_{\epsilon}(b,V) . The computation of the probabilities P_{D}(b^{\prime}) (resp. \neg b^{\prime} ) and of the moments of the conditioned distributions D_{\mid b^{\prime}} (resp. \neg b^{\prime} ) uses the formulas from [ 17 ] , as in the case of observe nodes. Therefore both the probabilities and the truncated moments are differentiable in \Theta • v\colon\textit{entry} and v\colon\textit{exit} the conclusion follows trivially. 0.B.2 Proof of Theorem 2 Theorem 0.B.0 Suppose P is a valid program and \llbracket{P}\rrbracket^{\Delta,\epsilon} \mathcal{B}_{\epsilon} is applied consinstently when computing \llbracket{P}\rrbracket^{\Delta,\epsilon} . Then \lim_{\epsilon\to 0}\llbracket{P}\rrbracket^{\Delta,\epsilon}=\llbracket{P}\rrbracket^{S} (where convergence for the distributions is intended in the sense of convergence in distribution ). Proof Recall that both for \llbracket{\cdot}\rrbracket^{\Delta,\epsilon} and \llbracket{\cdot}\rrbracket^{S} the semantics of P is defined as a mixture of the semantics of the paths in \Omega^{P} . Since we are only considering finite programs, the convergence of the program semantics is implied by the convergence of the path semantics. First, we only consider paths \omega\in\Omega^{P} such that \llbracket{\omega}\rrbracket^{S}=(p,D) with p>0 . Consider one such path with differentiable semantics \llbracket{\omega}\rrbracket^{\Delta,\epsilon}=\llbracket{v_{n}}\rrbracket^{\Delta,\epsilon}_{\omega}\circ\ldots\circ\llbracket{v_{0}}\rrbracket^{\Delta,\epsilon}_{\omega} . We prove that this converges to \llbracket{\omega}\rrbracket^{S}=\llbracket{v_{n}}\rrbracket^{S}_{\omega}\circ\ldots\circ\llbracket{v_{0}}\rrbracket^{S}_{\omega} by induction on n . For n=1 we only have an entry and an exit node, so the conclusion follows trivially. Suppose that up to node v_{i-1} one has \llbracket{v_{i-1}}\rrbracket^{\Delta,\epsilon}_{\omega}\circ\ldots\circ\llbracket{v_{0}}\rrbracket^{\Delta,\epsilon}=(p_{\epsilon},D_{\epsilon},V) and \llbracket{v_{i-1}}\rrbracket^{S}_{\omega}\circ\ldots\circ\llbracket{v_{0}}\rrbracket^{S}_{\omega}=(p,D) with \lim_{\epsilon\to 0}(p_{\epsilon},D_{\epsilon})=(p,D) . We prove that \llbracket{v_{i}}\rrbracket^{\Delta,\epsilon}_{\omega}(p_{\epsilon},D_{\epsilon},V)=(p_{\epsilon}^{\prime},D_{\epsilon}^{\prime},V^{\prime}) such that \lim_{\epsilon\to 0}(p_{\epsilon}^{\prime},D_{\epsilon}^{\prime})=(p^{\prime},D^{\prime})=\llbracket{v_{i}}\rrbracket^{S}_{\omega}(p,D) . Without loss of generality we assume that D_{\epsilon} (resp. D ) is a Gaussian with mean \mu_{\epsilon} (resp. \mu ) and covariance matrix \Sigma_{\epsilon} (resp. \Sigma ). When acting on a Gaussian D_{\epsilon} , \llbracket{v}\rrbracket^{\Delta,\epsilon} and \llbracket{v}\rrbracket^{S} can in general yield a GM with a fixed number of components, which is the semantics in both semantics, for all values of \epsilon . In this case We will denote with \mu_{\epsilon}^{\prime} (resp. \mu ) and \Sigma_{\epsilon}^{\prime} (resp. \Sigma^{\prime} ) the mean and the covariance matrix of any component of D_{\epsilon}^{\prime} (resp. D^{\prime} ), assuming to choose corresponding components in each distributions. The proof can be generalized to GMs by applying the same arguments componentwise. Observe that if D_{\epsilon}^{\prime} and D are both Gaussians it sufficient to prove that \mu_{\epsilon}^{\prime}\to\mu and \Sigma_{\epsilon}^{\prime}\to\Sigma , since, by convergence of the characteristic function, this implies convergence in distribution. We consider the possible type of v_{i} separately. • v_{i}\colon\textit{det} . If \textit{arg}(v)=\texttt{skip} , conclusion follows trivially. If \textit{arg}(v)={x_{i}}~\texttt{:=}~{e} , we only need to prove convergence of D_{\epsilon}^{\prime} to D^{\prime} . Suppose e is linear with \alpha vector of coefficients and \alpha_{0} zero-th order term. Let x^{\prime} denote the vector x\setminus x_{i} , so that x can be represented as (x^{\prime},x_{i}) . Then: \mu_{\epsilon}^{\prime}=\begin{bmatrix}[\mu_{\epsilon}]_{x^{\prime}}\\ \alpha\mu_{\epsilon}+\alpha_{0}\end{bmatrix} \Sigma_{\epsilon}^{\prime}=A\Sigma_{\epsilon}A^{T}=\begin{cases}\begin{bmatrix}[\Sigma_{\epsilon}]_{x^{\prime},x^{\prime}}&[\Sigma_{\epsilon}]_{x^{\prime},x_{i}}\alpha^{T}\\ \alpha[\Sigma_{\epsilon}]_{x_{i},x^{\prime}}&\alpha[\Sigma_{\epsilon}]_{x^{\prime},x^{\prime}}\alpha^{T}+\epsilon^{2}\end{bmatrix}&x_{i}\text{ not in }e\\ \begin{bmatrix}[\Sigma_{\epsilon}]_{x^{\prime},x^{\prime}}&[\Sigma_{\epsilon}]_{x^{\prime},x_{i}}\alpha^{T}\\ \alpha[\Sigma_{\epsilon}]_{x_{i},x^{\prime}}&\alpha[\Sigma_{\epsilon}]_{x^{\prime},x^{\prime}}\alpha^{T}\end{bmatrix}&x_{i}\text{ in }e\end{cases} For \epsilon\to 0 it is trivial to check that \mu_{\epsilon}^{\prime} and \Sigma_{\epsilon}^{\prime} converge to \mu^{\prime} , \Sigma^{\prime} . If e is non linear, \mu_{\epsilon}^{\prime} and \Sigma_{\epsilon}^{\prime} are obtained using Isserlis’ theorem [ 33 ] as polynomial functions of \mu_{\epsilon} and \Sigma_{\epsilon} . Since polynomials are continuous, the limit is preserved. • v_{i}\colon\textit{rnd}. Again, we only need to prove convergence for D_{\epsilon} but this follows immediately from convergence of G_{\pi,\mu,\sigma^{\prime}} to G_{\pi,\mu,\sigma} (recall \sigma_{j}^{\prime}=\sigma_{j} if \sigma_{j}>0 and \epsilon else). • v_{i}\colon\textit{observe} . If \textit{arg}(v)=x_{i}==c and x_{i}\not\in V convergence follows immediately from \lim_{\epsilon\to 0}\mathcal{N}(c,\epsilon)=\mathcal{N}(c,0) . Let b be x_{i}\bowtie c in one of the remaining cases. We consider two different scenarios. If \Sigma_{x_{i},x_{i}}\neq 0 we have that P_{D}(\partial b)=0 where \partial b denotes the border of the set b . In this case b is called a continuity set for D . Moreover, since V only contains variables that would be discrete in the original program x_{i}\not\in V and \mathcal{B}_{\epsilon}(b,V)=b . Therefore convergence reduces to proving P_{D_{\epsilon}}(b)\to P_{D}(b) and (D_{\epsilon})_{\mid b}\to D_{\mid b} . Since b is a continuity set for D both limits are guaranteed by Portmanteau lemma [ 4 ] . If \Sigma_{x_{i},x_{i}}=0 then \textrm{Marg}_{x_{i}}(D) has a point mass at x_{i}^{0} . Moreover, since we are working under the hypothesis that \llbracket{\omega}\rrbracket^{\Delta,\epsilon}=(p_{\omega},D_{\omega}) with p_{\omega}>0 , then P_{D}(b)>0 . Therefore, x_{i}^{0}\in(b)_{i} , where (b)_{i} is the projection of b on the i -th coordinate. Therefore P_{D}(b)=1 and D_{\mid b}=D . For D_{\epsilon} we have (\Sigma_{\epsilon})_{x_{i},x_{i}}\to 0 and (\mu_{\epsilon})_{x_{i}}\to x_{i}^{0} . Now consider let b_{\epsilon}=\mathcal{B}_{\epsilon}(b,V) and (b_{\epsilon})_{i} be the projection of b_{\epsilon} to the i -th coordinate. Then x_{i}^{0}\in(b_{\epsilon})_{i} . Moreover, since \mathcal{B}_{\epsilon} is applied consistently \delta_{\epsilon}(\epsilon)/\sqrt{\Sigma_{\epsilon}}\to+\infty and this implies \lim_{\epsilon\to 0}P_{\textrm{Marg}_{x_{i}}(D_{\epsilon})}((b_{\epsilon})_{i})=1 . But then \lim_{\epsilon\to 0}P_{D_{\epsilon}}(b_{\epsilon})=1=P_{D}(b) . For the distributions we can prove the limit using the metric induced by weak convergence, called the Levi Prokhorov metric and denoted as d_{LP}(\cdot,\cdot) . Then, d_{LP}((D_{\epsilon})_{\mid b_{\epsilon}},D)\leq d_{LP}((D_{\epsilon})_{\mid b_{\epsilon}},D_{\epsilon})+d_{LP}(D_{\epsilon},D). The first term at the r.h.s. tends to zero because \delta_{\epsilon}(\epsilon)/\sqrt{\Sigma_{\epsilon}}\to+\infty , while the second term tends to zero by hypothesis. • v_{i}\colon\textit{test} . In this case the proof works analogously as in the observe case. We have now proved that \llbracket{\omega}\rrbracket^{\Delta,\epsilon}\to\llbracket{\omega}\rrbracket^{S} for paths with positive probabilities. For paths such that \llbracket{\omega}\rrbracket^{S}=(0,D) we can just prove that p_{\epsilon}\to 0 . Let v_{i} be the first node in the path such that \llbracket{v_{i}}\rrbracket^{S}(p,D)=(p^{\prime},D^{\prime}) with p^{\prime}=0 . Then up to this node the differentiable semantics output triples (p_{\epsilon},D_{\epsilon},V) such that p_{\epsilon}\to p , D_{\epsilon}\to D and we want to prove p_{\epsilon}^{\prime}\to 0 . We know that v_{i} must either be an observe or a test node. Suppose is an observe node (the other case can be treate in the same way). Let \arg(v_{i})=b=x_{i}\bowtie c . We can rule out the case in which \bowtie is == and x_{i}\not\in V as this case can never yield probability 0. In the other cases we can distinguish again two scenarios. If \Sigma_{x_{i},x_{i}}\neq 0 then b is a continuity set for D , \mathcal{B}_{\epsilon}(\exp,V)=b and convergence is guaranteed by the Portmanteau lemma. If \Sigma_{x_{i},x_{i}}=0 , the marginal \textrm{Marg}_{x_{i}}(D) is a point mass x_{i}^{0}\not\in(b)_{i} . The D_{\epsilon} instead are Gaussians concentrating their probability mass around x_{i}^{0} . Exploiting again the consistency of the operator \mathcal{B}_{\epsilon} we can again prove P_{D_{\epsilon}}(b_{\epsilon})\to 0 . Appendix 0.C DeGAS In this section we give an overview of the tool DeGAS that implements the differentiable semantics presented earlier. DeGAS is implemented in PyTorch, and can be used programmatically from Python. A prototype implementation can be found in url-anonymized . Algorithm 1 DeGAS( \textit{input\_file},\textit{params\_dict},\textit{loss\_func},\epsilon,\textit{steps} ): 1: \textit{cfg}=\texttt{smooth\_cfg}(\textit{input\_file},\epsilon) 2: \textit{optimizer}=\texttt{import\_optimizer\_from\_torch()} 3: for \texttt{ \_ in range}(\textit{steps}) do 4: optimizer.zero_grad() 5: \textit{current\_dist}=\texttt{compute\_degas}(\textit{cfg},\textit{params\_dict}) 6: \textit{loss}=\textit{loss\_func}(\textit{current\_dist}) 7: loss.backward() 8: optimizer.step() 9: end for 10: return params_dict The algorithm implemented by DeGAS is outlined in Algorithm 1 . It takes as input a .soga file input_file , which encodes a program in the syntax of Section 3.1 ; a dictionary params_dict whose keys are parameter names (also appearing in the program, prefixed by an underscore) and whose values are PyTorch tensors with \texttt{requires\_grad}=\textit{True} ; a loss function loss_func mapping distributions to real values; the smoothing parameter \epsilon>0 ; and the number of optimization steps steps . Where required, constraints on individual parameters can be specified directly in the optimization loop by clamping them to their respective interval domain. The algorithm begins by constructing the control-flow graph (cfg) of the program via smooth_cfg . This step also prepares the information needed for computing the differentiable semantics: for instance, assignments {x}~\texttt{:=}~{c} are transformed into {x}~\texttt{:=}~{c+gm([1],[0],[\epsilon])} , and analogous rewritings are applied to other instructions. Moreover, the set of smoothed variables V is also pre-computed at each node. The resulting object cfg encodes the program’s cfg, enriched with all information required to evaluate \llbracket{\cdot}\rrbracket^{\Delta,\epsilon} . After constructing the cfg, a gradient-based optimizer from PyTorch is initialized (line 2) and the optimization loop begins (line 3). At each step, the posterior distribution is computed by compute_degas (line 5), the loss is evaluated (line 6), and the parameters in params_dict are updated via backpropagation (lines 7–8). After all iterations, the optimized parameters are returned. Computational cost of DeGAS. In computing the semantics of a program, DeGAS shares the same cfg structure of SOGA. The operations introduced to guarantee differentiability do not alter the asymptotic computational cost, since computation of the program differentiable semantics involves the same elementary operations and function calls described for SOGA [ 29 ] . The overall complexity is therefore still O(|V|2^{|T|}n^{4}) , where |V| denotes the number of nodes in the cfg, |T| denotes the number of test and observe nodes and n is the number of variables in the program, assuming that all the distributions used in rnd nodes have been pushed to the initial distribution. Analogously to SOGA, a pruning strategy can be introduced in DeGAS to limit the number of mixture components and control the computational overhead. However, in the case studies presented in this paper this was not necessary. Appendix 0.D Experimental evaluation details 0.D.1 Convergence Experiments To show how the convergence works in practice, we consider the following three programs: \displaystyle P_{1} \displaystyle\colon{x}~\texttt{:=}~{0};\texttt{observe}~{x\geq 0}; \displaystyle P_{2} \displaystyle\colon{x}~\texttt{:=}~{0};\texttt{observe}~{x>0}; \displaystyle P_{3} \displaystyle\colon{x}\sim{gm([0.5,0.5],[0,1],[0,0])};\texttt{observe}~{x==0}; In the following table we report the result of p , \mu and \sigma when \epsilon decreases and \mathcal{B}_{\epsilon} is applied consistently, choosing \delta_{\epsilon}=\sqrt{\epsilon} . For \epsilon=10^{-4} the values of all three outputs are equal to that of SOGA up to the third decimal digit. P_{1} P_{2} P_{3} p \mu \sigma p \mu \sigma p \mu \sigma \epsilon=10^{-1} 0.9992 0.0002 0.0995 0.0008 0.3434 0.0256 0.4992 0.0000 0.0991 \epsilon=10^{-2} 1.0000 0.0000 0.0100 0.0000 0.0000 0.0100 0.5000 0.0000 0.0100 \epsilon=10^{-3} 1.0000 0.0000 0.0010 0.0000 0.0000 0.0010 0.5000 0.0000 0.0010 \epsilon=10^{-4} 1.0000 0.0000 0.0001 0.0000 0.0000 0.0001 0.5000 0.0000 0.0001 SOGA 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.5000 0.0000 0.0000 Table 4: Results for DeGAS and SOGA as the value of \epsilon decreases. By testing DeGAS on the synthesis of the parameters of probabilistic programs varying the value of \epsilon we obtain consistent results except, in some cases highlighted in gray, for \epsilon=0.1 . These programs are more complex, involving multiple variables and nested conditional branches. Model \boldsymbol{\epsilon=0.1} \boldsymbol{\epsilon=0.01} \boldsymbol{\epsilon=0.001} \boldsymbol{\epsilon=0.0001} Bernoulli 0.001 0.001 0.001 0.001 Burglary 1.6857 1.6857 1.6857 1.6857 ClickGraph 0.375 0.085 0.086 0.086 ClinicalTrial 3.463 0.659 0.657 0.657 Grass 0.695 0.036 0.036 0.036 MurderMistery 0.203 0.203 0.203 0.203 SurveyUnbiased 0.008 0.008 0.008 0.008 TrueSkills 0.003 0.003 0.003 0.003 TwoCoins 0.688 0.688 0.688 0.688 AlterMu 0.312 0.312 0.312 0.312 AlterMu2 0.096 0.096 0.096 0.096 NormalMixtures 0.386 0.386 0.386 0.386 Table 5 : Performance on the programs parameters synthesis varying the value of \epsilon 0.D.2 PID The Proportional Integral Derivative (PID) is described by the following dynamics. \displaystyle d_{k}=\pi-\theta_{k} \displaystyle T_{k}=s_{0}d_{k}+s_{1}\omega_{k}+s_{2}I_{k} \displaystyle I_{k+1}=0.9I_{k}+d_{k}\Delta t \displaystyle\omega_{k+1}=\omega_{k}+\frac{\Delta t}{10}T_{k}+\mathcal{N}(0,\sigma_{\omega}^{2}) \displaystyle\theta_{k+1}=\theta_{k}+\frac{\Delta t}{2}(\omega_{k}+\omega_{k+1})+\mathcal{N}(0,\sigma_{\theta}^{2}) The result of DeGAS optimization is shown in Figure 7 . 0 20 40 0 2 4 Time step PID Figure 7 : PID optimization from ideal trajectories keeping a stable dynamic with \theta=3.14 leads to the red trajectory, starting from the blue one. In green the trajectory obtained by VI. 0.D.3 Hyperparamters Program Optimization In Table 6 , we report the hyperparameters selected through tuning during the experiments on parameter synthesis of probabilistic programs via data likelihood optimization. Model VI MCMC DeGAS LR Steps Samples Warmup R-hat N eff LR Steps Bernoulli 0.05 247 500 50 1.005 802 0.01 248 Burglary 0.05 1000 500 50 1.003 1008 0.005 295 ClickGraph 0.001 1000 500 50 1.018 333 0.2 216 ClinicalTrial 0.2 1000 500 50 1.021 146 0.001 500 Grass 0.01 1000 500 50 1.004 1444 0.1 500 MurderMistery 0.001 1000 500 50 1.001 1036 0.01 239 SurveyUnbiased 0.01 675 500 50 1.001 1382 0.01 500 TrueSkills 0.2 1000 t.o. t.o. t.o. t.o. 0.2 367 TwoCoins 0.05 1000 500 50 1.015 279 0.001 337 AlterMu 0.0005 1000 t.o. t.o. t.o. t.o. 0.05 235 AlterMu2 0.001 1000 1500 50 1.040 81 0.2 228 NormalMixtures 0.0005 1000 500 50 1.018 457 0.01 500 PID 0.05 1000 n.c. n.c. n.c. n.c. 0.2 1000 Table 6 : Tuned hyperparameters (see Section 5 ) used for the synthesis of probabilistic program parameters. 0.D.4 CPS We illustrate the three CPSs considered in our study, showing their mode-dependent dynamics, switching conditions, and key model parameters. Heater ON \frac{dT}{dt}=-kT+h+\mathcal{N}(0,\epsilon) Heater OFF \frac{dT}{dt}=-kT+\mathcal{N}(0,\epsilon) T>t_{off} T0 Controlled bouncing ball. The position of a ball of mass m=7 varies accordingly to \frac{dH}{dt}=v+\mathcal{N}(0,\epsilon) , starting from initial height H_{0}\sim\mathcal{N}(9,1) , with g=9.81 , m=7 . The reachability optimization target is expressed by 1-CDF(H_{i}\geq 7) where H_{i} is the maximum height achieved by the ball after bouncing. 0.D.5 Analysis of reachability properties The target of the optimization in the framework of the reachability properties is computed with respect to the DeGAS semantics. To obtain some qualitative insights on how this relate to the real system and the SOGA semantics, and on how the error may accumulate on long execution traces, we consider the example with largest iterations number, Controlled Bouncing Ball, and plot the mean trajectories computed by DeGAS, SOGA and randomly sampled trajectories from the real system. Figure 8 shows that there is no significant discrepancy induced by the smoothing, even after a large number of iterations. Moreover, despite the error induced by the Gaussian approximation, there is a substantial agreement among the mean trajectories estimated by SOGA and DeGAS and the simulated trajectories. 0 10 20 30 0 5 10 Time step Controlled Bouncing Ball Figure 8 : DeGAS semantics (red) compared to SOGA semantics (blue) and real system (gray trajectories), all considering the optimized parameters obtained by DeGAS optimization of reachability properties 0.D.6 Comparison with SOGA For every program in Table 1 we compared the mean value of a target variable computed in DeGAS and in SOGA for fixed value of the parameters, to asses the error introduced by the smoothing. Our results, reported in Table 7 , show that for the smoothing hyperparameters used in our experimental setting ( \epsilon=1e-3,\delta_{\epsilon}=\sqrt{\epsilon} ) no error is introduced up to third decimal digit. Model Target DeGAS SOGA Parameters Bernoulli y 0.810 0.810 p=0.794 Burglary called 0.237 0.237 pe=0.063;pb=0.132 ClickGraph sim 0.617 0.617 p=0.646 ClinicalTrial ytreated 0.789 0.789 pe=0.054;pc=0.797;pt=0.778 Grass wetGrass 0.666 0.666 pcloudy=0.546;p1=0.705;p2=0.910;p3=0.864 MurderMistery withGun 0.716 0.716 palice=0.138 SurveyUnbiased ansb2 0.713 0.713 bias1=0.778;bias2=0.723 TrueSkills perfC 119.021 119.021 pa=105.990;pb=89.931;pc=119.021 TwoCoins both 0.158 0.158 first=0.367;second=0.367 AlterMu y 4.530 4.530 p1=0.617;p2=0.617;p3=-3.388 AlterMu2 y 3.553 3.553 muy=3.553;vary=2.838 NormalMixtures y -3.192 -3.192 theta=0.718;p1=-4.788;p2=0.627 PID v -0.008 -0.008 s0=46.500;s1=-23.496;s2=-0.495 Table 7 : Comparison among the mean values of a selected target variable computed by DeGAS and SOGA for the programs of Table 1 and fixed values of the parameters.