Active-Trace Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling

We study the Moreau–Yosida unadjusted Langevin algorithm (MYULA) for the nonsmooth composite target $$\pi (dx)\propto \exp \{-f(x)-g(x)\}dx,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_{\lambda }$ be the Moreau envelope of $g$, ${\pi }_{\lambda }$ the corresponding smoothed target, and $a_{\lambda }=\mathrm{tr}{H}_{\lambda }$, where $H_{\lambda }$ is the a.e./weak Hessian of $g_{\lambda }$. We show that the leading MYULA discretization error is controlled by the reference active trace $B_{\mathrm{r}\mathrm{e}\mathrm{f}}$, the average of $a_{\lambda }$ along the heat substep of one MYULA update started from ${\pi }_{\lambda }$, rather than by the global curvature bound $d\mathrm{/}\lambda$. If $M_{\lambda }$ is an a.e. upper bound for $a_{\lambda }$, then, up to logarithmic factors, $$N\lesssim \frac{1}{m}[L_f+\frac{{\tau }_f+G^2+B_{\mathrm{r}\mathrm{e}\mathrm{f}}}{{\epsilon }_{\mathrm{a}\mathrm{l}\mathrm{g}}^2}+\frac{M_{\lambda }}{{\epsilon }_{\mathrm{a}\mathrm{l}\mathrm{g}}}],{\tau }_f:=\underset{x}{\sup }\mathrm{tr}{\mathrm{\nabla }}^{2}f(x),$$ iterations suffice to ensure $\sqrt{m}{W}_2({\mu }_N,{\pi }_{\lambda })\le {\epsilon }_{\mathrm{a}\mathrm{l}\mathrm{g}}$, where ${\mu }_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({\pi }_{\lambda },\pi )\le \frac{G^2\lambda }{4}\mathrm{.}$$ Thus, choosing $\lambda \asymp \epsilon \mathrm{/}{G}^2$ gives an end-to-end guarantee for $\pi$. The universal estimate $B_{\mathrm{r}\mathrm{e}\mathrm{f}}\le d\mathrm{/}\lambda$ yields $\tilde{O}({\epsilon }^{-3})$ accuracy dependence. For the structured piecewise-linear, lasso-type, group, and total-variation penalties considered here, curvature–tube estimates make $B_{\mathrm{r}\mathrm{e}\mathrm{f}}$ independent of $\lambda$, yielding $\tilde{O}({\epsilon }^{-2})$ for the same classical MYULA kernel.