Gradient-based Approximation of Nonuniform Low-Discrepancy Samples

摘要

Low-discrepancy points have proven to be a useful source of samples for numerical integration via quasi-Monte Carlo integration. Low-discrepancy points are typically uniformly distributed in the unit hypercube. It is thus common to transform the input uniform points into target non-uniform samples via mapping, just like how uniform random numbers are used for generating non-uniform samples. Unfortunately, this common approach does not guarantee to carry over the low-discrepancy nature of the input points into the output non-uniform samples, giving the resulting non-uniform samples suboptimal discrepancy. The existing methods for generating low-discrepancy points focus only on uniform points, thus generating non-uniform and low-discrepancy samples has been an open problem. We introduce an optimization framework to approximate non-uniform low-discrepancy samples by numerically minimizing the discrepancy metric for non-uniform samples. We propose a differentiable numerical estimator of the generalized non-uniform discrepancy to enable gradient-based optimization. Our differentiable discrepancy estimator turns a challenging problem of generating non-uniform low-discrepancy samples into a simple numerical optimization problem. Since optimization can generate only one set of samples, we further propose a neural network architecture to encode the sample generation process, allowing us to generate multiple sets of samples from conditional targets without runtime optimization. We experimentally validate that our method reduces discrepancy below prior methods at least up to a certain sample size and consequently achieves lower integration error on numerical integration problems.