  We introduce a new framework for efficient sampling from complex probability
distributions, using a combination of optimal transport maps and the
Metropolis-Hastings rule. The core idea is to use continuous transportation to
transform typical Metropolis proposal mechanisms (e.g., random walks, Langevin
methods) into non-Gaussian proposal distributions that can more effectively
explore the target density. Our approach adaptively constructs a lower
triangular transport map-an approximation of the Knothe-Rosenblatt
rearrangement-using information from previous MCMC states, via the solution of
an optimization problem. This optimization problem is convex regardless of the
form of the target distribution. It is solved efficiently using a Newton method
that requires no gradient information from the target probability distribution;
the target distribution is instead represented via samples. Sequential updates
enable efficient and parallelizable adaptation of the map even for large
numbers of samples. We show that this approach uses inexact or truncated maps
to produce an adaptive MCMC algorithm that is ergodic for the exact target
distribution. Numerical demonstrations on a range of parameter inference
problems show order-of-magnitude speedups over standard MCMC techniques,
measured by the number of effectively independent samples produced per target
density evaluation and per unit of wallclock time.
