Research map / Probabilistic and scientific modeling / Variational and generative sampling
Fast Non-Log-Concave Sampling under Nonconvex Equality and Inequality Constraints with Landing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces OLLA, a projection-free overdamped Langevin SDE with a landing mechanism that enforces nonlinear equality and inequality constraints, proves exponential W2 convergence, and gives a Hutchinson-accelerated Euler-Maruyama discretization (OLLA-H).
Problem
Sampling from a density constrained to a nonconvex feasible set defined by nonlinear equality and inequality constraints, where existing methods rely on costly projections, handle only one constraint type, or lack quantitative convergence guarantees.
Approach
Design overdamped Langevin dynamics whose noise and drift are projected onto the tangent space of the active constraint manifold via least squares, with a deterministic normal "landing" drift that drives trajectories onto the feasible set, avoiding explicit projections and handling equality and inequality constraints jointly.
Key results
- OLLA-H's CPU time per ESS stays roughly flat near 0.05 s/sample as dimension grows to 700, while OLLA grows to about 1.1 s/sample at d=700; CHMC and CLangevin stay at 0.2-0.3 and about 0.1 s/sample.
- On the molecular system with up to d=90, OLLA-H (N=0) is substantially faster than projection-based samplers (e.g., 704 s vs 52220 s for CLangevin at d=90) with comparable R_g^2 estimates.
- On Bayesian logistic regression, OLLA-H (N=0) achieves the lowest test NLL (about 0.52) while being orders of magnitude faster than projection-based baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OLLA-H (N=0) rather than projection-based constrained samplers | Bayesian logistic regression · Bayesian logistic regression, d=100002 | test NLL: 0.601 -> 0.520 | Helped |
| Use OLLA-H (N=0) rather than projection-based constrained samplers | Bayesian logistic regression · Bayesian logistic regression, d=100002 | total CPU time: 1370s -> 82s | Helped |
| Omit the Hutchinson trace correction (N=0) (ablation) | OLLA-H · Bayesian logistic regression, d=100002 | total CPU time: 197s -> 82s | Helped |
| Omit the Hutchinson trace correction (N=0) (ablation) | OLLA-H · Bayesian logistic regression, d=100002 | test NLL: 0.516 -> 0.520 | No clear effect |
| Use 5 Hutchinson probes rather than N=0 (ablation) | OLLA-H · Molecular system, d=90 | equality constraint violation: from a range of ≈ 0.0055 down to ≈ 0.00035 | Helped |
| Use 5 Hutchinson probes rather than N=0 (ablation) | OLLA-H · Molecular system, d=90 | total CPU time: 704s -> 1732s | Hurt |
| Increase landing rate α (ablation) | OLLA · Synthetic 2D examples | squared W2 distance | Mixed |
| Increase boundary repulsion ε (ablation) | OLLA · Synthetic 2D examples | squared W2 distance | Mixed |
| Use OLLA-H rather than OLLA | constrained sampling · Stress-test dimension scaling, d=10 to 700 | CPU time per ESS: around 0.05s/sample; OLLA ... reaching ≈ 1.1s/sample at d = 700 | Helped |
| Increase the number of equality constraints | OLLA and OLLA-H · Stress-test constraint scaling, d=100 | sampling accuracy | Hurt |
| Increase the number of inequality constraints | OLLA-H · Stress-test constraint scaling, d=100 | sampling accuracy | No clear effect |
Surprising findings
- Omitting the Hutchinson-estimated Ito-Stratonovich (mean curvature) correction (N=0) gives comparable sampling accuracy while substantially reducing compute.
- CLangevin's test-function estimate collapses to about 0.2 for P(x1>0) in high dimensions while the other methods stay near 0.5.
Limitations
- Convergence guarantees are only for the continuous-time SDE; no non-asymptotic guarantee for the discretized algorithm is provided.
- Theory requires strong assumptions (compact connected manifold, LSI constant, uniform boundedness of the projected density, and conditions on the boundary behavior), and the boundedness assumption is not proven.
- Large numbers of equality constraints limit the stable landing rate alpha and degrade accuracy at the discretization level.
Experimental setup
Datasets: German Credit
Benchmarks: synthetic 2D constrained manifolds high-dimensional stress test molecular system with realistic potential Bayesian logistic regression with fairness and monotonicity constraints
Metrics: W2 distance energy distance constraint violation CPU time per ESS test negative log-likelihood radius of gyration squared
Baselines: CLangevin CHMC CGHMC
Builds on: Langevin dynamics constrained Langevin (CLangevin) constrained hamiltonian monte carlo landing methods for nonconvex optimization
Closest papers by meaning
- Constrained Sampling with Primal-Dual Langevin Monte Carlo (NeurIPS 2024 · similarity 0.89)
- Non-asymptotic Error Bounds in $\mathcal{W}_2$-Distance with Sqrt(d) Dimension Dependence and First Order Convergence for Langevin Monte Carlo beyond Log-Concavity (ICML 2025 · similarity 0.89)
- Constrained Exploration via Reflected Replica Exchange Stochastic Gradient Langevin Dynamics (ICML 2024 · similarity 0.88)
- Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited (ICLR 2024 · similarity 0.88)
- From stability of Langevin diffusion to convergence of proximal MCMC for non-log-concave sampling (NeurIPS 2025 · similarity 0.88)
- Generalization of noisy SGD in unbounded non-convex settings (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.