Search papers, labs, and topics across Lattice.
This paper investigates the Moreau--Yosida unadjusted Langevin algorithm (MYULA) for nonsmooth composite targets, establishing that the leading discretization error is governed by the active trace of the Moreau envelope rather than the global curvature bound. The authors derive a refined iteration complexity bound that significantly improves upon previous estimates, showing that the number of iterations required for convergence is influenced by the average active trace along the heat substep. Notably, they demonstrate that for structured penalties, the active trace can be made independent of the smoothing parameter, leading to enhanced convergence rates of \(\widetilde O(\varepsilon^{-2})\).
The leading error in MYULA is driven by the active trace of the Moreau envelope, not the global curvature, allowing for faster convergence rates in high-dimensional settings.
We study the Moreau--Yosida unadjusted Langevin algorithm (MYULA) for the nonsmooth composite target \[ \pi(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_\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_{\mathrm{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{ \tau_f+G^2+B_{\mathrm{ref}} }{ \varepsilon_{\mathrm{alg}}^2 } + \frac{M_\lambda}{\varepsilon_{\mathrm{alg}}} \right], \qquad \tau_f:= \sup_x\operatorname{tr}\nabla^2 f(x), \] iterations suffice to ensure \(\sqrt m\,W_2(\mu_N,\pi_\lambda)\leq\varepsilon_{\mathrm{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^2\lambda}{4}. \] Thus, choosing \(\lambda\asymp\varepsilon/G^2\) gives an end-to-end guarantee for \(\pi\). The universal estimate \(B_{\mathrm{ref}}\leq d/\lambda\) 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 \(\lambda\), yielding \(\widetilde O(\varepsilon^{-2})\) for the same classical MYULA kernel.
