Inference via Low-Dimensional Couplings

Alessio Spantini, Daniele Bigoni, Youssef M. Marzouk

TL;DR

This paper introduces a novel approach to inferring complex probability distributions by leveraging the low-dimensional structure of "transport maps." By connecting the sparsity and decomposability of these maps to the Markov properties of the target distribution, the authors enable more efficient and scalable inference, particularly for nonlinear, non-Gaussian state-space models.

What Problem Does This Paper Address?

In statistics and machine learning, a common task is to characterize or sample from a complex probability distribution (the "target measure"). A powerful technique is to use a "transport map" to deterministically transform samples from a simple, tractable "reference measure" (like a standard Gaussian) into samples from the target measure. This allows us to leverage the known properties of the reference measure for inference. However, as the dimensionality of the problem increases, representing and evaluating these transport maps becomes computationally intractable. This paper addresses the challenge of efficiently characterizing and utilizing transport maps in high-dimensional settings by exploiting underlying structural properties.

Methods

The core contribution lies in establishing a link between the Markov properties of the target distribution and the low-dimensional structure of the transport maps. Specifically, the authors show that if the target distribution exhibits certain conditional independence properties (captured by its Markov network), the corresponding transport maps can be characterized as either:

  • Sparse: Each component of the map depends only on a small subset of input variables.
  • Decomposable: The map can be expressed as a composition of several simpler, low-dimensional maps.

The paper introduces the Knothe-Rosenblatt (KR) rearrangement as a fundamental building block for triangular transport maps and derives bounds on its sparsity based on the target's Markov structure. It then extends this to decomposable transports, showing how they can be constructed recursively from simpler, generalized triangular functions. This decomposition allows for breaking down complex inference problems into a sequence of smaller, more manageable low-dimensional optimization problems. The authors also propose new variational algorithms for filtering, smoothing, and sequential parameter inference in nonlinear, non-Gaussian state-space models, which are presented as generalizations of the standard Gaussian smoothers.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and algorithmic design, illustrated with numerical examples rather than specific datasets.

Key Insights and Ideas

  • Markov structure dictates map structure: The conditional independence properties of a target distribution directly influence the sparsity and decomposability of the transport maps that can couple it to a reference distribution. This is a crucial insight for simplifying high-dimensional inference.
  • Inverse transports can be sparser: The paper highlights that inverse transport maps often inherit more sparsity from the target's Markov structure than direct transports. This suggests a strategic advantage in characterizing inverse maps when possible.
  • Decomposability as a computational advantage: By breaking down a high-dimensional transport map into a composition of low-dimensional maps, inference becomes more tractable. Each low-dimensional map can be optimized and computed more efficiently.
  • Generalization of Gaussian smoothers: The proposed algorithms for state-space models are presented as a natural extension of well-established Gaussian smoothing techniques (like the Rauch-Tung-Striebel smoother) to the non-Gaussian setting.

Key Results

  • Sparsity Bounds: Theorem 3 provides theoretical bounds on the sparsity patterns of triangular transport maps (both direct and inverse) based on the I-map of the target measure.
  • Decomposability Theorem: Theorem 7 establishes the existence of decomposable transport maps for target measures that admit a proper graph decomposition, linking graph structure to map structure.
  • Sequential Inference Algorithms: Theorems 9 and 12 present new variational algorithms for sequential Bayesian inference (filtering, smoothing, and joint parameter/state estimation) in nonlinear, non-Gaussian state-space models. These algorithms build decomposable transport maps in a single forward pass.
  • Numerical Validation: The paper includes numerical experiments (e.g., on a stochastic volatility model) demonstrating that the proposed methods achieve accurate results comparable to MCMC, often with significant computational speedups, especially when using linear parameterizations for the low-dimensional maps. For instance, Table 1 shows dramatic reductions in computational time for parameter estimation and long-time smoothing when using linear maps compared to higher-order nonlinear maps, while maintaining reasonable accuracy.

Limitations and Future Work

  • Approximation Accuracy: The paper acknowledges that the proposed methods rely on numerical approximations of the transport maps. While the accuracy can be controlled by the complexity of the parameterization, there's a tradeoff between computational cost and statistical accuracy.
  • Error Accumulation: For sequential inference, there's a potential for error accumulation as maps are computed iteratively. The paper notes that this is an active area of research.
  • Approximate Markov Properties: The paper discusses the potential of using sparser or more decomposable couplings when the target distribution only approximately satisfies Markov properties. This suggests future work in adapting inference strategies based on approximate graphical models.
  • Low-Rank Couplings: The authors mention exploring "low-rank couplings," where transport maps are low-dimensional up to a rotation of the space, as a naturally occurring structure in some high-dimensional Bayesian inference problems.
  • Error Analysis: The paper suggests the need for rigorous error analysis for these variational approximations, analogous to existing work on Sequential Monte Carlo (SMC) methods.
  • Discovering Low-Dimensional Couplings: The authors envision future work on adaptively discovering low-dimensional couplings, potentially by incrementally decreasing sparsity levels.

Summary updated

Abstract

We investigate the low-dimensional structure of deterministic transformations between random variables, i.e., transport maps between probability measures. In the context of statistics and machine learning, these transformations can be used to couple a tractable “reference” measure (e.g., a standard Gaussian) with a target measure of interest. Direct simulation from the desired measure can then be achieved by pushing forward reference samples through the map. Yet characterizing such a map---e.g., representing and evaluating it---grows challenging in high dimensions. The central contribution of this paper is to establish a link between the Markov properties of the target measure and the existence of low-dimensional couplings, induced by transport maps that are sparse and/or decomposable. Our analysis not only facilitates the construction of transformations in high-dimensional settings, but also suggests new inference methodologies for continuous non-Gaussian graphical models. For instance, in the context of nonlinear state-space models, we describe new variational algorithms for filtering, smoothing, and sequential parameter inference. These algorithms can be understood as the natural generalization---to the non-Gaussian case---of the square-root Rauch--Tung--Striebel Gaussian smoother.
BibTeX
@article{spantini2018inference,
  author = {Alessio Spantini and Daniele Bigoni and Youssef M. Marzouk},
  title = {{Inference via Low-Dimensional Couplings}},
  journal = {J. Mach. Learn. Res.},
  year = {2018},
  url = {https://openreview.net/forum?id=cawP5oKLZs},
}
Figure