Source-linked AI summary
Penalized Nonreversible Langevin for Constrained Sampling
Pervez Ali, Weihao Dong, Xiaoyu Wang
TL;DR
Constrained sampling is needed when feasibility or prior information restricts the parameter space, but hard constraints complicate direct use of Langevin methods. This paper combines squared-distance penalization with compatible skew perturbations and analyzes full- and stochastic-gradient algorithms. It establishes error guarantees and shows that curvature-tuned perturbations can reduce the sufficient iteration bound in a quadratic model.
Problem
Hard constraints prevent direct application of unconstrained Langevin methods, although constrained targets arise when prior information or feasibility requirements restrict parameters.
Source: §1 · p. 1Method
The algorithms combine a squared-distance penalty with constant or compatible state-dependent skew drift perturbations that preserve the penalized target.
Source: §1 · p. 2Results
For quadratic potentials, a penalty-tuned skew perturbation gives a sufficient iteration bound logarithmic in the curvature ratio; experiments also report faster initial convergence and improved sampling under strong penalization.
Source: §1 · p. 3, §5 · p. 28Takeaways & Limitations
The quadratic analysis and experiments emphasize designing the nonreversible perturbation together with the penalty parameter.
Source: §5 · p. 28A nonzero skew perturbation alone does not guarantee strict acceleration, which depends on coupling between the skew term and Hessian directions of different curvature.
Source: §3.1 · p. 8
Abstract
from arXiv · showhide
We propose penalized nonreversible Langevin algorithms for sampling from $\pi(x)\propto e^{-f(x)}\mathbf 1_{\mathcal C}(x)$, where $\mathcal C\subset\mathbb R^d$ is a compact convex set. The algorithms combine a squared distance penalty with constant or compatible state dependent skew symmetric perturbations that preserve the penalized Gibbs distribution. For smooth, possibly nonconvex $f$, we derive nonasymptotic total variation bounds for the full gradient algorithm under a log Sobolev inequality. When unbiased stochastic gradients are available, we establish $2$-Wasserstein bounds under global contraction and Lipschitz conditions on the full drift in an adapted quadratic metric. For a fixed penalty parameter, the error relative to the penalized Gibbs distribution decays exponentially to an $\mathcal{O}(\sqrt{\eta})$ neighborhood, where $\eta$ is the stepsize. We also bound the discrepancy between the penalized Gibbs distribution and the constrained target. In a two dimensional quadratic model, we establish nonreversible acceleration by tuning the skew perturbation to the curvature imbalance induced by penalization. With the target accuracy and smaller curvature fixed and initial Wasserstein distances uniformly bounded, tuning the skew perturbation improves the sufficient Euler iteration bound from linear to logarithmic in the curvature ratio. Numerical experiments evaluate the algorithms on constrained Bayesian regression, classification, neural networks, and truncated sampling, and examine the acceleration mechanism in a stochastic quadratic model.
1 Introduction
The paper addresses constrained sampling by combining squared-distance penalization with nonreversible Langevin drift. It establishes guarantees for full- and stochastic-gradient algorithms and analyzes when tuning the skew perturbation accelerates sampling.
1 Introduction
- Squared-distance penalization replaces the hard constraint with a smooth potential on R^d, while the iterates evolve without projection.The penalty improves approximation of the constrained target as its parameter decreases, but also increases potential smoothness and tightens the stepsize requirement.Source: §1 · p. 2
- Bounded Lipschitz skew perturbations preserve the penalized target when they satisfy the stated compatibility condition.The paper separates convergence to the penalized law, approximation of the constrained target, and stochastic-gradient noise.Source: §1 · p. 2
- For the full-gradient algorithm, entropy arguments yield nonasymptotic total-variation bounds under a log-Sobolev inequality.Combining those bounds with target-approximation results gives a guarantee for the constrained law.Source: §1 · p. 3
- For stochastic gradients, global contraction of the full drift yields Wasserstein bounds in strongly convex and dissipative nonconvex cases.The analyses cover constant and state-dependent skew matrices; the latter requires additional fourth-moment control.Source: §1 · p. 3
- A tuned skew perturbation gives a sufficient Euler iteration bound logarithmic in the curvature ratio for the stated quadratic setting.The construction extends by pairing Hessian eigenvectors to high-dimensional block matrices, and also applies to skew circulant matrices when their Fourier planes are Hessian-invariant.Source: §1 · p. 3
2 Unadjusted Penalized Nonreversible Langevin Dynamics
This section analyzes unadjusted penalized nonreversible Langevin dynamics, including a full-gradient total-variation guarantee under a log-Sobolev condition. It also specializes the analysis to a squared-distance penalty and gives stepsize and iteration choices under the stated assumptions.
2 Unadjusted Penalized Langevin Dynamics
- Theorem 7 gives a nonasymptotic guarantee for the law after K steps, assuming the penalized target satisfies a log-Sobolev inequality and the stated regularity conditions.For state-dependent J, the theorem also requires boundedness, Lipschitz continuity, compatibility, and a finite fourth moment for the initialization.Source: §2 · p. 5
- For state-dependent J, the theorem requires skew symmetry, boundedness, Lipschitz continuity, compatibility, and finite fourth moment of the initial law.The constant-J case instead uses the stated constant-matrix stepsize restriction.Source: §2 · p. 5
- The section specializes the theorem to the squared-distance penalty using δ = ε^4 for sufficiently small ε.The supplied passage identifies this penalty choice but does not provide the resulting bound's full expression.Source: §2 · p. 6
3 Stochastic Penalized Nonreversible Langevin Dynamics
This section develops convergence analyses for stochastic penalized nonreversible Langevin dynamics in an adapted metric and examines how skew-perturbation tuning affects spectral rates and mixing in quadratic models. It also considers higher-dimensional extensions under block and invariance conditions.
3.1 Construction of the PJ Metric
- For each αJ below the local spectral rate βJ, an adapted positive definite metric yields local contraction, but acceleration requires suitable curvature coupling and global control of the full drift.A nonzero skew term alone does not guarantee a strict spectral gain; the metric must also satisfy the global contraction condition for convergence guarantees.Source: §3.1 · p. 8
3.2 Strongly Convex Case
- The strongly convex analysis gives PNSGLD convergence guarantees under gradient-noise, drift-contraction, and smoothness assumptions, with a compatible metric supporting the stated bounds.The section also bounds the stochastic-gradient noise and requires a finite initial potential-gap moment.Source: §3.2 · p. 11
3.3 Nonconvex Case
- For the PNSGLD iterate after K steps, Theorem 16 includes the penalty-approximation error and bounds distance to π; Theorem 18 bounds distance to πδ, and if W2(πδ,π)≤ε then W2(νK,π)≤2ε.Source: §3.3 · pp. 12–13
3.4 Acceleration by Tuning the Skewed Coefficient
- In the two-dimensional quadratic model, tuning the skew coefficient equalizes the eigenvalues, raises the slowest rate to (λ + Λδ)/2, and removes penalty-induced spectral stiffness.A fixed nonzero coefficient gives only constant-factor acceleration and leaves stiffness diverging as δ approaches zero.Source: §3.4 · p. 15
- For fixed nonzero a and tuned aδ, Proposition 22 gives fixed, tuned, and reversible chains stepsizes satisfying (3.53) and bounds for sufficiently small δ, under its globally quadratic setting and finite-second-moment initial laws.Source: §3.4 · p. 16
- For quadratic models in dimension d, the two-dimensional estimates extend through the largest block contraction and summed squared invariant biases, allowing correlated initial blocks and reversible unpaired coordinates.The construction pairs Hessian eigenvectors with skew blocks under a common stable stepsize; for skew-circulant matrices, Fourier planes must be invariant under the quadratic Hessian.Source: §3.4 · p. 17
4 Numerical Experiments
Numerical experiments assess nonreversible perturbations across regression, truncated-distribution, neural-network, and quadratic settings. They examine early sampling or predictive performance and the effects of penalty-dependent skew choices in quadratic models.
4.1 Constrained Bayesian Linear Regression
- At iteration 50, PNSGLD’s unnormalized sliced W2 distance to πC is 0.0474 versus 0.1367 for PSGLD, a reduction of about 65%; at iteration 1000, distances are 0.0224 versus 0.0300.PNSGLD decreases sampling error faster initially, but PSGLD has the smaller terminal distance at the common fixed stepsize.Source: §4.1 · pp. 18–19, Figure 1 · p. 19
4.2 Constrained Bayesian Logistic Regression
- Five of twelve early accuracy comparisons remained significant after Holm adjustment, with mean gains of about 0.32–0.55 percentage points; four of those gains persisted after halving the stepsize and doubling iterations.Final accuracies were close across methods, while block perturbation improved terminal accuracy and NLL under the Titanic sublevel constraint.Source: §4.2 · pp. 20–21, Table 1 · p. 21
4.3 Penalized Truncated Laplace Sampling
- At δ = 0.005, tridiagonal PNSGLD reduces terminal mean empirical W2 distance to the constrained reference from 0.5015 to 0.4298, about 14.3%, under the same iteration budget.Nonreversible methods have smaller average distances at every tested penalty; for smaller penalties, distances between πδ and πC approach the distance between independent constrained-reference samples.Source: §4.3 · pp. 22, 24, Figure 3 · p. 22, Table 2 · p. 23
4.4 Constrained Bayesian Neural Networks
- On MAGIC, state-dependent PNSGLD raises accuracy from 84.48% to 85.24%, lowers NLL from 0.3724 to 0.3597, and raises AUROC from 0.8977 to 0.9033.On Rice, circulant perturbation lowers NLL from 0.1894 to 0.1822; accuracy is 93.61% versus 93.92% for PSGLD, and fewer than 1% of retained states lie outside C in every configuration.Source: §4.4 · p. 24, Table 3 · p. 25
4.5 Spectral Acceleration for Small Penalty Parameters
- The penalty-dependent choice equalizes both spectral rates at (1 + Λδ)/2, while the slow rate for fixed a = 1 approaches two as δ decreases.Figure 7 illustrates the spectral prediction. The experiment initializes every penalty setting at W2 distance one and evaluates convergence to a target accuracy of 0.05.Source: §4.5 · pp. 26, 28, Figure 7 · p. 26, Figure 8 · p. 27
- At δ = 5 × 10^-4, PNSGLD with a = a_δ reaches prescribed accuracy in 76 iterations versus 38315 for PSGLD, an approximately 500-fold reduction.Across all eight penalty values, it required 75–76 iterations.Source: §4.5 · p. 28
- PSGLD and fixed-coefficient PNSGLD iteration counts grow approximately linearly with Λδ, while the fixed coefficient reduces required counts by a factor approaching 1.50.This agrees with the spectral gain after accounting for the selected stepsizes, since 2q_fixed/q_rev ≈ 1.50.Source: §4.5 · p. 28
- All methods meet the same stationary-error tolerance, so the improvement comes from more effective nonreversible perturbation selection rather than relaxed accuracy.The results support favorable penalty dependence established in Proposition 22 and show acceleration in this stochastic-gradient quadratic experiment.Source: §4.5 · p. 28
5 Conclusion
The paper develops penalized nonreversible Langevin algorithms and nonasymptotic bounds for full- and stochastic-gradient discretizations, combining convergence to the penalized distribution with approximation of the constrained target. Numerical experiments illustrate benefits across constrained sampling and learning, while the quadratic analysis shows improved iteration bounds when the skew perturbation adapts to penalty-induced curvature.
5 Conclusion
- Adapting the skew perturbation to penalty-induced curvature improves the sufficient iteration bound for quadratic potentials.Source: §5 · p. 28
- Experiments show faster initial convergence in constrained linear regression, improved sampling under strong penalization, and predictive benefits from suitable perturbations in statistical learning.Source: §5 · p. 28
A Technical Details
- The minimizer of the penalized potential has norm at most ∥∇f(0)∥/µ, uniformly over δ > 0, under the stated strong-convexity assumptions.The lemma also bounds this norm by (1 + c)R.Source: A Technical Details · p. 34
- For the target approximation result, δ = ε^4 is used, with α = 0 in the strongly convex case and α = ε^2 in the merely convex case.The result assumes the stated representation and, in the merely convex case, an additional condition.Source: A Technical Details · p. 34
- The technical bounds give Lδ = O(δ^-1), mδ = Θ(δ^-1), and bδ = O(δ^-1), with constants depending on problem data.Source: A Technical Details · p. 34
A.1 Proof of Lemma 6
The proof establishes invariance of the penalized Gibbs law for the nonreversible diffusion, then derives full-gradient total-variation guarantees and combines them with target approximation. Its entropy argument controls the discretization error using moment bounds, including additional terms for state-dependent perturbations.
A.1 Proof of Lemma 6
- The penalized Gibbs law πδ is invariant for the diffusion, using skew symmetry and the compatibility condition on J.Source: §A.1 · p. 35
A.2 Proof of Theorem 7
- The discretization proof controls moment and drift errors; state-dependent J adds a Lipschitz-dependent term that is unnecessary when J is constant.Source: §A.2 · p. 39
- The entropy argument yields a bound for the Euler iterate relative to πδ, with Pinsker’s inequality converting the density bound into total variation.Source: §A.2 · p. 39
A.3 Proof of Proposition 8
- The target-level argument applies Theorem 7 with δ = ε^4 and uses bounds on the step-size restrictions to obtain the stated accuracy guarantee.Source: §A.3 · pp. 39, 41
A.4 Proof of Proposition 10
These proofs establish an adapted-metric contraction improvement for the quadratic model and control one-step discretization errors for constant and state-dependent perturbations. The latter require additional bounds when J varies with the state.
A.4 Proof of Proposition 10
- When βJ exceeds λmin(H∗), an αJ between them yields a strict improvement in the adapted metric.Source: §A.4 · p. 43
A.5 Proof of Lemma 12
- The contraction proof bounds the difference between the Euler maps through the drift difference D and the stepsize condition.Source: §A.5 · p. 43
A.6 Proof of Lemma 13
- The one-step error bound treats constant and state-dependent J separately: the state-dependent case retains an additional term controlled by the Lipschitz constant of J.Source: §A.6 · pp. 44–46
A.7 Proof of Lemma 15
The stochastic-gradient proof first establishes a contracting recursion for expected penalized-potential error, then couples the Euler iterates to a stationary diffusion to bound Wasserstein distance. The coupling uses shared noise and controls the one-step remainder.
A.7 Proof of Lemma 15
- The expected penalized-potential error contracts geometrically, up to a stepsize-dependent remainder involving stochastic-gradient error and dimension.Source: §A.7 · p. 48
A.8 Proof of Theorem 16
- Shared Brownian increments and independent gradient noise support the coupling argument under the stated assumptions.Source: §A.8 · p. 48
- The Wasserstein proof couples Euler iterates to a stationary process with invariant law πδ, then bounds their distance through the coupling cost.Source: §A.8 · p. 50
A.9 Proof of Theorem 18
The proof reuses the synchronous coupling for the present assumptions and concludes the bound in (3.35).
A.9 Proof of Theorem 18
- The synchronous coupling argument applies with an arbitrary finite-cost initial coupling of ν0 and πδ.The proof invokes target moments from Lemma 23 and retains the coupling notation used for Theorem 16.Source: §A.9 · p. 50
- Conditional unbiasedness and skew symmetry support the coupling estimate under the present assumptions.The drift and remainder estimate remains valid because it uses only Lemmas 12 and 13.Source: §A.9 · pp. 50–51
- Taking square roots and applying norm equivalence proves (3.35).The estimate is obtained by iterating the coupling inequality and minimizing over the initial coupling.Source: §A.9 · p. 51
A.10 Proof of Corollary 19
The proof derives the complexity bound in Corollary 19 from (3.35), then establishes eigenvalue properties used for Proposition 20.
A.10 Proof of Corollary 19
- The stepsize in (3.36) is used to bound the discretization contribution in the complexity argument.The proof combines this with the iteration bound to obtain (3.39).Source: §A.10 · pp. 51–52
- The complexity proof bounds the two error terms separately, making the discretization term at most ε/2 and choosing K to control the other term.The resulting iteration choice yields (3.39), with a logarithmic factor hidden in the stated bound.Source: §A.10 · pp. 51–52
A.11 Proof of Proposition 20
- For sufficiently small δ, the characteristic polynomial has positive discriminant, and its two roots are positive.The proof rationalizes the smaller root and uses the root sum to establish the second limit in (3.44).Source: §A.11 · p. 52
A.12 Proof of Proposition 21
These proofs establish stability and convergence bounds for quadratic recursions and derive supporting moment and smoothness estimates for the algorithms.
A.12 Proof of Proposition 21
- The proof establishes stability of the recursion from its eigenvalue bounds and applies the discrete Lyapunov theorem.The argument treats a fixed coefficient, zero, and the tuned coefficient.Source: §A.12 · pp. 53–54
- The centered recursion has invariant law N(0, Σδ,a), and iteration converges from every initial law to this Gaussian.The covariance convergence is used to compare the limiting covariance with the target covariance.Source: §A.12 · p. 53
A.13 Proof of Proposition 22
- For the tuned coefficient, the proof bounds the matrix power and uses the resulting conditions on K to establish the three assertions of Proposition 22.The proof couples the centered chain with a stationary copy using the same Gaussian increments.Source: §A.13 · pp. 54–55
B Proof Details of Supporting Lemmas
- The supporting lemmas establish moment bounds under dissipativity and identify Lyapunov recursions for Euler iterates.The section also supplies projection and smoothness arguments for the preceding lemmas.Source: §B.1 · pp. 55–56, §B.3 · p. 57, §B.4 · p. 57
B.2 Proof of Lemma 24
- Conditional unbiasedness and skew symmetry are used to control the second moment of the update.The proof applies smoothness and iterates a geometric recursion to obtain the stated moment bound.Source: §B.2 · pp. 56–57
B.5 Proof of Lemma 28
The proof bounds the target discrepancy by separating changes to the constraint set from the squared-distance penalty, and establishes constants uniform in α for Lemma 29.
B.5 Proof of Lemma 28
- For fixed dimension and problem data, the proof combines the constraint-set and distance-penalty errors using δ = ε^4 and α ∈ {0, ε^2}.The argument separately estimates replacing C by Cα and replacing the constraint with the squared-distance penalty.Source: §B.5 · pp. 58–60
- The proof obtains a bound on the constraint-set error by comparing the Gibbs laws on Cα and its complement.For α = 0, C0 = C and π0 = π, so this error is zero.Source: §B.5 · p. 58
B.6 Proof of Lemma 29
- For every α ≥ 0, Lemma 25 gives the same constants (ℓ, mS, bS) = (4, 1, R^2); all bounds are uniform in α, with implied constants depending only on R, L, |f(0)|, and ∥∇f(0)∥.Source: §B.6 · p. 60
C.1 Moment bounds under dissipativity
- Dissipativity provides the moment control used in the supporting bounds.The proof uses radial integration and integration by parts to establish the moment estimates.Source: §C.1 · pp. 61–62
C.2 Lyapunov bounds for the Euler scheme
The appendix develops Euler-scheme Lyapunov bounds, an entropy estimate for the Euler interpolation, and a uniform log Sobolev bound for the penalized target. The stated results rely on stepsize and regularity conditions, and the log Sobolev bound is independent of α and δ under its stated condition.
C.2 Lyapunov bounds for the Euler scheme
- The Euler transition has stated Lyapunov bounds when the stepsize satisfies 0 < η ≤ 1 ∧ [Lδ(1 + MJ)2]−1, with an additional condition for the further bound.The lemma allows measurable skew-symmetric J with operator norm bounded by MJ, including constant and state-dependent J.Source: §C.2 · p. 62
C.3 Entropy estimate for the Euler interpolation
- The entropy estimate considers KL divergence to the penalized Gibbs law for an Euler interpolation initialized at a law with finite second moment and finite relative entropy.The interpolation uses drift −Bδ(Z) and Brownian noise; compatibility and skew symmetry make the perturbation divergence-free and orthogonal to ∇Vδ.Source: §C.3 · pp. 64–65
C.4 A uniform log Sobolev bound for the penalized target
- The penalized target admits the stated uniform log Sobolev bound, which is independent of α and δ whenever the specified condition on µα holds.The bound is presented under geometric and smoothness assumptions on the penalized target.Source: §C.4 · p. 66