acceptodds
Under review as a conference paper at ICLR 2027

MASLA: Metropolis-Adjusted Subdifferential Langevin Sampling for Nonsmooth Nonconvex Potentials

Abstract

Sampling from distributions with nonsmooth nonconvex potentials challenges gradient-based Langevin methods and can complicate proximal approaches. We introduce Metropolis-adjusted subdifferential Langevin algorithm (MASLA), which combines a fixed measurable selection from a conservative field with an exact Metropolis–Hastings correction. The method accommodates locally Lipschitz potentials without requiring smoothing or a proximal mapping. We establish well-posedness, reversibility, and exact invariance of the target distribution, together with positive Harris recurrence. Our central theoretical result rigorously proves geometric ergodicity for positive-definite quadratic potentials perturbed by Lipschitz functions admitting bounded conservative fields. The result provides an explicit admissible range of step sizes and holds from every initial point, including points of nondifferentiability. Numerical experiments verify the predicted geometric convergence behavior on a convex composite target and demonstrate competitive performance against proximal and subgradient samplers. Further experiments on a nonsmooth nonconvex target show that the Metropolis correction substantially reduces sampling error relative to unadjusted subdifferential Langevin dynamics. These results establish MASLA as a theoretically grounded sampling method for a class of nonsmooth nonconvex distributions.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Markov chain Monte Carlo, Metropolis-adjusted Langevin algorithm, Generalized subdifferential, Non-convex and non-smooth optimization, Exponential convergence

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_z6CXOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

Let π\pi be a probability density function of the form Cexp⁡(−U(x))C\exp(-U(x)) where CC is the normalizing constant and UU is a potential function defined on RdR^d. The goal of the paper is to analyze the METROPOLIS-ADJUSTED SUBDIFFERENTIAL LANGEVIN SAMPLING (MASLA) algorithm, which samples a random variable YY having a distribution close to the target π\pi. It is assumed that one has access to a measurable version of the conservative field of UU. Main results show that the MASLA algorithm is well-defined and geometrically ergodic under some conditions. I find these results interesting, but of limited importance compared to the standards of the top ML conferences. The paper also provides some numerical experiments, which are interesting. However, these experiments do not allow us to conclude that MASLA is better than the proximal algorithm.

Critical strengths

The problem of sampling from an unknown density has been central in theoretical and applied ML. The paper is easy to read; the main related work seems to be appropriately cited.

Critical weaknesses

The main contributions appear to be rather incremental. Having geometric ergodicity without any evaluation of ργ\rho_\gamma and is an important limitation. Another weakness is the lack of an example of UU that has some practical importance and for which the other existing approaches do not work as well as the present one. In other words, the current paper appears as a conceptual extension of existing methods and theories, rather than a study motivated by some concrete needs.

Minor remarks

  1. Page 2, just after eq 2.1: it should be mentioned that X0X_0 is independent of the Brownian motion WW.
  2. Section 2: for a fair account, it should be mentioned here that if the dimension is large (say, larger than 20) the acceptance rate of MALA can drop to a value very close to zero. This results in a very high computational cost of MALA in large dimensions.
  3. Eq (3.5): notation D(U)\mathcal D(U) is not defined at this stage
  4. Example 3.2: the Clarke subdifferential is mentioned here, without any connection to the notion of a conservative field.
  5. My feeling is that there is not enough novelty in Proposition 3.3 to state it as a proposition. This result directly follows from well-known facts.
Questions for authors

I have no question.

4 comments
AuthorsOpenReview ↗

Official comment to Reviewer z6CX

Thank you for your careful review. We agree that geometric ergodicity without evaluating its constants was an important limitation of the submitted manuscript. To address this concern, we have added Theorem 4.5 in Section 4.4, p. 7, which gives computable geometric convergence constants for MASLA under the assumptions of the geometric-ergodicity theorem. Its rigorous proof is provided in Section D.2, pp. 51–54, using the quantitative coupling result in Section D.1, pp. 48–50. We also agree that practical applications were needed to establish the relevance of the method. We have added two high-dimensional real-data analyses that existing methods are not directly applicable.

The revised manuscript contains 79 pages in total, with the notation table in Appendix I on pp. 77–79, while keeping the main text within 10 pages. The computable geometric constants, two high-dimensional real-data analyses, expanded numerical accuracy study, and clarifications above substantially strengthen both the theoretical content and practical motivation. Below, all page references refer to the revised file.

  1. Evaluation of the geometric convergence constants: new Theorem 4.5

The submitted result established geometric ergodicity but did not evaluate MγM_\gamma and ργ\rho_\gamma. Theorem 4.5 now constructs both constants for the class U(x)=12x⊤Hx+g(x),U(x)=\tfrac12 x^\top Hx+g(x), where HH is symmetric positive definite and gg is globally LL-Lipschitz with a conservative field bounded by BB. The selected drift is β(x)=Hx+v(x)\beta(x)=Hx+v(x) with ∥v(x)∥≤B\|v(x)\|\leq B. Writing h−h_- and h+h_+ for the extreme eigenvalues of HH, the result holds at every fixed step size 0<γ<2/h+0<\gamma<2/h_+. It allows nonconvex gg and does not require a warm start.

Specifically, the proof evaluates drift constants 0<θ<10<\theta<1 and b>0b>0 and a minorization constant 0<ϵγ≤1/20<\epsilon_\gamma\leq1/2 from d,h−,h+,L,Bd,h_-,h_+,L,B, and γ\gamma. With V(x)=1+∥x∥2V(x)=1+\|x\|^2, these satisfy

\qquad R_\gamma(x,\cdot)\geq\epsilon_\gamma\nu_{C_S}(\cdot)\quad(x\in C_S),$$ where $S=\max\{4,4b/(1-\theta)\}$, $C_S=\{x:V(x)\leq S\}$, and $\nu_{C_S}$ is normalized Lebesgue measure on $C_S$. Equation (4.8), p. 7, specifies $$\eta_\gamma=\frac{\epsilon_\gamma}{2b},\qquad M_\gamma=1+\frac{2}{\eta_\gamma}+\frac{b}{1-\theta} \qquad\text{and}\qquad \rho_\gamma=1-\frac{\epsilon_\gamma}{2+\eta_\gamma S}.$$ Theorem 4.5 proves that these choices satisfy $M_\gamma<\infty$, $0<\rho_\gamma<1$, and the bound in equation (4.9). The estimate concerns the MASLA kernel itself and includes initialization at nondifferentiable points. The proof evaluates the quantities entering these formulas, rather than leaving them as unspecified drift or minorization constants. First, it bounds the exact log MH ratio and constructs an acceptance radius in equations (D.7)–(D.9), pp. 51–52. Second, it derives the drift radius and inequality in equations (D.10)–(D.11), p. 52. Third, it constructs a common minorization on the required enlarged set in equations (D.12)–(D.13), p. 53. Finally, the weighted coupling bound of Lemma D.1 converts these estimates into the displayed $M_\gamma$ and $\rho_\gamma$. The construction uses the stated model bounds and does not require evaluating the target normalizing constant. Corollary D.2, p. 54, also gives a sufficient iteration count for an initial distribution $\mu$ with $\mu(V)<\infty$. For requested accuracy $0<\varepsilon<1$, it suffices to take $$n\geq\left\lceil\frac{\log(M_\gamma\mu(V)/\varepsilon)}{-\log\rho_\gamma}\right\rceil$$ to obtain $\|\mu R_\gamma^n-\pi\|_V\leq\varepsilon$. Thus the revision provides an evaluable rate and prefactor, as well as an iteration bound. These constants work for all requested accuracies at the fixed step size.
AuthorsOpenReview ↗

Official comment to Reviewer z6CX

  1. Two new high-dimensional real data analyses

We have added two inverse problems using measured data to complement the synthetic benchmarks. Both use nonsmooth nonconvex posterior models and compare MASLA and USLA at matched steps and update budgets. Each setting uses four independent repetitions of four chains, with 5000050000 updates and 1000010000 burn-in updates per chain.

Walnut X-ray tomography: Section 5.4, p. 9; Figure 4, p. 10; Appendix G, pp. 69–72; Table 3, p. 71. We reconstruct an 82×8282\times82 image, giving d=6724d=6724 unknowns, from measured walnut X-ray projections. The posterior combines a Gaussian observation model and ridge prior with capped total variation. This penalty makes the posterior nonsmooth and nonconvex while preserving the quadratic-plus-Lipschitz structure of our theoretical class. Sixty measured angles define the target, and thirty held-out angles assess prediction. MASLA increases mean held-out pointwise log predictive density from 1.734451.73445 to 1.765421.76542 and reduces prediction root mean squared error (RMSE) from 0.0322540.032254 to 0.0316620.031662. All four repetitions favor MASLA on both reported predictive metrics, and the exploratory paired intervals exclude zero. These results assess prediction of unseen physical measurements, not merely numerical stability.

Optical phase retrieval: Section 5.5 and Table 1, p. 10; Appendix H, pp. 73–76; Figure 10, p. 76. We use measured optical transmission-matrix data for three 16×1616\times16 real input patterns, each with d=256d=256 unknowns. The Gaussian amplitude likelihood leads to a nonsmooth nonconvex posterior with a quadratic-plus-Lipschitz decomposition. Each image is evaluated at two shared step sizes. We assess the absolute radial Stein residual using the exact posterior identity 1dEπPR[XTβ(X)]=1.\frac{1}{d}\mathbb E_{\pi_{\mathrm{PR}}}\left[X^{\mathsf T}\beta(X)\right]=1. Its known target value avoids reliance on an approximate reference chain. MASLA reduces the mean absolute residual by 94.194.1–96.3%96.3\% at the larger steps and 67.167.1–78.9%78.9\% at the smaller steps. All 2424 image–step–repetition pairs favor MASLA, and all six exploratory paired intervals exclude zero. This checks agreement with an exact posterior moment in addition to stability.

These applications provide high-dimensional evidence at d=6724d=6724 and d=256d=256, alongside the expanded d=100d=100 study. The reported predictive and moment diagnostics are selected finite-run comparisons. The appendices provide the models, data preparation, simulation settings, and uncertainty calculations.

  1. Practical motivation and the scope of comparisons

We agree that the submitted experiments did not establish superiority over proximal algorithms. The revised paper does not make a general claim of that kind. The convex benchmark in Section 5.1, p. 8, remains a comparison with established samplers; the new applications address the additional question of practical relevance for nonsmooth nonconvex targets that those algorithms are not directly applicable.

For each real-data example, we have added a specific discussion of why the cited competing frameworks do not directly apply: Section G.1, p. 70, for walnut tomography, and Section H.1, p. 74, for optical phase retrieval. The nonconvex potentials violate the convex-composite assumptions of Grad-sub and Prox-sub and the log-concavity and convex proximal/Moreau assumptions of the cited P-MALA and MYULA frameworks. In phase retrieval, we further show that the full-potential proximal map at zero is not single-valued. Classical gradient-based ULA/MALA also require an additional selection convention at the nonsmooth states. These discussions identify the specific assumptions and constructions that fail for our models.

We have also added an explanation of why MASLA can improve on USLA. In Section H.2, p. 75, equation (H.8) derives a positive-step discrepancy in the radial Stein identity for USLA: if its stationary law exists with the required finite moments, its normalized radial moment exceeds the target value by γEμγ∥β(X)∥2/(2d)\gamma\mathbb E_{\mu_\gamma}\|\beta(X)\|^2/(2d). MASLA's MH correction preserves the intended target, for which this discrepancy is zero. This provides a mathematical mechanism for the smaller Stein residuals observed in the phase-retrieval experiments.

AuthorsOpenReview ↗

Official comment to Reviewer z6CX

  1. Changes addressing the minor remarks

(i) Independence of the initial condition and Brownian motion. We now explicitly state immediately after equation (2.1), Section 2, p. 3, that the initial state is independent of the driving Brownian motion.

(ii) Acceptance and computational cost in high dimension. Section 2, pp. 3–4, now explains that acceptance can approach zero when the step size is too large relative to dimension and target geometry, and that reducing the step size can also reduce movement per iteration. It discusses the classical dimension-dependent MALA scaling under its stated smooth-target assumptions.

(iii) Undefined differentiability-set notation. Section 3, p. 4, now defines Df\mathcal D_f and distinguishes this set from the conservative field DfD_f. We further added a notation table in Appendix I on pp. 77–79.

(iv) Connection between the Clarke subdifferential and conservative fields. Example 3.2, p. 4, now refers explicitly to Definition B.8 and Propositions B.9–B.10, p. 23. Proposition B.10 relates the chain rule for the Clarke subdifferential to its conservative-field property, and Section B.2 verifies that chain rule for the example. Proposition B.9(ii) also explains that, whenever a locally Lipschitz function admits a conservative field, its Clarke subdifferential is conservative. The example therefore connects its subdifferential calculation to the field used in the algorithm.

(v) Status and placement of the former Proposition 3.3. We agree that exact invariance follows from standard MH arguments and should not be presented as a novel contribution. The full statement has been moved to Appendix, Proposition B.14 in Section B.2, p. 25. Section 3 retains a brief sentence referring readers to that result.

AuthorsOpenReview ↗

Follow-up before the discussion concludes

Dear Reviewer z6CX,

Thank you again for your careful review and constructive suggestions. As the discussion period draws to a close, we would like to briefly summarize how we addressed your main concerns:

  • Explicit geometric convergence constants: We added Theorem 4.5, which makes the geometric convergence constants MγM_\gamma and ργ\rho_\gamma explicitly computable and provides a corresponding iteration bound, rather than leaving the rate purely qualitative.
  • Practical motivation and real-data applications: We added two real-data nonsmooth nonconvex inverse problems—walnut X-ray tomography with d=6724d=6724 and optical phase retrieval with d=256d=256—for which the cited convex proximal and smooth-gradient frameworks are not directly applicable.
  • Why MASLA can improve on the unadjusted method: We added a mathematical explanation showing a positive-step discrepancy in the radial Stein identity for USLA, while the MH correction in MASLA preserves the intended target and removes this discrepancy.
  • Minor comments: We addressed all five points concerning independence assumptions, high-dimensional MALA acceptance, notation, the connection between Clarke subdifferentials and conservative fields, and the presentation of the standard MH invariance result.

If these revisions resolve your concerns, we would greatly appreciate it if you could consider reflecting this in your assessment.

Best regards,

Authors

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

By combining a fixed measurable conservative-field selection with an exact Metropolis–Hastings correction, the paper introduces Metropolis-adjusted subdifferential Langevin algorithm (MASLA) for sampling from distributions with locally Lipschitz potentials that may be nonsmooth and nonconvex. It is shown that MASLA preserves the target distribution without requiring smoothing or a proximal mapping. Notably, the paper established reversibility and positive Harris recurrence, characterized selection independence, and proved geometric ergodicity for positive-definite quadratic potentials with Lipschitz perturbations admitting bounded conservative fields. Numerical results confirmed the predicted geometric convergence behavior on a convex composite target and demonstrated competitive performance where existing proximal and subgradient methods apply. On a nonsmooth nonconvex target beyond their convex framework, MASLA substantially reduced sampling errors relative to unadjusted subdifferential Langevin dynamics. The topic of this paper is relevant in the area of sampling.

Critical strengths

New sampling algorithms with ergodicity guarantees.

Critical weaknesses

For numerical tests, many efforts are put on low-dimension cases. In the high-dimensional case (Ex. 3), only the stability was tested. In the ML area, high-dimensional cases are more interesting. Moreover, the new algorithm is compared with USLA. What about ULA, particularly in high-dimensions?

Questions for authors

More numerical tests in the high-dimension sampling?

5 comments
AuthorsOpenReview ↗

Official comment to Reviewer B7a5

Thank you for your constructive review. We revised the manuscript accordingly. Specifically, we expanded the (100)-dimensional quartic experiment in Section 5.3 (pp. 8–9) to include repeated accuracy comparisons and longer runs, and added two high-dimensional real-data applications: walnut X-ray tomography with (d=6724) in Section 5.4 (p. 9), and optical phase retrieval with (d=256) per image in Section 5.5 (p. 10). We also clarified the relationship between ULA and the USLA baseline for the nonsmooth targets considered in this work. Below, all page references refer to the revised file.

  1. Further accuracy tests for the 100-dimensional numerical example

Your observation that the high-dimensional experiment focused on stability motivated a substantial extension. The submitted experiment considered numerical escape over 1000010000 updates and marginal histograms. The revised experiment evaluates approximation accuracy at 1000010000, 2500025000, and 5000050000 updates, using eight independent repetitions, each containing 1616 chains per method. Both methods retain the same initialization and 20002000-update burn-in. The main results are summarized in Section 5.3, pp. 8–9; the protocol and metric definitions are in Section F.3, pp. 63–68; Table 2, p. 67, reports 16 accuracy comparisons, and Figure 8, p. 68, shows their dependence on the update budget.

The target is Ud(x)=∑i=1d(xi44−xi2+∣xi∣),d=100.U_d(x)=\sum_{i=1}^{d}\left(\frac{x_i^4}{4}-x_i^2+|x_i|\right),\qquad d=100. Although the target factorizes, each proposal updates all 100100 coordinates jointly, and MASLA makes one MH accept–reject decision for the full vector. The factorization permits numerical marginal references and independent full-vector reference draws, which allow more informative checks than numerical stability alone.

We compare the two methods at the shared steps γ=0.05\gamma=0.05 and 0.100.10, where USLA remains numerically stable over the reported runs. Eight complementary accuracy metrics assess coordinate-11 Wasserstein-22 error, mean Wasserstein-22 error across five coordinate marginals, absolute errors in mean energy and second and fourth moments, Wasserstein-11 discrepancies for the distributions of energy and squared norm, and mean Wasserstein-22 error over eight fixed random projections. The full-vector summaries and projections supplement the marginal checks.

After 5000050000 updates, MASLA reduces mean marginal Wasserstein-22 error from 0.020020.02002 to 0.009700.00970 at γ=0.05\gamma=0.05 and from 0.040970.04097 to 0.009860.00986 at γ=0.10\gamma=0.10, reductions of approximately 52%52\% and 76%76\%. Fourth-moment error decreases from 0.043410.04341 to 0.002670.00267 and from 0.112080.11208 to 0.003180.00318, respectively. Seven of the eight exploratory paired intervals favor MASLA at each step.

The longer trajectories also reveal behavior that the original run length obscured. At γ=0.05\gamma=0.05, MASLA has a larger mean marginal error after 1000010000 updates, but a smaller error at the longer endpoints. Thus the revised evidence concerns target approximation over increasing update budgets, rather than only the prevention of numerical escape. We retain the observation that MASLA has low acceptance at γ=0.20\gamma=0.20 and do not interpret stability at that step as evidence of efficient exploration. The quartic experiment is an empirical stress test beyond the quadratic-plus-Lipschitz class covered by our geometric-ergodicity theorem.

AuthorsOpenReview ↗

Official comment to Reviewer B7a5

  1. Two new high-dimensional real data analyses

We have added two inverse problems using measured data to complement the synthetic benchmarks. Both use nonsmooth nonconvex posterior models and compare MASLA and USLA at matched steps and update budgets. Each setting uses four independent repetitions of four chains, with 5000050000 updates and 1000010000 burn-in updates per chain.

Walnut X-ray tomography: Section 5.4, p. 9; Figure 4, p. 10; Appendix G, pp. 69–72; Table 3, p. 71. We reconstruct an 82×8282\times82 image, giving d=6724d=6724 unknowns, from measured walnut X-ray projections. The posterior combines a Gaussian observation model and ridge prior with capped total variation. This penalty makes the posterior nonsmooth and nonconvex while preserving the quadratic-plus-Lipschitz structure of our theoretical class. Sixty measured angles define the target, and thirty held-out angles assess prediction. MASLA increases mean held-out pointwise log predictive density from 1.734451.73445 to 1.765421.76542 and reduces prediction root mean squared error (RMSE) from 0.0322540.032254 to 0.0316620.031662. All four repetitions favor MASLA on both reported predictive metrics, and the exploratory paired intervals exclude zero. These results assess prediction of unseen physical measurements, not merely numerical stability.

Optical phase retrieval: Section 5.5 and Table 1, p. 10; Appendix H, pp. 73–76; Figure 10, p. 76. We use measured optical transmission-matrix data for three 16×1616\times16 real input patterns, each with d=256d=256 unknowns. The Gaussian amplitude likelihood leads to a nonsmooth nonconvex posterior with a quadratic-plus-Lipschitz decomposition. Each image is evaluated at two shared step sizes. We assess the absolute radial Stein residual using the exact posterior identity 1dEπPR[XTβ(X)]=1.\frac{1}{d}\mathbb E_{\pi_{\mathrm{PR}}}\left[X^{\mathsf T}\beta(X)\right]=1. Its known target value avoids reliance on an approximate reference chain. MASLA reduces the mean absolute residual by 94.194.1–96.3%96.3\% at the larger steps and 67.167.1–78.9%78.9\% at the smaller steps. All 2424 image–step–repetition pairs favor MASLA, and all six exploratory paired intervals exclude zero. This checks agreement with an exact posterior moment in addition to stability.

These applications provide high-dimensional evidence at d=6724d=6724 and d=256d=256, alongside the expanded d=100d=100 study. The reported predictive and moment diagnostics are selected finite-run comparisons. The appendices provide the models, data preparation, simulation settings, and uncertainty calculations.

AuthorsOpenReview ↗

Official comment to Reviewer B7a5

  1. Why compare with USLA rather than a separately named ULA baseline?

Thank you for raising this point. We have clarified that the paper focuses on locally Lipschitz potentials that may be nonsmooth and nonconvex. Classical gradient-based ULA uses

\qquad Z_{n+1}\sim\mathcal N(0,I_d).$$ For the targets studied here, $\nabla U$ is undefined at the nonsmooth states, so this formula does not specify an update at every state without an additional selection convention. The smoothness assumptions of standard ULA analyses also do not directly cover these potentials. Nonsmoothness, rather than nonconvexity or high dimension alone, is the reason for introducing the conservative-field formulation. USLA is the unadjusted counterpart using the same fixed selection as MASLA: $$X_{n+1}=X_n-\gamma\beta(X_n)+\sqrt{2\gamma}\,Z_{n+1}, \qquad \beta(x)\in D_U(x).$$ At differentiable states where $\beta=\nabla U$, this is exactly the ULA update. In particular, the implemented quartic drift is $$\beta_i(x)=x_i^3-2x_i+\operatorname{sign}(x_i), \qquad \operatorname{sign}(0)=0,$$ which agrees with the classical gradient away from the coordinate hyperplanes and specifies the convention at the kinks. Thus the high-dimensional USLA comparisons already provide the unadjusted ULA-type baseline for the same target and selected drift. Adding a baseline called “ULA” with that same convention would reproduce the same update. MASLA then differs by the exact MH correction, making its effect identifiable in the comparison. This clarification appears in the algorithm description in Section 3, p. 4, the discussion of the shared proposal and nonsmooth-state selection in Section A.3, pp. 20–21, and the experiment-specific descriptions in Section F.3 and Appendices G–H. We do not claim that ULA cannot be implemented for a nonsmooth target: after fixing its drift at nonsmooth points, the resulting unadjusted scheme is the USLA baseline used here. Our aim is to study this nonsmooth setting and assess the benefit of the MH correction without changing the target or the selected drift.
Reviewer_uuacOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers the problem of sampling from a high dimensional distribution using Langevin dynamics. The paper proposes an algorithm MASLA based on Langevin dynamics with a subdifferential and a Metropolis correction step. Convergence bounds are provided for the algorithm, as well as simulations on synthetic data/settings.

Critical strengths

-The paper is quite well-written and easy to follow

-The results, specifically the main theoretical guarantee Theorem 4.3, makes sense and provides quantitative (in a sense) convergence guarantees on the proposed algorithm under a wide range of conditions, assuming that the potential takes a particular "quadratic + Lipschitz" form. The efficacy of the algorithm is backed by simulation.

Critical weaknesses

The main weakness of the paper is its significance. While Theorem 4.3 does provide a convergence guarantee, it does not necessarily yield convergence in polynomial time or any sort of interpretable rate (this is because MγM_\gamma therein can be very large and ργ\rho_\gamma therein can be arbitrarily close to 1 in terms of the dimension). Indeed, one does not expect this algorithm to succeed in non-convex situations due to computational intractability of sampling via Langevin dynamics in such settings. Analogous algorithms as the algorithm proposed have also been provided in the learning theory literature (see [1] for a survey). The simulations are in synthetic settings without real datasets.

Presentation on the above limitations of Theorem 4.3 and the related literature on Langevin-based sampling in learning theory would also significantly strengthen the positioning of the paper.

[1] Log-concave sampling. Sinho Chewi. https://chewisinho.github.io/main.pdf, 2026.

Questions for authors

Is it possible to obtain quantitative bounds on the proposed MASLA algorithm, say when the lipschitz function g is also log-concave? (Note in Thm 4.3, MγM_\gamma can be very large and ργ\rho_\gamma can be arbitrarily close to 1 in terms of the dimension, so the current result doesn't give polynomial time bounds under the stated assumptions).

How do the design principles of MASLA differ from, e.g., the MALA algorithm [2] studied in the log concave sampling literature?

[2] Log-concave sampling: Metropolis-Hastings algorithms are fast. Raaz Dwivedi, Yuansi Chen, Martin J Wainwright, Bin Yu. JMLR 2019

6 comments
AuthorsOpenReview ↗

Official comment to Reviewer uuac

Thank you for your constructive review. We revised it accordingly: We have added Theorem 4.4 in Section 4.3, pp. 6–7 of the revised manuscript, whose rigorous proof is provided in Section C.3, pp. 38–47; we have also added the requested comparison with MALA and two high-dimensional real data applications. Below, all page references refer to the revised file.

  1. A quantitative mixing bound under convexity: Theorem 4.4

In the submitted manuscript, Theorem 4.3 established geometric ergodicity for U(x)=12x⊤Hx+g(x)U(x)=\tfrac12x^\top Hx+g(x), with HH positive definite and gg a globally Lipschitz, potentially nonconvex perturbation admitting a bounded conservative field. As you noted, the existence of Mγ<∞M_\gamma<\infty and ργ<1\rho_\gamma<1 does not establish polynomial-time convergence.

The new Theorem 4.4 directly addresses your question about quantitative bounds in the log-concave setting. In our notation, π∝e−U\pi\propto e^{-U}, so log-concavity of the target corresponds to convexity of UU. Accordingly, the theorem assumes that the Lipschitz perturbation gg is convex. The resulting UU is strongly convex because HH is positive definite. The drift β(x)=Hx+v(x)\beta(x)=Hx+v(x) may use any fixed Borel selection v(x)v(x) from the convex subdifferential of gg. Neither differentiability of gg nor continuity of the selected subgradient is required.

For a ww-warm initial distribution μ0\mu_0 and a requested TV accuracy ε∈(0,1)\varepsilon\in(0,1), Theorem 4.4 specifies a sufficient step size and an explicit iteration bound. In particular, equation (4.7), p. 7, gives

+\frac{h_+^2d^2w^2}{h_-^2\varepsilon^2}\right] \log\frac{2w}{\varepsilon}\right),$$ where $h_-$ and $h_+$ are the extreme eigenvalues of $H$, $L$ is the global Lipschitz bound for $g$, and the suppressed constants are universal. After this many MASLA updates, $\mathrm{TV}(\mu_0R_\gamma^n,\pi)\leq\varepsilon$. Thus, for fixed model bounds, we now obtain polynomial dependence on dimension, warmness, and inverse accuracy, rather than only an existence statement about geometric constants. The conclusion applies to the MASLA kernel $R_\gamma$, with its usual MH accept–reject step. The proof uses $A_\gamma=\tfrac12 I+\tfrac12 R_\gamma^2$ as an auxiliary kernel, but does not add a holding step to the algorithm. Lemma C.1 in Section C.2, pp. 35–37, proves the transfer from the auxiliary estimate to actual MASLA updates. This distinction is also explained in Section C.1, p. 35. 2. Connection with Dwivedi et al. (2019) and differences in the bound We have followed your suggestion to connect the analysis to Dwivedi et al. (2019). Our proof extends their local-overlap and conductance strategy to the nonsmooth convex perturbation setting. Specifically, we first identify a high-probability region with bounded selected drift, control the exact MH rejection probability there, and establish overlap between nearby transition laws. We then apply the log-concave isoperimetric and stationary-flow argument underlying their Lemma 6 and the warm-start conductance inequality in their equation (22). These uses are identified explicitly in Step 4 of the proof in Section C.3, pp. 45–47. The extension requires different local estimates. The smooth MALA analysis assumes a Lipschitz gradient, whereas our selected subgradient may jump across a nonsmooth set. We therefore cannot directly apply its smoothness-based control of the drift and acceptance ratio. Instead, we use bounded subgradients on a high-probability ball and a direct bound on the exact log MH ratio. In our proof, the ball radius satisfies $R^2=2dw^2/(h_-\varepsilon^2)$, and the sufficient step is in equation (4.5) in Theorem 4.4, p. 6. These estimates explain the polynomial inverse-accuracy dependence in our bound. Consequently, our theorem does not recover the sharper smooth-setting rate of Dwivedi et al. (2019), whose accuracy dependence is logarithmic up to its concentration factors. We do not claim that such a sharper rate is impossible for nonsmooth targets; rather, it is not established by the broader assumptions and estimates used in our theorem. The contribution is a quantitative guarantee allowing a nonsmooth potential and a discontinuous selected subgradient, with the assumptions and resulting rate stated explicitly.
AuthorsOpenReview ↗

Official comment to Reviewer uuac

  1. Comparison of MASLA and MALA, and related literature

In response to your question about design principles, we added Section A.3, “Design principles of MASLA and their relation to MALA,” pp. 20–21, and revised the positioning and contributions in the introduction, pp. 1–2. This discussion makes clear that MASLA retains MALA’s Gaussian drift proposal and standard exact MH correction. Its distinction is the fixed measurable conservative-field selection used to define the proposal at nonsmooth states, together with the convergence analysis under the stated assumptions. When UU is smooth and the selection is its gradient, MASLA coincides with MALA. We do not present exact MH invariance as a new acceptance principle. The selection specifies the drift at every state, including deterministic initial states where a classical gradient is unavailable, without smoothing the potential or solving a proximal subproblem.

Section A.3 also distinguishes the log-concave assumptions of the cited mixing analysis from the applicability of MALA itself: MALA can be used for smooth nonconvex targets, and MASLA accommodates nonsmooth convex and nonconvex targets under its stated conditions. The discussion points to the conservative-field results in Appendix B for the broad classes of functions admitting such selections, while distinguishing this availability from the stronger assumptions needed for quantitative convergence. This positions our results as an extension of the framework to specified nonsmooth settings, rather than a replacement for the established MALA literature.

  1. Two new high-dimensional real data applications

We have added two real data analyses, summarized in Sections 5.4–5.5 on pp. 9–10, with full model descriptions, protocols, and results in Appendices G–H.

Walnut X-ray tomography: Section 5.4, p. 9; Figure 4, p. 10; Appendix G, pp. 69–72; Table 3, p. 71. We use measured X-ray projections to infer an 82×8282\times82 image with 6724 unknowns. The posterior combines a Gaussian likelihood and ridge prior with a capped total-variation penalty, giving a nonsmooth nonconvex model in the quadratic-plus-Lipschitz class of our theory. With matched steps and update budgets, four repetitions of four chains compare MASLA and USLA using held-out measurements. Mean pointwise log predictive density increases from 1.73445 to 1.76542, while prediction root mean squared error decreases from 0.032254 to 0.031662. All four repetitions favor MASLA on both reported predictive metrics, and the exploratory paired intervals exclude zero.

Optical phase retrieval: Section 5.5 and Table 1, p. 10; Appendix H, pp. 73–76; Figure 10, p. 76. We use measured optical transmission-matrix data for three 16×1616\times16 real input patterns, each with 256 unknowns. The amplitude likelihood yields a nonsmooth nonconvex posterior with the required quadratic-plus-Lipschitz decomposition. For each image, we compare two shared steps using four repetitions of four chains. Accuracy is assessed through an exact posterior moment identity, EπPR[XTβ(X)]/d=1\mathbb E_{\pi_{\mathrm{PR}}}[X^{\mathsf T}\beta(X)]/d=1, rather than an approximate reference chain. MASLA reduces the mean absolute radial Stein residual by 94.1–96.3% at the larger steps and 67.1–78.9% at the smaller steps. All 24 image–step–repetition pairs favor MASLA, and all six exploratory paired intervals exclude zero.

Both applications use 50000 updates and 10000 burn-in updates per chain. These comparisons isolate the effect of MH correction using the same target and drift selection. They provide evidence of improved predictive and posterior-moment agreement in the reported settings. The appendices describe the selected metrics and exploratory uncertainty calculations.

Thanks to the authors for their response. I appreciate the detail in the response, however my main concerns with the work remain. I still believe the significance of the work is a major weakness: the mixing bound only applies to distributions with a particular form and an extension to distributions of this form is not very surprising, the design principles are known, and the data analyses still feel in a fairly toy setting. In fact, the new quantitative bound Theorem 4.4 is not truly polynomial: it depends polynomially on the warmness ww, which for a "cold start" is exponentially large in the dimension (see eq 4.7). This is a classical fact in the mixing time of markov chains (see e.g. "Geometric Random Walks: A Survey" by Vempala) and indeed much work in mixing time of markov chains is devoted to obtaining a start with ww polynomial in the dimension. Therefore I keep my previous assessment.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Thank You for Your Time, Careful Review, and Constructive Feedback

We sincerely thank all three reviewers and the Area Chair for their time, careful evaluation, and constructive feedback throughout the rebuttal period. Their comments have helped us substantially strengthen both the theoretical development and the empirical evaluation of the paper.

The revised manuscript now contains 79 pages in total, with the main text kept within 10 pages, and incorporates substantial additions to the theory, experiments, applications, and exposition to address the concerns raised by all three reviewers. In particular, compared with the original submission, we have added two new theoretical results with full proofs: a quantitative warm-start mixing bound under convexity (Theorem 4.4) and computable geometric convergence constants together with an iteration bound (Theorem 4.5). We have also substantially expanded the d=100d=100 numerical experiment and added two real-data inverse problems: walnut X-ray tomography with d=6724d=6724 and optical phase retrieval with d=256d=256 per image.

The main concerns raised by each reviewer have been addressed as follows:

  • Reviewer uuac: We added Theorem 4.4 to provide an explicit quantitative warm-start mixing bound under convexity, clarified its dependence on the warmness parameter and its distinction from arbitrary cold-start polynomial mixing, expanded the comparison with classical MALA and the related log-concave sampling literature, and added two measured-data applications.
  • Reviewer B7a5: We substantially expanded the high-dimensional d=100d=100 experiment from a stability study to repeated accuracy comparisons with runs up to 50,000 iterations, added the d=6724d=6724 tomography and d=256d=256 phase-retrieval applications, and clarified why USLA is the appropriate unadjusted ULA-type baseline for the nonsmooth targets considered here.
  • Reviewer z6CX: We added Theorem 4.5 to make the geometric convergence constants explicitly computable, introduced two measured-data nonsmooth nonconvex applications to strengthen the practical motivation, clarified why the cited proximal and gradient-based competing frameworks are not directly applicable to these examples, and addressed all five minor comments concerning independence assumptions, high-dimensional acceptance, notation, conservative fields, and the presentation of the standard MH invariance result.

We greatly appreciate the reviewers’ thoughtful comments and the Area Chair’s consideration. We believe the revised manuscript is substantially stronger in its theory, empirical evidence, practical motivation, and presentation, and we hope that the revisions and detailed responses provide a clear basis for the final assessment.

Thank you again for your time and consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.