PaperlayerView exact revision on arXiv

Source-linked AI summary

Poisson-Corrector Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling

Yuchen Xin, Zhihua Zhang

arXiv:2609.12594v1cs.LG

TL;DR

For MYULA, quantifying invariant-measure error is difficult because smoothing and discretization interact, and fixed-smoothing estimates need quantified dependence on λ. The paper uses a Poisson corrector with active-trace and shared-noise curvature estimates, obtaining an invariant-measure bias bound and a sufficient ε^-4/3 iteration complexity.

  • Problem

    The interaction between smoothing and discretization makes invariant-measure error difficult to quantify, and fixed-λ estimates require quantified dependence on λ.

    Source: §1 · pp. 2–3

  • Method

    A discrete Poisson corrector combines active-trace estimates with a shared-noise curvature estimate to control average rather than worst-case curvature.

    Source: §1 · p. 3

  • Results

    The invariant-measure bias is O(h) + ˜O(h^3/4), with error coefficients depending only logarithmically on λ^-1; the resulting sufficient iteration complexity is ˜O(ε^-4/3).

    Source: §9 · p. 20

  • Takeaways & Limitations

    For the stated strongly convex smooth component and convex Lipschitz nonsmooth term, these bounds apply to classical MYULA.

    Source: §9 · p. 20

    The iteration complexity is stated for fixed model parameters and initialization.

    Source: §9 · p. 20

Abstract

from arXiv · show

We study the classical Moreau--Yosida unadjusted Langevin algorithm (MYULA) for $\pi(\,\mathrm{d} x)\propto e^{-f(x)-g(x)}\,\mathrm{d} x$, where $f\in C^2(\mathbb{R}^d)$ is $m$-strongly convex with $L_f$-Lipschitz gradient and $g:\mathbb{R}^d\to\mathbb{R}$ is convex and globally $G$-Lipschitz. For the Moreau-smoothed target $\pi_\lambda$ and the MYULA invariant law $\widehat\pi_{\lambda,h}$, we prove \[ \sqrt m\,W_2(\pi_\lambda,\widehat\pi_{\lambda,h}) =O(h)+\widetilde O(h^{3/4}) \] under $0<h(L_f+\lambda^{-1})\le c$, with only logarithmic dependence on $\lambda^{-1}$ in the error coefficients. Combining this estimate with the Moreau approximation bias yields $\widetilde O(\varepsilon^{-4/3})$ iterations to achieve $\sqrt m\,W_2(\mu_N,\pi)\le\varepsilon$, for fixed model parameters and initialization. The proof combines a discrete Poisson corrector with active-trace estimates and a shared-noise bound for the exact--Euler two-point curvature.

1 Introduction

The paper analyzes classical MYULA for composite targets with a smooth strongly convex term and a convex Lipschitz term, focusing on the interaction between Moreau smoothing and discretization. It combines a discrete Poisson corrector with active-trace and shared-noise curvature estimates to bound invariant-measure error and derive an end-to-end complexity guarantee.

1 Introduction

  • The target combines an m-strongly convex function with L_f-Lipschitz gradient and a convex, globally G-Lipschitz term that may be nonsmooth.Examples of the latter include ℓ1 and total-variation penalties.Source: §1 · p. 2
  • As λ decreases, the smoothed target approaches the original, but its global smoothness bound increases and the Euler invariant law generally differs from πλ.Accuracy for the original target therefore requires controlling Moreau approximation bias, Euler invariant-measure bias, and convergence from the initial distribution.Source: §1 · pp. 2–3
  • The invariant-measure bound has error coefficients with only logarithmic dependence on λ^-1, although the usual step-size restriction remains.The constants depend on model parameters but not on h or λ.Source: §1 · p. 3
  • For fixed model parameters and initialization, the paper derives a sufficient iteration-complexity bound after choosing λ=ε/G² and the step size specified in Theorem 5.2.The supplied passage does not state the resulting exponent; it notes that eO suppresses logarithmic factors.Source: §1 · p. 3
  • The proof compares MYULA with the exact Langevin diffusion using shared noise and a discrete Poisson corrector that captures cancellations between successive local errors.Active-trace estimates and a shared-noise curvature estimate control average curvature rather than applying the worst-case λ^-1 bound for gλ throughout.Source: §1 · p. 3
  • MYULA’s transition is unchanged: λ and h stay fixed during each run, no Metropolis correction is added, and complexity counts exact proximal evaluations rather than their internal solve cost.Each iteration uses one gradient evaluation of f and one proximal evaluation of g.Source: §1 · pp. 2–3

2 Related Work

The related work situates MYULA among proximal samplers and two analyses that supply key ingredients: active-trace bounds and Poisson-corrector estimates. The paper refines the latter for the smoothing dependence, while distinguishing its classical MYULA setting from other transition kernels and oracle models.

Moreau regularization and proximal sampling

  • Pereyra developed proximal MCMC methods, and Durmus et al. introduced MYULA; both connect sampling with proximal operations used in convex optimization.Durmus et al. offer a complementary Wasserstein-optimization viewpoint and analyze smooth and nonsmooth Langevin variants.Source: §2 · pp. 3–4

Active-trace analysis of MYULA

  • Xin and Zhang [13] use reference heat-path active traces for structured penalties and obtain eO(ε^-2) end-to-end complexity; this paper instead uses corrected synchronous coupling and shared-noise curvature estimates for general convex Lipschitz g.Their approach requires geometric verification for the examples treated, whereas the shared-noise estimate controls the actual exact–Euler two-point curvature.Source: §2 · p. 4

Poisson correctors and a direct MYULA benchmark

  • For MYULA, direct use of the global-smoothness estimate gives eO(ε^-2) accuracy dependence, while refining curvature terms in the corrector analysis gives eO(ε^-4/3) under this paper’s assumptions.The gain concerns smoothing dependence, not the order in h for a fixed smoothed target.Source: §2 · p. 4

Other composite samplers

  • Other composite samplers use different transitions or guarantees: proximal stochastic-gradient Langevin sampling has eO(ε^-2) Wasserstein complexity, while a Metropolis-corrected method gives polylogarithmic total-variation complexity under its assumptions.The latter requires a proximal sampling oracle and associated normalizing constants; this paper instead studies classical MYULA with exact proximal evaluations and √m W2 error for the original target.Source: §2 · p. 4

Poisson correctors and a direct MYULA benchmark

  • The mollification argument extends the estimate from smooth potentials to C1,1 potentials by preserving the strong-convexity and smoothness bounds and passing to the limit.The passage states that synchronous contraction gives W2 convergence of both diffusion and Euler invariant laws.Source: §2 · p. 4

3 Preliminaries

The preliminaries establish notation for measures, norms, and matrix order, then introduce Moreau regularization and its weak second-order structure. The envelope has a Lipschitz gradient, whose weak derivative is used to define the Moreau active trace.

3.1 Basic notation

  • The notation section sets the domain as Borel measures on R^d, uses the Euclidean norm and inner product, and introduces quadratic Wasserstein distance and matrix order.It also specifies Lp norms for vector-valued functions.Source: §3.1 · p. 5

3.2 Moreau–Yosida regularization and weak second-order structure

  • For convex g, Moreau regularization gives gλ a continuously differentiable, Lipschitz gradient with Lip(∇gλ) ≤ λ^-1.The displayed passage also points to cocoercivity and standard Moreau theory.Source: §3.2 · p. 5
  • The almost-everywhere derivative of ∇gλ represents its weak derivative; following Xin and Zhang [13], the paper calls aλ the Moreau active trace.The weak-Hessian properties and integration-by-parts identities are collected in Appendix A.Source: §3.2 · p. 5

4 Problem Setup and Standing Assumptions

The paper studies a composite target with a smooth strongly convex component and a convex Lipschitz component, then applies MYULA to the Moreau-smoothed potential.

4 Problem Setup and Standing Assumptions

  • The target combines f, which is C^2, m-strongly convex, and has an Lf-Lipschitz gradient, with convex globally G-Lipschitz g.Source: §4 · p. 6
  • The smoothed potential Uλ remains m-strongly convex, is C1,1, and has an Lλ-Lipschitz gradient.Source: §4 · p. 6
  • MYULA is the Euler scheme for the Langevin diffusion with potential Uλ, with transition kernel Qλ,h.Source: §4 · p. 6

5 Main Results

The main results address fixed-smoothing invariant-measure bias and end-to-end complexity under the standing assumptions, including a specialization to fixed model parameters and initialization.

5 Main Results

  • R controls the stationary L2 norm of the drift and the mean active trace, while K controls all stationary drift moments.Source: §5 · p. 6
  • Theorem 5.1 states a fixed-smoothing invariant-measure result and gives Qλ,h a unique invariant distribution in P2(Rd).Source: §5 · p. 6
  • Theorem 5.2 gives an end-to-end complexity result and specifies a sufficiently small universal constant for its parameter choice.Source: §5 · pp. 6–7
  • For fixed model parameters and initialization, the theorem states a specialization of the iteration bound.Source: §5 · p. 7

6 Proof of the Main Results

The proof of the two main theorems isolates a corrector decomposition and a two-point curvature estimate, then uses them in the fixed-smoothing and end-to-end arguments.

6.1 The two-point drift matrix

  • Aλ(x, y) is named the two-point drift matrix and is used in the exact two-point drift identity.Source: §6.1 · pp. 7–8

6.2 A single corrector and the two technical inputs

  • The corrector is an L2(πλ; Rd) integral limit, and the proof relies on its defining relation and stated estimates alongside two technical propositions.Source: §6.2 · pp. 8–9

6.3 A one-step matrix inequality

  • The one-step matrix estimate applies to symmetric A with mI ⪯ A ⪯ LI when 0 < hL ≤ 1.Source: §6.3 · p. 9

6.4 Proof of the fixed-smoothing theorem

  • The fixed-smoothing proof couples MYULA and the exact diffusion using the same Gaussian increments, then identifies the limiting Euler law through a unique invariant distribution and W2 convergence.Source: §6.4 · pp. 9–11

6.5 Proof of the end-to-end complexity theorem

  • The end-to-end proof combines the Moreau bias bound with the fixed-smoothing bound and uses the triangle inequality to obtain its stated accuracy result.Source: §6.5 · p. 11
  • For fixed model parameters and an initialization in P2(Rd), the proof uses the resulting iteration bound to conclude the fixed-parameter specialization.Source: §6.5 · p. 11

7 Stationary Estimates and the Discrete Poisson Corrector

The section develops stationary drift and active-trace estimates, constructs a discrete Poisson corrector, and uses it to decompose local error and bound martingale variance.

7.1 Stationary active trace and drift moments

  • The stationary estimates control the mean active trace through weak integration-by-parts identities and establish stationary drift-moment bounds.Source: §7.1 · p. 12

7.2 The reversible semigroup and the corrector operator

  • The exact diffusion's semigroup is reversible under πλ, and the paper uses this semigroup to define its corrector operator.Source: §7.2 · p. 13

7.3 Construction and moments of the corrector

  • The discrete corrector χh is the unique mean-zero L2 solution of the stated relation, with moment estimates obtained from the corrector construction and multiplier bound.Source: §7.3 · pp. 13–14

7.4 Martingale decomposition of the local error

  • The local error is decomposed into a telescoping corrector increment and a martingale increment, following the cited Poisson-decomposition approach [10].Source: §7.4 · p. 15

7.5 Short-time crossing and the martingale variance

  • A short-time crossing estimate and the corrector-increment estimate are combined to establish the martingale variance bound in Proposition 6.2.Source: §7.5 · pp. 15–16

8 Shared-Noise Two-Point Curvature and Feedback

The section estimates shared-noise two-point curvature at one step, then uses that estimate and a Hölder product bound to control curvature feedback across steps.

8.1 A one-step shared-noise trace estimate

  • Proposition 8.1 concerns the first moment of shared-noise two-point curvature under hLλ ≤ c.The Gaussian endpoint and Brownian bridge are independent, and the exact and Euler endpoints use the same Gaussian vector conditional on the bridge.Source: §8.1 · pp. 16–17
  • An averaged Hessian along the segment between the exact and Euler endpoints maps their displacement to the difference of their Moreau-gradient values.The proof establishes the estimate in the smooth case and then passes to the C1,1 Moreau envelope by mollification.Source: §8.1 · pp. 18–19

8.2 From the one-step trace estimate to curvature feedback

  • For curvature feedback, the proof applies a Hölder product bound without assuming independence between the accumulated trace S_k and χ_h(X_kh).The application sets C = χ_h(X_kh), S = S_k, L = λ^-1, and B = CG; it uses H = ChK, a = 2, and p bounded logarithmically in e + L/B0.Source: §8.2 · pp. 19–20

9 Conclusion

The conclusion summarizes MYULA error bounds for a smooth strongly convex component and a convex Lipschitz nonsmooth term. Combining the invariant-measure estimate with Moreau bias and Wasserstein contraction gives a sufficient end-to-end iteration complexity.

9 Conclusion

  • The invariant-measure bias is O(h) + eO(h3/4), with error coefficients depending only logarithmically on the inverse smoothing parameter.The bound is for classical MYULA with a smooth strongly convex component and a convex Lipschitz nonsmooth term.Source: §9 · p. 20
  • Combining the bias estimate with Moreau approximation bias and Wasserstein contraction yields sufficient eO(ε^-4/3) iterations for √m W2(µN, π) ≤ ε.The complexity holds with model parameters and initialization fixed.Source: §9 · p. 20
  • The conclusion attributes the invariant-measure bound to a discrete Poisson corrector together with active-trace and shared-noise curvature estimates.The estimates apply to classical MYULA for a smooth strongly convex component and a convex Lipschitz nonsmooth term.Source: §9 · p. 20

A Weak Hessians and Integration by Parts

The appendix supplies weak-derivative and integration-by-parts tools, then records semigroup and spectral-calculus facts used by the corrector.

A Weak Hessians and Integration by Parts

A.1 Weak derivatives and weak Hessians

  • For C1,1 functions, the weak Hessian agrees almost everywhere with the classical derivative of the gradient and inherits the convexity and Lipschitz-gradient bounds.For gλ, the gradient Lipschitz constant is λ^-1.Source: §A.1 · pp. 20–21

A.2 Weighted integration by parts under the Gibbs law

  • Weighted weak integration by parts is justified using cutoffs, linear growth of the gradient, and Gaussian tails under πλ.The cutoff-annulus contribution tends to zero, allowing the identity to pass to the Gibbs law.Source: §A.2 · pp. 21–22

A.3 The weak integration by parts used in the BV estimate

  • The weak generator integration-by-parts identity expresses the Hessian-gradient contraction used in the BV estimate.The proof extends the identity to the weak gradient and removes the cutoff before summing over coordinates.Source: §A.3 · pp. 22–23

B Operator Facts Used by the Corrector

B.1 From the Markov semigroup to a nonnegative generator

  • For the reversible diffusion, the semigroup is strongly continuous, self-adjoint, and contractive, while Aλ = −Lλ is nonnegative and self-adjoint.The generator is defined on its full L2 domain.Source: §B.1 · pp. 23–24

B.2 Bounded functions of the generator

  • Bounded functions of Aλ act as bounded self-adjoint operators, and the corrector’s time integral is interpreted as an L2(πλ) Riemann-sum limit.The appendix also records mean-zero invariance and the Poincaré consequence of strong log-concavity.Source: §B.2 · pp. 24–26

B.3 The single Lp multiplier theorem used in the proof

The appendix supplies an Lp multiplier bound for the corrector by verifying that the reversible diffusion semigroup meets a quoted Laplace-transform multiplier theorem’s assumptions.

B.3 The single Lp multiplier theorem used in the proof

  • The corrector requires an Lp estimate in addition to the bounded functional calculus available in L2.The appendix states the external multiplier result in notation suited to checking its assumptions.Source: §B.3 · pp. 26, 28
  • The proof verifies the multiplier theorem’s assumptions using πλ as a probability measure, self-adjointness and nonnegativity of Aλ, and semigroup contractivity on every Lq.Convergence to zero in L2 for mean-zero functions follows from the Poincaré estimate.Source: §B.3 · pp. 27–28
  • The multiplier bound quoted from Carbonaro and Dragičević yields the corrector estimate (7.17).The appendix constructs the relevant multiplier using a bounded sawtooth function and treats its value at zero separately.Source: §B.3 · pp. 27–28
Loading 2609.12594v1…