🔢 mathematics

Ergodicity of Langevin Dynamics and its Discretizations for Non-smooth Potentials

This paper establishes the exponential and geometric ergodicity of continuous and discretized subgradient Langevin dynamics for sampling from Gibbs distributions with strongly convex, non-smooth potentials, while proving the validity of the law of large numbers for practical statistical estimation and demonstrating the methods' efficacy in imaging applications.

Original authors: Lorenz Fruehwirth, Andreas Habring

Published 2026-05-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Lorenz Fruehwirth, Andreas Habring

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the deepest valley in a vast, foggy mountain range. This valley represents the "perfect answer" to a complex problem, like cleaning up a blurry photo or figuring out the most likely shape of an object from incomplete data. In mathematics, this valley is called a Gibbs distribution, and the landscape is defined by a "potential" function (let's call it the Terrain).

The problem is that this Terrain isn't always smooth. Sometimes, the ground has sharp cliffs, jagged rocks, or sudden drops (these are non-smooth potentials). Furthermore, the slope of the ground might get steeper and steeper as you move away from the center, but it never gets infinitely steep (this is linearly growing drift).

Standard tools for exploring this terrain (like the Langevin Dynamics) usually require the ground to be perfectly smooth, like a polished marble floor. If the ground is jagged, these tools break or get stuck. This paper introduces new, rugged boots that allow explorers to navigate these jagged landscapes safely and efficiently.

Here is a breakdown of what the authors did, using simple analogies:

1. The Goal: Finding the Valley

The authors want to generate random samples from the bottom of this valley. In the real world, this is used for Bayesian imaging (like removing noise from a photo) and inverse problems (figuring out the cause of an effect).

The Challenge: The "Terrain" (the math behind the image) is often made of two parts: a smooth part (like the physics of light) and a jagged part (like a rule that says "edges must be sharp").
The Old Way: Previous methods tried to smooth out the jagged rocks before walking, which is like filling a pothole with cement just to walk over it. It works, but it changes the landscape slightly and can be slow.

2. The Solution: Rugged Boots (Subgradient Dynamics)

The authors developed a way to walk directly on the jagged rocks without smoothing them first. They use Subgradients, which are like "best guesses" for the slope at a sharp corner.

Continuous Time (The Ideal Hike): First, they proved that if you could hike continuously (without taking steps), you would eventually find the deepest part of the valley and stay there, no matter how jagged the rocks are. They showed this happens exponentially fast (you don't wander around forever).
Discrete Time (The Actual Steps): Since computers can't take infinite tiny steps, you have to take finite steps. The authors tested two ways to take these steps:
1. The Explicit Step: You look at the slope where you are standing and take a step in that direction.
2. The Semi-Implicit Step: You look at the slope where you want to be and adjust your step to land there perfectly. This is like looking ahead and planting your foot carefully.

3. The Results: Why These Boots Are Better

The paper proves three main things about these new boots:

They Don't Get Lost (Ergodicity): No matter where you start, if you keep walking, you will eventually settle into the correct distribution of the valley. You won't get stuck on a random hilltop.
The Semi-Implicit Step is Smoother: When you take very small steps (which is usually good for accuracy), the "Semi-Implicit" method converges to the answer faster and more reliably than the "Explicit" method. It's like the difference between stumbling over rocks versus carefully placing your feet.
You Can Trust Your Footprints (Law of Large Numbers): This is a crucial practical point. Usually, to get a good average of the valley's depth, you might need to send out 100 different hikers, each starting from a different spot, and average their results.
- The authors proved that with their method, one single hiker is enough. If that hiker walks long enough, their path alone provides a perfect statistical average. This saves a massive amount of computer memory and time, which is vital for high-dimensional tasks like processing large images.

4. Real-World Tests (The Field Trip)

The authors didn't just do the math; they went hiking in the real world (simulated on computers):

2D Experiments: They tested on simple 2D maps with jagged shapes. They compared their new boots against the old "smoothed" method (called MYULA). Their method was just as fast but had less "bias" (it didn't get stuck in a slightly wrong spot).
Image Denoising: They tried to clean up a noisy photo. The jagged part of the math was the "Total Variation" rule (which keeps edges sharp). Their method successfully removed the noise while keeping the edges crisp, outperforming the smoothed method.
Image Deconvolution: They tried to un-blur a photo. Again, their method worked well, proving it can handle complex, real-world imaging problems where the math is messy.

Summary

In short, this paper says: "You don't need to smooth out the jagged rocks to find the bottom of the valley. We have proven that you can walk directly on the jagged rocks, find the bottom quickly, and use just one walker to get the perfect average, saving time and memory."

This is a significant upgrade for anyone trying to solve difficult imaging problems where the math involves sharp, non-smooth rules.

Technical Summary: Ergodicity of Langevin Dynamics for Non-smooth Potentials

Problem Statement
The paper addresses the challenge of sampling from Gibbs distributions $\pi(x) \propto e^{-U(x)}$ where the potential $U: \mathbb{R}^d \to \mathbb{R}$ is strongly convex but potentially non-differentiable. Specifically, the authors focus on potentials where the subgradient grows at most linearly. Such potentials arise frequently in Bayesian inference for mathematical imaging (e.g., $L_1$ loss, Lasso priors) and inverse problems, often taking the form $U(x) = F(x) + G(x)$ , where $F$ represents data fidelity and $G$ a regularization functional.

Existing sampling methods, such as the Unadjusted Langevin Algorithm (ULA), typically require the potential to be differentiable with a Lipschitz continuous gradient. When $U$ is non-smooth, standard approaches either fail to establish ergodicity (convergence to a stationary distribution) or rely on smoothing techniques (e.g., Moreau-Yoshida envelopes) which introduce approximation bias and computational overhead. Furthermore, without a Law of Large Numbers (LLN) for the Markov chain, one must simulate multiple independent chains to estimate statistics, which is computationally prohibitive in high-dimensional imaging applications.

Methodology
The authors analyze Langevin dynamics in both continuous and discrete time settings under Assumption A: $U$ is $m$ -strongly convex, and its subgradient $\partial U$ satisfies a linear growth condition ( $\|g\| \leq C(1+\|x\|)$ ).

Continuous-Time Analysis:
The authors consider the stochastic differential equation (SDE):
$dX_t = -\nabla U(X_t)dt + \sqrt{2}dW_t$
where $\nabla U$ denotes the weak derivative (or a measurable subgradient selection). They prove the existence and uniqueness of a strong solution and establish that the process is exponentially ergodic with respect to the Wasserstein-2 distance ( $W_2$ ). The stationary distribution is identified as the target $\pi$ .
Discrete-Time Discretizations:
Two discretization schemes are proposed and analyzed:
- Explicit Scheme (Subgradient ULA): An Euler-Maruyama discretization using a measurable subgradient selection $\theta(x) \in \partial U(x)$ :
  $X_{k+1} = X_k - \tau \theta(X_k) + \sqrt{2\tau}W_k$
- Semi-Implicit Scheme (Proximal-Gradient): Designed for potentials of the form $U(x) = F(x) + G(x)$ , where $F$ is smooth and $G$ is non-smooth. This scheme uses a proximal step for $G$ :
  $X_{k+1} = \text{prox}_{\tau G}(X_k - \tau \nabla F(X_k) + \sqrt{2\tau}W_k)$
For both schemes, the authors establish geometric ergodicity (convergence to a stationary distribution $\pi_\tau$ ) and prove that the chains satisfy a Law of Large Numbers (LLN). This allows for the computation of statistics using consecutive iterates of a single chain rather than multiple independent chains.

Key Contributions

Ergodicity for Non-smooth Potentials: The paper proves exponential ergodicity for the continuous-time Langevin diffusion and geometric ergodicity for both explicit and semi-implicit discretizations. Crucially, these results hold without assuming Lipschitz continuity of the potential or its gradient, relaxing the regularity requirements to linear growth of the subgradient.
Convergence of Stationary Distributions: The authors demonstrate that the stationary distribution $\pi_\tau$ of the discrete schemes converges to the target $\pi$ as the step size $\tau \to 0$ . Specifically, they show a Wasserstein-2 error bound of order $O(\tau)$ for both schemes.
Law of Large Numbers (LLN): A practical contribution is the proof that the discrete chains satisfy the LLN. This validates the use of running means over a single chain for estimating statistics, significantly reducing memory consumption compared to methods requiring multiple independent chains.
Comparison of Schemes: The semi-implicit scheme is shown to exhibit better convergence rates for small step sizes compared to the explicit scheme, particularly when the potential is decomposable into smooth and non-smooth parts.

Results and Numerical Experiments
The theoretical findings are supported by numerical experiments in 2D and high-dimensional imaging applications (image denoising and deconvolution).

2D Experiments: The authors tested potentials with mixed norms and non-Lipschitz subgradients. Results confirmed exponential convergence and the reduction of bias as $\tau$ decreases. The proposed methods were compared against the Moreau-Yoshida Unadjusted Langevin Algorithm (MYULA).
Imaging Applications: In denoising and deconvolution tasks using Total Variation (TV) regularization, the proposed explicit and semi-implicit schemes were compared to MYULA and Belief Propagation (BP).
- The proposed methods achieved lower bias (closer to the target distribution) than MYULA, which suffers from the approximation error of the Moreau envelope.
- The semi-implicit scheme avoided the need for iterative proximal computations required by MYULA when the proximal operator is not explicit (e.g., in the presence of linear operators), leading to significant computational savings.
- The experiments confirmed that single-chain statistics (mean and variance) computed via the LLN provide accurate approximations of the target distribution.

Significance and Claims
The paper claims to fill a gap in the literature regarding the ergodicity of Langevin dynamics for non-differentiable, non-Lipschitz potentials. Previous works often assumed higher regularity, proved convergence only for ergodic means without establishing the ergodicity of the scheme itself, or circumvented non-smoothness via smoothing (introducing bias).

The authors emphasize that their results allow for direct sampling from non-smooth potentials without prior smoothing. The establishment of the LLN is highlighted as particularly relevant for high-dimensional applications like imaging, where simulating multiple independent chains is computationally expensive. The paper modestly notes that while the theoretical bounds are established, the precise bias-variance trade-off regarding the step size $\tau$ for a fixed number of samples is not explicitly quantified in the analysis.

Limitations and Future Work
The authors note that the current results assume strong convexity over the entire space $\mathbb{R}^d$ . Future work aims to extend these results to functions that are strongly convex only outside a compact set. Additionally, they plan to extend the non-smooth analysis to kinetic Langevin dynamics.