The OS* Algorithm: a Joint Approach to Exact Optimization and Sampling
This addresses a bottleneck in probabilistic inference for researchers and practitioners in machine learning, offering a novel joint approach that could improve efficiency in high-dimensional settings, but it appears incremental as it builds on adaptive rejection sampling and A* optimization.
The paper tackles the problem of exact sampling from high-dimensional distributions, which is slow with rejection sampling and approximate with MCMC, by proposing the OS* algorithm that unifies exact optimization and sampling through incremental refinements of an upper bound. It demonstrates tractability in high dimensions with experiments on high-order HMMs and large discrete graphical models, though no concrete performance numbers are provided.
Most current sampling algorithms for high-dimensional distributions are based on MCMC techniques and are approximate in the sense that they are valid only asymptotically. Rejection sampling, on the other hand, produces valid samples, but is unrealistically slow in high-dimension spaces. The OS* algorithm that we propose is a unified approach to exact optimization and sampling, based on incremental refinements of a functional upper bound, which combines ideas of adaptive rejection sampling and of A* optimization search. We show that the choice of the refinement can be done in a way that ensures tractability in high-dimension spaces, and we present first experiments in two different settings: inference in high-order HMMs and in large discrete graphical models.