  Monte Carlo inference has asymptotic guarantees, but can be slow when using
generic proposals. Handcrafted proposals that rely on user knowledge about the
posterior distribution can be efficient, but are difficult to derive and
implement. This paper proposes to let users express their posterior knowledge
in the form of proposal programs, which are samplers written in probabilistic
programming languages. One strategy for writing good proposal programs is to
combine domain-specific heuristic algorithms with neural network models. The
heuristics identify high probability regions, and the neural networks model the
posterior uncertainty around the outputs of the algorithm. Proposal programs
can be used as proposal distributions in importance sampling and
Metropolis-Hastings samplers without sacrificing asymptotic consistency, and
can be optimized offline using inference compilation. Support for optimizing
and using proposal programs is easily implemented in a sampling-based
probabilistic programming runtime. The paper illustrates the proposed technique
with a proposal program that combines RANSAC and neural networks to accelerate
inference in a Bayesian linear regression with outliers model.
