 Award ID(s):
 1650733
 NSFPAR ID:
 10086312
 Date Published:
 Journal Name:
 32nd Annual Conference on Neural Information Processing Systems
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Asynchronous Gibbs sampling has been recently shown to be fastmixing and an accurate method for estimating probabilities of events on a small number of variables of a graphical model satisfying Dobrushin's condition~\cite{DeSaOR16}. We investigate whether it can be used to accurately estimate expectations of functions of {\em all the variables} of the model. Under the same condition, we show that the synchronous (sequential) and asynchronous Gibbs samplers can be coupled so that the expected Hamming distance between their (multivariate) samples remains bounded by O(τlogn), where n is the number of variables in the graphical model, and τ is a measure of the asynchronicity. A similar bound holds for any constant power of the Hamming distance. Hence, the expectation of any function that is Lipschitz with respect to a power of the Hamming distance, can be estimated with a bias that grows logarithmically in n. Going beyond Lipschitz functions, we consider the bias arising from asynchronicity in estimating the expectation of polynomial functions of all variables in the model. Using recent concentration of measure results, we show that the bias introduced by the asynchronicity is of smaller order than the standard deviation of the function value already present in the true model. We perform experiments on a multiprocessor machine to empirically illustrate our theoretical findings.more » « less

The seminal result of Kahn, Kalai and Linial shows that a coalition of O(n/(log n)) players can bias the outcome of any Boolean function {0,1}^n > {0,1} with respect to the uniform measure. We extend their result to arbitrary product measures on {0,1}^n, by combining their argument with a completely different argument that handles very biased input bits. We view this result as a step towards proving a conjecture of Friedgut, which states that Boolean functions on the continuous cube [0,1]^n (or, equivalently, on {1,...,n}^n) can be biased using coalitions of o(n) players. This is the first step taken in this direction since Friedgut proposed the conjecture in 2004. Russell, Saks and Zuckerman extended the result of Kahn, Kalai and Linial to multiround protocols, showing that when the number of rounds is o(log^* n), a coalition of o(n) players can bias the outcome with respect to the uniform measure. We extend this result as well to arbitrary product measures on {0,1}^n. The argument of Russell et al. relies on the fact that a coalition of o(n) players can boost the expectation of any Boolean function from epsilon to 1epsilon with respect to the uniform measure. This fails for general product distributions, as the example of the AND function with respect to mu_{11/n} shows. Instead, we use a novel boosting argument alongside a generalization of our first result to arbitrary finite ranges.more » « less

Many twolevel nested simulation applications involve the conditional expectation of some response variable, where the expected response is the quantity of interest, and the expectation is with respect to the innerlevel random variables, conditioned on the outerlevel random variables. The latter typically represent random risk factors, and risk can be quantified by estimating the probability density function (pdf) or cumulative distribution function (cdf) of the conditional expectation. Much prior work has considered a naïve estimator that uses the empirical distribution of the sample averages across the innerlevel replicates. This results in a biased estimator, because the distribution of the sample averages is overdispersed relative to the distribution of the conditional expectation when the number of innerlevel replicates is finite. Whereas most prior work has focused on allocating the numbers of outer and innerlevel replicates to balance the bias/variance tradeoff, we develop a biascorrected pdf estimator. Our approach is based on the concept of density deconvolution, which is widely used to estimate densities with noisy observations but has not previously been considered for nested simulation problems. For a fixed computational budget, the biascorrected deconvolution estimator allows more outerlevel and fewer innerlevel replicates to be used, which substantially improves the efficiency of the nested simulation.more » « less

Abstract The goal of this paper is to prove a comparison principle for viscosity solutions of semilinear Hamilton–Jacobi equations in the space of probability measures. The method involves leveraging differentiability properties of the 2Wasserstein distance in the doubling of variables argument, which is done by introducing a further entropy penalization that ensures that the relevant optima are achieved at positive, Lipschitz continuous densities with finite Fischer information. This allows to prove uniqueness and stability of viscosity solutions in the class of bounded Lipschitz continuous (with respect to the 1Wasserstein distance) functions. The result does not appeal to a mean field control formulation of the equation, and, as such, applies to equations with nonconvex Hamiltonians and measuredependent volatility. For convex Hamiltonians that derive from a potential, we prove that the value function associated with a suitable meanfield optimal control problem with nondegenerate idiosyncratic noise is indeed the unique viscosity solution.

null (Ed.)We consider the problem of estimating the Wasserstein distance between the empirical measure and a set of probability measures whose expectations over a class of functions (hypothesis class) are constrained. If this class is sufficiently rich to characterize a particular distribution (e.g., all Lipschitz functions), then our formulation recovers the Wasserstein distance to such a distribution. We establish a strong duality result that generalizes the celebrated KantorovichRubinstein duality. We also show that our formulation can be used to beat the curse of dimensionality, which is well known to affect the rates of statistical convergence of the empirical Wasserstein distance. In particular, examples of infinitedimensional hypothesis classes are presented, informed by a complex correlation structure, for which it is shown that the empirical Wasserstein distance to such classes converges to zero at the standard parametric rate. Our formulation provides insights that help clarify why, despite the curse of dimensionality, the Wasserstein distance enjoys favorable empirical performance across a wide range of statistical applications.more » « less