Deterministic Sampling through Energy Minimization

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

This project aims at developing optimal deterministic methods for statistical sampling / statistical observations, in contrast to commonly-used random sampling methods such as Monte Carlo (MC) and Markov Chain Monte Carlo (MCMC). The MC/MCMC methods have revolutionized statistics, allowing statisticians to model and solve complex and high-dimensional problems that would have been intractable using conventional techniques. One drawback of these methods is that very many observations or data samples are needed due to the slow convergence rate inherent in random sampling. This becomes an issue when the sampling is expensive. The deterministic method under study in this project attempts to overcome this problem by sampling points more intelligently, so that the same information provided by a random sample can be obtained with fewer deterministic samples. This can significantly cut down the cost of sampling and subsequent computations. The method under development has applications in many fields, such as uncertainty quantification, computer experiments, and machine learning. The project aims to provide deterministic samples obtained through the minimization of certain energies. The goal is to use carefully developed optimization techniques to reduce the number of expensive evaluations of a probability distribution, thereby reducing the overall computational cost. Furthermore, the deterministic sample provides a much better representative set of points for the distribution, which can further reduce the cost of subsequent computations involving integrals. Compared to the existing Quasi-Monte Carlo methods, which are mostly developed for sampling from the uniform hypercube, the methods under study are much more general and can be used to directly sample from any probability distribution. Two methods for deterministic sampling will be investigated. The first method, known as minimum energy designs, is useful when the probability density is expensive to evaluate. The second method, known as support points, is useful when the integrand is expensive but sampling from the probability density is easy. The minimum energy design possesses an important property: its empirical distribution asymptotically converges to the target distribution. This is a property not shared by some of the competing representative point sets in the literature, such as principal points. On the other hand, support points are obtained by minimizing an energy distance which is used for goodness-of-fit testing. In this light, support points can be viewed as point sets that optimally compact a continuous probability distribution. The project focuses on developing efficient optimization methods for these energy functions using as few function evaluations as possible, and improving the distributional properties of the point sets so that they can be used in problems where MC/MCMC methods are computationally impracticable.