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

arXiv:2608.13467v1 Announce Type: new Abstract: We study the Moreau--Yosida unadjusted Langevin algorithm (MYULA) for the nonsmooth composite target [ pi(dx)propto exp{-f(x)-g(x)},dx, qquad xinmathbb 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=operatorname{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_{ref}), 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/lambda). If (M_lambda) is an a.e. upper bound for (a_lambda), then, up to logarithmic factors, [ N lesssim frac{1}{m} left[ L_f + frac{ au_f+G^2+B_{ref} }{ arepsilon_{alg}^2 } + frac{M_lambda}{arepsilon_{alg}} right], qquad au_f:= sup_xoperatorname{tr}nabla^2 f(x), ] iterations suffice to ensure (sqrt m,W_2(mu_N,pi_lambda)leqarepsilon_{alg}), 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) leq frac{G^2lambda}{4}. ] Thus, choosing (lambdaasymparepsilon/G^2) gives an end-to-end guarantee for (pi). The universal estimate (B_{ref}leq d/lambda) yields (widetilde O(arepsilon^{-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 (lambda), yielding (widetilde O(arepsilon^{-2})) for the same classical MYULA kernel.

Source: arXiv cs.LG | 2026-08-14

Related