Source-linked AI summary
Reflected Anchored Langevin Algorithms
Changwei Tu, Xiaoyu Wang, Yingli Wang, Xicheng Zhang, Lingjiong Zhu
TL;DR
Gradient-based Langevin methods for constrained sampling require differentiable log densities, limiting their applicability to non-differentiable targets. The paper introduces reflected anchored dynamics and its projected Monte Carlo discretization, and proves convergence bounds and iteration complexity in W2, alongside numerical results supporting their use.
Problem
First-order constrained Langevin methods such as PLMC rely on differentiable log densities, limiting their applicability to non-differentiable targets.
Source: §1 · p. 3Method
RALD uses a smooth anchored reference potential and a state-dependent factor that scales the reference drift and noise covariance, with projected Euler–Maruyama discretization yielding RALMC.
Source: §1 · pp. 3–4Results
The paper proves target invariance and convergence guarantees for RALD, W2 discretization bounds and iteration complexity for RALMC, and reports numerical support for nonsmooth constrained sampling.
Source: §1 · p. 4, §4 · p. 35Takeaways & Limitations
The numerical results support RALMC for nonsmooth constrained sampling and show complementary behavior for constant and Gaussian-smoothed reference potentials.
Source: §4 · p. 35The comparison establishes a fixed-stepsize advantage for RALMC in one-step Wasserstein contraction; local expansion alone does not establish that PLMC fails to converge over multiple steps.
Source: §2.5 · p. 23
Abstract
from arXiv · showhide
First order Langevin algorithms for constrained sampling in machine learning, such as projected Langevin Monte Carlo which are based on discretizations of reflected Langevin dynamics, require differentiable log densities that limits their applicability. This paper introduces reflected anchored Langevin dynamics (RALD), a reflected diffusion that converges to non-differentiable targets on constrained domains. The method uses a smooth anchored reference potential and multiplies the drift and noise covariance of its reflected Langevin dynamics by the same state dependent scaling factor. Its Euler-Maruyama discretization with projection gives reflected anchored Langevin Monte Carlo (RALMC) algorithm. We prove explicit convergence bounds and iteration complexity for RALMC in the 2-Wasserstein distance to the target distribution. Numerical experiments are provided to illustrate the theoretical predictions and the empirical performance of the method.
1 Introduction
The introduction addresses constrained sampling when target potentials are non-differentiable, which limits gradient-based Langevin methods. It introduces RALD and RALMC, then presents convergence guarantees and numerical results.
1 Introduction
- Classical overdamped Langevin dynamics requires an everywhere-defined gradient, while prior nonsmooth approaches include smoothing, proximal methods, and subgradient methods.For constrained sampling, projected Langevin methods discretize reflected dynamics; proximal methods are relevant when the corresponding map is tractable.Source: §1 · pp. 1–2
- The scaling factor multiplies both the reference drift and noise amplitude; with a constant reference, the projected scheme needs evaluations of U but not its gradient.On a compact domain, the factor e^(U−U0) is automatically uniformly bounded; the cited unconstrained anchored construction requires U−U0 to be bounded for stability.Source: §1 · pp. 3–4
- RALD modifies reflected Langevin dynamics using an anchored reference potential and state-dependent diffusion to sample constrained targets whose potentials need not be differentiable.Its discretization, RALMC, is a projected Markov chain Monte Carlo algorithm.Source: §1 · pp. 3–4
- The paper proves target invariance for RALD and explicit convergence guarantees in χ2 divergence and, as a corollary, W2 under stated assumptions.For RALMC, it gives W2 discretization bounds under dissipative-drift and constant-reference settings; the latter yields e O(ε^-4) iterations for fixed model parameters, without claiming dimension independence.Source: §1 · p. 4
- Experiments report faster W2 convergence than PLMC for truncated Laplace and Gaussian-mixture targets, plus accuracy and stability differences across reference choices in constrained Bayesian regression.For non-differentiable Laplace, SCAD, and MCP priors, constant-reference RALMC improves accuracy at small stepsizes, while Gaussian-smoothed-reference RALMC remains stable at larger stepsizes where the constant-reference variant can become unstable.Source: §1 · pp. 4–5
2 Main Results
The section develops theoretical guarantees for reflected anchored Langevin dynamics and its projected discretization, including invariant distributions, discretization bounds, and iteration criteria. It also examines constant-reference and smoothed nonsmooth-potential settings, approximation errors, and comparisons with PLMC in stepsizes, spectral gaps, and bottleneck crossings.
2 Main Results
- The main results assume a bounded, closed, convex constraint set with nonempty interior, containing zero and lying within a ball of radius R.The reflected dynamics use outward normal reflection at the boundary.Source: §2 · pp. 5–6
2.1 Continuous time analysis
- Under continuous-time regularity conditions, RALD is well posed and has the Gibbs distribution as its unique invariant distribution.Its transition semigroup has a symmetric Neumann form and a strictly positive, jointly continuous heat kernel; a Poincaré inequality yields quantitative convergence estimates.Source: §2.1 · pp. 6–7
2.2 Discrete time analysis
- Under the stated assumptions, RALMC has a finite-time W2 convergence guarantee, combining continuous-time convergence with a discretization bound.The discretization result assumes an interior-supported initial law and 2m > 1 + 4α; a separate argument covers constant reference potentials without dissipativity. The paper also derives an iteration complexity corollary.Source: §2.2 · pp. 10–12
2.3 The case of constant U0
- With constant U0, RALMC is a zeroth-order projected scheme that requires evaluations of U but not its gradient.The target potential enters through the state-dependent diffusion coefficient, making this choice useful for constrained sampling with non-differentiable or nonconvex potentials.Source: §2.3 · p. 13
- For constant U0, fixed-block projected Euler–Maruyama error is uniform over initial points including the boundary, while heat-kernel smoothing and the spectral gap control error propagation without using nondegeneracy as contraction.The block length is independent of total running time and target accuracy.Source: §2.3 · pp. 13–14
- Theorem 19 bounds the constant-reference discretization error uniformly in total running time by separating mixing and discretization errors, with its constant independent of the number of blocks.The fixed block length is chosen independently of total running time and desired accuracy.Source: §2.3 · pp. 13–14
- For fixed model parameters and block length, RALMC reaches W2 error ε in k = e O(ε^-4) iterations under the stated initial χ2 condition; this accuracy order does not imply polynomial dependence on dimension.The criterion chooses block count to control mixing error and steps per block to control discretization error.Source: §2.3 · pp. 14–15
2.4 Gaussian smoothing reference potential
- Gaussian convolution smooths only the nonsmooth component g; gµ remains ρ-weakly convex, and Uµ is strongly convex on C with constant mf − ρ when mf > ρ.The smoothing estimates also bound U − Uµ and the gradient of Uµ.Source: §2.4 · pp. 16, 18
- A finite coefficient margin ensures the smoothed effective drift and diffusion satisfy the required coefficient assumptions, but Lipschitzness and weak convexity of g alone do not guarantee that perturbation terms vanish.For penalties such as ℓ1, SCAD, or MCP, the margin must be checked for the chosen f, g, µ, and domain.Source: §2.4 · pp. 17–18
- Under the theorem’s smoothing, initialization, and step-size conditions, Monte Carlo RALMC has a W2 error bound combining mixing, discretization, and Monte Carlo errors, and these terms can be made at most ε/3 each.The Monte Carlo iterate error relative to exact-coefficient iterates is bounded uniformly in k.Source: §2.4 · pp. 18–19
2.5 Comparison with PLMC
- Normalizing RALD and PLD to the same stationary-average noise covariance removes arbitrary global time scaling, so any stated advantage comes from spatial variation in the scaling factor.The normalization also makes the comparison independent of additive constants in the potentials.Source: §2.5 · p. 20
- For fixed κ, R, and µ, the stated coefficient condition holds for all sufficiently small K > 0 without restricting δ.This is a coefficient-bound result for the parameterized quadratic-potential comparison.Source: §2.5 · p. 21
- RALMC contracts globally at a fixed normalized stepsize, whereas PLMC expands near zero and requires η = O(δ) for global nonexpansiveness in any fixed bounded stepsize range.The separation concerns one-step Wasserstein contraction; local PLMC expansion does not establish failure to converge over multiple steps.Source: §2.5 · p. 23
- Contraction toward the smoothed target does not by itself bound RALMC’s error to the target; discretization bias and Monte Carlo error need separate estimates.The fixed contraction interval is independent of δ, but this result alone does not establish target-distribution accuracy.Source: §2.5 · pp. 22–23
- The Dirichlet-form comparison gives baseline spectral-gap bounds, but does not establish that normalized RALD has a larger gap than PLD.A strict improvement requires information about how the scaling factor is distributed relative to gradients of relevant test functions.Source: §2.5 · pp. 23–24
- When a_n(x) > 1 at a bottleneck point, RALMC has a larger one-step crossing probability for sufficiently small stepsizes; uniform conditions can guarantee an advantage throughout the bottleneck layer.The finite-stepsize bound accounts for gains from wider proposal variance as well as reductions from scaling and drift terms.Source: §2.5 · pp. 25–26
- For an open landing set, a_n(x) > 1 is necessary and sufficient for a strictly positive exponential rate in the crossing-probability ratio.Both probabilities vanish as η → 0; the result gives sharp logarithmic rates, not prefactors.Source: §2.5 · p. 26
- The crossing comparison is conditional on reaching the bottleneck and does not establish global mixing times or mean transition times.A large probability ratio need not mean a large absolute crossing probability.Source: §2.5 · p. 27
3 Numerical Experiments
The experiments compare RALMC with PLMC on synthetic constrained-sampling targets and constrained Bayesian logistic regression. They examine convergence, movement between mixture modes, and test accuracy under different priors and stepsizes.
3.1 Truncated Laplace distribution sampling
- In the truncated Laplace experiment, both algorithms visually match the target, while RALMC’s W2 curve has a steep initial decrease consistent with larger updates in low-density outer regions.The identified bottleneck is movement through low-density outer regions, rather than passage through a geometrically narrow constraint.Source: §3.1 · pp. 27–28, Figure 3 · p. 28
3.2 Truncated Gaussian Mixture Model
- RALMC with a constant reference converges faster than PLMC in W2 distance for the truncated Gaussian mixture across three stepsizes.The scaling-factor ratio across the density valley is invariant to additive shifts of U, isolating state-dependent acceleration.Source: §3.2 · p. 31, Figure 5 · p. 31
3.3 Constrained Bayesian logistic regression on real data
- RALMC-Const improves test accuracy fastest on MAGIC Gamma Telescope data at the smaller stepsize, while RALMC-GS performs best at the larger stepsize; the same pattern appears on Breast Cancer data.Positive potential values can amplify RALMC-Const's effective update and may cause instability unless the nominal stepsize is small; smoothing controls the approximation error and remains stable at larger stepsizes.Source: §3.3 · p. 33, Figure 6 · p. 33, Figure 7 · p. 34
4 Conclusion
The paper introduces RALD and its projected discretization RALMC for nonsmooth constrained targets, using a smooth anchored reference potential and state-dependent scaling. It provides explicit 2-Wasserstein convergence guarantees and reports experiments supporting RALMC for this setting.
4 Conclusion
- RALD and its projected discretization RALMC use a smooth anchored reference potential and state-dependent scaling for nonsmooth constrained targets.Source: §4 · p. 35
- The analysis gives explicit convergence guarantees and iteration complexity for RALMC in 2-Wasserstein distance.Source: §4 · p. 35
- Numerical results support RALMC for nonsmooth constrained sampling and illustrate complementary behavior of constant and Gaussian-smoothed references.Source: §4 · p. 35
A.1 Proof of Lemma 3
The proof constructs the reflected dynamics through a time change of a base reflected diffusion. Boundedness of the scaling factor controls the time change, while inverse path transformations establish uniqueness in law.
A.1 Proof of Lemma 3
- The proof sets a(x)=e^(U−U0) and uses compactness and continuity to bound it above and away from zero.Source: §A.1 · p. 39
- A clock built from the reciprocal scaling factor and its inverse reparameterizes the base reflected process; the bounds on a control both clocks.Source: §A.1 · p. 39
- The time-changed process retains the reflected boundary behavior and solves the target dynamics, while inverse time changes give uniqueness in law.Source: §A.1 · pp. 39–40
A.2 Proof of Proposition 4
The proof establishes the reflected process's continuity and semigroup properties, then uses weighted Dirichlet-form and kernel results to characterize its transition behavior. These properties support the proposition's claims about the process and its transition density.
A.2 Proof of Proposition 4
- The weighted form is closed, densely defined, Markovian, regular, and strongly local, providing the form framework for the reflected diffusion.Source: §A.2 · p. 40
- The associated semigroup is conservative and agrees with the Neumann martingale problem for the generator.Source: §A.2 · p. 40
- Convexity and comparability of the weighted and unweighted forms yield a jointly continuous, strictly positive kernel, including at the boundary.Source: §A.2 · pp. 40–41
- Coupling base diffusions and comparing their time changes establishes continuity in the initial point and the Feller property.Source: §A.2 · p. 41
- The transition density relative to the target measure is continuous and strictly positive on the compact state space.Source: §A.2 · p. 41
A.3 Proof of Theorem 5
The proof first establishes invariance from self-adjointness and conservativity. Strict positivity of the transition density then yields a uniform minorization, which forces any other invariant probability measure to coincide with the target.
A.3 Proof of Theorem 5
- Self-adjointness of the semigroup and preservation of constants imply that the target measure is invariant.Source: §A.3 · p. 41
- Strict positivity and continuity of the transition density on the compact state space give it a positive uniform lower bound.Source: §A.3 · p. 41
- The lower bound yields a minorization whose residual Markov kernel contracts total variation, proving uniqueness of the invariant measure.Source: §A.3 · p. 41
A.4 Proof of Theorem 6
The proof establishes a finite Poincaré constant for the target and uses the self-adjoint semigroup to control the evolving density in L2(π). Strong continuity then extends the bound to the initial density.
A.4 Proof of Theorem 6
- The density bounds and a Lebesgue Poincaré constant on the bounded convex domain give the admissible constant CP = (wmax/wmin)CC.The convergence argument can use any valid CP, not only this bound.Source: §A.4 · pp. 41–42
- Finite χ2(µ0∥π) places h0 in L2(π), and self-adjointness gives the density evolution ht = Pth0.Source: §A.4 · p. 42
- Strong continuity yields hs → h0 in L2(π) as s → 0, allowing the convergence bound established for positive times to extend to the initial time.The proof applies Grönwall’s inequality on intervals [s,t] with 0 < s < t before taking s to zero.Source: §A.4 · p. 42
A.5 Proof of Corollary 7
The proof bounds total variation using the density relative to the target, then uses a maximal coupling on the bounded domain and Theorem 6 to obtain the corollary’s bound.
A.5 Proof of Corollary 7
- Cauchy–Schwarz applied to ht = dµt/dπ provides the initial estimate for the distance between µt and π.Source: §A.5 · p. 42
- A maximal coupling makes the probability that Y and Z differ equal to TV(µt, π), with both variables lying in the bounded domain C.The proof uses C ⊂ B(0, R).Source: §A.5 · p. 42
- Theorem 6 supplies the bound needed to conclude the corollary.Source: §A.5 · p. 42
A.6 Proof of Lemma 10
The proof reduces the modulus of continuity to grid-interval increments, bounds their maximum through Lp and Brownian-motion estimates, and combines these estimates to complete the lemma.
A.6 Proof of Lemma 10
- The proof chooses p = ⌈log N⌉ and bounds N1/p and p in terms of T/η and log(T/η) before completing the estimate.Here N = ⌈T/η⌉, with T/η ≥ e.Source: §A.6 · pp. 43–44
- For times separated by at most η, the modulus is bounded by twice the largest grid-interval increment Yi.The argument places both times in an interval [iη, (i + 2)η] and applies the triangle inequality.Source: §A.6 · p. 43
- An Lp maximal inequality reduces the maximum over increments to a moment bound for Y0, using the identically distributed increments.Stationary increments and time reversal relate the Brownian suprema to supv∈[0,η] ∥Wv∥; Doob’s inequality and Gaussian moment bounds then control them.Source: §A.6 · p. 43
A.7 Proof of Lemma 11
The proof controls the continuous regulator using interior-ball geometry, then applies Itô’s formula and grid-based estimates to bound the discretization terms.
A.7 Proof of Lemma 11
- The almost-sure interior-ball condition dist(X0, ∂C) ≥ r0 supplies points in C along the regulator’s outward-normal directions.Source: §A.7 · p. 44
- Itô’s formula and the quadratic variation trace bQt express the continuous-path estimate in terms of the drift, martingale, and regulator contributions.The subsequent estimate uses boundedness of ˆXs and X0 in C ⊂ B(0, R), Cauchy–Schwarz, and Itô’s isometry.Source: §A.7 · pp. 44–45
- At grid times tj = jη, the proof bounds the update using the normal-cone condition and sums one-step estimates, including a chi-squared bound for QW/η.The estimates are combined using elementary squared-sum inequalities to finish the proof.Source: §A.7 · pp. 45–46
A.8 Proof of Lemma 12
The proof uses a convex Skorokhod comparison to control the reflected paths, then combines the resulting estimates to establish (2.32).
A.8 Proof of Lemma 12
- The convex Skorokhod comparison uses the normal cone conditions to discard nonpositive terms and prove (A.29).The comparison defines differences of the paths, regulators, and reflected processes.Source: §A.8 · pp. 46–47
- Taking suprema, expectations, and term-by-term substitutions consolidates the estimates to prove (2.32).The derivation also uses parameter bounds including 0 < η ≤ 1, T ≥ e, and log(T/η) ≥ 1.Source: §A.8 · pp. 47–48
- The comparison applies to a càdlàg driver and a continuous driver while retaining the regulator contribution.The drivers agree at grid points, and the continuous driver's coefficients are constant within each grid interval.Source: §A.8 · p. 47
A.9 Proof of Theorem 13
The appendices establish technical conditions and bounds for the reflected algorithms, including regularity, convergence, complexity, contraction, and spectral-gap properties. They also derive estimates for Monte Carlo approximation and Gaussian-proposal crossing rates, with bounds that include boundary initial states.
A.9 Proof of Theorem 13
- Theorem 13’s energy estimate has a nonpositive reflection contribution, yielding inequality (A.51).The proof uses the pointwise normal-cone inequalities and takes expectations after integrating the product formula.Source: §A.9 · pp. 49–50
A.10 Proof of Theorem 14
- Under dimension-independent coefficient assumptions, the proof obtains the stated dimension-scaling result using A, B, H_K, and C_0 bounds.The intermediate orders are A = O(d^2), B = O(d), H_K = O(d), and C_0 = O(d^2).Source: §A.10 · p. 50
A.11 Proof of Corollary 15
- Under the additional scaling assumptions, the proof derives the stated O(d^4) dependence for Corollary 15’s complexity.It uses that T_ε grows at most logarithmically in 1/ε when the other parameters are fixed.Source: §A.11 · p. 51
A.12 Proof of Proposition 17
- Proposition 17’s estimates hold uniformly over every initial point in C, including boundary points.The proof bounds the bridge error and then conditions on a common initial law to obtain (2.45).Source: §A.12 · pp. 52–53
A.13 Proof of Lemma 18
- Lemma 18 proves (2.48) by combining semigroup decay with transport estimates for the smoothed densities.For t ≥ s, the proof notes that the densities are bounded below by m_s before applying the transport estimate.Source: §A.13 · p. 54
A.14 Proof of Theorem 19
- The proof of Theorem 19 derives bounds (2.50) and (2.51) by comparing projected Euler–Maruyama steps with the diffusion semigroup.For (2.51), it additionally uses the initial chi-square condition, Corollary 7, and the stated bounds on α_0 and g_0.Source: §A.14 · pp. 54–55
A.15 Proof of Corollary 20; A.16 Proof of Corollary 21
- Corollary 20’s proof chooses m = O(1 + log(1/ε)) and obtains n and k = mn with the stated ε^-4 dependence.Corollary 21 uses τ = 1/g_0 to obtain m_s* ≥ 1/2 and M_s* ≤ 3/2, and gives the sufficient condition σ ≤ dΛ Lip(U)^2/4.Source: §A.15 · p. 56, §A.16 · pp. 56–57
A.17 Proof of Lemma 24
- Gaussian convolution preserves g’s K-Lipschitz bound and weak convexity parameter ρ while producing a differentiable smoothed function g_μ.The proof also establishes the gradient bound ∥∇g_μ(x)∥ ≤ K.Source: §A.17 · pp. 57–58
A.18 Proof of Lemma 25
- Lemma 25 verifies Assumptions 8 and 9 and the coefficient assumptions of Theorem 13 by establishing the required relations among the constants.In particular, the proof concludes that 2m_μ > 1 + 4α_μ.Source: §A.18 · p. 59
A.19 Verification of the explicit Gaussian smoothing criterion
- The explicit Gaussian smoothing criterion (2.69) implies (2.66), while an alternative sufficient condition ensures (2.66) for every sufficiently small μ > 0.The proof combines bounds to verify the implication and states the alternative small-μ condition.Source: §A.19 · p. 60
A.20 Proof of Lemma 26
- Lemma 26 bounds the 2-Wasserstein distance between ideal and Monte Carlo iterates by estimator-error terms under its coefficient condition.The proof uses a synchronous coupling and closes a one-step recursion before iterating it.Source: §A.20 · p. 63
A.21 Proof of Theorem 27
- Theorem 27 combines continuous-time mixing, discretization, and Monte Carlo errors to obtain an overall error at most ε, with Monte Carlo error O(N^-1/2).For fixed model and smoothing level, the two quantities in (2.75) and (2.76) are O(N^-1), and the proof chooses the stepsize and sample count to control the three errors.Source: §A.21 · pp. 64–65
A.22 Proof of Lemma 28
- Lemma 28 derives the three coefficient estimates in (2.87) under condition (2.86), using convexity, Gaussian integration by parts, and calculus bounds.The estimates concern the normalized scaling factor and derivatives of the drift and diffusion coefficients.Source: §A.22 · p. 65
A.23 Proof of Proposition 29
- Proposition 29 establishes a strict contraction for the RALMC transition, yielding a unique fixed point and a k-step bound, with contraction constants independent of δ.The proof obtains the contraction from the one-step Wasserstein bound and applies the Banach fixed point theorem.Source: §A.23 · p. 66
A.24 Proof of Theorem 30
- Theorem 30 shows that global nonexpansiveness of PLMC forces a stepsize restriction of order O(δ), with a constant independent of δ.The proof also derives the RALMC assertion from the contraction bound when the stepsize meets the stated condition.Source: §A.24 · pp. 66–68
A.25 Proof of Proposition 31
- Proposition 31 bounds the RALD spectral gap between the minimum and maximum scaling factors multiplied by the PLD spectral gap.The Rayleigh-quotient argument does not require either infimum to be attained.Source: §A.25 · p. 68
A.26 Proof of Proposition 32
- The proof confirms η(x, D+) > 0 and uses bounds on drift penalties over B to obtain the uniform estimate (2.101).The positivity follows from strict positivity of the Gaussian density and |D+| > 0.Source: §A.26 · p. 69
A.27 Proof of Corollary 33
- The Gaussian-proposal crossing-rate comparison yields Equations (2.102)–(2.103), with a strictly positive difference exactly when a_n(x) > 1.The final uniform bound follows when r_x ≥ r and a_n(x) ≥ ρ.Source: §A.27 · p. 70