Skip to content

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

Sep 2026 · arXiv.org · Vol abs/2609.40193 · 0 citations
Computer Science

Abstract

We establish near-linear accuracy bounds for the classical Moreau--Yosida unadjusted Langevin algorithm (MYULA). The target is $\pi\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 $\mu_N$ satisfy $\sqrt m\,W_2(\mu_N,\pi)\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.

View source

Similar papers

Penalized Nonreversible Langevin for Constrained Sampling

We propose penalized nonreversible Langevin algorithms for sampling from $\pi(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 prese...

P. Ali, Wei-Hao Dong, Xiao-Yu Wang · 0 citations
Preprint Oct 2026

Closing the Accuracy Gap in Stochastic First-Order Bilevel Optimization

The optimal accuracy dependence for smooth nonconvex--strongly-convex bilevel optimization with stochastic first-order oracles is characterized and an $\Omega(\epsilon^{-6})$ lower bound matching the accuracy exponent of existing upper bounds is proved.

Hai-Han Zhang, Wen-Dao Wu, Chen-Heng Zhang et al. · 0 citations
Preprint Oct 2026

On the Quantitative Bounds of Nonlinear Roth Theorem

We prove that any subset $A \subseteq \{1, \dots, N\}$ lacking non-trivial polynomial progressions $(x, x + y, x + y^2)$ satisfies $\lvert A \rvert \le CN \exp\bigl(-c(\log \log N)^\beta\bigr)$ for effective absolute constants $C, c, \beta>0$. The argument develops a density increment framework localized to anisotropic...

Yun-Fan Zhao · 0 citations
Preprint Oct 2026

Minimax estimation of linear functionals in the Darcy inverse problem

We study estimation of linear functionals $\int f\psi$ of the conductivity $f$ in the Darcy problem $\nabla\cdot(f\nabla u)=g$ from observations of $u$ in Gaussian white noise of level $N^{-1/2}$. When the potential has a single nondegenerate minimum, we determine the minimax rates over Sobolev balls in the linearised...

Yi Liu, Xiao-Tian Chang, Qi-Rui Hu · 0 citations
Preprint Oct 2026

The Minimax Cost of Smoothness in Fully First-Order Stochastic Bilevel Optimization

We study the sample complexity of finding a point with expected hypergradient norm at most $\epsilon>0$ in nonconvex--strongly-convex stochastic bilevel optimization using fresh, globally unbiased first-order samples with bounded variance. For lower-variable smoothness order $p\ge1$, F$^2$SA-$p$ achieves $\widetilde O(...

Wen-Dao Wu, Hai-Han Zhang, Chen-Heng Zhang et al. · 0 citations
Preprint Oct 2026

Weighted Gagliardo--Nirenberg Inequalities of Grushin Type: Symmetries, Compactness, and Optimizers

In this paper, we study a family of weighted Gagliardo--Nirenberg interpolation inequalities associated with Grushin--type operators on $\mathbb{R}^n \times \mathbb{R}^m$. Specifically, we examine how to control the weighted norm $\||x|^\beta u \|_{L^B}$ by balancing fractional derivatives $D_x^s u$ with weighted deriv...

Amin Esfahani · 0 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.