Near-Linear Accuracy Bounds for Moreau--Yosida Unadjusted Langevin Sampling

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.

We study the Moreau--Yosida unadjusted Langevin algorithm (MYULA) for the nonsmooth composite target $$π(dx)\propto \exp\{-f(x)-g(x)\}\,dx, \qquad x\in\mathbb R^d,$$ where $f$ is $m$-strongly convex with $L_f$-Lipschitz gradient and $g$ is convex and $G$-Lipschitz. Let $g_λ$ be the Moreau envelope of $g$, $π_λ$ the corresponding smoothed target, and $a_λ=\operatorname{tr}H_λ$, where $H_λ$ is the a.e./weak Hessian of $g_λ$. We show that the leading MYULA discretization error is controlled by the reference active trace $B_{\mathrm{ref}}$, the average of $a_λ$ along the heat substep of one MYULA update started from $π_λ$, rather than by the global curvature bound $d/λ$. If $M_λ$ is an a.e. upper bound for $a_λ$, then, up to logarithmic factors, $$N \lesssim \frac{1}{m} \left[ L_f + \frac{ τ_f+G^2+B_{\mathrm{ref}} }{ \varepsilon_{\mathrm{alg}}^2 } + \frac{M_λ}{\varepsilon_{\mathrm{alg}}} \right], \qquad τ_f:= \sup_x\operatorname{tr}\nabla^2 f(x),$$ iterations suffice to ensure $\sqrt m\,W_2(μ_N,π_λ)\leq\varepsilon_{\mathrm{alg}}$, where $μ_N$ is the law of the $N$-th iterate and $W_2$ is the quadratic Wasserstein distance. We also prove the Moreau-bias bound $$\sqrt m\,W_2(π_λ,π) \leq \frac{G^2λ}{4}.$$ Thus, choosing $λ\asymp\varepsilon/G^2$ gives an end-to-end guarantee for $π$. The universal estimate $B_{\mathrm{ref}}\leq d/λ$ yields $\widetilde O(\varepsilon^{-3})$ accuracy dependence. For the structured piecewise-linear, lasso-type, group, and total-variation penalties considered here, curvature--tube estimates make $B_{\mathrm{ref}}$ independent of $λ$, yielding $\widetilde O(\varepsilon^{-2})$ for the same classical MYULA kernel.

We establish improved nonasymptotic bounds for Langevin Monte Carlo in the strongly log-concave setting, when the error is measured by the Wasserstein distance. The main result shows that the discretization error is governed by an average coordinate-wise smoothness constant, rather than by the usual global smoothness constant. The proof is short and probabilistic, and relies on a refined use of the synchronous coupling. We further show that the same ideas lead to improved bounds for variable step sizes, for potentials whose Laplacian is Lipschitz-continuous, and for finite-sum problems sampled by stochastic-gradient Langevin dynamics with fixed point control variates. In the Laplacian-smooth case, the usual Hessian-Lipschitz contribution is replaced by a weaker trace-type third-order smoothness quantity. In the finite-sum setting, the resulting SGLD bound improves the dependence on the root mean square smoothness of the component functions. Applications to generalized linear models with Gaussian design show that these refinements can yield substantial, dimension-dependent improvements over previously known bounds, especially for correlated covariates.