acceptodds
Under review as a conference paper at ICLR 2027

A Poisson Corrector for Complexity Bounds of Moreau–Yosida Unadjusted Langevin Sampling

Abstract

We study the classical Moreau–Yosida unadjusted Langevin algorithm (MYULA) of sampling from , where is -strongly convex and has a -Lipschitz gradient, and is convex and globally -Lipschitz. For the Moreau-smoothed target and the MYULA invariant law , we prove under , with only logarithmic dependence on in the error coefficients. Combining this estimate with the Moreau approximation bias yields iterations to achieve , 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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Langevin sampling, Moreau-Yosida regularization, nonsmooth log-concave sampling, Poisson correctors, Wasserstein convergence, iteration complexity

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_uVqNOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the complexity of the classical Moreau-Yosida unadjusted Langevin algorithm (MYULA) for sampling from strongly log-concave distributions with a smooth strongly convex component and a nonsmooth convex Lipschitz component. Building on the Poisson-corrector framework and the active-trace analysis, the authors establish a refined invariant-measure bias bound of order O(h)+O~(h3/4)O(h)+\tilde O(h^{3/4}), with only logarithmic dependence on the inverse smoothing parameter in the error coefficients. Combining this estimate with the Moreau approximation bias yields an end-to-end iteration complexity of O~(ϵ−4/3)\tilde O(\epsilon^{-4/3}), improving upon the O~(ϵ−2)\tilde O(\epsilon^{-2}) bound obtained by directly applying the existing Poisson-corrector result.

Critical strengths
  1. The paper addresses a relevant theoretical problem concerning the interaction between Moreau regularization and discretization errors in Langevin sampling for nonsmooth potentials.
  2. The improved O~(ϵ−4/3)\tilde O(\epsilon^{-4/3}) complexity bound is a meaningful quantitative improvement over the O~(ϵ−2)\tilde O(\epsilon^{-2}) benchmark. The result applies to general convex Lipschitz nonsmooth components without requiring additional geometric assumptions on their structure.
  3. The shared-noise two-point curvature estimate provides an interesting technical ingredient for controlling the dependence on the smoothing parameter.
Critical weaknesses
  1. The analysis largely follows the Poisson-corrector framework of Pedrotti and Whalley (2026) and builds on the active-trace techniques of Xin and Zhang (2026). The main new ingredient is the shared-noise two-point curvature estimate, together with refined moment and variance bounds. While these estimates appear technically nontrivial, the contribution is primarily a refinement of existing analytical techniques. It remains unclear whether the proposed analysis provides broader theoretical insights beyond improving the complexity bound for classical MYULA.

  2. Although the improved O~(ϵ−4/3)\tilde O(\epsilon^{-4/3}) rate is meaningful, the improvement is established asymptotically with fixed model parameters and dimension. The explicit bounds also introduce a potentially less favorable dimension dependence than the direct Poisson-corrector benchmark. A more detailed comparison of the parameter regimes in which the new result provides a substantial improvement would strengthen its significance. Furthermore, it remains unclear whether the h3/4h^{3/4} bias dependence reflects an intrinsic feature of MYULA or a limitation of the current analysis.

Questions for authors
  1. The proposed analysis builds on the Poisson-corrector framework of Pedrotti and Whalley (2026) and the active-trace approach of Xin and Zhang (2026). Could the authors clarify what fundamental mathematical difficulty is resolved by the new shared-noise two-point curvature estimate, and whether this estimate provides insights beyond the existing frameworks?

  2. The proposed invariant-measure bias bound scales as O(h)+O~(h3/4)O(h)+\tilde O(h^{3/4}), whereas the existing Poisson-corrector analysis achieves O(h)O(h) for a fixed smooth potential, albeit with unfavorable dependence on the smoothing parameter. Is the h3/4h^{3/4} dependence inherent to obtaining favorable smoothing dependence, or does it arise from specific inequalities in the current analysis? What are the main obstacles to improving this rate?

  3. Can the shared-noise curvature estimate be extended to other Langevin discretizations or nonsmooth sampling algorithms? If not, which properties of the classical MYULA dynamics are essential to the argument?

3 comments

Thank you for your comments and questions. We have revised the manuscript, while the main theoretical results and proof arguments remain unchanged in substance. All references below refer to the first revised manuscript, iclr2027_R1.

1. Mathematical difficulty and the new estimate.

The corrected-error recursion in Section 6.1 requires controlling E ⁣[χh(Xkh)⊤Akgχh(Xkh)],\mathbb E\!\left[ \chi_h(X_{kh})^\top A_k^g\chi_h(X_{kh}) \right], where χh\chi_h is the Poisson corrector and AkgA_k^g represents the Moreau curvature between the coupled states. Using the worst-case bound Akg⪯λ−1IA_k^g\preceq\lambda^{-1}I gives h2R2/λh^2R^2/\lambda, whereas Proposition 6.3 gives O~(h3/2)\widetilde O(h^{3/2}), with only logarithmic dependence on λ−1\lambda^{-1}. As explained in Section 6.3, this changes the contribution of this particular term to the Wasserstein bound from O(h/λ)O(h/\sqrt\lambda) to O~(h3/4)\widetilde O(h^{3/4}).

The difficulty is that the relevant curvature lies along the random segment joining the actual diffusion and Euler states, which is not directly controlled by existing reference-path averages. Proposition D.1 uses their shared Gaussian noise to average curvature along this segment and control it through the bounded Moreau gradient, avoiding the worst-case curvature bound. Combined with higher corrector moments and Hölder’s inequality (Appendix D.2), this handles the correlation between curvature and the corrector and improves the smoothing dependence of this term within the existing Poisson-corrector framework.

2. Generality and broader theoretical insights

Generality of the curvature estimate.

The mechanism in Section 6.3 and Appendix D.1 is that a common Gaussian shift of two endpoints also shifts the entire segment joining them. For a convex function with bounded gradient, Gaussian integration by parts then controls the expected Hessian trace along this segment through the gradient bound(see Appendix D.1, proof of Proposition D.1, Step 1). For the exact diffusion, the endpoint is not a simple Gaussian shift because the drift also depends on the noise. Our small-step condition ensures that its response to the shared noise remains close to that of the Euler endpoint, allowing the same averaging argument to apply. These conditions are not specific to MYULA: for example, replacing the deterministic Euler update by another deterministic map before adding the same Gaussian noise leaves this local argument unchanged.

Broader theoretical insight and scope.

The broader insight is that shared noise can control curvature along the segment between the actual coupled states, even when the worst-case Hessian bound diverges as smoothing decreases. This may provide a reusable way to exploit averaged curvature in coupling analyses. Whether it improves another algorithm’s convergence rate requires further analysis: the corresponding curvature term must arise and limit the existing bound, while the remaining local-error, corrector, and mixing estimates must also be established.

3.Origin and possible improvement of the rate

Where the exponent comes from.

The h3/4h^{3/4} rate arises from our current estimates; we do not establish it as an inherent cost of favorable smoothing dependence. The nonsmooth martingale variance and curvature feedback each contribute O~(h5/2)\widetilde O(h^{5/2}) per step (Propositions 6.2–6.3). Accumulation under contraction gives O~(h3/2)\widetilde O(h^{3/2}) mean-square error, hence the O~(h3/4)\widetilde O(h^{3/4}) bound (Section 6.4).

Possible limitation of synchronous coupling.

Figures 1–2 support h3/4h^{3/4} synchronous RMS scaling along the tested decreasing-smoothing paths, while suggesting Wasserstein bias of order hh. As discussed at the end of Section 7, this suggests that our analysis captures the synchronous-error scaling, but bounding Wasserstein bias by this error may limit the rate.

Obstacles to improvement.

Within the current recursion, improving only one nonsmooth estimate leaves the other as a bottleneck. Moreover, if the observed h3/4h^{3/4} synchronous-error scaling persists asymptotically, sharpening the RMS bound for this same coupling would not suffice to obtain an O(h)O(h) Wasserstein bound. Such an improvement may require exploiting cancellations at the level of the invariant laws or using a different coupling, while avoiding the unfavorable inverse-power dependence on λ\lambda in the existing fixed-smooth-potential analysis.

4.Parameter regimes and dimension dependence

We have added a parameter comparison in Section 2 (“Poisson correctors and a direct MYULA benchmark”), complementing our main improvement of the accuracy exponent from 22 to 4/34/3 for fixed model parameters and dimension.

Dimension dependence and the role of GG.

For m,Lf,G=Θ(1)m,L_f,G=\Theta(1), our O~(dε−4/3)\widetilde O(d\varepsilon^{-4/3}) bound has a larger dimension factor than the O~(d ε−2)\widetilde O(\sqrt d\,\varepsilon^{-2}) benchmark, but improves it when ε≪d−3/4\varepsilon\ll d^{-3/4}, up to logarithmic factors. Dimension dependence can also improve when GG grows with dd. For example, g(x)=ρ∥x∥1g(x)=\rho\|x\|_1 with fixed ρ>0\rho>0 has G=ρdG=\rho\sqrt d. With m,Lf=Θ(1)m,L_f=\Theta(1), our bound becomes O~(d4/3ε−4/3)\widetilde O(d^{4/3}\varepsilon^{-4/3}), compared with O~(d3/2ε−2)\widetilde O(d^{3/2}\varepsilon^{-2}) for the benchmark, improving both exponents. Thus, the comparison depends jointly on accuracy, dimension, and model parameters such as GG; neither bound is uniformly better across all parameter regimes.

Thank you for the clarifications. However, my main concern remains. The main contribution seems to be sharper estimates within the existing Poisson-corrector framework. The dimension dependence is worse in some regimes, and the numerical results suggest that the Wasserstein bound may not be sharp. Although the improved complexity rate is useful, I still find the overall contribution rather limited and therefore maintain my original score.

Reviewer_1zpCOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper aims to provide complexity bounds for classical Moreau–Yosida unadjusted Langevin algorithm (MYULA), which treats a composite target with potential f(x)+g(x)f (x) + g (x). Here f∈C2f \in C^2 is mm-strongly convex and gg is convex and both are Lipschitz. Following the Poisson-corrector framework of Pedrotti & Whalley (2026), the authors show that the Wasserstein error bounds between the Moreau-smoothed target and the MYULA invariant law logarithmically depend on λ−1\lambda^{-1}. This is an interesting point. Some refinements are done to obtain improved error bounds.

Critical strengths

The Wasserstein error bounds between the Moreau-smoothed target and the MYULA invariant law logarithmically depend on the inverse smoothing parameter λ−1\lambda^{-1}.

Critical weaknesses
  1. The strongly convex or convex setting is restrictive. The authors should give some examples in applications that obeys the setting.

  2. No numerical evidence to support findings.

Questions for authors
  1. More details on "it does not establish optimality of the accuracy exponent 4/3" in the CONCLUSION part;

  2. Can the step-size restriction be further improved? I mean, the dependence on the inverse smoothing parameter;

  3. No evidence to support the rate h3/4h^{3/4} in the error bound. Have you implemented numerical tests?

  4. Some numerical experiments are necessary.

2 comments

Thank you for your comments and questions. We have revised the manuscript to improve its presentation and added numerical illustrations and application examples. The main theoretical results and proof arguments remain unchanged in substance. All references to sections, theorems, figures, and appendices below refer to the first revised manuscript, iclr2027_R1.

1. Meaning of the 4/34/3 exponent.

Theorem 5.2 (End-to-end complexity) establishes a sufficient iteration-complexity upper bound of O~(ε−4/3)\widetilde O(\varepsilon^{-4/3}) for fixed model parameters, dimension, and initialization. Combining the bias bound in Theorem 5.1 with the Moreau approximation bound gives λ=ε/G2\lambda=\varepsilon/G^2 and h=Θ~(ε4/3)h=\widetilde\Theta(\varepsilon^{4/3}), which yield this exponent. We do not establish a matching lower bound; thus, we do not claim that 4/34/3 is optimal, and a better complexity guarantee may be possible.

2. Added numerical experiments.

Section 7 (Numerical illustration), Figure 1, and Appendix G, Figure 2, now report experiments for f(x)=x2/2f(x)=x^2/2 and gβ(x)=∣x∣+βxg_\beta(x)=|x|+\beta x, with β∈0,0.5,1\beta\in{0,0.5,1}. We test fixed λ\lambda, λ∝h3/4\lambda\propto h^{3/4}, and λ∝h\lambda\propto h, measuring both the invariant-measure bias W2(π^λ,h,πλ)W_2(\widehat\pi_{\lambda,h},\pi_\lambda) and the near-stationary synchronous-coupling RMS error. Numerical procedures and sensitivity checks are provided in Appendix G.

3. What the observed rates imply.

Over the tested range in Figure 1, the Wasserstein bias has slopes approximately 0.990.99–1.001.00, whereas the synchronous RMS has slopes approximately 0.770.77 and 0.750.75 along the two decreasing-smoothing paths. Figure 2 shows the same qualitative behavior for the other models. As discussed in the final paragraph of Section 7, the RMS slopes close to 3/43/4 provide numerical evidence that our analysis captures the correct power of hh for the long-time synchronous error ∣Xkh−X^k∣L2|X_{kh}-\widehat X_k|_{L^2} along the decreasing-smoothing paths. The observed Wasserstein bias suggests that the distance between the invariant laws may be of order hh in these examples, and that the remaining loss may arise from bounding this distance by the synchronous coupling error.

4.Step-size dependence on the smoothing parameter.

Weakening the dependence on λ−1\lambda^{-1} presents difficulties for our current proof. The corrected-error recursion in Section 6.1 and the global W2W_2 contraction in Lemma E.2 rely on hLλhL_\lambda being sufficiently small. When h/λh/\lambda is large, the Euler map can be locally expansive, so retaining our bias and complexity guarantees would require new averaged error estimates and a different mixing argument. Under the parameter choices in Theorem 5.2, however, hε/λε→0h_\varepsilon/\lambda_\varepsilon\to0, so this restriction is not asymptotically dominant. Relaxing h=O(λ)h=O(\lambda) alone would therefore not automatically improve the current 4/34/3 accuracy exponent.

5.Application examples

We have added application examples immediately after Assumption 4.2 in Section 4. These include Gaussian linear inverse problems with full-column-rank operators and TV priors (Habring et al., 2024; Pereyra et al., 2020), and Bayesian elastic-net coefficient posteriors with fixed positive hyperparameters (Li and Lin, 2010).

Thanks! My concerns have been addressed and I keep the rating.

Reviewer_mvKsOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper analyzes MYULA, the Moreau–Yosida unadjusted Langevin algorithm. It samples from π∝e−f−g\pi \propto e^{−f−g}, where f is smooth and strongly convex and g is convex and Lipschitz. The authors follow the discrete Poisson-corrector framework and prove an invariant-measure bias of O(h)+O~(h3/4)O(h) +\tilde O(h^{3/4}). Combined with the Moreau approximation bias, this yields an iteration complexity guarantee Wasserstein convergence.

Critical strengths

The paper provides a solid proof for the Wasserstein convergence of MYULA.

Critical weaknesses

The work seems more like a lecture note, instead of a paper. It tells us a problem setup, a final theorem, and how to prove the theorem. What it fails to present is why the problem is important, how to locate the work in the literature, how to compare the results and what insight is contained in the proof.

To make it get closer to the acceptance threshold, a thorough revision should be completed, including

  1. Revision of the introduction: Write about why to solve this problem, what does the existing work do, what’s the gap to be improved and how to distinguish this work from the previous work. A contribution section should also be provided, including the innovative techniques in plain language to show why this work can get results better than prior.

  2. Revision of the main results section: Most of the concrete formulas of the parameters do not help with understanding. Try to move them to the appendix and only exhibits those formulas that can provide motivation for the proof or theorem concept.

  3. Revision of the “ PROOF OF THE MAIN RESULTS” section: Directly presenting the proof pipeline is not helpful at all. Instead, consider presenting the proof in a human reasoning order. For example, you can start with the limitation of the analysis in prior work, and present what modification or proof techniques you apply to avoid that limitation. Of course the writing style is not unique. However, it’ more important to present the thinking and reasoning in the paper rather than the direct proof.

Questions for authors

See Weaknesses

2 comments

Thank you for the detailed suggestions on presentation. We have revised the manuscript in the three areas you identified. All section and appendix references below refer to the first revised manuscript, iclr2027_R1.

1. Motivation, literature positioning, and contributions — Sections 1–2.

The opening paragraphs of Section 1 now motivate MYULA through Bayesian uncertainty quantification and imaging applications. The example g(x)=G∣x∣g(x)=G|x| explains why worst-case curvature can obscure the behavior of the dynamics as smoothing decreases. We have expanded and reorganized Section 2 to clarify the relationship with previous MYULA analyses, the direct Pedrotti–Whalley benchmark, and other composite samplers. The new “Our contributions” list in Section 1 highlights the improved accuracy exponent and explains in plain language how shared noise and bounded gradients enable the new curvature estimate.

2. Main results and explicit parameter formulas — Section 5 and Appendix F.

Section 5 now emphasizes the bias bound, its smoothing dependence, and the O~(ε−4/3)\widetilde O(\varepsilon^{-4/3}) complexity guarantee. We moved the explicit definitions of R,KR,K to Appendix F.1, the intermediate bias calculations to Appendix F.2, and the detailed step-size choice and expanded iteration bound to Appendix F.3. The text following Theorem 5.2 explains how the step-size scaling produces the 4/34/3 exponent.

3. Proof exposition organized around the mathematical difficulties — Section 6.

Section 6 now begins with the limitation of using the global smoothness bound as λ\lambda decreases. Section 6.1 follows the Poisson-corrector framework of Pedrotti and Whalley (2026) to derive the error recursion. It then identifies where our analysis introduces sharper estimates: the martingale variance and curvature feedback, addressed in Sections 6.2 and 6.3, respectively. Section 6.2 explains how bounded gradients and averaged curvature improve the variance estimate. Section 6.3 compares the worst-case curvature estimate with our bound, then uses a simple common-Gaussian-shift example to explain how integration by parts controls segment curvature through the gradient bound. Finally, Section 6.4 explains how these estimates produce the h3/4h^{3/4} rate.

Thank you for your response. The presentation looks better now. However, I still think it is below the average presentation of ICLR conference papers. For example, there is no need to present so many constants in Theorem 5.1, hiding the key message it wants to convey. The remark after Theorem 5.2 is not quite relevant, missing the more important discussions, such as the implication of the theoretical results, and on the comparison with prior work. The proof section gets better, but is still not good enough and deserves more revision.

I will increase my score to 2 to reflect the improvement. However, I still think it does not meet the bar for acceptance.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.