🤖 machine learning

DC-LA: Difference-of-Convex Langevin Algorithm

This paper introduces the Difference-of-Convex Langevin Algorithm (DC-LA), a novel sampling method that leverages Moreau envelopes and DC programming to handle non-smooth, non-log-concave target distributions, while establishing its convergence in Wasserstein distance and demonstrating its efficacy in both synthetic and real-world Computed Tomography applications.

Original authors: Hoang Phuc Hau Luu, Zhongjian Wang

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hoang Phuc Hau Luu, Zhongjian Wang

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 best spot to set up camp in a vast, foggy, and mountainous landscape. Your goal is to find the "perfect" spot, but the terrain is tricky. Some parts are smooth hills, but others are jagged cliffs, sharp spikes, or weirdly shaped valleys that don't follow the usual rules of geometry.

In the world of machine learning and data science, this "landscape" is a mathematical map of possibilities, and finding the best spot is called sampling. Usually, scientists use a method called the Langevin Algorithm, which is like a hiker taking small, random steps downhill, guided by a map (the gradient) to find the lowest point.

However, this paper tackles a specific problem: what happens when the map has jagged, non-smooth edges (like a cliff) and weird, non-convex shapes (like a valley that isn't just a simple bowl)? Standard hikers (algorithms) get stuck, fall off cliffs, or wander aimlessly because their maps break down at these sharp edges.

Here is the paper's solution, explained simply:

1. The Problem: The "Jagged" Map

The researchers are dealing with a special type of landscape called a Difference-of-Convex (DC) function.

Think of it like this: Imagine your terrain is built by taking a smooth, round bowl (Convex 1) and carving a weird, bumpy shape out of it (Convex 2). The result is a landscape that is neither smooth nor simple.
The Issue: Many real-world problems (like medical imaging or compressing data) use these "carved" landscapes because they are better at capturing complex details. But standard algorithms can't handle the sharp edges where the two shapes meet.

2. The Solution: The "DC-LA" Algorithm

The authors created a new method called DC-LA (Difference-of-Convex Langevin Algorithm). They didn't try to force the jagged map to be smooth; instead, they used a clever trick called Moreau Envelopes.

The Analogy: Imagine the jagged cliff edges are too dangerous to walk on. Instead of trying to walk on the sharp rock, the algorithm puts a thick, soft foam padding over the sharp parts of the map. This "padding" smooths out the edges just enough so the hiker can walk on them without falling, but it keeps the general shape of the mountain intact.
The Split: The algorithm is smart enough to know that the "carving" part of the map is actually two different things: one part that adds a bump and one part that removes a bump. It treats them separately, smoothing each one individually before combining them. This is like smoothing the "add" part and the "subtract" part separately, rather than trying to smooth the messy result of both at once.

3. How It Works: The "Forward-Backward" Hike

The algorithm moves in a specific rhythm, like a dance step:

Forward Step (The Slide): The hiker slides down the smooth parts of the map (the data part) and the smoothed-out "subtract" part.
Backward Step (The Bounce): The hiker hits a "proximal operator," which is like a springy trampoline. This step gently nudges the hiker back toward the "add" part of the map, correcting their path without getting stuck on the jagged edges.

By repeating this slide-and-bounce dance, the hiker eventually explores the whole landscape and finds the true "perfect spots" (the target distribution) with high accuracy.

4. Why It Matters: The Proof and the Test

The paper proves mathematically that this method works.

The Guarantee: They showed that even if the landscape is weird and the hiker starts far away, as long as the landscape eventually slopes upward (a condition they call "distant dissipativity"), the hiker will eventually settle into the right distribution. They proved this works for various measures of "distance" between the hiker's path and the true map.
The Real-World Test:
- Synthetic Test: They tested it on a 2D map with sharp, cross-shaped valleys. The DC-LA hiker found the correct shape perfectly, while other methods either got blurry or focused too much on the wrong lines.
- Medical Imaging (CT Scan): They applied it to a real-world problem: reconstructing a CT scan of a human abdomen.
  - The Result: The algorithm didn't just produce a single "best guess" image (which is what most methods do). It produced a map of uncertainty. It showed exactly which parts of the image were clear and which parts were fuzzy or ambiguous.
  - Comparison: It performed as well as the best optimization methods at finding the image, but it also gave a "variance map" (a heat map of uncertainty) that told doctors, "We are confident about the bones, but we are less sure about this specific soft tissue area."

Summary

In short, this paper introduces a new way to navigate complex, jagged mathematical landscapes. By splitting the problem into two parts and smoothing them individually, the DC-LA algorithm allows computers to explore these difficult terrains safely and accurately. It works better than previous methods for complex data and provides a unique ability to show not just what the answer is, but how confident the computer is in that answer.

Technical Summary: DC-LA: Difference-of-Convex Langevin Algorithm

Problem Statement
The paper addresses the sampling problem from a Gibbs distribution $\pi \propto \exp(-V)$ in $\mathbb{R}^d$ , where the potential function $V$ is composite and non-smooth. Specifically, the authors consider potentials of the form $V = f + r$ , where $f$ is a Lipschitz smooth data fidelity term, and $r$ is a non-smooth regularizer defined as a difference-of-convex (DC) function, i.e., $r = r_1 - r_2$ with $r_1$ and $r_2$ being convex. This setting arises frequently in Bayesian inference and machine learning, particularly when using non-convex priors (e.g., $\ell_1 - \ell_2$ , Capped- $\ell_1$ , or data-driven priors based on Input-Convex Neural Networks) that better model sparsity or complex data structures than convex counterparts.

Existing methods face limitations in this regime. Standard Unadjusted Langevin Algorithms (ULA) require differentiability, which fails for non-smooth $r$ . Proximal Langevin algorithms (like PSGLA) typically assume the regularizer is weakly convex or convex. However, many effective DC regularizers are not weakly convex, rendering standard convergence guarantees inapplicable. Furthermore, applying a single Moreau envelope to the entire non-weakly-convex term $r$ can lead to ill-posed or discontinuous proximal operators.

Methodology: The DC-LA Algorithm
The authors propose the Difference-of-Convex Langevin Algorithm (DC-LA), a forward-backward sampler that leverages the specific DC structure of the regularizer. The core innovation lies in applying Moreau smoothing separately to the convex components $r_1$ and $r_2$ rather than to the difference $r$ as a whole.

Given a smoothing parameter $\lambda > 0$ , the algorithm operates on an augmented potential $V_\lambda = (f - r_2^\lambda) + r_1^\lambda$ , where $r_i^\lambda$ denotes the Moreau envelope of $r_i$ . The update rule for the sequence $\{X_k\}$ is:
$X_{k+1} = \text{Prox}_{\gamma r_1^\lambda} \left( X_k - \gamma \nabla f(X_k) + \gamma \nabla r_2^\lambda(X_k) + \sqrt{2\gamma} Z_{k+1} \right)$
where $\gamma$ is the step size and $Z_{k+1} \sim \mathcal{N}(0, I)$ .

The algorithm is decomposed into elementary operators:

Forward Step: A gradient step involving the smooth term $f$ and the gradient of the smoothed concave part $\nabla r_2^\lambda$ .
Backward Step: A proximal step involving the smoothed convex part $r_1^\lambda$ .

The authors note that if $r_2$ is already smooth (e.g., in certain structured DC regularizers like Geman or SCAD penalties), the algorithm simplifies to DC-LA-S, where $\nabla r_2$ is used directly without smoothing.

Theoretical Contributions and Convergence
The paper establishes convergence guarantees for DC-LA under the assumption that the potential $V$ satisfies a distant dissipativity condition (also known as strong convexity at infinity). This condition requires the drift to be dissipative only when points are sufficiently far apart, a weaker assumption than global strong convexity.

Key theoretical results include:

Convergence in Wasserstein Distance: For any $q \in \mathbb{N}^*$ , the $q$ -Wasserstein distance between the law of the iterate $X_k$ and the target distribution $\pi$ is bounded by:
$W_q(p_{X_k}, \pi) \leq O(\rho^k \gamma) + O(\gamma^{1/2q}) + O(\lambda^{1/q})$
where $\rho \in (0, 1)$ . The terms represent the convergence rate of the Markov chain, the discretization error, and the smoothing error, respectively.
General Regularity Assumptions: The analysis covers a continuum of regularity for $r_2$ $r_{2}$ :
1. $r_2$ is Lipschitz continuous (non-smooth).
2. $r_2$ is differentiable with a $\kappa$ -Hölder continuous gradient ( $0 < \kappa < 1$ ).
3. $r_2$ is smooth ( $C^{1,1}$ ).
Handling Non-Weakly Convex Functions: Unlike prior work (e.g., Renaud et al., 2025a) which requires the regularizer to be weakly convex, DC-LA provides convergence guarantees for non-weakly convex DC regularizers (such as $\ell_1 - \ell_2$ and DICNNs), provided the distant dissipativity condition holds.
Stability Analysis: The authors utilize recent stability results for Langevin dynamics with general drifts to bound the distance between the discretized process and the invariant distribution of the smoothed potential.

Experimental Results
The authors validate DC-LA through two sets of experiments:

Synthetic Data ( $\ell_1 - \ell_2$ Prior): In a 2D setting with Gaussian likelihoods, DC-LA successfully captures the target density, which exhibits sparsity-promoting behavior along coordinate axes. Compared to baselines (ULA, Moreau ULA, and PSGLA), DC-LA produces the most faithful empirical distributions, achieving the lowest binned KL divergence. PSGLA, while sharp, tends to overemphasize coordinates, while ULA variants are blurry.
Real-World Computed Tomography (CT): Using a data-driven DC prior based on the difference of two Input-Convex Neural Networks (DICNNs), the authors perform CT reconstruction on 512 $\times$ 512 abdominal scans. DC-LA recovers anatomical structures with high Structural Similarity (SSIM) and Peak Signal-to-Noise Ratio (PSNR), comparable to a Proximal Subgradient Method (PSM) optimizer running for significantly more iterations. Crucially, DC-LA provides uncertainty quantification via pixel-wise posterior variance, highlighting regions of high uncertainty (boundaries, fine textures) that deterministic MAP estimates miss.

Significance and Claims
The paper claims to provide a mathematically justified framework for sampling from non-log-concave, non-smooth distributions with DC structure. Its primary significance lies in:

Extending the Scope of Langevin Sampling: It moves beyond the log-concave and weakly convex regimes to handle a broader class of non-convex regularizers widely used in compressed sensing and inverse problems.
Robustness to Non-Weakly Convexity: It is the first to offer convergence guarantees for Langevin-type algorithms applied to non-weakly convex DC regularizers without requiring the restrictive assumptions found in previous non-log-concave sampling literature.
Practical Utility: The method demonstrates effectiveness in both synthetic and real-world applications, offering not just point estimates but also meaningful uncertainty quantification, which is critical for safety-critical applications like medical imaging.

The authors acknowledge that their analysis relies on the distant dissipativity condition and that the Lipschitz continuity of $r_1$ is a current assumption, suggesting future work could explore relaxing these conditions or handling mixed-growth regularizers.