Moreau-Yosida Langevin algorithm achieves near-linear accuracy bounds
Near-Linear Accuracy Bounds for Moreau--Yosida Unadjusted Langevin Sampling
Machine Learning
Summary
This paper studies a mathematical algorithm used to sample from complex probability distributions. The authors show that the Moreau-Yosida unadjusted Langevin algorithm (MYULA) can achieve accurate results with near-linear computational effort. They provide error bounds under clear conditions on the problem’s shape, without needing strong smoothness assumptions. This means the algorithm can be more reliably used when certain exact calculations are available for parts of the problem.
What this means in practice
- •For machine learning engineers: Implement efficient sampling methods for high-dimensional probabilistic models with provable error guarantees using proximal computations.
- •For operations research analysts: Use improved Langevin algorithms with guaranteed convergence rates for optimization problems involving nonsmooth but convex functions.
A theory result. No direct application yet.
Authors
Yuchen Xin, Zhihua Zhang
Abstract
We establish near-linear accuracy bounds for the classical Moreau--Yosida unadjusted Langevin algorithm (MYULA). The target is $π\propto e^{-f-g}$, where $f\in C^2(\mathbb{R}^d)$ is $m$-strongly convex with Lipschitz gradient and $g$ is convex and globally Lipschitz. Under an explicit parameter-dependent step-size condition, we bound the invariant-measure bias relative to the Moreau-smoothed target by $\widetilde O(h)$, with only logarithmic dependence on the inverse smoothing parameter in the error coefficient. Combining this estimate with the Moreau approximation bias and Wasserstein contraction gives $\widetilde O(\varepsilon^{-1})$ iterations to make the $N$th-iterate law $μ_N$ satisfy $\sqrt m\,W_2(μ_N,π)\le\varepsilon$, for fixed model parameters and initialization. We bound the stationary error directly, without assuming third derivatives or a Lipschitz Hessian. Each iteration uses one gradient evaluation and one exact proximal evaluation. The key idea in our analysis is to convert a second-order stationary residual into a Wasserstein bound using a Poisson-based estimate.