We present an exact Bayesian inference method for discrete statistical models, which can find exact solutions to a large class of discrete inference problems, even with infinite support and continuous priors. To express such models, we introduce a probabilistic programming language that supports discrete and continuous sampling, discrete observations, affine functions, (stochastic) branching, and conditioning on discrete events. Our key tool is probability generating functions: they provide a compact closed-form representation of distributions that are definable by programs, thus enabling the exact computation of posterior probabilities, expectation, variance, and higher moments. Our inference method is provably correct and fully automated in a tool called Genfer, which uses automatic differentiation (specifically, Taylor polynomials), but does not require computer algebra. Our experiments show that Genfer is often faster than the existing exact inference tools PSI, Dice, and Prodigy. On a range of real-world inference problems that none of these exact tools can solve, Genfer's performance is competitive with approximate Monte Carlo methods, while avoiding approximation errors.

Algorithm 2 details the pseudocode for the partition function used in LaMCTS, which we use in LaP3 as well. Algorithm 2 Partition Function 1: Input: Input Space Ω, Samples St, Node partition threshold Nthres, Partitioning Latent Model s(x) 2: Set V0 = {Ω} 3: Set Vqueue = {Ω} 4: while Vqueue 6= do 5: Ωp Vqueue.pop(0) It is clear that Fk(y) is a monotonically decreasing function with Fk(0) = 1 and limy + Fk(y) = 0. Here we assume it is strictly decreasing so that Fk(y) has a well-defined inverse function F 1k . In the following, we will omit the subscript k for brevity. P[f(xi) g y|xi Ωk] (4) = 1 Fntk (y) (5) Note that 1 is due to the fact that all samples x1,...,xnt are independently drawn within the region Ωk.

We consider the problem where nclients transmit d-dimensional real-valued vectors using dp1 `op1qqbits each, in a manner that allows the receiver to approximately reconstruct their mean. Such compression problems naturally arise in distributed and federated learning. We provide novel mathematical results and derive computationally efficient algorithms that are more accurate than previous compression techniques. We evaluate our methods on a collection of distributed and federated learning tasks, using a variety of datasets, and show a consistent improvement over the state of the art.

The performance of trained neural networks is robust to harsh levels of pruning. Coupled with the ever-growing size of deep learning models, this observation has motivated extensive research on learning sparse models. In this work, we focus on the task of controlling the level of sparsity when performing sparse learning. Existing methods based on sparsity-inducing penalties involve expensive trial-anderror tuning of the penalty factor, thus lacking direct control of the resulting model sparsity. In response, we adopt a constrained formulation: using the gate mechanism proposed by Louizos et al. [31], we formulate a constrained optimization problem where sparsification is guided by the training objective and the desired sparsity target in an end-to-end fashion. Experiments on CIFAR-{10, 100}, TinyImageNet, and ImageNet using WideResNet and ResNet{18, 50} models validate the effectiveness of our proposal and demonstrate that we can reliably achieve pre-determined sparsity targets without compromising on predictive performance.