CS Paper Radar

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

Yuchen Xin, Zhihua Zhang

cs.LG ·submitted 2026-08-13 16:47 UTC · v1
theory

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Poisson-Corrector Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling

cs.LG ·2026-09-11 ·Yuchen Xin, Zhihua Zhang
theory similarity 0.84
Abstract

We study the classical Moreau--Yosida unadjusted Langevin algorithm (MYULA) for $π(\,\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 $π_λ$ and the MYULA invariant law $\widehatπ_{λ,h}$, we prove \[ \sqrt m\,W_2(π_λ,\widehatπ_{λ,h}) =O(h)+\widetilde O(h^{3/4}) \] under $0<h(L_f+λ^{-1})\le c$, with only logarithmic dependence on $λ^{-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(μ_N,π)\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.

0.20

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

cs.LG ·2026-09-30 ·Yuchen Xin, Zhihua Zhang
similarity 0.82
Abstract

We establish near-linear accuracy bounds for the classical Moreau--Yosida unadjusted Langevin algorithm (MYULA). The target is $π\propto e^{-f-g}$, where $f\in C^2(\mathbb{R}^d)$ is $m$-strongly convex with Lipschitz gradient and $g$ is convex and globally Lipschitz. Under an explicit parameter-dependent step-size condition, we bound the invariant-measure bias relative to the Moreau-smoothed target by $\widetilde O(h)$, with only logarithmic dependence on the inverse smoothing parameter in the error coefficient. Combining this estimate with the Moreau approximation bias and Wasserstein contraction gives $\widetilde O(\varepsilon^{-1})$ iterations to make the $N$th-iterate law $μ_N$ satisfy $\sqrt m\,W_2(μ_N,π)\le\varepsilon$, for fixed model parameters and initialization. We bound the stationary error directly, without assuming third derivatives or a Lipschitz Hessian. Each iteration uses one gradient evaluation and one exact proximal evaluation. The key idea in our analysis is to convert a second-order stationary residual into a Wasserstein bound using a Poisson-based estimate.

0.07

Penalized Nonreversible Langevin for Constrained Sampling

cs.LG stat.MLmath.PR ·2026-09-21 ·Pervez Ali, Weihao Dong, Xiaoyu Wang
similarity 0.71
Abstract · 68 pages, 8 figures

We propose penalized nonreversible Langevin algorithms for sampling from $π(x)\propto e^{-f(x)}\mathbf 1_{\mathcal C}(x)$, where $\mathcal C\subset\mathbb R^d$ is a compact convex set. The algorithms combine a squared distance penalty with constant or compatible state dependent skew symmetric perturbations that preserve the penalized Gibbs distribution. For smooth, possibly nonconvex $f$, we derive nonasymptotic total variation bounds for the full gradient algorithm under a log Sobolev inequality. When unbiased stochastic gradients are available, we establish $2$-Wasserstein bounds under global contraction and Lipschitz conditions on the full drift in an adapted quadratic metric. For a fixed penalty parameter, the error relative to the penalized Gibbs distribution decays exponentially to an $\mathcal{O}(\sqrtη)$ neighborhood, where $η$ is the stepsize. We also bound the discrepancy between the penalized Gibbs distribution and the constrained target. In a two dimensional quadratic model, we establish nonreversible acceleration by tuning the skew perturbation to the curvature imbalance induced by penalization. With the target accuracy and smaller curvature fixed and initial Wasserstein distances uniformly bounded, tuning the skew perturbation improves the sufficient Euler iteration bound from linear to logarithmic in the curvature ratio. Numerical experiments evaluate the algorithms on constrained Bayesian regression, classification, neural networks, and truncated sampling, and examine the acceleration mechanism in a stochastic quadratic model.

0.17

Subpolynomial-Query Proximal Sampling Beyond Log-Concavity

cs.CC stat.MLcs.LGmath.ST ·2026-11-02 ·Wei Guo, Bo Yuan, Ye He, Jiaming Liang, Molei Tao +1 more
theory similarity 0.68
Abstract

We study the gradient query complexity of sampling from a density $π(x)\propto\mathrm{e}^{-V(x)}$ on $\mathbb{R}^d$, where $V$ has a $β$-Lipschitz gradient but need not be convex. Our approach uses the proximal sampler, which alternates Gaussian perturbation with sampling a position conditional on the noisy observation. We implement its observation chain using the high-order noisy conditional sampler of [OpenAI 2026], obtaining improved dimension dependence under functional inequalities. If $π$ satisfies a log-Sobolev inequality (LSI) with constant $α$, then for every fixed $ν>0$, there is a finite constant $C_ν$ depending only on $ν$ such that the algorithm returns a sample within total-variation distance $\varepsilon$ using at most $C_νκ(d+κ+\varepsilon^{-1}+\|\nabla V(x_0)\|^2/β)^ν$ queries, where $κ=β/α$ and $x_0$ is an arbitrary reference point for initialization. The analysis controls center-dependent local errors along exact proximal histories and removes the final observation noise by conditional decoding. Under a Poincaré inequality (PI), we obtain a corresponding guarantee from a warm start with a known bound on its Rényi divergence. An oracle lower bound shows that a stationary point alone, which suffices under LSI, is insufficient under PI.

0.17

Zeroth-Order Langevin Dynamics for Stochastic Nonconvex Optimization: Curvature Regularization and Non-Asymptotic Guarantees

cs.LG math.OCmath.PRstat.ML ·2026-11-07 ·Stefano Bruno, Dong-Young Lim
similarity 0.63
Abstract

Zeroth-order methods provide a way to optimize stochastic nonconvex objectives using only noisy function evaluations. However, the smoothing inherent in their gradient estimators effectively modifies the objective being optimized. In particular, Gaussian smoothing with smoothing parameter $η>0$ induces, to leading order, an implicit Hessian-trace regularization, which motivates the study of the curvature-regularized objective of the form $f(x)+(η^2/2) tr(\nabla^2 f(x))$. We develop a non-asymptotic theory in the nonconvex setting for a class of algorithms called stochastic zeroth-order Langevin dynamics (ZOLD), which use only noisy function evaluations and do not have access to first- or higher-order derivative information, and derive excess-risk guarantees for the curvature-regularized objective. We first control the finite-time distribution of the ZOLD iterates in Wasserstein distance with respect to the Gibbs measure associated with the Gaussian-smoothed objective. An explicit coupling between the smoothing and inverse temperature parameters then quantifies the proximity of this measure to the Gibbs measure associated with the corresponding Hessian-trace-regularized objective. These distributional estimates in Wasserstein distance lead to excess-risk bounds for the curvature-regularized objective. Our analysis accommodates assumptions under which the stochastic function evaluations are allowed to have non-uniform dependence on the data stream. In addition, the constants in the non-asymptotic bounds do not rely on log-Sobolev or Poincaré inequalities as in prior zeroth-order Langevin analyses. To the best of our knowledge, this is the first non-asymptotic analysis of a zeroth-order Langevin method that simultaneously establishes excess-risk guarantees for a curvature-regularized objective and Wasserstein guarantees for the associated Gibbs measure in the nonconvex setting.

0.14

Muon meets Tamed Langevin: Momentum Preconditioning beyond Convex and gradient-Lipschitz Potentials

cs.LG math.OCmath.PRstat.ML ·2026-10-01 ·Nikolaos Makras, Sotirios Sabanis
theory similarity 0.62
Abstract · 26pages

We consider the problem of sampling from Gibbs distributions on matrix spaces whose potential energies are neither convex nor globally gradient-Lipschitz. We introduce a family of non-quadratic kinetic energies that lead to a new underdamped Langevin system with momentum preconditioning, in which the gradient of the kinetic energy acts as a smooth spectral taming of the momentum. We prove that, under these relaxed assumptions on the potential, the resulting dynamics leaves the target Gibbs measure invariant, and we establish exponential convergence to equilibrium in a weighted total variation distance. Finally, we show that the corresponding Euler-Maruyama discretization admits moment bounds that are uniform in time, without any modification of the potential gradient, which ensures the stability of the resulting sampling algorithm.

0.43

Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions

cs.LG math.STmath.PR ·2026-09-11 ·Weiming Ou, Xiao Wang
hot direction similarity 0.62
Abstract · Under Review

We establish the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in every fixed dimension $d\geq1$. For $μ$-strongly convex, $L$-smooth potentials with unknown minimizers $x_f^\star$ in the ball $\mathbb{B}(0,μ^{-1/2})$, and unbiased gradient oracles with variance at most $σ^2$, the minimax worst-case expected query complexity is $Θ\left(\log(1+κ)+\frac{σ^2}{μ\varepsilon}\right)$, jointly optimal for the condition number $κ:=L/μ$, variance $σ^2\ge 0$, and TV accuracy $0<\varepsilon\leq 1/10$. In the noiseless setting $σ=0$, this tight complexity $Θ\left(\log(1+κ)\right)$ is independent of $\varepsilon$. Moreover, a gradient-only sampler generates an exact sample with ${O}(\log(1+κ))$ worst-case expected queries. Without previous ball $\mathbb{B}(0,μ^{-1/2})$, exact sampling from any initial point $x_0$ can be implemented with expected cost ${O}\left(\log(1+κ)+\log(1+\sqrtμ\|x_0-x_f^\star\|)\right)$, without knowing the initial distance. We also show that dependence on initial distance is generally unavoidable.

0.25

Statistical Rates for Entropic Optimal Transport in the Discrete to SubGaussian Regime

cs.LG math.ST ·2026-09-22 ·Tomas Gonzalez, Gonzalo Mena
theory similarity 0.62
Abstract

We study statistical rates in entropic optimal transport in the semi-discrete regime where one measure has finite support and the other is subGaussian. Our main result establishes parametric convergence rates for the empirical dual potentials to their population counterparts, with no dimension dependence in the leading term. Our result relies on tailored strong concavity analysis of the semi-dual objective, coupled with specialized bounds for the semi-discrete potentials. As a consequence, we obtain fast rates for downstream quantities derived from the optimal coupling. Chiefly, the empirical barycentric projection achieves a squared-error rate $n^{-1}$, matching the fully compact case and improving over the less favorable $n^{-1/2}$ rate known for fully subGaussian settings. Altogether, these results may indicate a lower complexity adaptation phenomenon whereby the statistical complexity of the barycentric projection is governed by the discrete measure. As an application, we analyze Sinkhorn-EM, an EM-type algorithm in which the E-step is replaced by an entropic optimal transport problem. In a well-specified and balanced two-component Gaussian mixture model, we prove $\sqrt{n}$-consistency of the empirical iterates to their population counterparts for any fixed number of iterations, matching classical EM rates up to a $\sqrt{\log n}$ factor. Simulations support the theory.

0.12