 NSFPAR ID:
 10216894
 Date Published:
 Journal Name:
 Proceedings of the ACM on Programming Languages
 Volume:
 5
 Issue:
 POPL
 ISSN:
 24751421
 Page Range / eLocation ID:
 1 to 28
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Wasserstein Barycenter is a principled approach to represent the weighted mean of a given set of probability distributions, utilizing the geometry induced by optimal transport. In this work, we present a novel scalable algorithm to approximate the Wasserstein Barycenters aiming at highdimensional applications in machine learning. Our proposed algorithm is based on the Kantorovich dual formulation of the Wasserstein2 distance as well as a recent neural network architecture, input convex neural network, that is known to parametrize convex functions. The distinguishing features of our method are: i) it only requires samples from the marginal distributions; ii) unlike the existing approaches, it represents the Barycenter with a generative model and can thus generate infinite samples from the barycenter without querying the marginal distributions; iii) it works similar to Generative Adversarial Model in one marginal case. We demonstrate the efficacy of our algorithm by comparing it with the stateofart methods in multiple experiments.more » « less

Summary It is now common to survey microbial communities by sequencing nucleic acid material extracted in bulk from a given environment. Comparative methods are needed that indicate the extent to which two communities differ given data sets of this type. UniFrac, which gives a somewhat ad hoc phylogeneticsbased distance between two communities, is one of the most commonly used tools for these analyses. We provide a foundation for such methods by establishing that, if we equate a metagenomic sample with its empirical distribution on a reference phylogenetic tree, then the weighted UniFrac distance between two samples is just the classical Kantorovich–Rubinstein, or earth mover’s, distance between the corresponding empirical distributions. We demonstrate that this Kantorovich–Rubinstein distance and extensions incorporating uncertainty in the sample locations can be written as a readily computable integral over the tree, we develop Lp Zolotarevtype generalizations of the metric, and we show how the pvalue of the resulting natural permutation test of the null hypothesis ‘no difference between two communities’ can be approximated by using a Gaussian process functional. We relate the L2case to an analysisofvariance type of decomposition, finding that the distribution of its associated Gaussian functional is that of a computable linear combination of independent X12 random variables.

This work is devoted to the study of rates of convergence of the empirical measures μn over a sample (Xk) of independent identically distributed realvalued random variables towards the common distribution μ in Kantorovich transport distances Wp. The focus is on ﬁnite range bounds on the expected Kantorovich distances E(Wp(μn, μ)) in terms of moments and analytic conditions on the measure μ and its distribution function. The study describes a variety of rates, from the standard one to slower rates, and both lower and upperbounds on E(Wp(μn,μ)) for ﬁxed n in various instances. Order statistics, reduction to uniform samples and analysis of beta distributions, inverse distribution functions, logconcavity are main tools in the investigation. Two detailed appendices collect classical and some new facts on inverse distribution functions and beta distributions and their densities necessary to the investigation.more » « less

We consider the verification of inputrelational properties defined over deep neural networks (DNNs) such as robustness against universal adversarial perturbations, monotonicity, etc. Precise verification of these properties requires reasoning about multiple executions of the same DNN. We introduce a novel concept of difference tracking to compute the difference between the outputs of two executions of the same DNN at all layers. We design a new abstract domain, DiffPoly for efficient difference tracking that can scale large DNNs. DiffPoly is equipped with custom abstract transformers for common activation functions (ReLU, Tanh, Sigmoid, etc.) and affine layers and can create precise linear crossexecution constraints. We implement an inputrelational verifier for DNNs called RaVeN which uses DiffPoly and linear program formulations to handle a wide range of inputrelational properties. Our experimental results on challenging benchmarks show that by leveraging precise linear constraints defined over multiple executions of the DNN, RaVeN gains substantial precision over baselines on a wide range of datasets, networks, and inputrelational properties.more » « less

We derive nonasymptotic quantitative bounds for convergence to equilibrium of the exact preconditioned Hamiltonian Monte Carlo algorithm (pHMC) on a Hilbert space. As a consequence, explicit and dimensionfree bounds for pHMC applied to highdimensional distributions arising in transition path sampling and path integral molecular dynamics are given. Global convexity of the underlying potential energies is not required. Our results are based on a twoscale coupling which is contractive in a carefully designed distance.more » « less