Related papers: Active-Trace Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling

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

URL: http://arxiv.org/abs/2608.13467v1
Date: Thu, 13 Aug 2026 16:47:41 GMT
Title: Active-Trace Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling
Abstract summary: We study the Moreau--Yosida unoperator Langevin algorithm (MYULA) for the nonsmooth composite target [()propto expf(x)-g(x),dx, qquad xinmathbb Rd, ]<n>We show that the leading MYULA discretization error is controlled by the reference active trace (B_mathrmref), the average of (a_) along the heat substep of one MYULA update started from (
Score: 9.454986540713655
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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.

Related papers

Poisson-Corrector Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling [9.454986540713655]
We study the classical Moreau--Yosida unadjusted Langevin algorithm (MYULA) for $(,mathrmd x)propto e-f(x)-g(x),mathrmd x$, where $fin C2(mathbbRd)$ is $m$-strongly convex with $L_f$-Lipschitz gradient and $g:mathbbRdtomathbbR$ is convex and globally $G$-Lipschitz
arXiv Detail & Related papers (2026-09-11T08:47:33Z)
Optimal Neural Network Approximation via Empirical Least Squares with Deterministic Samples [7.864201093845001]
We develop a theory of discrete residual least-squares approximation for elliptic spectral equations $mathfrak L_u=f$ using linearized ReLU$k$ neural networks.<n>We establish a high-probability residual estimate, up to a logarithmic factor and an arbitrarily small smoothness loss.<n>The key analytical ingredient is a Bernstein inequality for linearized ReLU$k$ network spaces.
arXiv Detail & Related papers (2026-08-07T01:22:27Z)
A Bundle Isomorphism Relating Complex Velocity to Quantum Fisher Operators [0.0]
We show that averaging matter dynamics over gravitational fluctuations gives rise to a complex velocity field (_ = _ - i u_) living as a section of the pullback bundle (E = _2*(T*M)to mathcalCtimes M.<n>We prove that (_) is isomorphic, via the Schrdinger representation, to the symmetric logarithmic derivative (SLD) operator (L_) on the Hilbert space (mathcalH
arXiv Detail & Related papers (2026-04-14T01:35:43Z)
Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
arXiv Detail & Related papers (2026-03-20T01:53:44Z)
Complexity Bounds for Hamiltonian Simulation in Unitary Representations [0.0]
We consider the Hamiltonian evolution [ U_X(t) coloneqq (exp(tX)) = et,d(X), qquad tinmathbbR.<n>We first describe how the Hamiltonian (d(X)) is distributed along the directions of root spaces $mathfrakg_$.<n>Our main result shows that for each fixed (Xinmathfrakg) there exists a constant such that
arXiv Detail & Related papers (2026-03-07T14:28:46Z)
Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
arXiv Detail & Related papers (2025-08-28T17:04:18Z)
Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
We show that the Monotonic Value Omega (MVP) algorithm achieves a variance-aware gap-dependent regret bound of $$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land mathttVar_maxtextc$.
arXiv Detail & Related papers (2025-06-06T20:33:57Z)
Exact objectives of random linear programs and mean widths of random polyhedrons [0.0]
We consider emphrandom linear programs (rlps) as a subclass of emphrandom optimization problems (rops) Our particular focus is on appropriate linear objectives which connect the rlps to the mean widths of random polyhedrons/polytopes.
arXiv Detail & Related papers (2024-03-06T11:51:52Z)
Capacity of the Hebbian-Hopfield network associative memory [0.0]
In citeHop82, Hopfield introduced a emphHebbian learning rule based neural network model and suggested how it can efficiently operate as an associative memory. We study two famous pattern's basins of attraction: textbfemph(i) The AGS one from citeAmiGutSom85; and textbfemph(ii) The NLT one from citeNewman88,Louk94,Louk94a,Louk97,Tal
arXiv Detail & Related papers (2024-03-04T10:10:23Z)
On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
This paper considers the RMSProp and its momentum extension and establishes the convergence rate of $frac1Tsum_k=1T.<n>Our convergence rate matches the lower bound with respect to all the coefficients except the dimension $d$.<n>Our convergence rate can be considered to be analogous to the $frac1Tsum_k=1T.
arXiv Detail & Related papers (2024-02-01T07:21:32Z)
Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
arXiv Detail & Related papers (2022-06-17T17:55:43Z)
On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
We describe an implicit sparsity-inducing mechanism based on over a family of kernels. As an application, we use this sparsity-inducing mechanism to build algorithms consistent for feature selection.
arXiv Detail & Related papers (2021-10-12T09:36:41Z)
Optimal Mean Estimation without a Variance [103.26777953032537]
We study the problem of heavy-tailed mean estimation in settings where the variance of the data-generating distribution does not exist. We design an estimator which attains the smallest possible confidence interval as a function of $n,d,delta$.
arXiv Detail & Related papers (2020-11-24T22:39:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.