Sampling in Unit Time with Kernel Fisher–Rao Flow

Sampling in Unit Time with Kernel Fisher–Rao Flow

2024 | Aimee Maurais, Youssef Marzouk
This paper introduces a new mean-field ordinary differential equation (ODE) and corresponding interacting particle systems (IPS) for sampling from an unnormalized target density. The IPS are gradient-free, available in closed form, and only require the ability to sample from a reference density and compute the (unnormalized) target-to-reference density ratio. The mean-field ODE is derived by solving a Poisson equation for a velocity field that transports samples along the geometric mixture of the two densities, π₀¹⁻ᵗπ₁ᵗ, which is the path of a Fisher–Rao gradient flow. A reproducing kernel Hilbert space (RKHS) ansatz for the velocity field makes the Poisson equation tractable and enables discretization of the resulting mean-field ODE over finite samples. The mean-field ODE can also be derived from a discrete-time perspective as the limit of successive linearizations of the Monge–Ampère equations within a framework known as sample-driven optimal transport. A stochastic variant of the approach is introduced, and empirical results show that the IPS can produce high-quality samples from varied target distributions, outperforming comparable gradient-free particle systems and competitive with gradient-based alternatives. The paper presents a novel approach to sampling via transport, where the goal is to find a map T that transforms samples from a reference distribution π₀ to a target distribution π₁. The approach is based on a mean-field ODE that transports samples from π₀ to π₁ in unit time, with the time-dependent distribution of the samples following the geometric mixture πₜ ∝ π₀¹⁻ᵗπ₁ᵗ. This path corresponds to the Fisher–Rao gradient flow of the expected negative log likelihood. The underlying dynamics are described by a mean-field ODE model, which is shown to be the limit of two different interacting particle systems. These systems, referred to as Kernel Fisher–Rao Flow (KFRFlow), are obtained through two distinct but related methods: one in continuous time via the weak formulation of a Poisson equation in RKHS, and another in discrete time via linearization of the Monge–Ampère equations over kernel basis functions and samples. The paper also discusses the computational cost and numerical stability of the proposed methods, highlighting the importance of regularization and stochastic modifications to ensure stable and high-quality sampling. Numerical experiments demonstrate the effectiveness of KFRFlow, KFRFlow-I, and KFRD in generating samples from various target distributions, outperforming other gradient-free and gradient-based sampling methods in terms of sample quality and efficiency. The results show that KFRFlow and KFRFlow-I produce better-quality samples than gradient-based methods in certain settings, while KFRD performs competitively with other gradient-based methods. The paper concludes with a discussion of future work, including the potential for further improvements in computational efficiency and the exploration of the theoretical connections between the proposed methods and other sampling techniques.This paper introduces a new mean-field ordinary differential equation (ODE) and corresponding interacting particle systems (IPS) for sampling from an unnormalized target density. The IPS are gradient-free, available in closed form, and only require the ability to sample from a reference density and compute the (unnormalized) target-to-reference density ratio. The mean-field ODE is derived by solving a Poisson equation for a velocity field that transports samples along the geometric mixture of the two densities, π₀¹⁻ᵗπ₁ᵗ, which is the path of a Fisher–Rao gradient flow. A reproducing kernel Hilbert space (RKHS) ansatz for the velocity field makes the Poisson equation tractable and enables discretization of the resulting mean-field ODE over finite samples. The mean-field ODE can also be derived from a discrete-time perspective as the limit of successive linearizations of the Monge–Ampère equations within a framework known as sample-driven optimal transport. A stochastic variant of the approach is introduced, and empirical results show that the IPS can produce high-quality samples from varied target distributions, outperforming comparable gradient-free particle systems and competitive with gradient-based alternatives. The paper presents a novel approach to sampling via transport, where the goal is to find a map T that transforms samples from a reference distribution π₀ to a target distribution π₁. The approach is based on a mean-field ODE that transports samples from π₀ to π₁ in unit time, with the time-dependent distribution of the samples following the geometric mixture πₜ ∝ π₀¹⁻ᵗπ₁ᵗ. This path corresponds to the Fisher–Rao gradient flow of the expected negative log likelihood. The underlying dynamics are described by a mean-field ODE model, which is shown to be the limit of two different interacting particle systems. These systems, referred to as Kernel Fisher–Rao Flow (KFRFlow), are obtained through two distinct but related methods: one in continuous time via the weak formulation of a Poisson equation in RKHS, and another in discrete time via linearization of the Monge–Ampère equations over kernel basis functions and samples. The paper also discusses the computational cost and numerical stability of the proposed methods, highlighting the importance of regularization and stochastic modifications to ensure stable and high-quality sampling. Numerical experiments demonstrate the effectiveness of KFRFlow, KFRFlow-I, and KFRD in generating samples from various target distributions, outperforming other gradient-free and gradient-based sampling methods in terms of sample quality and efficiency. The results show that KFRFlow and KFRFlow-I produce better-quality samples than gradient-based methods in certain settings, while KFRD performs competitively with other gradient-based methods. The paper concludes with a discussion of future work, including the potential for further improvements in computational efficiency and the exploration of the theoretical connections between the proposed methods and other sampling techniques.
Reach us at info@study.space