📊 statistics

Error estimates for tamed Euler and Randomized Euler schemes for SDEs with locally Lipschitz drift with applications to non-logconcave sampling and optimization

This paper establishes finite-time, non-asymptotic error estimates for tamed Euler and randomized Euler schemes applied to stochastic differential equations with locally Lipschitz, super-linearly growing drifts, demonstrating that the KL-accelerated tamed unadjusted Langevin algorithm (kTULA) and a new tamed randomized midpoint scheme (tRLMC) achieve near-optimal iteration complexities for sampling from non-log-concave distributions and solving non-convex optimization problems.

Original authors: Iosif Lytras, Angelos Ntousis

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Iosif Lytras, Angelos Ntousis

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 lowest point in a vast, foggy, and wildly uneven landscape. This landscape represents a complex problem, like training an AI or figuring out the most likely arrangement of atoms in a molecule. The "lowest point" is the perfect solution (the global minimum), but the terrain is tricky: it has steep cliffs, deep valleys, and some areas that get infinitely steep as you move away from the center.

In the world of mathematics, this journey is modeled by something called a Stochastic Differential Equation (SDE). Think of this equation as a set of instructions for a hiker who is trying to find the bottom. The hiker has two forces acting on them:

The Drift: A force pulling them downhill (toward the solution).
The Noise: A gusty wind that pushes them around randomly, helping them escape small local pits so they don't get stuck.

The Problem: The "Explosive" Hiker

For decades, mathematicians have used a standard method called the Euler-Maruyama scheme (or the Unadjusted Langevin Algorithm) to simulate this hiker's journey on a computer. It's like taking small, regular steps based on the slope at your current location.

However, this paper points out a fatal flaw in this standard method when the landscape gets too steep (a condition called "super-linear growth").

The Analogy: Imagine the slope gets so steep that for every step you take, the ground drops twice as far as you expected. If you take a step that is even slightly too big, the math says you fall off the edge of the world. In computer terms, the numbers get so huge they "explode" and crash the simulation.
The Result: The standard hiker (the algorithm) becomes unstable and fails to find the solution, especially in complex, non-smooth landscapes.

The Solution: "Taming" the Hiker

The authors of this paper introduce two new, safer ways to guide the hiker. They call these methods "Tamed" schemes.

Think of "taming" like putting a leash on a dog that wants to run too fast. If the dog (the math) tries to run toward a cliff, the leash (the algorithm) gently pulls it back, ensuring it never falls off, even if the terrain is wild.

They propose two specific types of leashed hikers:

1. The "Smart Leash" (kTULA)

This is a modified version of the standard hiker.

How it works: It adjusts the size of the step based on how steep the ground is. If the ground is flat, it takes normal steps. If the ground is a cliff, it shrinks the step automatically to stay safe.
The Result: The paper proves that this hiker never explodes. Furthermore, they show that this hiker reaches the bottom of the valley (the solution) very efficiently. They measured this efficiency using a metric called KL Divergence (which is like measuring how much the hiker's map differs from the real map). They found that this method is nearly the best possible speed for this type of problem.

2. The "Randomized Leash" (tRLMC)

This is a more sophisticated approach. Instead of checking the slope at the exact start of the step, this hiker checks the slope at a random point in the middle of the step.

The Analogy: Imagine walking down a hill. The standard hiker looks at the ground right under their feet. The randomized hiker closes their eyes, takes a guess at where they will be halfway down, checks the slope there, and then adjusts their step.
Why it helps: This random check smooths out the errors. It's like taking a "middle-ground" guess that prevents the hiker from overreacting to sudden spikes in the terrain.
The Result: The authors proved this method is also stable (it won't explode) and is highly accurate. They measured its success using Total Variation (a way of checking if the hiker's final location matches the true target distribution). This is the first time such a guarantee has been proven for this type of "randomized" method on steep terrain.

Why This Matters (According to the Paper)

The paper doesn't just say "it works"; it provides rigorous mathematical proof that these methods work even when the landscape is:

Non-Convex: Meaning it has many hills and valleys, not just one smooth bowl.
Super-linear: Meaning the slopes can get infinitely steep.
Locally Lipschitz: Meaning the rules of the terrain can change abruptly, as long as they don't change too abruptly.

The authors tested their ideas with two types of experiments:

Sampling: Trying to generate random numbers that follow a specific, complex pattern (like the double-well potential, which looks like a "W" shape). The standard hiker crashed immediately, while the "tamed" hikers stayed stable and accurate.
Optimization: Trying to train a simple neural network (a basic AI). When the learning rate (step size) was set high (aggressive), standard optimizers (like SGD or Adam) became unstable or performed poorly. The "tamed" methods remained stable and found better solutions.

The Bottom Line

This paper solves a long-standing problem in computational statistics and optimization. It shows that by "taming" the mathematical steps—essentially adding a safety mechanism that prevents the algorithm from running off the edge of the world—we can reliably solve complex problems that were previously too dangerous for standard methods. They have provided the first mathematical guarantees that these "tamed" methods are both stable and efficient, even in the most chaotic and steep mathematical landscapes.

Technical Summary: Error Estimates for Tamed Euler and Randomized Euler Schemes for SDEs with Locally Lipschitz Drift

1. Problem Statement and Motivation

The paper addresses the numerical discretization of Stochastic Differential Equations (SDEs) of the form $dX_t = -h(X_t)dt + \sigma dB_t$ , where the drift $h: \mathbb{R}^d \to \mathbb{R}^d$ is locally Lipschitz but exhibits super-linear growth at infinity. This regime is critical for sampling from non-log-concave distributions (often arising in Bayesian inference and large-scale optimization) and for solving non-convex optimization problems.

The central challenge is that the classical Euler–Maruyama scheme, which underpins the Unadjusted Langevin Algorithm (ULA), is known to be unstable in this setting. When $h$ grows super-linearly, the Euler–Maruyama approximation can diverge from the true SDE solution in the mean-square sense, even over finite time horizons, due to the explosion of moments in the discretized process. While previous literature has addressed either non-convexity (via isoperimetric inequalities) or super-linear growth (via taming under strong dissipativity), rigorous non-asymptotic guarantees for the combination of super-linear drift and non-log-concave targets (specifically under Logarithmic Sobolev Inequalities) have remained limited.

2. Methodology

The authors develop a two-layer analytical framework:

General SDE Level: Establishing finite-time error estimates against the underlying SDE for general locally Lipschitz drifts, without assuming a gradient structure ( $h \neq \nabla u$ ).
Sampling Specialization: Applying these estimates to the Langevin case ( $h = \nabla u$ ) under a Logarithmic Sobolev Inequality (LSI) to derive sampling and optimization guarantees.

2.1. Tamed Schemes

To ensure stability, the authors employ taming techniques, modifying the drift $h$ to a tamed version $h_\lambda$ that grows at most linearly while converging pointwise to $h$ as the step size $\lambda \to 0$ . Two specific algorithms are analyzed:

kTULA (KL-accelerated Tamed Unadjusted Langevin Algorithm): A deterministic tamed Euler scheme.
tRLMC (Tamed Randomized Langevin Monte Carlo): A new tamed scheme based on a randomized midpoint discretization, where randomness is introduced via uniform random variables in the integration time.

2.2. Local-Error Frameworks

The core technical innovation involves developing two distinct local-error frameworks based on the shifted-composition approach of [5]:

KL Framework (for kTULA): This framework controls the Kullback–Leibler (KL) divergence. It relies on a "shifted chain rule" that introduces an auxiliary interpolating process to separate discretization bias from the contraction of the SDE semigroup. A key difficulty addressed is the state-dependence of the coupling increment caused by the polynomial Lipschitz nature of the drift, which differs from the constant coupling increments in prior work [5].
TV Framework (for tRLMC): Since the randomization of the integration time in tRLMC prevents the construction of a sharp cross-regularity estimate required for the KL framework, the authors introduce a Total Variation (TV) local-error framework. This approach utilizes a direct one-step TV estimate and the same shifted Wasserstein recursion to bound the error.

3. Key Contributions and Results

3.1. Finite-Time Error Estimates against the SDE

Theorem 1 (kTULA): Establishes a finite-time KL error estimate for kTULA against the SDE. For general locally Lipschitz drift, the error scales as $\mathcal{O}(\lambda^2)$ (ignoring logarithmic factors and dimension dependence), specifically:
$KL(\mu \hat{P}^N \| \nu P^N) \lesssim \frac{1}{\lambda} W_2^2(\mu, \nu) + ((N\lambda) \vee \log N)\lambda^2$
Theorem 2 (tRLMC): Provides the first finite-time Total Variation error estimate for a randomized scheme applied to SDEs with super-linearly growing drift. The bound scales as $\mathcal{O}(\lambda)$ :
$TV(\mu \tilde{P}^N \| \nu P^N) \lesssim \frac{1}{\sqrt{\lambda}} W_2(\mu, \nu) + \lambda \sqrt{(N\lambda) \vee \log N}$

3.2. Sampling Guarantees under Logarithmic Sobolev Inequality

Specializing the results to the sampling setting ( $h=\nabla u$ ) under an LSI:

kTULA Complexity: Achieves a near-optimal iteration complexity of $\tilde{\mathcal{O}}(\epsilon^{-1/2})$ to reach accuracy $\epsilon$ in KL divergence. This implies corresponding guarantees in Total Variation and Wasserstein distance with complexity $\tilde{\mathcal{O}}(\epsilon^{-1})$ .
tRLMC Complexity: Establishes a non-asymptotic guarantee in Total Variation for a tamed randomized Langevin scheme under super-linear drift, with iteration complexity $\tilde{\mathcal{O}}(\epsilon^{-1})$ for both Total Variation and Wasserstein distance.

3.3. Optimization Implications

The paper connects the sampling convergence to non-convex optimization. By decomposing the excess risk into a sampling error and a concentration term (which vanishes as the inverse temperature $\beta \to \infty$ ), the authors derive explicit non-asymptotic excess-risk bounds for both kTULA and tRLMC in the non-log-concave setting.

4. Numerical Experiments

The authors validate their theoretical findings through two sets of experiments:

Stability and Accuracy: Using a double-well potential in $d=100$ , they demonstrate that the classical ULA explodes (numerical overflow) within a few iterations, whereas both kTULA and tRLMC remain stable over long horizons and accurately capture the second moments and bimodal structure of the target distribution.
Neural Network Optimization: In a fixed-feature neural network regression task with aggressive learning rates, the tamed schemes (kTULA and tRLMC) exhibit more controlled parameter growth and lower test Mean Squared Error (MSE) compared to standard optimizers (SGD, Adam, AMSGrad), which show deterioration as the learning rate increases.

5. Significance and Claims

The paper claims to provide the first rigorous non-asymptotic error estimates for randomized discretization schemes applied to SDEs with super-linearly growing drift. By combining taming with randomized midpoint methods, the work bridges a gap between the stability of tamed Euler schemes and the bias-reduction properties of randomized schemes.

The authors emphasize that their results are significant because:

They extend convergence guarantees to non-log-concave distributions satisfying only an LSI, a setting where standard global Lipschitz assumptions fail.
They provide finite-time guarantees in Total Variation for randomized schemes, a metric previously out of reach for such drift conditions.
They offer a unified theoretical treatment that applies to general SDEs before specializing to sampling, thereby isolating the numerical-analytic obstacles (moment explosion) from the specific gradient structure.

The paper remains modest regarding the scope, noting that the results rely on specific structural assumptions (polynomial growth, dissipativity, one-sided Lipschitz continuity) and that the experimental validation is limited to synthetic and small-scale diagnostic studies.