Appendix for Rethinking Variational Inference for Probabilistic Programs with Stochastic Support Tim Reichelt 1 Luke Ong 1,2 Tom Rainforth

B.1 Background on Successive Halving Successive Halving (SH) divides a total budget of T iterations into L " rlog This results in an exponential distribution of resources allocated to the different candidates, with more resources allocated to those that are more promising after intermediate evaluation. Adapting it to our setting of treating the problem as a top-m identification is done by simply using L " rlog The online variant of the algorithm is useful if a user is unsure about the total iteration budget that they want to spend on the input program. We therefore need to adapt Algo. 1 so that it can be'restarted' after it has terminated. A naive approach to this would be to simply run Algo. 1 again but re-use the q's for the SLPs that have already been discovered and only initialize the q However, this scheme is limited as it disproportionately favours SLPs which were discovered in the previous run. This is because for those SLPs the local ELBOs will already be relatively large compared to the newly added SLPs.