Rethinking Variational Inference for Probabilistic Programs with Stochastic Support
Authors: Tim Reichelt
Luke Ong
Tom Rainforth
Venue: NeurIPS 2022 Accept (2022)
Keywords: Probabilistic Programming
Variational Inference
Stochastic Support

Abstract: We introduce Support Decomposition Variational Inference (SDVI), a new variational inference (VI) approach for probabilistic programs with stochastic support. Existing approaches to this problem rely on designing a single global variational guide on a variable-by-variable basis, while maintaining the stochastic control flow of the original program. SDVI instead breaks the program down into sub-programs with static support, before automatically building separate sub-guides for each. This decomposition significantly aids in the construction of suitable variational families, enabling, in turn, substantial improvements in inference performance.

Rethinking Variational Inference for Probabilistic Programs with Stochastic Support
Tim Reichelt
Luke Ongl2
Tom Rainforth'
University of Oxford
Nanyang Technological University, Singapore
(tim.reichell lc]ecs. ox.oxxo.ccccoooo.ooeooooooo ac..u. rainforth@stats.c ax.ac.uk ac.uk uk
Abstract
We introduce Support Decomposition Variational Inference (SDVI) a new varia- tional inference (VI) approach for probabilistic programs with stochastic support. Existing approaches this problem rely on designing a single global variational guide on bariable-by-variable basis, while maintaining the stochastic control flow the original program. SDVI instead breaks the program down into sub-programs with static support, before automatically building separate sub-guides for each. This decomposition significantly aids the construction suitable variational families, enabling, in turn, substantial improvements in inference performance.
Introduction
Probabilistic programming systems (PPSs) enable users to express probabilistic models with computer programs and provide tools for inference. Many PPS, such as Stan [1] PyMC3 [2], limit the expressiveness of their language to ensure that the programs in their language always correspond models with static support-i.e. the number of variables and their support do not vary between program executions. In contrast, universal PPSs [3-11] can encode programs where the sequence of variables itself-not just the variable caauuus-hannge between executions, leading models with stochastic support. These models have applications in numerous fields, such as natural language processing [12]. Bayesian Nonparametrics [13], and statistical phylogenetics [14]. wide range of simulator- based models similarly require such stochastic control flow [15-17].
The effectiveness of PPSs is heavily reliant on the underlying inference schemes they support. Variational inference (VI) is one of the most popular such schemes, both in PPSs and more gen- erally [18-20]. This popularity is due its ability to derivatives scale to large datasets and high-ding dinh-niimnsional models [2] 1-24,, often providing much faster and more scalable inferences compared to Monte Carlo approaches [25]. To provide the required derivatives, a number of modern universal
as Pyro [5], ProbTorch [26]. PyProb [15]. Gen [7]. and Turing ha]-have introduced automatic differentiation [27] capabilities for programs with stochastic control flow. One of the core aims behind these developments was to support VI schemes in such settings [5].
However, constructing appropriate variational families, typically known guides in PPSs, can be very challenging for problems with stochastic support, even for expert users. This is because the stochasticity of the control flow induces discontinuities and complex dependency structures that difficult to remain faithful to and design parameterized approximations for. Furthermore, while there are plethora of different automatic guide construction schemes for static support problems [18-20], there is a lack of suitable schemes applicable to models with stochastic support. Consequently, existing methods tend give unreliable results in such settings, we demonstrate in Figure
We argue that a significant factor of this shortfall is that standard practice- for both manual and automated methods-is is to construct the guide
pariable-by-varialee basis [28-31]. Namely,
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Al 10000
def model ():
x sample ("x", Normal (0, 1))
Prohabality of Branch
0.9
if (ample("z1"; Normal (-3, 1))
2
else:
0.5
sample ("22", Normal (3, 1))
BRVI SUVI
Ground Truth
sample ("y", Normal (z, 2), oba=2.0
5000 1010
1500
2000
Number Iterations
Figure 1: Pyro program with stochastic control flow [Left]. Existing procedures for automatically constructing the guide mirror the control flow of the input program [BBVI, Blue]. However, this produces inherently limited variational family, leading unsatisfactory performance despite the problem's simplicity. By breaking down the guide over paths, SDVI [Red] is able to provide accurate inference. Results computed over 102 replications, plotted are mean and standard deviation.
existing approaches generally use a single global guide that mirrors the control flow of the input program, then introduce variational approximation for each unique variable. This is problematic because control flows inherently introduce discontinuities into the program's 's density function, such that the conditional distribution of each variable will typically change significantly whenever the program path-that is the sequence of random variables pariables-changes, Thus it is extremely challenging to learn a single approximation for each variable that appropriate across all paths. Further, as the set of variables that exist can itself be stochastic, it is difficult for such guides to appropriately condition on previously sampled variables. Existing automated approaches, therefore, typically rely on mean-field assumptions [29], thereby forgoing any conditioning on the program path itself, consequently leading to poor approximations for most problems.
To overcome these difficulties, we propose Support Decomposition Variational Inference (SDVI, a new VI approach based around novel way of constructing the variational guide. SDVI "rethinks" the guide construction by breaking it down over paths, instead of building it on buriablebb--vriiile basis. Specifically, by utilizing the fact that any program can be reformulated as mixture of straight- line programs (SLPs) [32-34] each defined by unique realization of the path-SSVV constructs the guide as a mixture of sub-guides with static support. We show that optimizing the variational objective with this guide structure leads to natural decomposition of the overall optimization problem into independent sub-problems, each taking the form of a VI with static support. The sub-guides can thus be effectively constructed and trained using more standard VI techniques, before being recombined to form our overall variational approximation. To make SDVI accessible to a wide audience, we have implemented it in Pyro [5]. We evaluate it on set of example problems with synthetic and real-world data, finding that it provides substantial improvements over existing techniques.
2 Background
2.1 Probabilistic Programs Universal PPSs
PPSs allow users to express probabilistic models and condition on observed data [31, 35]. A common mechanism achieve this is to extend standard programming languages with two new primitives: sample and observe.' I sample (id, dist) draws samples from the distribution object dist, where id unique lexical identifier. observe (id, data, dist) enables conditioning on an observed outcome data, where dist and id are as before. For problems admitting a Bayesian formulation, the sample and observe terms can informally be thought of as prior and likelihood factors respectively.
Universal PPSs allow users to write complex models whose support can vary from one execution to the next, e.g. stochastic branching can mean certain variables only sometimes exist. This can substantially complicate the process of performing inference.
A probabilistic program in a universal PPS defines an unnormalized density function ((#1m,)) over the raw random draws Fiim defdeee as the (sequences of) direct outputs of sample statements where nl E N+ is itself potentially random. Though each outcome of Ti:n, uniquely defines program execution,
notationally convenient to further associate an address o; to each draw J; that indicates the position in the program the draw was made. This address can be uniquely defined as the tuple formed by the id the sample and the number of times that sample has previously been called. For a given execution of the program, the addresses now form an address path A dim..
Pyro instead overloads the sample primitive: sample (id, dist, obs=data) observe (id, data, dist).

---

Each sample statement encountered during execution contributes the factor fa; (T; 17) to the program density, where a, is the address of the sample statement, fa, a parameterized density function, and f) are its associated parameters. Similarly, each encountered observe statement contributes the factor Gb, (yj Φ5), with by denoting an address, 1/j the observed value, Ib parameterized density function, and @j its parameters. Following [36, $4.3.2), we write the program density function as
fas (z, mi) IT,", by 9b, (vy 0j).
(TI:ng)
(I)
All of Fuy Byy "1:n. Mine Vinny bi:,, > and $1,n, are potentially random variables. The goal of inference is to approximate the conditional distribution of the program, which has normalized density T (T1m) (z1mm) )/2 with marginal likelihood Z Sx 7(Z1.,, )drin. and the integral is computed with respect to reference measure that is implicitly defined by the sample statements in the program.
2.2 Variational Inference
Variational Inference (VI) [18, 37] solves the inference problem by transforming it to an optimization
problem. Specifically, given unnormalized joint distribution 7(x) and parameterized distribution q(x; o). VI computes the variational parameters & such that g(2; Φ) most closely approximates Txx) /z)) This is most commonly done by maximizing the Evidence Lower Bound (ELBO) ( := (2(0) (=))((<==))) via stochastic gradient ascent using Monte Carlo estimates of
Val(o) [38]. Two popular estimators are the score function estimator [39, 40], and the reparameter- ized gradient estimator [24, 41, 42]. The latter provides lower variance gradient estimates but requires that the distribution qx:; 6) can be reparameterized and that y(x) is differentiable everywhere.
3 Difficulties for Variational Inference in Universal PPSs
The starting point for any VI scheme is to construct an appropriate variational family, also known as a guide. To automate inference, desire (at least partially) automate the process of constructing this guide. Existing methods for this all generate the guide on a variable-by pariable-by-varihhee by-viiaaell basis [28, 29, 31]: they introduce single variational distribution qa, (I;; da.) for each unique sampling address a, then form the guide by replacing all the original random draws, IG ~ fa. ( m)), with draws from the corresponding variational distribution instead. This forms a global guide that maintains the stochastic dependency structure of the original program, such that the guide itself has stochastic support.
Our motivating insight is that this high-level approach has some fundamental limitations. Consider the simple example from Fig. 1. Here the variable x influences the program's 's control flow. This causes discontinuities that mean it is difficult approximate its conditional density with a single variational approximation, especially if that variational approximation is restricted to a simple distribution class. Here the different possible paths essentially working against each other, what is helpful for the approximation of x on one path, is generally detrimental for the other.
A further complication occurs when the stochastic control flow of a program influences whether a variable exists at all. Here it can become extremely challenging to set up guides which are faithful to the dependency structure of previously sampled variables [43], as the set of variables we condition on itself stochastic. Because of this, existing approaches typically rely on mean-field assumptions across paths 388- However, this assumption is rarely reasonable given that the path typically strongly influences the distribution of individual variables.
Finally, creating single unique variational approximation for each address also leads to challenging optimization problems: the same address can be present in multiple program paths, and the number of variables and their dependencies can vary between different paths.
4 Support Decomposition Variational Inference
We now introduce a novel VI approach to overcome the challenges mentioned in Sec. 3. We call our method Suppor! Decomposition Variational Inference (SDVI), because the key design decision the choice (and automatic construction) of guide that takes the form of a mixture distribution over the set of possible paths a program can take. That is, rather than constructing a single guide with the same stochastic control flow as the original program and separate variational approximation for
3

---

each unique address, we instead construct separate sub-guides with deterministic control flows for each unique path. These are then combined into an overall guide using the mixture distribution which maximizes the overall ELBO. As we will see, this alternative approach substantially simplifies the process of constructing effective guides and allows the full weight of the well-developed techniques for VT in the static support setting to be brought to bear on problems with stochastic support.
4.1 Decomposing Probabilistic Programs into Straight-Line Programs
As noted by, e.g., [32-34], all probabilistic programs can be reformulated as mixture distributions over straight-line programs (SLPs), which are sub-programs without any stochastic control flow. Building on earlier notation, the constituent SLPs of program correspond directly to the unique instances of the program path, A. Given the path, the set of variables making up the raw random draws in the program is fixed, along with their form and reference distribution; that is each SL.P represents a probabilistic model with fixed variable typing and support.
apply arbitrary fixed ordering the set of SLPs in a program, such that we can uniquely define and index them using the set of possible addresses Aş for k K,, where K is countable (but potentially infinite) indexing set. Each SLP As now corresponds to a particular sub-region, Xg. of the raw random draw sample space, X. These sub-regions disjoint and their union is the full sample space. Unlike X, each element in any given Xx has the same length 7i and is measurable with respect to the same reference measure. The unnormalized density for the kth SLP is now given by
Following the notation of Zhou et al. [34],
( = I[Ii:n E 2x ((1mm))))) = [rim, E Ex I SAuMq( m:)
ny I[,",, 96, (vy Φg), (2)
and the unnormalized density function for the original program can be written as a simple sum the individual SLP densities: ((1m..) Exex (=im))) The corresponding normalized conditional density can then be written as mixture distribution over the conditional distributions of the individual SLPs, with mixture weights given by their (normalized) local partition functions:
[x(
Zu
S (x)ddx (3)
(xx) = Σ π( k)) (Tk) where T( k)
I(k)
Zz =
Zz
BEK
Zi
xx.
kEAC
4.2 Decomposing the Variational Family into Straight-Line Programs
The key idea behind SDVI is now to construct the guide using factorization that is analogous to that of the SLP decomposition above. Precisely, we aim to learn variational approximations the form
(x Σx_ (x( (x)q(k; A)
(4)
where (k;; A) defines a categorical distribution over the indices of the SLPs, with support k K); and (2; Φx) is the local guide of the kth SLP, with support E Xx. Critically, as each N3 represents fixed support, the local variational families q can be automatically constructed using standard techniques for static problems, as we discuss in Sec. 4.5. Note that it is valid for the guide q(x; o, A) to not cover all SLPs, i.e. it is possible that K < |/]]
Writing o = { 1- the KI. divergence we wish to minimize for standard VI is now
(L((g<;; db A) (x)) Eg(3)))))) [log g(2;; o. A) log (x)),
(5)
which we call the global KL divergence. By standard reasoning, minimizing this is equivalent to maximizing the globul ELBO
C( A) A)) [log y(x) log (1;;,,))))
(6)
which, as we show in App. A, can be rewritten as
L(o, A) = (y(e))) (Ox( - log (k:; A)], where Ca(dx) == (arob)) log The (x(
Uh (2;; sh.)
the term we refer as the local ELBO for the kth SLP. Notice that each (x(ck) depends only on the parameter Φv and the local SLP density Yh it is completely independent of q(k: A), the other SLPs, and der for k' a k. Thus, it follows from (7) that the inference problem for the whole program can be decomposed into independent 'local" inference problems for the component SIPs, along with establishing the mixture probabilities (k;; A). Furthermore, turns out that the optimal q(k; A) simply the softmax of Li,..., LK, k, as shown by the following result.

---

Algorithm Support Decomposition Variational Inference
Require: Target program y, iteration budget T, minimum no, of SH candidates m
1: Extract SLPs | from y and set C = (1,...,K)
Sec 4.3 - Sec 4.5
2: Formulate guide for each SLP and initialize parameters Ob
3: for (orl= ........ L [log2(E5 (mg)(m) 1| do
4: for E C do
5:
Perform [T/4/||] optimization iterations of Φe targeting Leurr,(((xx) 6: end for
t Sec 4.5
7: Remove min([]C|/2) [C] m) SLPs from C with the lowest (x()))
t Sec. 4.4
8: end for
9: Truncate qi outside SLP support, Xs, using Eq. (13)
10: Estimate each (d(d)) using Monte Carlo estimate of Eq. (7)
11: Calculate (k:; X) according to Eq. (8) and return g(>; Φ, X) as per Eq. (4)
Proposition 1. Let == (L L be the set of local ELBOs, defined as per (7), where L is countable but potentially not finite. If 0 Σk_ exp(f.t) < cc, then the optimal corresponding q(k; X) terms of the global ELBO (6) is given by
<(k; A) exp(Lx) Ex, exp(Cx).
(8)
The proof of this result is given in App. A. Though each of the L. terms here is itself intractable, they can be estimated efficiently and accurately by simple Monte Carlo. We can thus straightforwardly construct q(:: f; X) once we have learned our local variational approximations: noting that these two processes are separable, (k;; A) is not needed until after the individual qs are trained.
4.3 Finding SLPs
We have just shown how we can solve the VI problem of a probabilistic program with stochastic support by reducing it to a of independent and simpler VI problems, each concerning an SLP, program with static support. However, we still need a mechanism to 'discover' the SLPs, i.e. extract the possible address paths from program.
Here we first note that we only need to consider an SLP if it has a non-zero probability of being identified under forward simulation of the program, while ignoring conditioning statements. This hints at cheap and simple discovery mechanism whereby we draw samples by forward simulation and take note of the unique paths that have been generated. We can either do this upfront, or in an online manner whereby we seek new SLPs as our budget increases and we have scope to deal with them (see App. B for details). Although this is a stochastic process that is not guaranteed find all the SLPs for finite budgets. for the problems considered in our experiments, it was always able to reliably identify all SLPs with non-negligible posterior mass. Nonetheless, this approach may not be sufficient for all problems, such as when the likelihood concentrates in an area of very low prior mass. Here one should instead look to employ more sophisticated discovery methods instead, such as those based on MCMC sampling [34] or static analysis of the program code [32, 44, 45).
4.4 Allocating Resources
Using the same amount of computational budget each SLP is potentially wasteful, particularly if there is a large number of SLPs with insignificant marginal likelihoods. Therefore, we seek scheme that allocates the different inference problems are trivially parallelizable.
computational resources to promising SLPs, making sure exploit the fact that
To formalize this resource allocation problem, let T represent some fixed resource budget. Further, let l the amount of this budget we spend on optimizing the kth SLP, such that Σ, 44 T at the end of our training. Our ultimate aim is produce the maximum possible final global ELBO, which will be a function of Φ (t1). ..... Φx (tx). ), where (tx) denotes the value óR achieved after allocating &x resources that SLP. By plugging the optimal mixture distribution q(k; A) from (8) into (6), that, after some rearranging, our resource allocation can be formulated as trying to maximize
K
K
L(o. X*) log 2 exp(Lx(óx(ta)) s.t.
k= to T.
(9)
5

---

In practice, this is not suitable objective for controlling our resource allocation directly, as it is still itself a random variable given .t....,to ., because the optimization procedure is stochastic. Moreover, we cannot consider its expectation, since the distribution of the d2 (4x) is unknown. However, it does provide insight into how we ideally would like to allocate resources: we want to allocate more resources to SLPs whose exponentiated ELBOs are significant. In particular, we can think of the 'reward' for allocating more resources to SLP & as exp( (ox (t4 + +))) - exp (or (ox((t))) (fx))).
One could now, in principle, formulate the problem as a sequential decision making problem [46]. However, the diminishing nature of the rewards and the fact that they are highly unlikely to be nau-Gaussinn, along with the need to allow choosing multiple arms at once for parallelization, mean that setting up such an approach which is effective practice likely to be quite challenging.
Instead, we propose a simple heuristic, based on the Successive Halving algorithm (SH) [47] (see App. B for description), an approach commonly used for resource allocation in hyperparameter optimization (HO) [48, 49). In standard SH, the final objective is to identify and train the single best candidate, whereas ours maximize the sum of all the local ELBOs. Despite this difference, the use of SH can still be justified by the fact that the distribution over exp be heavily concentrated small adaptation to the approach to stop over-focusing on a single SLP: we stop the halving process when a chosen number, 1 < m E K, of the candidates are left, with m 1 corresponding to standard SH. The minimum proportion of the budget allocated to any given candidate by this scheme [K[[loog K- log, m m+ I]), so we can use m as a hyperparameter to control how evenly resources are allocated, with m K corresponding to uniform allocation. This approach is also helpful for parallelization, as we can set m equal to the number of available cores.
will typically small number of SLPs, often only single one. Nonetheless, we make
Putting everything together, summary of our SDVI algorithm is given in Algo. 1. In App. B, we further show how this can be extended an online variant of the approach, wherein we repeatedly run SH using the objective exp(aLx. (óx (f4) where 0 < a & 1 is hyperparameter, with smaller values of a encouraging more exploration.
4.5 Formulating and Training the Local Guides
In Algo. 1 we assume a mechanism to construct the local guide 9k Φk) for each SLP specified by path Ag- In many ciuuations-nttbbll when the program path is uniquely determined by the sampled values from discrete distributions-ir is possible to construct guides qk that are guaranteed to place support within the sub-region Xr. which, in turn, allows to use the reparameterized gradient estimator for the gradients of ((x)). Many models encountered in practice, e.g. mixture models [13], have this property. In this case it is possible eliminate all the variables which influence the control flow by conditioning, effectively setting them to constants; see App. C for further details.
In situations where we cannot casily construct qu which places support only within Xx. need to take care when training our guide. Recall that for path Aş the number of variables ng and their type sequence is fixed, which allows us to construct an initial guide qr with correct dimensionality and variable typing. Let the support of this guide be denoted by X% = supp(āx). In general, we will have Xx. < X² because the control flow in the program imposes additional constraints each individual variable. Having constructed a guide with supp(ăx) = X/- one might be tempted to optimize KL(@x (Ir; (x) || <(x; k)), but we cannot guarantee the absolute continuity condition (i.e. (x(x;; Φh)) = 0 if (( k) = 0), and so, the KL divergence may not be well-defined, giving an ELBO of -c0. To alleviate this issue we temporarily create a new surrogate target density defined as
)e(())) = The (Z1:,,)) + cIIar. $ Xx],
(10)
for a small positive, finite constant c. This surrogate density is used solely for optimizing qu Φx). We train d; to optimize the corresponding surrogate ELBO
Laur (ox) := (. [log (x) - log dh (2; (h)]
(11)
We need be careful to choose an appropriate e that is sufficiently small compared to the values of (x<(x) for z E Xx., which we ensure by setting c adaptively. During the SLP discovery phase (Line I in Algo. 1), we keep track of the smallest density value encountered so far, and call that dman We then set 0.01dmin to ensure that the density values for (x(x)) outside of X are significantly below the values of 7x (x) for I E Xz. Hence, optimizing (11) faithfully optimizes qe to be a good approximation to (x) while avoiding the issues of infinite ELBO values. While 5/ is not proper

---

unnormalized density (it will in general not integrate to a finite value) this is not an issue in practice due to the mode-seeking behaviour of optimizing the ELBO.
Unfortunately, the bounds on the support of the SI.P inevitably create a discontinuity in the objective. Thus, for fully unbiased gradients we need to the score function estimator some extension thereof. However, in some cases, the bias of the reparameterization gradient estimator may be sufficiently small to warrant its use. Note that ( retains the desirable property of the standard ELBO that, if the observations are conditionally independent given the latent variables, we can get unbiased estimates of the ELBO using minibatches of the full dataset [19, 22, 42].
Further we need to be careful when initializing 9k as we require it to place sufficient probability mass within Xx to provide suitable training signal. To ensure this, we initialize @v by minimizing the forward KI. divergence between the prior density of the kth SI.P and ÿk (be)
(Tpriioe &e (1) 1| (x; )x)) ) Oc (xp)) |-1[x E X& log (u( 0u)]
(12)
where Tprior (T ) = I Sa: (arg m.). This objective can be optimized via stochastic gradient descent (cf. App. C). Note that, for the purpose of initialization, are targeting the prior, and thus we do not have to resort to expensive schemes to estimate the gradients which are necessary if one aims to minimize the forward KL targeting the posterior [50].
So far we have outlined how to train Åk but to evaluate the local ELBOs, Cs, we need to construct a distribution gı: which satisfies the hard constraint supp(g*) = Az.- Our solution for this is truncating @s: by checking whether specific raw random draws 1in,, are valid for the path Ag, i.e. whether II [=1_.. E J. We can do this by simply executing the program with fixed draws set to xi.m. and then noting that the program terminates and follows the address path As if, and only if, x'mne E Xr. Thus, we truncate ÿk using
Th (x; Φx) = (x: 2x @x) Nil
where Zn(du) = [ Th. lx) I E Nul dæ. x%
(13)
Hence, d% is implicitly defined as the output of a rejection sampler with q proposal. Note, that as we use the surrogate ELBO in (1I) when training &x. we never need to take gradients through ga or Zz (ox), thereby avoiding the significant practical issues this would cause (see App. G). Thus, the local guide 9r (Eq. (13)) is only used for estimating the local ELBOs (Eq. (7)). This is done by first drawing N samples (,,()),,,, from Ōr. then rejecting samples which do not fall into the SL.P and estimate Z as the acceptance rate of this sampler (i.e. Na/N where NA is the number of samples accepted). Using A to denote the set of indices of accepted samples, we form our ELBO estimate as
]==1
Σ
AEA log(NA (x)) - log( N au (xx) (x)).
(14)
NA
Note here that A and NA A are random variables that both implicitly depend on @x. which is why we can use this for estimation, but not training.
5 Related Work
The vast majority of prior work on deriving automated VI algorithms focuses on the setting of static support [20, 23, 51-55). Of particular note, [43, 56, 57] also consider using variational families that do not match the dependency structure of the original problem, but they still require static support. More generally, there have been models with stochastic support for which bespoke guides where developed which do not follow the control-flow structure of the input program [58]. However, these custom guides do not leverage the breakdown of the input program into SLPs.
The Divide-Conquert Conquer--ombiinie (DCC) algorithm [34] also exploits the breakdown of the program density into individual SLPs. However, [34] mainly focused on local inference algorithms that are sampling based, especially MCMC. As we showed in Sec. 4 unique challenges and opportunities arise when we consider the breakdown from a variational perspective. Further, our work shows that using a variational family based on SLPs naturally leads to sovide-and-conquee style algorithm, due to the resulting separability of the ELBO. One of the most practical differences is that SDVI only requires (exponentiated) ELSOs to be estimated for each SI.P, rather than marginal likelihoods. The former can typically be estimated substantially more accurately for given budget, allowing SDVI to
7

---

Squaedd Eevor
10-7
BLBO
DDVI
-20-
2
10
10a
10
10
10
10
Computational Cost
Compatatioonl Crst
(a) Squared error.
(b) ELBOs.
Figure 2: Results for the model in & 6.1. Computational cost is measured in the number likelihood evaluations. For each metric show the mean and standard deviation over 10 runs. a) Squared error between the true SLP weights and the estimated SLP weights. b) Evidence Lower Bounds (ELBOs) for the variational algorithms, dashed line indicates the analytic log marginal likelihood.
scale better to high dimensional problems (see Sec. 6.2). [32] and [33] both also the general idea of breaking down programs into SLPs, but both papers consider starkly different problem settings. Neither have any direct link variational inference.
Our work is situated in the larger context of automated inference for universal PPSs. Other popular approaches include particle-based methods [6, 11, 59-61996 and MCMC approaches with automated proposals [1, 62-64]. Some work has looked to perform amortized inference over a range of possible datasets [16, 56, 57, 65], often by training proposal that is similar to variational approximation.
Experiments
To make SDVI easily accessible practitioners have implemented it in Pyro with code available at github. cow wommtreigerm//eteeeeemmeeeeeeeee swwrreiire//svi........ ssvi/vviiiia httpi///dddiiiiiipsdeeeeee The first baseline we consider, Pyro AutoGuide, uses the butcoNormalMesseegerr class to automatically generate guide, and trains with Pyro's built-in tools for VI (http://pyzo //pyro..././//// ai/ //ee/pllm/sssiiiiieeeeeeeeeeeeee srs_/svi_pprriiiieee html). As an additional VI baseline, we also implement custom guide for each model which uses the variable-by- cariable-by-varisn by-variable scheme outlined in Sec. 3, in combination with the score function gradient estimator; we refer to this baseline as BBVI. For SDVI, we run SH until there are 10 active SLPs left (i.e. m 10 in Algo. 1) and parallelize the computation across 10 cores. We further construct each local guide distribution as a mean-field normal. The specific configurations for each method for each experiment are provided App. D.
6.1 Program with Normal Distributions
We use our first experiment further clarify the failure modes of existing VI approaches, We consider an extension of the model from Fig. to contain more SLPs. The full model
5², N(z, 1), ((x
0, if E (-00,-4
where
z
K, u (-5+ K, K,-4+ K] for I....,8 (15)
9, if (4, 00)
We assume have observed y 2. The results in Fig. demonstrate that SDVI is able overcome the limitations of the other variational approaches. BBVI and Pyro AutoGuide both use the same guide in this model; BBVI uses the score function gradient estimator for training, whereas Pyro AutoGuide uses the reparamcterized gradient estimator. This difference results in different posterior approximations for the different baselines. The BBVI guide tends to place all its mass on a single SLP and then provides suitable approximation for only that one SLP, ignoring all the others. This explains the large standard deviations for the ELBO values in Fig. 2b as the ELBOs in different SLPs will converge to drastically different values. For Pyro AutoGuide the biased gradient estimates will train variational approximation for variable to close to the prior (0, 52). SDVI is able to avoid the shortcomings of the baselines as it provides an overall better posterior approximation leading to larger ELBO values, i.e. lower KI. divergences to the true posterior, and more accurate weighting of the different SLPs (Fig. 2a).

---

Table 1: Log posterior predictive densitiy (LPPD), ELBO, and maximum a posteriori (MAP) estimate for K for GMM model. Mean and standard deviation for LPPD and ELBO computed over 5 runs.
Method
LPPD (1, x x10²)
ELBO (1, x x00)
MAP K
DCC
-9842.90 + 3904.57
N/A
14, 11, 16, 14, 15 25, 25, 25, 25, 25 5,5, 6,
BBVI
-2217.07 + 146.31
-8700.55 544.95
SDVI
32.84 + 0.02
128.76 1 0.17
S-SDVI
32.80 0.02
128.63 i 0.22
6, 5,
6.2 Infinite Gaussian Mixture Model
Our next model is Gaussian Mixture Model (GMM) with Poisson prior the number of clusters:
1 K K Σ
K ~ Poisson(9) + 1; ug NN(0, 101) for k == l. K;
, 0.1
where I is the D D identity matrix and 0 is D dimensional vector of zeros (we set D 100). A similar model was considered in Zhou et al. [34] but with = 1 instead of D = 100. We generate a dataset of 1250 observations with K 5. To compare and evaluate the different algorithms, we hold out 250 data points as a test dataset to compute the log posterior predictive density (LPPD)..
The Pyro AutoGuide baseline from the previous experiment is not applicable here since it assumes all latent variables are continuous. In BBVI, for practical reasons, we had to cap the maximum number of clusters in the guide 25 (cf. App. D). To provide a further baseline, have also implemented DCC [34] in Pyro with Random-wand maak lightweight Metropolis-Hastinne algorithm. We chose DCC in particular because it also exploits the same breakdown into SLPs, so comparing against DCC is an opportunity to highlight the benefits of using a VI method.
(RMH) [63] as local inference
In this model, the observations are assumed to be conditionally independent given the latent variables, thus enabling SDVI to work on subsets of the whole dataset [19, 22]. Specifically, we run SDVI on a model which samples a random minibatch of size B 100 at each iteration and then scales the likelihood by the factor N/B, where N 1000 the size of the full dataset; we refer to this setup as Stochastic SDVI (S-SDVI). Furthermore, for this model SDVI is able directly construct valid local guides qu (using the mechanism for models branching on discrete variables outlined Sec. 4.5) and therefore SDVS can use the reparameterized gradient estimator.
Table shows that SDVI and S-SDVI significantly outperform the baselines, yielding several orders of magnitude larger posterior predictive density and providing the only reasonable predictions for the numbers of clusters. the few instances were (S-)SDVI returns suboptimal MAP estimate of K 6. this was because the local guide for the SI.P with 5 components had fallen into a local model that fails to correctly identify all the clusters the data, turn returning a suboptimal local ELBO. BBVI and DCC struggle with this model due to the high-dimensional parameter space. DCC's local inference algorithm, RMH, only updates one variable at a time which results in slow mixing times. Note, DCC does not provide any ELBO values; its marginal likelihood estimator PI-MAIS [66] constructs an importance sampling (IS) proposal distribution based on the outputs of MCMC chains which could theoretically be used to estimate ELBO value. However, IS requires over-dispersed proposals, the ELBO scores for this approach are trivially - 0C, preventing a sensible comparison.
6.3 Inferring Gaussian Process Kernels
Observed Data
For our final experiment, we consider the prob- lem of inferring the kernel structure of Gaus- sian Process (GP). Following [67, 68], we place a prior over kernel functions using probabilis- tic context-free grammar (PCFG). We consider the squared exponential (SE), rational quadratic (RQ), periodic (PER), and linear (LIN) base ker- nels, and use the production rules
Nunber of Pazeenges
Hell--Out Data
Mouth
SE| RQ| PER LIN
K. K. +
Figure 3: Posterior predictions of the GP for SDVI, shaded regions indicate standard deviations that are computed from 100 posterior samples.
Sampling from the PCFG implemented with recursive probabilistic program that uses sam-

---

ples from a categorical distribution to decide which production rule in the PCFG should be applied. In addition to the kernel structure, we also perform inference over the kemel hyperparameters for each base kernel and the observation noise; we place an aiverseggamm prior on each base kernel hyperparameter and a half-normal prior on the observation noise. We further assume a normal likelihood function and marginalize out the latent GP. Additional model details are in App. D. We apply this model to a dataset of monthly counts of international airline passengers [69], withholding the last 10 % of all observations as test dataset.
For SDVI we can construet local valid proposals Ql using the mechanism for models with dis- crete branching outlined in Sec 4.5. Hence, in each SLP the local guide qs provides posterior approximation over the kernel hyperparameters and the observation noise; the posterior distribu- tion over kernel structures is implicitly defined through the mixture distribution over program paths. Table shows that SDVI provides higher LPPD values, and is also able to achieve higher final ELBO value compared to BBVI, Fig. 3 shows the posterior predictions for the SDVI run with the median LPPD score. SDVI is able to provide qualitatively reasonable predictions, the predictions follow the periodic trend in the observed data.
Table 2: Final log posterior predictive densitiy (LPPD) and ELBO for GP model. Shown are mean and standard deviation computed over 5 runs.
Method
LPPD (1)
ELBO (1)
DCC
58.92 + 32.47
N/A
BBVI
-18.82 + 1.20
-48 -88.88 + 0.33
SDVI
2.05 3.30
34.53 21.42
7 Discussion
We believe that SDVI provides number of significant contributions towards the goal of effective (automated) inference for probabilistic programs with stochastic support, nonetheless it still naturally has some limitations. Perhaps the most obvious is that it. if there is a very large number of SLPs that cannot be easily discounted from having significant posterior mass, it can be challenging to learn effective variational approximations for all of them, such that SDVI is likely perform poorly if the number becomes too large. Here, customized conventional VI or reversible jump MCMC approaches might be preferable, as they be set up to focus on the transitions between SLPs, rather than trying to carefully characterize individual SLPs.
Another limitation is that our current focus automation means that there are still open questions about how best to construct more customized guides within the SDVI framework. Here the breakdown into individual SLPs and use of resource allocation strategies will still often be useful, but changes to our implementation would be required to allow more user control and customization. For example, the discovery of individual SLPs using the prior is a potential current failure mode, and it would be useful to support the use of more sophisticated program analysis techniques (c.g. [45]).
A more subtle limitation is that the local inferences of each SLP can sometimes still be quite challenging themselves. If the true posterior places a lot of mass near the boundaries of the SLP, there can still be a significant posterior discontinuity, meaning we might need advanced local variational families (e.g. normalizing flows) and/or gradient estimators. Such problems also occur in static support settings and are usually much more manageable than the original stochastic support problem, but further work is needed to fully automate dealing with them.
Finally, variational methods are often used not only for inference, but as a basis for model learning as well. In principle, SDVI could also be used in such settings, but as described in App. F, there are still some hurdles that need to be overcome to do this in practice.
8 Conclusion
We have presented SDVI and shown that it is able to overcome the limitations of existing VI approaches for programs with stochastic support by using a novel guide structure that breaks the program down into SLPs with fixed support, rather than matching the original stochastic control flow. The structure of the variational family separates the ELBO into multiple independent inference problems which naturally motivates a resource allocation. Experimentally we found that these innovations meant that SDVI was able to provide significant performance improvements over the previous state-of-the-an approaches.
style training procedure with explicit
10

---

Acknowledgments and Disclosure of Funding
We would like thank Yuan Zhou for useful discussions in the early stages of this project. Tim Reichelt is supported by the UK EPSRC CDT in Autonomous Intelligent Machines and Systems with the grant EP/S024050/L. Luke Ong would like acknowledge funding from EPSRC UK and National Research Foundation Singapore NRF-RSS2022-009.
References
[1] Bob Carpenter, Andrew Gelman, Matthew D. Hoffman, Daniel Lee, Ben Goodrich, Michael Betancourt, Marcus Brubaker, Jiqiang Guo, Peter Li, and Allen Riddell. Stan: A Probabilistic Programming Language. Journal of Statistical Software, 76:1-32, January 2017. ISSN 1548- 10w.o/863777/0 v076. 101.
7660. doi: 10. 18887//....076..000 URL https://doi.or
[2] John Salvatier, Thomas V. Wiecki, and Christopher Fonnesbeck. Probabilistic programming in Python using PyMC3. PeerJ Computer Science, 2:e55, April 2016. ISSN 2376-5992, doi: 10.7717/peerj-cs.555. URL htwp:://t////e /perr/eerrjje wommartiilees/eeeeoooooocooceeee cs-55
[3] David Tolpin, Jan- Willem van de Meent, Hongseok Yang, and Frank Wood. Design and Implementation of Probabilistic Programming Language Anglican. In Proceedings of the 28th Symposium on the Implementation and Application of Functional Praaenaalllrgrreere Programming Languages IFL 2016, pages 1-12, Leuven, Belgium, 2016. ACM Press. ISBN 978-1-4003--7667-99 doi: 10. 1145/ 8064899.3064910. URL http: //tp://ll..// acm.
acm. weeea.ogg//iii org/citation.....mo wwwpddddddd0042399939 300-449999999490000000 3064910.
[4] Noah D. Goodman, Vikash K. Mansinghka, Daniel Roy, Keith Bonawitz, and Joshua B. Tenen- baum. Church: A language for generative models. In Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence, UAI'08, pages 220-229, Arlington, Vir- ginia, USA, July 2008. AUAI Press. ISBN 978-0 778-0-9749039-41.
[5] Eli Bingham, Jonathan P. Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul Szerlip, Paul Horsfall, and Noah D. Goodman. Pyro: Deep Universal Probabilistic Programming. Journal of Machine Learning Research, 20(28):1-6,
2019. ISSN 1533-7928. URL batt:://jmml. orggo//go.....ooo www.oorgg/eeeeeeeeeeee halpppps//vaa/ seneers/v2//15 100///8143 403.000... html.
[6] Hong Ge, Kai Xu, and Zoubin Ghahramani. Turing: A Language for Flexible Probabilistic Inference. In International Conference on Artificial Intelligence and Statistics, pages 1682-1690. PMLR, March 2018. URL http: http://poooeeeenn////ee/ mlr. ppwps/v84// /ansss//84//1BBB gebb.. html.
[7] Marco F. - Gen: A general-purpose probabilistic programming system with programmable inference. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PI.DI 2019, pages 221-236, New York, NY, USA, June 2019. Association doi: 10.1145/331422 .33116422 URL
Feras A. Saad, Alexander K. Lew, and Vikash K. Mansinghka.
for Computing Machinery. ISBN 978-1-4503-67122
https: http://do...gggoe 1111/111411111 3314642.
[8] Vikash Mansinghka, Daniel Selsam, and Yura Perov. Venture: A higher-order probabilistic programming platform with programmable inference. arXiv:1404.000 0099 [cs, stat], March 2014.
URL /ttp://///axv//a/a barg//bs//444/ hatps//144.000000
[9] Praveen Narayanan, Jacques Carette, Wren Romano, Chung-chich Shan, and Robert Zinkov. Probabilistic Inference by Program Transformation in Hakaru (System Description). In Oleg Kiselyov and Andy King, editors, Functional and Logic Programming, volume 9613, pages 62-79. Springer International Publishing, Cham, 2016. ISBN 778-3-319-29603-2 978-3- 319-29604-3, doi:
URL http:////l springer com/10.
[10] Noah D Goodman and Andreas Stuhlmüller. WebPPL- probabilistie programming for the web, 2014. URL http:://// http::/wwwbppppeee org/.
[11] Lawrence M. Murray and Thomas B. Schön. Automated learning with a probabilistic program- ming language: Birch. Annual Reviews in Control, 46:29-43, 2018. ISSN 1367-5788. doi:
URL URI wwtptttt///ettt..tt.eeeeeeeeetet /www sciencedirect. com/

---

[12] Christopher Manning and Hinrich Schütze. Foundations of Statistical Natural Language Processing. MIT Press, Cambridge, MA, USA, May 1999. ISBN 978-0-262-13360-9,
[13] Sylvia. Richardson and Peter J. Green. On Bayesian Analysis of Mixtures with Unknown Number of Components (with discussion). Journal of the Royal Statistical Sociery: Series B (Sta- ristical Methodooogyy, 5944)7311 1997. ISSN 1467-9868. doi: 10.11 10.1111/4467988680000 00095. URL httpps://onlimllirreeee wiley hamm/dii/aba/l/n wta.a//.....1/111111....1
1111/1467 1111//116779888... 086888009990
[14] Fredrik Ronquist, Jan Kudlicka, Viktor Senderov, Johannes Borgström, Nicolas Lartillot, Daniel Lundén, Lawrence Murray, Thomas B. Schön, and David Broman. Universal prob- abilistic programming offers powerful approach to statistical phylogenetics. bioRriv, page 2020.06. 66. 16.14444.. December 2020. doi: 10.1 1..11000/200....11 15.144 URL https: //www.biorzetee org/ content/10.... 1111/1111000.1 06. 16. 154443v4.
[15] Atilim Güneş Baydin, Lei Shao, Wahid Bhimji. Lukas Heinrich, Lawrence Meadows, Jialin Liu, Andreas Munk, Saeid Naderiparizi, Bradley Gram-Hansed Gilles Louppe, Mingfei Ma, Xiaohui Zhao, Philip Torr, Victor Lee, Kyle Cranmer, Prabhat, and Frank Wood. Etalumis: Bringing probabilistic programming to scientific simulators at scale. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC '19, pages 1-24, New York, NY, USA, November 2019. Association for Computing Machinery. ISBN 978-1 11811-4003-6229-00 3295500 3356180.
doi: 10.1 744114455550003356611 URL https: //doi. org/10...... 1.10.115.. 1145/
[16] Tuan Anh Le, Atilim Gunes Baydin, and Frank Wood. Inference Compilation and Universal Probabilistic Programming, In Artificial Intelligence and Statistics, pages 1338-1348, PMLR, April 2017. URL http::/prooceediggss mmlr www.mml....resseee press/v54/le17a... html.
[17] Bradley Gram-Hansen, Christian Schröder de Witt, Tom Rainforth, Philip H. S. Torr, Yee Whye Teh, and Atilim Güneş Baydin. Hijacking Malaria Simulators with Probabilistic Programming. arXiv: 1OXXv:1905.130 12432 [cs, stat], May 2019. URL http://arxiv.oo org/ www.:/sgg//////a/eeee/.o 1905 12432.
[18] David M. Blei, Alp Kucukelbir, and Jon D. McAuliffe. Variational Inference: A Review for Statisticians. Journal of the American Statistical Association, July 2017. ISSN 0162-1459. URL /tattps://wwrrr tandf ine. ctw/coo////ccccccccccccoooccooot http///llll//./1//// 11t0//1.110000001110011100011100
2017. 201.599..77....7777.
[19] Alp Kucukelbir, Rajesh Ranganath, Andrew Gelman, and David M. Blei. Automatic Variational Inference in Stan. arXiv:1506.0344 03431 [stat]. June 2015. URL attp:://axxet org/ htrg/abs/1506
03431.
[20] Abhinav Agrawal, Daniel R Sheldon, and Justin Domke. Advances in black-box VI: Normaliz- ing flows, importance weighting, and optimization. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, vol- ume 33, pages 77358-17366 Curran Associates, Inc., 2020. URL https:tt///pooceediiig http:////........44.444.000222.0
heurips.cc/papeere
pdf.
[21] Cheng Zhang, Judith Bütepage, Hedvig Kjellström, and Stephan Mandt. Advances in variational inference. IEEE transactions on pattern analysis and machine intelligence, 41(8):2008-2026, 2018.
[22] Matthew D Hoffman, David M. Blei, Chong Wang, and John Paisley. Stochastic Variational Inference. Journal of Machine Learning Research, 14(5), May 2013.
[23] Danilo Rezende and Shakir Mohamed. Variational Inference with Normalizing Flows. In Proceedings of the 32nd International Conference Machine Learning, pages 1530-1538. PMLR, June 2015. URL https::///// http://oooceeeeeeeeeeee/eee marpeaddiiiimmm.......mmmm.mmr.e wtw.mmll......//e.m wwwpppers//1///. prees/v33/reezedde w html.
[24] Diederik Kingma and Max Welling, Auto-Engoding Variational Bayes. arXiv:1312.611 [cs. stat], May 2014. URL http:://rxxxi owg.aos//////ooooooooooooooee. hts/////////// 1at.a//////ae... 11811.66114..
[25] Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Handbook of Markov Chain Monte Carlo. CRC Press, May 1.11. ISBN -77----400--942255.
12

---

[26] N. Siddharth, Brooks Paige, Jan-Willee Willem van de Meent, Alban Desmaison, Noah D. Goodman, Pushmeet Kohli, Frank Wood, and Philip Torr. Learning disentangled representations with semi-supervised deep generative models. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances Neural Information Processing Systems 30, pages 5927-5937. Curran Associates, Inc., 2017.
[27] Atilim Gunes Baydin, Barak A Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning: a survey. Journal of Marchine Learning Research, 18: 18:1-43, 2018.
[28] David Wingate and Theophane Weber. Automated Variational Inference in Probabilistic Pro- gramming, arXiv:1301. 109.1199 [es, stat], January 2013. URL http: btctp://axxi....///// www.aaiwiiv........ee.ooo.ooo org/ htt//bbs/33000 1299.
[29] Timothy Brooks Paige.
Automatic Inference for Higher-Order Probabilistic Programs. University of Oxford, 2016. URL https://ora. ox. ac.
http://uud.rrr/d//ddmmmtttoo//// uk/ uk/objjr obj//t/js////////o//e hwtict////uuii/ueeeeitititiiiiie dedd:::dd222dee-eee
[30] Jan- Willei Vandemeent, Brooks Paige, David Tolpin, and Frank Wood. Black-Box Policy Search with Probabilistic Programs. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pages 1195-1204. PMLR, May 2016. URL https: httl..
// prroceddings.... mlr. press/
[31] Jan-Willem de Meent, Brooks Paige, Hongseok Yang, and Frank Wood. An Introduction to Probabilistic Programming. arXiv: 1809. 10756 [cs, stat), September 2018. URL http: / //arxivv.e. orxiv.org/aat 180//1809..00 10756.
[32] Arun Chaganty, Aditya Nori, and Sriram Rajamani. Efficiently Sampling Probabilistic Programs via Program Analysis. In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, pages 153-160. PMLR, April 2013. URL httttttt////occeeeeee mlr. ptr.ppeessvv11 catpa////t//aaattty///// aaaaaantty3a.... 13a. html.
[33] Sriram Sankaranarayanan, Aleksandar Chakarov, and Sumit Gulwani. Static analysis for probabilistic programs: Inferring whole program properties from finitely many paths. In Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '13, pages 447-458, New York, NY, USA, June 2013. Association for Computing Machinery. ISBN 978-1-4503-2011 https://doi.. org/ 1145/24919566 24615/2299956..227777
doi: 10.114/24919562442277 URL
[34] Yuan Zhou, Hongseok Yang, Yee Whye Teh, and Tom Rainforth. Divide, Conquer, and Combine: New Inference Strategy for Probabilistic Programs with Stochastic Support. In Proceedings the 37th International Conference on Machine Learning, pages 11534-11545. PMLR, November 2020. URL https:: httpe//dwww.....eeeeeee/e//////e htmm.
mlr.
[35] Andrew D. Gordon, Thomas A. Henzinger, Aditya V. Nori, and Sriram K. Rajamani. Prob- abilistic programming. In Future of Software Engineering Proceedings, FOSE 2014, pages 167-181, New York, NY, USA, May 2014. Association for Computing Machinery. ISBN URL https://doi. htt////iio////////// otgg/0.1144.
978-1-4503-2865-4, doi: 10. 2544/22298822.2599900 2593882 2593900.
[36] Thomas William Gamlen Rainforth. Automating Inference, Learning, and Design Using Probabilistic Programming. http://ppu..or///ccccemmtte////p University of Oxford, 2017. URL https://ora, wx.........o.oooooooooo..oooooo. ac. -
[37] Martin J Wainwright, Michael Jordan, et al. Graphical models, exponential families, and variational inference. Foundations and Trends@ in Machine Learning, 1 1(1-2):1-305, 2008.
[38] Shakir Mohamed, Mihaela Rosca, Michael Figumov, and Andriy Mnih. Monte Carlo Gradient Estimation Machine Learning. Journal of Machine Learning Research, 21(132):1 2020. ISSN 1533-7928. URL bttt:://jmll org/ hatee/ppprs////// 1211/9////11/1-/// 346 html.
13

---

[39] Jack P. C. Kleijnen and Reuven Y. Rubinstein. Optimization and sensitivity analysis of computer simulation models by the score function method. European Joumnal of Operational Research, 88(3):413 427,, February 1996. ISSN 0377-2217. doi: 10.11010600000772227000000000010 URI.
httpss:/www.... http:://ww..ceeeeddrree......
[40] Ronald J. Williams. Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning. Machine Language, 8(3-4):229-2566 May 1992. ISSN 0885-6125, doi: 10.1007/BF00992666 URL htt.:htttt/:.iorrrgte. wtt.://///....///000000000000000 0t000///0...////////././0/./0/0/
[41] Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic Backpropagation and Approximate Inference in Deep Generative Models. arXiv:/401.4082 (cs, stat), May 2014. URL http: /ttp::///aaxii aawiiviiiviivii org/ /10os//111.... 4082.
[42] Michalis Titsias and Miguel Lázaro-Gredilla. Doubly Stochastic Variational Bayes for non- Conjugate Inference. In Proceedings of the 31st International Conference on Machine Learning, pages 1971-1979. PMLR, June 2014.
[43] Stefan Webb, Adam Golinski, Robert Zinkov, N. Siddharth, Tom Rainforth, Yee Whye Teh, and Frank Wood. Faithful Inversion of Generative Models for Effective Amortized Inference. arXiv:1712.00287 [cs, stat], November 2018. URL http://// /ttttt::/arxii...o org/ abs 177110022777....
[44] Aditya V Nori, Chung-Kil Hur, Sriram K Rajamani, and Selva Samuel. R2: An Efficient MCMC Sampler for Probabilistic Programs. AAAI Conference on Artificial Intelligence (AAAI), page 7, 2015.
[45] Raven Beutner, Luke Ong, and Fabian Zaiser. Guaranteed bounds for posterior inference in universal probabilistic programming. PLDI 2022: International Conference on Programming Language Design and Implementation, 2022.
[46] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020. doi: 10.1017/9781 10857140)
[47] Zohar Karnin, Tomer Koren, and Oren Somekh. Almost optimal exploration in multi-armed bandits. In International Conference on Machine Learning, pages 1238-1248 PMLR, 2013.
[48] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hy- perband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18(185):1-52, 2018. URL / jmlr. prggpapers/viee www/ww-///// 1/////655555 558. html.
[49] Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: Robust and efficient hyperparameter optimization at scale. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1437-1446. PMLR, 10-15 Jul 2018. URL
mml.
press/v80ffes htt.////ffaaaaeaaa/eeee html.
[50] Christian Naesseth, Fredrik Lindsten, and David Blei. Markovian score climbing: Variational inference with kl(p ll q). In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15499-15510. Curran Associates, Inc., 2020. URL https: https://procceddngg hwwpsisnnrr..p... cc/paper/2020/ (ttll///776555aa0000666777766682 Paper. pdf.
[51] Rajesh Ranganath, Sean Gerrish, and David Blei. Black Box Variational Inference. In Pro- ceedings of the Seventeenth International Conference on Artificial Intelligence and Statis- tics, pages 8 814-822. PMLR, April 2014. URL ranganath14 1hmmm..
mlr, www..ppee//e..... press/v33/
[52] Alp Kucukelbir, Dustin Tran, Rajesh Ranganath, Andrew Gelman, and David M. Blei. Auto- matic differentiation variational inference. J. Mach. Learn. Res., 18(1), Jan 2017.
[53] Luca Ambrogioni, Kate Lin, Emily Fertig, Sharad Vikram, Max Hinne, Dave Moore, and Marcel van Gerven. Automatic structured variational inference. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, pages 676-684. PMLR, March / 2021. URL https:://prceeeeeeeeeee http///pooeeee...c/// mlr, press/v1300 wwt.0///rm0oon0222121 html. html
14

---

[54] Akash Kumar Dhaka, Alejandro Catalina. Manushi Welandawe, Michael Ris Andersen, Jonathan Huggins, and Aki Vehtari. Challenges and Opportunities in High-dimensional Varia- tional Inference. 01085.
null, March 2021. URI. htt.:http//ee www.iv.org/abs....
[55] Wonyeol Lee, Hangyeol Yu, and Hongseok Yang. ent for Non-differentiable Models. In Advances in Neural Information Pro-
Reparameterization Gradi-
cessing Systems, 2018. URL tttps://paperas wipp....ipp.... www..iiis........ scc/paper/2018/hahhi 40667778844ee26644144322222 www.--bbstttttteeeeeeeeaa
[56] Brooks Paige and Frank Wood. Inference networks for sequential monte carlo in graphical models. In International Conference on Machine Learning, pages 3040-3049. PMLR, 2016.
[57] Andreas Stuhlmüller, Jacob Taylor, and Noah Goodman. Learning stochastic inverses. Advances in neural information processing systems, 26, 2013.
[58] S. M. Ali Eslami, Nicolas Heess, Theophane Weber, Yuval Tassa, David Szepesvari, Koray Kavukcuoglu, and Geoffrey E. Hinton. Attend, Infer, Repeat: Fast Scene Understanding with Generative Models. 10X:v:1603 [cs], March 2016. URL http://arxiv org/ abs/ 1603. 0857..
[59] Brooks Paige and Frank Wood, Compilation Target for Probabilistic Programming Languages. arXiv: 1403.0504 [cs, stat], July 2014. URL http: /tcttp//arxivv org. hatp///bs//133... 0504.
[60] Frank Wood, Jan Willem Meent, and Vikash Mansinghka. A New Approach to Probabilistic Programming Inference. In Artificial Intelligence and Statistics, pages 1024-1032. PMLR, April 2014. URL http:::/ppooeeedinneeeeeoo/o .mlr. www.mmwww....aw....mm.mm.mmm press/v333 stass//333wwodd/ wood14. html.
[61] Tom Rainforth, Christian Naesseth, Fredrik Lindsten, Brooks Paige, Jan-Willem Vande- meent, Arnaud Doucet, and Frank Wood. Interacting particle markov chain monte carlo. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd Inter- national Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2616-2625. New York, New York, USA, 20-22 Jun 2016. PMLR. URL html.
atttps://proceedingg. mlr pptpss//vA/raaifoootiti
[62]
David Wingate, Andreas Stuhlmueller, and Noah Goodman. Lightweight Implementations of Probabilistic Programming Languages Via Transformational Compilation. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 770-778. JMLR Workshop and Conference Proceedings, June 2011. URL http:: h/pppe/e///cceeigggs.... mlr.
press/v15/ http///////a/////// aaallaa.ttmmm html.
[63] Tuan Anh Le. Inference for Higher Order Probabilistic Programs. Master's Thesis, University of Oxford, 2016
[64] Carol Mak, Fabian Zaiser, and Luke Ong. Nonparametric Hamiltonian Monte Carlo. In Proceedings of the 38th International Conference on Machine Learning, pages 7336-7347. PMLR, July 2021. URL
mlr wpwpppeeewe//aaeeeeeeeesee wtw.1///////.aaa..... html..
[65] William Harvey, Andreas Munk, Atilmm Güneş Baydin, Alexander Bergholm, and Frank Wood. Attention for inference compilation. arXiv preprint arXiv: 1961, 2019.
[66] L. Martino, V. Elvira, D. Luengo, and J. Corander. Layered adaptive importance sampling. Statistics and Computing, 27(3), May 2017.
[67] David Duvenaud, James Lloyd, Roger Grosse, Joshua Tenenbaum, and Ghahramani Zoubin. Structure Discovery in Nonparametric Regression through Compositional Kernel Search. In International Conference on Machine Learning, pages 1166-1174, PMLR, May 2013. URL http://proceedde
mlr. wwwps//2s.... dude//udv html.
[68] David Janz, Brooks Paige, Tom Rainforth, Jan- Willem van de Meent, and Frank Wood. Proba- bilistic structure discovery in time series data. arXiv preprint /6Xiv:1611.06688 2016.
[69] G.E.P. Box, G.M. Jenkins, G.C. Reinsel, and G.M. Ljung. Time Series Analysis: Forecasting and Control. Wiley Series in Probability and Statisties. Wiley, 2015. ISBN 97811 1 18674925. URL https:/ / /bokobooooooo wtt.boooooooll..../ooo//ooo.o..p co.
15

---

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]
(b) Did you describe the limitations of your work? [Yes] Limitations are discussed in relevant sections throughout the paper.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The paper provides a generic variational inference algorithm for probabilissic models with stochastic support. As our contributions are methodological and our experiments do not contain any personalized data, we believe that this paper does not introduce any fundamentally new risks.
(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] See Proposi- tion
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL.? [Yes) See supplemen- tary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 6 and Appendix D.
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix D.
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [Yes] Code in supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "ZgkiugRDayY", "reviewer": "Reviewer_NHpY", "summary": "This paper presents a new way to automatically construct and train variational families for models expressed as general probabilistic programs. \n\nGiven a program $p$, it first generates many (prior) samples from $p$ to identify a collection of control flow paths that collectively have high mass under the prior. Then, a separate variational family is trained to target the restriction of the model to each control flow path. During training, control-flow paths with low ELBOs are periodically pruned, so that computation is focused on paths that appear to have relatively high posterior probability. Finally, the learned variational families are combined into a mixture, with mixture weights based on estimated ELBOs for each path. \n\nExperiments show competitive performance against other fully automated inference strategies for probabilistic programs, on three inference problems.", "questions": "1. In Section 4.5, you describe two methods for resolving the issue that local guides may not 'stay within' the boundaries of their SLPs. The way I read it, you are applying both solutions (mixing the target with a constant density, and rejection sampling the guide)---but isn't only one necessary? If you are rejection sampling, why introduce unnecessary discontinuities into the target?\n\n2. I am confused about how the rejection sampling in Section 4.5 is supposed to work. As you write, the density of the variational family now contains a \"Z\" term, equal to the probability that q produces a sample that is accepted. This Z term must be computed when estimating the ELBO and its gradient. (Though the notation does not make this clear, Z depends on the parameters phi, so Z cannot simply be dropped when training.) How do you compute Z and its gradient, which in general will be an intractable integral over the SLP's region (which could be strangely shaped)?\n\n(Note: my score is only \"borderline accept\" because I am not sure I've understood the method / if I have I am not sure it's sound, and also because I have concerns about certain misleading aspects of the current presentation, described in \"Strengths and Weaknesses.\" If these are addressed during the author response, I hope to revise my score to a more confident recommendation.)\n\n**EDIT AFTER DISCUSSION:** The author response has addressed my concerns and I am increasing my score to a 7.", "limitations": "As stated in \"Weaknesses,\" I think the limitations are not adequately discussed. The class of probabilistic programs in universal PPLs is huge: when should we expect this algorithm to work, and when should we expect it to fail? i.e., when might users still resort to custom guides in Pyro? What assumptions does the new method make (e.g., non-negligible posterior mass on an SLP implies non-negligible prior mass)?", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Convincing empirical results, showing that for a similar computational budget, the new method outperforms a few existing fully automatic inference methods.\n2. The paper grows the body of evidence that extracting SLPs and tackling inference separately in each (as done e.g. in DCC) is a useful technique for fully automated inference in universal PPLs.\n3. In models with discrete latent variables that influence control flow, gradient estimators are often based on REINFORCE, and a variant of the \"explore/exploit\" problem from reinforcement learning arises: without any gradient signal helping it to explore other branches of the control flow graph, the variational family may settle into 'exploiting' one suboptimal branch. This work presents a nice way of introducing some kind of 'exploration', by allocating some training time up front to many different branches, and pruning only if they do not look promising. This is a neat way of getting around the high variance of the REINFORCE estimator. (It's a bit similar to the strategy of exactly marginalizing the discrete variable, except maybe a bit less expensive in the long run, because if one path is not promising, it is pruned early.) \n4. An implementation in Pyro is provided, which increases the likelihood that this work will have real impact for practitioners.\n\nWeaknesses:\n\n1. In Section 4.5, rejection sampling the guide changes the variational family's density, as the authors write, introducing a \"Z\" term that measures the probability that the guide generates a sample that lies within its assigned SLP. But this Z term, which depends on the guide's parameters and so must be considered during optimization, appears to be intractable, and the authors do not explain how it is computed when estimating the ELBO and the ELBO's gradient. If it is ignored, I am worried that the gradient estimates would be biased. Furthermore, it doesn't seem this feature is 'stress-tested' by the experiments, the latter two of which use guides that ensure no rejection is necessary.\n\n2. I did not see any clear discussion of the method's limitations. At times, I thought the authors made misleading claims that downplayed limitations. For example, L176 says of the SLP discovery process that \"experiments show it can reliably identify all SLPs with non-negligible posterior mass.\" But my understanding is that you only discover SLPs with non-negligible _prior_ probability mass; in all the experiments, the posterior was concentrated in SLPs likely under the prior. Consider fitting the Gaussian mixture model to a dataset with many more components than the prior expects. The posterior will concentrate far from the prior, in an SLP that may not even have been discovered by the algorithm. Of course, this is a difficult case for many inference algorithms, but the limitation should be clearly explained. \n\n3. I find Figure 1 and its explanation on L99-110 misleading. The explanation makes it sound as though the problem in the example is the expressiveness of the default variational family (it cannot represent the posterior on x, due to stochastic control flow). But the striking behavior in the figure, where Autoguide fails, arises just because you are using the reparameterization trick in a non-reparameterizable model. This seems to be a totally separate question from the expressiveness of variational families: it's about whether the Pyro software happens to detect when to switch to the score function gradient estimator automatically. Unless your method *does* automatically detect when the reparameterization trick can or cannot be soundly applied, without any user intervention, this feels irrelevant to the paper. It reads as though a (predictable) failure of the gradient estimator is being passed off as a limitation of the variational family. This also applies to experiments that report results using biased gradient estimators—to me that feels like an orthogonal issue.\n\n4. I don't think the introduction (e.g. L24-42) gives an accurate summary of the state of the art. It is true that many PPLs, including those listed here, aim to support variational inference, but the aim has *not* in general been to automate the construction of guides (although of course, that is an interesting goal). Although Pyro has an Autoguide feature, many of the other PPLs in the list do not: the *intended* use case is that a user constructs a model *and* a guide as probabilistic programs, and the system automates gradient estimation and optimization of the ELBO. (Thus, L92-98 are also a bit misleading.) Even in Pyro, which does support automatic guide construction, many of the tutorials show how to construct custom guides, and the flexibility to do so is touted as a key feature. Arguably, this is what makes languages like Pyro useful for a much broader variety of problems than earlier languages that attempt to fully automate inference. I like that this paper tackles the hard problem of fully automated inference, and I think it makes progress in that direction, but the scope of the problem within the broader field of probabilistic programming should be clearly described: many PPLs already support accurate variational inference (with correct gradient estimates) in models with stochastic control flow if the user provides a sensible variational family. This paper is attempting to further automate the inference process by automatically constructing guides for a broader class of models than existing autoguide techniques can handle.\n\n\nSmall nitpick: on line 63, I don't think \"higher-order\" is relevant -- a first-order language with branching and recursion yields the same class of models.", "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": "YJok-jP1WDH", "reviewer": "Reviewer_Efev", "summary": "The authors address the problem of designing variational proposals for universal probabilistic programs with stochastic support.  Their method breaks down the stochastic support of the target program into a mixture model over control-flow paths through a space of straight-line programs, and the authors explain that their variational proposal method contrasts with Divide-Conquer-Combine (its closest cousin, used for MCMC sampling).  They demonstrate their method's performance on a toy program, an infinite mixture model, and learning Gaussian process kernels in a PCFG.  Their results appear to clearly set a new state of the art in log-predictive density and ELBO.", "questions": "When comparing against sampling-based inference methods, why not include one based on importance sampling?  Resample-move SMC inside DCC, for instance, could provide an estimate of the normalizing constant, and therefore (in log space) an ELBO to which to compare.\n\nI don't understand what's meant by \"marginal likelihood\" for an SLP within a larger program.  Not every straight-line subprogram is going to make observations before reaching a site of stochastic control-flow, and so your importance weight could just be a prior/proposal density ratio.  Is that ratio's expectation used as a normalizing constant to allocate compute power?\n\nThe authors have now clarified and explained away my previous concerns.", "limitations": "The authors, peculiarly for a Pyro paper, make no actual use of neural networks to represent conditional densities.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* Variational inference in deep universal PPLs is widely applicable and significant to a broad variety of downstream problems\n* Clearly superior experimental results, with 100*K dimensionalities\n* Latter two experiments are clearly nontrivial for variational inference settings\n* Color-coding provides clarity\n* Explanations and mathematics are clear to PPL readers\n\nWeaknesses:\n* Explanations and mathematics will be unclear to readers without probabilistic ML background", "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": "Ip8iKEAWb66", "reviewer": "Reviewer_A7EP", "summary": "The paper proposes a new variant of variational inference for probabilistic programs with stochastic support. To address the challenges stochastic support poses, this paper proposes a novel way of constructing a variational guide by breaking down the problem into sub-programs. The paper demonstrates that this approach results in improvements in inference performance.", "questions": "- Could authors justify the main differences between their work and that of for instance [35]?\n- How does it compare to MCMC VI?", "limitations": "- This work seems a little incremental thus some justification is required to distinguish between this work and others. \n- Choosing a variational family is always a crucial task when doing VI. I am not sure how it is compared to the MCMC VI models. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths: \n1) The paper addresses a very important and useful problem and the proposed method seems to be a nice and useful addition to probabilistic programming languages. I especially appreciate that the code is made available.\n2) The paper is very well written and easy to understand\n3) The paper contains comprehensive experiments to demonstrate the effectiveness of the method.\n\nWeakness: \n1) The work seems to be incremental over [33-35] especially [35]. The authors need to justify how their work differs from the aforementioned references.\n\n2) The paper needs to include more related works and explain the differences and similarities between the proposed method and related works in more detail. There has been a lot going on in this field and it begs a more comprehensive literature review. ", "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": "AlhZVqR5mIv", "reviewer": "Reviewer_M2CX", "summary": "The paper proposes a variational inference method named Support Decomposition Variational Inference (SDVI) that targets probabilistic programs with stochastic support. The main idea is to perform variational inferences separately on sub-programs with static support. The variational approximation has a mixture form where each variational component is optimized independently for each sub-program. Finally, the approach is compared to baseline algorithms on a Gaussian model with stochastic control flow, on an infinite Gaussian mixture model (IGMM) with a stochastic number of clusters, and on inferring the kernel structure of a Gaussian Process.", "questions": "The “rethinking” word in the title seems to create confusion because the main algorithm is only compared to the simple Gaussian approximation.\n\nThe mention of Pyro’s AutoGuide in Figure 1 may cause confusion. It might be better to use an explicit algorithm name, e.g. Gaussian variational approximation or the like.\n\nIt is not clear to me how we can differentiate between different paths of a program. Based on the program in Figure 1, apparently it requires users to use different variable names (z1, z2) for different paths. Is this a requirement for users?\n\nIn the discussion of Table 1, “MAP estimate of K=6, the local guide q_k corresponding to the SLP with 5 components” - should this be SLP with 6 components?", "limitations": "Nothing to report.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is clearly written and the structure is easy to follow. I don’t have problems getting the main ideas.\n\nThe paper tackles the universality perspective in probabilistic programming systems. This seems to be a difficult problem. Though the main idea follows the “Divide, Conquer, and Combine” approach proposed by Zhou et al. [35], using variational inference instead of MCMC poses different challenges, which are reasonably addressed in the section 4:\n+ Using the Successive Halving algorithm to avoid wasting computational resources on less interesting sub-programs.\n+ Truncating the target density by a small positive value to ensure obtaining a finite ELBO (when a variational component proposes samples outside of the support of its corresponding sub-program).\n+ Variational components need to be initialized smartly so that they have sufficiently large probability mass on the support of the corresponding sub-programs.\n\nDespite that the authors already provide an implementation in Pyro, I feel that it is a bit tricky for practitioners to adopt the approach due to the complication of the above challenges.\n\nThe paper lacks discussions on how expensive the approach is (though it seems that the method is scalable through the IGMM experiment). This is important for users who want to apply the method in practice.\n\nIn addition, though the experimental results seem to be correct, it would be more interesting for readers to know in which situations we need to construct a probabilistic program with stochastic support. This might deserve a paragraph in the introduction section.", "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