Geometrically Coupled Monte Carlo Sampling
Monte Carlo sampling in high-dimensional, low-sample settings is important in many machine learning tasks. We improve current methods for sampling in Euclidean spaces by avoiding independence, and instead consider ways to couple samples. We show fundamental connections to optimal transport theory, leading to novel sampling algorithms, and providing new theoretical grounding for existing strategies. We compare our new strategies against prior methods for improving sample efficiency, including quasi-Monte Carlo, by studying discrepancy. We explore our findings empirically, and observe benefits of our sampling schemes for reinforcement learning and generative modelling.
Summary: --------------  This paper proposes a number of expectation estimation strategies which strive to attain lower error than naive methods relying on iid sampling. This is especially important in settings where evaluating the objective function at the sampled variates is expensive (e.g. RL problems.) The advantage of Monte Carlo over deterministic methods is that theoretical assurances are more readily obtained.  The approach is based on (numerically) finding optimal couplings, i.e. joint distributions over an augmented state space marginalizing to the expectation distribution of interest. While a uniformly optimal coupling does not exist over generic function classes, as is appreciated in statistical decision theory, the problem is well-defined in both expected and minimax variants. The optimizer to the K-expected loss is shown to minimize a multi-marginal transport problem, with the nice result that the solutions are space-filling, bringing to mind the behavior of QMC methods. In Proposition 2.7, a relaxation of the minimax problem is obtained when F is the unit ball in a RKHS associated with K, which interestingly turns out to solve the expected loss under the GP prior with covariance K.  Algorithm 2 shows how to optimally couple m antithetic pairs in accordance with Theorem 2.10, which states that sequential orthogonal sampling achieves this under an isotropic marginal.  Section 3 connects geometrically-coupled sampling with low-discrepancy sequences, and Section 4 provides some instructive concentration bounds for both vanilla ES gradient estimators and orthogonal estimators.  This paper provides a number of valuable theoretical contributions with important practical implications, and I recommend its acceptance to NIPS. While the topic is not my field of research, the ideas in the paper were in my view sufficiently well-explained and motivated for me to appreciate the problems and solution.   Issues/Questions: ----------------- The intended domain of application is when evaluation time of f dominates the process. While Algorithm 1 is clearly efficient, is it possible to give a sense of the cost generating conditionally orthogonal samples as in Algorithm 2?   Clarity: -------------- The paper is very well-written and clear;.   Significance: ------------  In addition to its algorithmic contributions, this paper provides several explanations of the success of currently used approximation methodologies.  The restriction of the marginal to be isotropic is strong and prohibits applicability in other contexts, however the case is convincingly made that in ES-based policy learning and VAE ELBO optimization, the method is practically relevant.   Technical Correctness: ---------------------  I did not painstakingly verify each detail of the proofs, but the results are technically correct as far as I could tell.  Minor: ------- - Why does "s" refer to number of samples in the experiments while "m" in the rest of the paper? - l186: sampes -> samples