Abstract
Sampling from probability distributions subject to statistical constraints—such as fixed moments or fairness requirements—is a fundamental challenge in Bayesian inference and generative modeling. This paper, presented at NeurIPS 2024, introduces Primal-Dual Langevin Monte Carlo (PD-LMC), a theoretically grounded and computationally efficient algorithm for this task. By framing constrained sampling as a saddle-point problem in Wasserstein space, the authors develop a stochastic update rule that avoids the expensive integrations required by previous methods. Empirical results across synthetic benchmarks, fair logistic regression, and financial counterfactuals demonstrate that PD-LMC achieves high accuracy and convergence while maintaining computational efficiency.
Introduction
Sampling is a cornerstone of modern statistics and machine learning, underpinning everything from Bayesian posterior estimation to the generation of synthetic data. While standard tools like Langevin Monte Carlo (LMC) are effective at sampling from a target distribution $\pi$, they are not natively designed to handle constraints on the results of the sampling process.
In many real-world applications, we require samples that satisfy specific global properties. For instance, in fair machine learning, we may want to sample from a posterior distribution while ensuring the resulting model satisfies statistical parity. In finance, researchers often need to explore "what-if" scenarios where the average return of an asset is constrained to a specific value. Traditional approaches to these problems—such as rejection sampling, penalty-based methods, or projection-based LMC—often suffer from extreme computational inefficiency in high dimensions or fail to satisfy the constraints accurately. PD-LMC addresses these gaps by providing a principled framework for distribution-level constraints.
Methodology: The Primal-Dual Approach
The core innovation of this work is the formulation of constrained sampling as a saddle-point optimization problem within Wasserstein space (the space of probability distributions). The authors introduce a discrete-time algorithm that couples two simultaneous updates:
- Primal Update (Sampling): This is a modified Langevin step. The "particle" moves toward the target distribution, but its trajectory is "tilted" by the current estimates of the constraints. This ensures the particle is guided toward regions of the distribution that satisfy the required statistical properties.
- Dual Update (Constraints): This step updates the Lagrange multipliers (dual variables). Unlike prior theoretical frameworks that require calculating an exact expectation over the entire distribution at every step—an impossible task for complex distributions—PD-LMC uses a single-particle stochastic approximation. It updates the multipliers based solely on the current position of the sample.
Algorithmic Variants
The paper details two primary versions of the algorithm:
- Algorithm 1 (PD-LMC): A fully stochastic version designed for (strongly) convex potentials.
- Algorithm 2 (Stochastic Dual LMC): A variant incorporating a "burn-in" period, suitable for distributions satisfying a Log-Sobolev Inequality (LSI), allowing for a degree of non-convexity.
Empirical Evaluation
The authors evaluated PD-LMC across three distinct domains to test its versatility and accuracy.
Synthetic Truncated Gaussians
In 1D and 2D tasks where the goal was to sample from a Gaussian restricted to a specific set (like a box), PD-LMC outperformed existing methods. In a 1D mean-estimation task, PD-LMC achieved a mean of 1.508, remarkably close to the true value of 1.510. In contrast, Projected LMC (1.488) and Mirror LMC (1.470) were less accurate, primarily because they tended to over-sample the boundaries of the constraint set rather than representing the interior distribution correctly.
Fair Bayesian Logistic Regression
Using the UCI Adult dataset, the authors applied PD-LMC to ensure "statistical parity" in income prediction across genders. PD-LMC successfully reduced the disparity in positive predictions from a baseline gap of 21% (26% vs. 5%) to a much narrower 3% (18% vs. 15%). Notably, this significant improvement in fairness resulted in only a marginal 2% decrease in overall prediction accuracy.
Financial Counterfactuals
The algorithm was applied to five years of stock market data involving seven major assets (e.g., TSLA, NVDA, AAPL). By constraining the distribution to reflect specific average returns, the authors demonstrated how the Lagrange multipliers act as "probes," providing a sensitivity analysis that reveals which constraints are most at odds with the observed data.
Key Insights and Discussion
- Distributional vs. Sample Constraints: PD-LMC constrains the distribution rather than individual samples. This allows the samples to populate the interior of the allowed space naturally, avoiding the "bunching" at boundaries common in projection-based methods.
- Efficiency of Single-Sample Updates: A major finding is that mini-batches are not required for accurate constraint estimation. A single particle's path provides sufficient information over time to satisfy global statistical constraints, significantly reducing computational overhead.
- Limitations: Because the method constrains the distribution, individual samples may occasionally fall outside the constraint range during the early stages of the algorithm. Additionally, the current theoretical guarantees rely on the target distribution being strongly log-concave or satisfying an LSI; extending this to multi-modal distributions remains a subject for future research.
Conclusion
Primal-Dual Langevin Monte Carlo offers a robust and efficient solution for sampling under statistical constraints. By leveraging stochastic dual updates and Wasserstein space optimization, it bridges the gap between theoretical sampling guarantees and practical application requirements in fairness, finance, and beyond.
Summary updated