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

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_{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_{ref} }{ \varepsilon_{alg}^2 } + \frac{M_λ}{\varepsilon_{alg}} \right], \qquad τ_f:= \sup_x\operatorname{tr}\nabla^2 f(x), ] iterations suffice to ensure \sqrt m,W_2(μ_N,π_λ)\leq\varepsilon_{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_{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_{ref} independent of λ, yielding \widetilde O(\varepsilon^{-2}) for the same classical MYULA kernel.