改进了非光滑目标采样算法的收敛性分析,关键突破在更精确的误差控制。
Active-Trace Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling
- 用Moreau包络平滑非光滑目标,通过活跃迹控制采样误差
- 对典型稀疏惩罚项实现ε⁻²复杂度,优于传统ε⁻³的理论上限
- 适合需要高精度采样的机器学习优化与贝叶斯推断场景
本文研究针对非光滑复合目标 π(dx) ∝ exp{−f(x)−g(x)}dx(x∈R^d)的Moreau-Yosida无调整Langevin算法(MYULA)。其中,f是m-强凸且L_f-利普希茨梯度,g是凸且G-利普希茨。令g_λ为g的Moreau包络,π_λ为对应平滑目标,a_λ = tr H_λ,H_λ为g_λ的几乎处处/弱海森矩阵。我们证明:MYULA的主导离散误差由参考活跃迹B_ref控制,而非全局曲率界d/λ。若M_λ为a_λ的几乎处处上界,则在对数因子内,迭代次数满足: N ≲ (1/m)[L_f + (τ_f + G² + B_ref)/ε_alg² + M_λ/ε_alg],即可保证√m W₂(μ_N, π_λ) ≤ ε_alg,其中μ_N为第N步迭代分布,W₂为二次沃尔什斯特距离。同时证明了Moreau偏差界:√m W₂(π_λ, π) ≤ G²λ/4。因此取λ ≍ ε/G²可得π的端到端保证。通用估计B_ref ≤ d/λ给出~O(ε⁻³)精度依赖;而对分段线性、Lasso型、组和总变差等结构化惩罚项,曲率-管估计使B_ref与λ无关,从而实现~O(ε⁻²)的相同经典MYULA核复杂度。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。