arxiv: 2605.12461 · v1 · submitted 2026-05-12 · 🧮 math.ST · cs.DS· cs.LG· stat.ML· stat.TH

Recognition: no theorem link

A proximal gradient algorithm for composite log-concave sampling

Linghai Liu, Sinho Chewi

Pith reviewed 2026-05-13 02:44 UTC · model grok-4.3

classification 🧮 math.ST cs.DScs.LGstat.MLstat.TH

keywords composite log-concave samplingproximal gradient algorithmrestricted Gaussian oracletotal variation distancestrong convexityPoincaré inequalityMonte Carlo samplinglog-Sobolev inequality

0 comments

The pith

The proximal gradient sampler achieves the same iteration complexity as the smooth case for composite log-concave distributions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a proximal gradient algorithm for sampling from composite log-concave distributions over R^d, which are densities proportional to exp(-f-g). The algorithm uses gradient evaluations of the smooth function f and a restricted Gaussian oracle for g. Under the assumption that f+g is alpha-strongly convex and f is beta-smooth, the method achieves epsilon error in total variation in tilde O(kappa sqrt(d) log^4(1/epsilon)) iterations. This rate matches the state of the art for the case where g is zero. The results are extended to non-log-concave distributions satisfying a Poincare or log-Sobolev inequality and to non-smooth Lipschitz f.

Core claim

The proposed proximal gradient algorithm for sampling from composite log-concave distributions achieves an iteration complexity of tilde O(kappa sqrt(d) log^4(1/epsilon)) to reach epsilon total variation error, matching prior results for smooth log-concave sampling, and extends to weaker convexity conditions and non-smooth f.

What carries the argument

The restricted Gaussian oracle (RGO) for g, which samples from exp(-g(x) - 1/(2h)||y-x||^2) and serves as the sampling analogue of the proximal operator.

If this is right

The algorithm provides an efficient way to sample from high-dimensional composite log-concave distributions.
It extends sampling guarantees to distributions satisfying Poincaré or log-Sobolev inequalities.
The method handles cases where f is non-smooth but Lipschitz.
The complexity bound is the same as for smooth log-concave sampling.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the RGO can be efficiently implemented for particular g, such as convex constraints, the algorithm becomes practical for many applications.
This proximal approach could inspire similar algorithms for other types of composite sampling problems.
The matching complexity suggests that the non-smooth part does not add extra cost when the oracle is available.

Load-bearing premise

The algorithm requires access to an efficient restricted Gaussian oracle for the function g.

What would settle it

Running the algorithm on a specific composite distribution and measuring that the total variation distance does not fall below epsilon within the predicted number of iterations would falsify the complexity claim.

read the original abstract

We propose an algorithm to sample from composite log-concave distributions over $\mathbb{R}^d$, i.e., densities of the form $\pi\propto e^{-f-g}$, assuming access to gradient evaluations of $f$ and a restricted Gaussian oracle (RGO) for $g$. The latter requirement means that we can easily sample from the density $\text{RGO}_{g,h,y}(x) \propto \exp(-g(x) -\frac{1}{2h}||y-x||^2)$, which is the sampling analogue of the proximal operator for $g$. If $f + g$ is $\alpha$-strongly convex and $f$ is $\beta$-smooth, our sampler achieves $\varepsilon$ error in total variation distance in $\widetilde{\mathcal O}(\kappa \sqrt d \log^4(1/\varepsilon))$ iterations where $\kappa := \beta/\alpha$, which matches prior state-of-the-art results for the case $g=0$. We further extend our results to cases where (1) $\pi$ is non-log-concave but satisfies a Poincar\'e or log-Sobolev inequality, and (2) $f$ is non-smooth but Lipschitz.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives a proximal-gradient sampler for composite log-concave densities that matches the smooth-case iteration bound under an explicit RGO assumption for the non-smooth part.

read the letter

The main thing to know is that Liu and Chewi adapt the proximal gradient structure to sampling: they run a gradient step on the smooth f and then call a restricted Gaussian oracle on g to handle the composite density π ∝ exp(-f-g). Under α-strong convexity of f+g and β-smoothness of f they recover the same Õ(κ √d log⁴(1/ε)) iteration bound for ε total-variation error that was already known for g=0, with κ=β/α. They also outline extensions to Poincaré or log-Sobolev settings and to Lipschitz but non-smooth f. That algorithmic framing is the concrete new piece relative to earlier log-concave samplers. The argument is presented cleanly in the abstract and appears internally consistent, with the RGO treated as a modeling assumption rather than something derived or fitted. The complexity claim does not improve the √d dependence but does show the composite case can be handled without worsening the rate. The main soft spot is that the RGO itself is left unpriced: if sampling from exp(-g(x) - (1/(2h))||y-x||²) is not cheap for the g of interest, the whole procedure is not yet practical, and the abstract gives no general implementation or cost bound for common choices of g. Proof details are not visible here, so the error analysis and oracle error propagation would need checking, but nothing in the stated claims looks contradictory or circular. This is for readers already working on high-dimensional sampling and its links to optimization; someone who follows the Langevin and proximal literature will see the extension immediately. It is worth sending to peer review because the algorithmic idea is precise and the stated guarantees are sharp enough to merit referee scrutiny on the proofs and on when the RGO can be realized efficiently.

Referee Report

0 major / 2 minor

Summary. The paper proposes a proximal gradient algorithm for sampling from composite log-concave distributions π ∝ exp(-f - g) over R^d. It assumes access to gradients of f and a restricted Gaussian oracle (RGO) for g that samples from exp(-g(x) - (1/(2h))||y - x||^2). Under α-strong convexity of f + g and β-smoothness of f, the sampler achieves ε total variation error in Õ(κ √d log^4(1/ε)) iterations with κ = β/α, matching prior results for g = 0. Extensions are given to Poincaré/log-Sobolev settings and to non-smooth Lipschitz f.

Significance. If the guarantees hold, the work extends state-of-the-art sampling complexities to composite distributions by treating the proximal step for g via an explicit RGO assumption. The matching iteration bound to the smooth case and the clean separation of assumptions are strengths; the extensions to weaker isoperimetric conditions broaden the scope without introducing internal contradictions.

minor comments (2)

[Abstract] The abstract states the RGO as an assumption but does not quantify its per-call cost; a brief remark in §1 or §2 on when the RGO is efficient (e.g., for g convex or indicator) would clarify practicality.
[Introduction] The log^4(1/ε) factor appears in the main complexity statement; the paper should indicate in the introduction whether this exponent is an artifact of the analysis or believed to be improvable.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the work, the clear summary of our contributions, and the recommendation for minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper states its central complexity bound as a derived guarantee under explicit modeling assumptions (access to gradients of f and an RGO for g) together with standard α-strong convexity of f+g and β-smoothness of f. The bound is presented as matching the g=0 case from prior literature rather than being obtained by fitting parameters to data or by redefining the target quantity in terms of itself. No load-bearing step reduces by construction to an input or to a self-citation chain; the RGO is listed as an external oracle assumption, not a derived property. The extensions to Poincaré/log-Sobolev inequalities and non-smooth f are stated separately without internal redefinition or circular justification.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard domain assumptions of strong convexity of f+g and smoothness of f, plus the existence of an efficient restricted Gaussian oracle for g; no free parameters are fitted and no new entities are postulated.

axioms (2)

domain assumption f + g is α-strongly convex
Invoked to obtain the linear convergence rate in the complexity bound.
domain assumption f is β-smooth
Used to control the gradient step size and obtain the condition number κ = β/α.

pith-pipeline@v0.9.0 · 5520 in / 1365 out tokens · 63413 ms · 2026-05-13T02:44:48.928260+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

54 extracted references · 54 canonical work pages · 1 internal anchor

[1]

Structured logconcave sampling with a restricted

Lee, Yin Tat and Shen, Ruoqi and Tian, Kevin , booktitle =. Structured logconcave sampling with a restricted. 2021 , editor =

work page 2021
[2]

Optimal dimension dependence of the

Chewi, Sinho and Lu, Chen and Ahn, Kwangjun and Cheng, Xiang and Le Gouic, Thibaut and Rigollet, Philippe , booktitle=. Optimal dimension dependence of the. 2021 , organization=

work page 2021
[3]

Concentration of measure and logarithmic

Ledoux, Michel , booktitle=. Concentration of measure and logarithmic. 2006 , publisher=

work page 2006
[4]

2026+ , note=

Sinho Chewi , title=. 2026+ , note=

work page 2026
[5]

American Mathematical Soc., Providence , volume=

Markov chains and mixing times , author=. American Mathematical Soc., Providence , volume=

work page
[6]

arXiv preprint arXiv:2006.05976 , year=

Composite logconcave sampling with a restricted Gaussian oracle , author=. arXiv preprint arXiv:2006.05976 , year=

work page arXiv 2006
[7]

High-accuracy sampling for diffusion models and log-concave distributions

High-accuracy sampling for diffusion models and log-concave distributions , author=. arXiv preprint arXiv:2602.01338 , year=

work page internal anchor Pith review Pith/arXiv arXiv
[8]

Advances in Neural Information Processing Systems , volume=

Lower bounds on Metropolized sampling methods for well-conditioned distributions , author=. Advances in Neural Information Processing Systems , volume=

work page
[9]

Rapid convergence of the unadjusted

Vempala, Santosh and Wibisono, Andre , journal=. Rapid convergence of the unadjusted

work page
[10]

The Thirty Sixth Annual Conference on Learning Theory , pages=

Improved dimension dependence of a proximal algorithm for sampling , author=. The Thirty Sixth Annual Conference on Learning Theory , pages=. 2023 , organization=

work page 2023
[11]

Journal of the Royal Statistical Society Series B: Statistical Methodology , volume=

Theoretical guarantees for approximate sampling from smooth and log-concave densities , author=. Journal of the Royal Statistical Society Series B: Statistical Methodology , volume=. 2017 , publisher=

work page 2017
[12]

Nonasymptotic convergence analysis for the unadjusted

Alain Durmus and. Nonasymptotic convergence analysis for the unadjusted. The Annals of Applied Probability , number =

work page
[13]

Conference on learning theory , pages=

Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem , author=. Conference on learning theory , pages=. 2018 , organization=

work page 2018
[14]

Journal of Machine Learning Research , volume=

Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients , author=. Journal of Machine Learning Research , volume=

work page
[15]

Conference on Learning Theory , pages=

Improved analysis for a proximal algorithm for sampling , author=. Conference on Learning Theory , pages=. 2022 , organization=

work page 2022
[16]

Advances in Neural Information Processing Systems , volume=

In-and-out: algorithmic diffusion for sampling convex bodies , author=. Advances in Neural Information Processing Systems , volume=

work page
[17]

arXiv preprint arXiv:2505.01937 , year=

Faster logconcave sampling from a cold start in high dimension , author=. arXiv preprint arXiv:2505.01937 , year=

work page arXiv
[18]

, booktitle=

Kook, Yunbum and Zhang, Matthew S. , booktitle=. R. 2025 , organization=

work page 2025
[19]

Transactions on Machine Learning Research , year=

A proximal algorithm for sampling , author=. Transactions on Machine Learning Research , year=

work page
[20]

Minimax mixing time of the

Wu, Keru and Schmidler, Scott and Chen, Yuansi , journal=. Minimax mixing time of the

work page
[21]

Journal of the ACM , volume=

Faster high-accuracy log-concave sampling via algorithmic warm starts , author=. Journal of the ACM , volume=. 2024 , publisher=

work page 2024
[22]

, journal=

Chewi, Sinho and Erdogdu, Murat A and Li, Mufan and Shen, Ruoqi and Zhang, Matthew S. , journal=. Analysis of. 2025 , publisher=

work page 2025
[23]

and Yu, Bin , journal=

Dwivedi, Raaz and Chen, Yuansi and Wainwright, Martin J. and Yu, Bin , journal=. Log-concave sampling:

work page
[24]

Journal of Machine Learning Research , volume=

An efficient sampling algorithm for non-smooth composite potentials , author=. Journal of Machine Learning Research , volume=

work page
[25]

Advances in Neural Information Processing Systems , volume=

The randomized midpoint method for log-concave sampling , author=. Advances in Neural Information Processing Systems , volume=

work page
[26]

Conference on learning theory , pages=

Logsmooth gradient concentration and tighter runtimes for Metropolized Hamiltonian Monte Carlo , author=. Conference on learning theory , pages=. 2020 , organization=

work page 2020
[27]

arXiv preprint arXiv:2210.08448 , year=

Resolving the mixing time of the Langevin algorithm to its stationary distribution for log-concave sampling , author=. arXiv preprint arXiv:2210.08448 , year=

work page arXiv
[28]

arXiv preprint arXiv:2510.02983 , year=

Oracle-based Uniform Sampling from Convex Bodies , author=. arXiv preprint arXiv:2510.02983 , year=

work page arXiv
[29]

arXiv preprint arXiv:2602.14478 , year=

Constrained and composite sampling via proximal sampler , author=. arXiv preprint arXiv:2602.14478 , year=

work page arXiv
[30]

Transactions on Machine Learning Research , year=

Client-only Distributed Markov Chain Monte Carlo Sampling over a Network , author=. Transactions on Machine Learning Research , year=

work page
[31]

2018 , publisher=

High-dimensional probability: an introduction with applications in data science , author=. 2018 , publisher=

work page 2018
[32]

Random Structures & Algorithms , volume=

Random walks in a convex body and an improved volume algorithm , author=. Random Structures & Algorithms , volume=. 1993 , publisher=

work page 1993
[33]

Concentration inequalities , NOTE =

Boucheron, St\'. Concentration inequalities , NOTE =. 2013 , PAGES =

work page 2013
[34]

Foundations and Trends in Optimization , volume=

Proximal algorithms , author=. Foundations and Trends in Optimization , volume=. 2014 , publisher=

work page 2014
[35]

SIAM Journal on Imaging Sciences , volume=

A fast iterative shrinkage-thresholding algorithm for linear inverse problems , author=. SIAM Journal on Imaging Sciences , volume=. 2009 , publisher=

work page 2009
[36]

High-dimensional

Alain Durmus and. High-dimensional. Bernoulli , number =

work page
[37]

Langevin

Bernton, Espen , booktitle=. Langevin. 2018 , organization=

work page 2018
[38]

Proximal

Pereyra, Marcelo , journal=. Proximal. 2016 , publisher=

work page 2016
[39]

Sampling from a log-concave distribution with compact support with proximal

Brosse, Nicolas and Durmus, Alain and Moulines,. Sampling from a log-concave distribution with compact support with proximal. Conference on Learning Theory , pages=. 2017 , organization=

work page 2017
[40]

arXiv preprint arXiv:1911.01469 , year=

Proximal langevin algorithm: Rapid convergence under isoperimetry , author=. arXiv preprint arXiv:1911.01469 , year=

work page arXiv 1911
[41]

Efficient

Durmus, Alain and Moulines, Eric and Pereyra, Marcelo , journal=. Efficient. 2018 , publisher=

work page 2018
[42]

Sampling from a log-concave distribution with projected

Bubeck, S. Sampling from a log-concave distribution with projected. Discrete & Computational Geometry , volume=. 2018 , publisher=

work page 2018
[43]

Combinatorial and computational geometry , volume=

Geometric random walks: a survey , author=. Combinatorial and computational geometry , volume=. 2005 , publisher=

work page 2005
[44]

Inventiones Mathematicae , volume=

On the role of convexity in isoperimetry, spectral gap and concentration , author=. Inventiones Mathematicae , volume=. 2009 , publisher=

work page 2009
[45]

2026 , journal=

High-accuracy log-concave sampling with stochastic queries , author=. 2026 , journal=

work page 2026
[46]

2025 , journal=

Zeroth-order log-concave sampling , author=. 2025 , journal=

work page 2025
[47]

, title =

Kook, Yunbum and Vempala, Santosh S. , title =. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages =. 2025 , publisher =

work page 2025
[48]

On a class of

Yuan, Bo and Fan, Jiaojiao and Liang, Jiaming and Wibisono, Andre and Chen, Yongxin , booktitle =. On a class of. 2023 , editor =

work page 2023
[49]

Electron

Brigati, Giovanni and Pedrotti, Francesco , TITLE =. Electron. Commun. Probab. , FJOURNAL =. 2025 , PAGES =

work page 2025
[50]

Stochastic proximal

Salim, Adil and Kovalev, Dmitry and Richtarik, Peter , booktitle =. Stochastic proximal

work page
[51]

Primal dual interpretation of the proximal stochastic gradient

Salim, Adil and Richtarik, Peter , booktitle =. Primal dual interpretation of the proximal stochastic gradient

work page
[52]

Habring, Andreas and Holler, Martin and Pock, Thomas , TITLE =. SIAM J. Math. Data Sci. , FJOURNAL =. 2024 , NUMBER =

work page 2024
[53]

Analysis of

Durmus, Alain and Majewski, Szymon and Miasojedow, B. Analysis of. J. Mach. Learn. Res. , FJOURNAL =. 2019 , PAGES =

work page 2019
[54]

S\'eminaire de probabilit\'es , pages =

Bakry, Dominique and \'Emery, Michel , title =. S\'eminaire de probabilit\'es , pages =. 1985 , publisher =

work page 1985