The Adaptive Complexity of Minimizing Relative Fisher Information
Authors: Huanjian Zhou
Masashi Sugiyama
Venue: NeurIPS 2025 poster ()
Keywords: parallel sampling
non-log-concave
relative fisher information
Primary area: probabilistic_methods
TL;DR: New parallel algorithms for minimizing the relative Fisher information for non-log-concave and log-smooth distribution with first lower bound matching for specific accuracy.

Abstract: Non-log-concave sampling from an unnormalized density is fundamental in machine learning and statistics. As datasets grow larger, computational
efficiency becomes increasingly important, particularly in reducing adaptive complexity, namely the number of sequential rounds required for sampling algorithms. In this work,  we initiate the study of the adaptive complexity of non-log-concave sampling within the framework of relative Fisher information introduced by Balasubramanian et al. in 2022.  To obtain a relative fisher information of at most $\varepsilon^2$ from the target distribution, we propose a novel algorithm that reduces the adaptive complexity from $\mathcal{O}(d^2/\varepsilon^4)$ to $\mathcal{O}(d/\varepsilon^2)$ by leveraging parallelism. Furthermore, we show our algorithm is optimal for a specific regime of large $\varepsilon$. Our algorithm builds on a diagonally parallelized Picard iteration, while the lower bound is based on a reduction from the problem of finding stationary points.

The Adaptive Complexity of Minimizing Relative Fisher Information
Huanjian Zhou
Masashi Sugiyama
Graduate School of Frontier Sciences
Center for Advanced Intelligence Project
The University of Tokyo
RIKEN
Center for Advanced Intelligence Project
Graduate School of Frontier Sciences
RIKEN zhou thoukm...uutokyy.cc...ppp
The University of Tokyo sugi@ Bugi@k.u-toke sugi@k.u-tokyo.ac.ij
Abstract
Non-log-conees concave sampling from an unnormalized density is fundamental in ma- chine learning and statistics. As datasets grow larger. computational efficiency becomes increasingly important, particularly in reducing adaptive complexity, namely the number of sequential rounds required for sampling algorithms. In this work, we initiate the study of the adaptive complexity of non-log-concave sampling within the framework of relative Fisher information introduced by Balasubrama- nian et al. in 2022. To obtain relative Fisher information of at most e² from the target distribution, we propose a novel algorithm that reduces the adaptive complexity from (dd /E*) to ((d/=²) by leveraging parallelism. Furthermore, we show our algorithm is optimal for a specific regime large e. Our algorithm builds on diagonally parallelized Picard iteration, while the lower bound is based on a reduction from the problem of finding stationary points.
Introduction
We study the problem of adaptive sampling from target distribution over Rd given query access to its unnormalized density, fundamental task in areas such as Bayesian inference, randomized algorithms, and machine learning [MR+]] NWS19 RCC99]. Recently, significant progress has been made developing sequential algorithms for this problem, drawing inspiration from the extensive optimization toolkit, particularly when the target distribution is log-concave [JKO98] DMM19 2CC+21). Typically, when access to the function value available, many high-accuracy samplers have been designed based on Metropolis- filters or proximal sampler [DCWY19]
CDWY20 LST20 ALPW24 LST2T AC24 FYC23].
However, in many practical applications, such as mased models and Markov Decision Pro- cesses, evaluating the log- ligeliili is often computationally intractable [LCH 06 SBI3. In such
scenarios, an alternative approach to designing high-accuracy samplers involves leveraging paral- lelism [SL.19] YD24 ACV24 ZS24). ZS24. These algorithms effectively leverage contemporary parallel computing resources, such multi-core central processing units (CPUs) and many-core graphics processing units (GPUs), especially since log-likelihood gradient evaluations often admit paralleliza- tion [HLB+ 21 HLFS21] In particular, the authors 99 YD24 ACV24 ZS24 proposed samplers that find an e-accurate solution within (pooyy log log(d/e (d) iterations, significantly improving upon the sub-polynomial complexity of O(d" /E") for log-concave distributions for some constant a, E (0, 1).
39th Conference on Neural Information Processing Systems (NeurIPS 2025).
'Samplers with complexity poly(d, log(Kr/))), assuming constant smoothness and condition number and Ka initial KL divergence.

---

In contrast, there are comparatively few works which study the adaptive complexity when the target distribution is not strongly log-concave or are multimodal, such as mixtures of Gaussians.
To study the complexity of sampling from non-log-concave distributions, a general framework inspired by stationary point analysis in non-convex optimization (see, e.g., [8) has been developed.
Specifically, Balasubramanian et al. [BCE*2] 22] proposed defining an s-stationary point for sampling
as any measure μ satisfying /FI(p][T) I e, where FI( y | log(u/>))1* denotes
the relative Fisher information between μ and the target distribution и. They demonstrated that averaged Langevin Monte Carlo finds an E-stationary point within (ddKo/=) iterations, where Kg == x)) represents the initial Kullback-Leible divergence from the initial measure No to т. Furthermore, Chewi et al. [CGLL223 established an 22(1/²²) query complexity lower bound for this setting. Existing studies offer only few bounds the query complexity of non-log-concant sampling, and our understanding of the adaptive complexity remains critically limited. This gap
motivates our investigation into the question:
How many sequential rounds are needed to minimize flr non-log-concave sampling?
1.1 Our Contribution
In this paper, we establish the first upper and lower bounds for the parallel runtime complexity of sampling. We now informally describe our main results. We assume access to an initial point x. (4g, where the KL. divergence from the target distribution is Kn KL(Poll l/z) and the target distribution æ is L-log-smooth.
New parallelized algorithm with improved complexity. By parallelizing the averaged Langevin Monte Carlo [BCE-2), which has optimal query complexity for a specific regime of large Fl (8 O + log( ( (The- orem 3.1 When all parameters except the dimension d are treated as constants, our algorithm improves the adaptive complexity from (d) to Olog d), matching the parallel speedup known for strongly log-concave sampling [ZS24]. Moreover when K₂ = O(d), which is common assumption and the analog of the optimal gap (0) min f(x) 2 d) in non-convex optimization [CEI.+24]
VLd) [GLL23), we improve the adaptive complexity from O (
Appendix A], our algorithm achieves an adaptive complexity of Ö (( (d),, improving over the prior
complexity of O d.dd)
Lower bound. We further prove our parallelized algorithm is optimal for a specific regime of large FI (s Ld) by showing when ((K)) 2 d > ((Kk//3 ), the adaptive complexity is 2 Ke) (The- orem 4.1 For the accuracy level & = T.d, the adaptive complexity of the parallelized averaged Langevin Monte Carlo matches that of its sequential counterpart. Therefore, the sequential algo- rithm proposed by Balasubramanian et al. (BCE+22) also adaptively optimal in this regime. We summarize the comparison between existing bounds and our results in Table I
Moreover, although this lower bound only applies specific accuracy regime, it rules out the possibility of general high-accuracy sampler via parallelism. This highlights a stark separation between log- concave and con-log-concave sampling, whereas Zhou et ZS24] developed general high-accuracy sampler via parallelism for strongly log-concave distributions, along with a tight lower bound on the accuracy (ZWS24)
A separation between optimization and sampling. Our work also highlights a fundamental difference between sampling and optimization: Unlike in sampling, no analogous separation exists between convex and non-convex optimization, as parallelism fails to accelerate gradient descent for either class in high -ige-ninnnii settings [ESI8b] DGI9 ZHTS25). In contrast, for sampling, parallelism can accelerate Langevin Monte Carlo or its averaged version for both the strongly log-coneave case (S244 and non-log-concave case (Theorem 3.1)
AAdaptiee complexity refers to the minimal number of sequential rounds required for an algorithm to achieve a desired accuracy, assuming polynomially many queries can be executed in parallel at each round BS18a ZWS24

---

Table 1: Comparisons of our lower bounds and upper bounds. Here, P and Ö omit logarithmic factors. Ko denotes the initial KL divergence, defined as Kg = (L()ol)T) where the initial point is drawn from the distribution Ag.
Works
Adaptive Complexity
Queries per Iteration
Sequential averaged Langevin Monte Carlo
0 222Ka
BCE 22
Theorem 2]
Parallelized averaged Langevin Monte Carlo
0 0 + log( (d)
5 L2k e
Theorem 3.1
Lower bound for LLd
22 KR)
CGLL23 Theorem
Lower bound for Ld Theorem 4.1
2 (
poly(d)
1.2 Related works
Related works for minimizing Fl. The relative Fisher information (FI) between two distributions quantifies the score matching error, which is the expected squared distance between their score functions (the gradients of their log-densities). In contrast, KL. divergence (KL) compares the ratio of their density functions. When the reference distribution satisfies a log- Segoollolv inequality or Poincaré inequality, small Fl implies small KL or small total variation (TV). However, it is possible for KL or TV to remain small even when Fl becomes arbitrarily large (see [Wi625] Appendix DJ). Moreover, when the reference distribution is not log-concave, Fl can be made arbitrarily small while TV remains bounded away from zero BCE+22 Proposition 1].
A line of works in the literature investigates the mixing of Fl for the sequential methods. For non-log-concave case, Balasubramanian al. [BCE+22] analyzed the averaged Langevin Monte Carlo and Chewi et al. [CGLPK proved two query complexity lower bound. For log-concave case, Chewi et al. [CGLL23] Appendix A] established high-accuracy mixing time for proximal sampler with post-processing via the heat flow. For strongly log- log-concave case, Wibisono [Wib25] proved exponential convergence the proximal sampler using the strong data processing inequality.
Related works for minimizing TV or KL for non-log-concave case. Another line of works study the complexity of minimizing TV KL for non-log-concave sampling. For mixture Gaussian distributions with components sharing the same shape, Ge et al. [LRGI8] showed polynomially many queries are sufficient minimize TV for simulated tempering Langevin Monte Carlo. For general non-log-concave distributions, Guo et al. [GTC24 analyzed annealed Langevin Monte Carlo and established polynomial query complexity terms of the action associated with a curve of probability measures interpolating the target distribution and readily sampleable distribution. Notably, when the components of a mixture of Gaussians share the same shape and mode norm, the corresponding action grows only polynomially with respect to the dimension. Recently, He et al. (HZ25) proved
that the optimal query complexity scales as (ma (((d) where ma is the second moment of the target distribution.
2 Preliminaries
2.1 Problem setting
Given the potential function V D the goal of the sampling task is to draw a sample from the density œV Zz² vsp(-V), where Zv cxp(-V)dx is the normalizing constant.
Distribution class and assumption. If V is twice-differentiable and V²V 3 LI with L > 0 (where 3 denotes the Loewner order and I is the identity matrix), we say the distribution my is L-log-smooth.
Oracle.
Given the potential function V. and query x E DD the (-th order oracle answers the function value (xx) and the 1-st order oracle answers both V (x) and its gradient value VV(x). We
3

---

denote the oracle as Or. We also extend the oracle to parallel case, with input as fæ1...... 2b E R and return multiple answers (V (æ1).
(V))) } E TR2ak with h: = poly(d).
The adaptive algorithm class
The class of adaptive algorithms is formally defined fol- lows [DG19]. For any dimension d, an adaptive algorithm A takes V Rd - IR and a (possibly random) initial point x. and iteration number as input and returns output x which is denoted A performs a batch of queries
as A(V, x,, = x r+ At iteration E [r] := {1...., r.. ......,r.. (a= ...., 20"²,, with x²d E DD j [ki,, k = poly(d),
such that for any m, n E [ky], x.m and x are conditionally independent given all existing queries Jett-- and æ". Give queries set Qi the oracle returns a batch of answers: Or(Q:) (Oræf ,, (r()*))))
An adaptive algorithm is deterministic if in every iteration E fo,...,,).. A operates with the form Qi+1 = =A'(Q), Or(Q)), .... Q',
Or(Q)), where A' is mapping into Rdkc+1 with Q*+1 = x ++ as output and Q" x. as an initial point. We denote the class of adaptive deterministic algorithms by Adet.
adaptive randomized algorithm has the form
Qi+1 AEE Q"
Q',
given access to a random uniform variable on [o, 1] (i.e., infinitely many random bits), where is mapping into Bdds+1, We denote the class of adaptive randomized algorithms by Arand-
Measure of the output Consider the joint distribution of all involved points fx x E Q' O,..., 1+ and the random bits E Let the marginal distribution of the output x be p. We say the output to be =a-accurate in relative Fisher information (FI) if Fl Tv) Ex || log(p/TT]] 6²
Initialization.
We assume access to an initialization oracle that returns sample from distribution No satisfying KL [T] S Ko since it suffice to find stationary point which lies in a ball of radius O(vd), centered at the minimizer of f [CEL 24 And such stationary point can be found fast in both strongly-conver or non-convex cases
B V04 BM20].
Notion of complexity Given E > 0, V E F, and some algorithm A, define the run- ning iteration T(A, V, E) as the minimum number of rounds such that given ini- tial point with initial KL divergence upper bounded as Ko, algorithm A outputs a so- lution x whose marginal distribution P satisfies Fl(p, πV) S e, i.e. T(A, V, Ko, e) = sup (z Po: s.t. (L(Pol]T)) Ko inf [t:FI (p(A[V, x., f)). TT) $ We define the worst case complexity as
Compwc (F,, Ko) = inf sup T(A, V, Kn,E). AEAM VEF
For some randomized algorithm A E Arand, we define the randomized complexity a
(Fmpp(F,s,,) = inf sup T(A, V, 5).
AEAi VEF
By definition, we have Compwe Kn) 2 ComPR(F, (F, e, Ko). In the rest of this paper, we only consider the randomized complexity and we lower-bound it by considering the distributional complexity:
(Fmpp Ko) == sup inf E. PEA(J) AEAand V~F
V,,,
where A(F) is the set of probability distributions over the class of functions F.
We note that sampling. the iteration complexity is determined by the output of the last iteration, which analogous to last-iteration properties in optimizations [ALW19].
"We note that in sampling, cannot define the randomized complexity the expected running iteration the case optimization [BGP17]. since the intrinsic randomness
over mixtures of deterministic algorithms & will affect the marginal distribution of output. Furthermore, Yao's minimax principle (AB09) cannot be applied, since the different definition of randomized complexity. We acknowledge that another possible option not discussed in this paper is the "Las Vegas" algorithm, which return "failure," described in [AC24].

---

2.2 Averaged Langevin Monte Carlo
One of the most commonly-used dynamics for sampling Langevin dynamics [Che23], which is the solution the following SDE, dæ (v) v2dB,, where (B:))e(o.r] standard Brownian motion in R4. When т is a strongly log-concave or V a strongly convex, the time derivative of the relative Fisher information satisfies
l,Fl(),ll - -2ell(
where is the law at time t, (see Section 2.5 [Wib25]). To the best of our knowledge, when xy is non-log-concave its contraction properties remain unknown. However, discrete-time analog the de Bruijn identity holds for the Langevin Monte Carlo with step size h E T [BCE+22 Appendix B]:
1 =l( -
0 (
+ dL)
By integrating and summing, the averaged Fl along Langevin Monte Carlo be bounded
2KL(HolITT + dh)
Nh FI(HellT)dt
Nh
By the convexity of the Fisher information, is sufficient to output a sample from the averaged distribution Jina NR So / p,dt.
2.3 Parallelized Langevin Monte Carlo
The main idea of parallelized Langevin Monte Carlo is to regroup the discrete grids along time horizon and update all grids in same group simultancously [SL19 ACV24 YD24 ZS24]. Specifically, taking
Picard iteration [Cle57 ACV24 as example, to approximate the difference Lt,-1 2t, over time slice [t,, fn+1]
Ant1
V(x,)ds (2((B...) -B,.)
Itn
M
W. WVV (Ta, )s V2(B Bin),
with discrete grid of M collocation points t, tn Tn.0 S tn + Tu,1 S + Tn2 .... tn + Tn.as = fn+1- We update the points in a wave-like fashion, which inherently allows for parallelization: for m' =1, -l..., M, 1-p=0 0,
K
M
Tm.m Fi,n
Σ
Wm (ar
(a V2( tTmmm. B,,))
With such regrouping, as long as the total time length of each group scales as (L) the grids will converge exponentially fast. Given sufficiently accurate starting point time 6n the initial error scales (d). Therefore, K (log (%) steps suffice for the convergence of each group. In the strongly log-concave case, suffices to simulate Langevin dynamics over the time interval [0, (log( KL [m] })] Therefore, N (log( (L(v))| )) groups are sufficient, and the total number of steps scales KN (log² ((4) (1))), )) assuming (L(Ho]||T) Odd) Recently, Zhou al. (ZS24
c²
showed the sequential update over each group is not necessary and proposed a diagonal style update
with Olog( total steps (See Figure 1b.
3 Parallel Picard method for minimizing relative Fisher information
In this section, we present parallel Picard methods minimizing relative Fisher information in non-log-concave case (Algorithm) and show it holds improved convergence rate (Theorem 3.1)
We illustrate the algorithm in Section 3.T and give a proof sketch in Section 3.2 All the missing proofs can be found in Appendix
5

---

Time Depth: N (log d) time slices
initial dist.
target dist.
N
N 1
Picard Depth: J Ö(log d) depta
N
J
J+1
N+J
Figure 1: Illustration of the parallel Picard method: each rectangle represents an update, and the number within each rectangle indicates the index of the Picard iteration. The approximate time complexity is N
Ollo d).
Theorem 3.1. Given two integer parameters J 2 and M and an access the gradient oracle of VV, there is an algorithm that runs N + J iterations with at most M (N + +J queries per iteration and outputs a sample with marginal distribution p such that
[KL(
Ld
LKL( + Ld 0.5
Fl(pI(T) X
+
connergence of overaged LMC discvetization
parallization
(1)
Ld and J J- O(log( ((log(=#) (d),, the algorithm Furthermore, by setting N [KL( and M e
within O LKke + log (=4)) iterations with at most O 12KKo + Ld log (+/) queries per iteration, and returns 2 -acurrate sample in Fl.
Remark 3.2. We can usually take (L(uollar) = (d). Then taking
Ld M 0
(Ld)
Ld
Ld log
=
J = N
E2
2
E2
the algorithm runs O Ld having accuracy in terms the Fisher information w.r.f. the target.
(LT)) iterations with
128
queries per iteration and return a sample
Remark 3.3. Compared to the bound for the sequential method presented in (BC our upper bound (right-hand side of Eq. TT) for the parallel method also include one converge term LKLi (m)
and discretization error term M and an additional exponentially decaying error term by parallelism [KL((a))()) + +Ld) J-N. N
Remark 3.4 (Tradeoff between query per round and adaptive complexity). When the number of computation cores, denoted by W, is limited, the adaptive complexity of our algorithm O
sw log (=)) When W this recovers the sequential method; when W =Ō( dh) with assumption Ko Odd,, it recovers our fully parallel method. Another interesting intermediate case arises when applying averaged Langevin Monte Carlo to the algorithm in [ACV24), which updates time slices sequentially. This corresponds W 2. yielding an adaptive complexity of O log( 4)) which fits naturally within the above tradeoff curve.
&
3.1 Parallel Picard method
adopt the parallel Picard method ZS244 which achieve nearly tight result for log-concave
sampling. In Lines 5-9, we apply the averaged Langevin Monte Carlo [BCE+22] to initialize the vector value at all grids with Fisher information bounded by Odd). Specifically, we initialize a at all points along the time horizon using the output of the averaged Langevin Monte Carlo procedure

---

in Line 9. In Lines 1-4, we generate the random noises and fixed them. Subsequently, we seek to construct an approximate path of the true Langevin dynamics by means of parallel computation. Specifically, in Lines 10-16, we apply parallel Picard method with forward Euler-Maruyand Method In j-th each update, for m--th grid in n-th time slices, we in diagonal style as illustrated in Figure I perform
h
Σ (V( + 2(( - Bah),
.
m'=0
where nm corresponds to time nh + mr h. In Lines 17, we return the average point along the interpolation path of {a 72 [N], [M]].
Algorithm 1: Parallel Picard method for con-log-concave sampling
Input: x. (oo: gradient oracle VV, the number of the iterations in outer loop J, the number of time slices N, the length of time slices h, the number of points on each time slices M.
for n O,..... . 1. m O,..., , M (in parallel) do Sn.m (0, (h)
generate the noise
for n = .N..... - L, m 0,... M (in parallel) do BnR+(m+1)6/M
Σ
Σ En', an Σ En,m
n'=(0...,, m m(EMM)
mn mmEmm
5 x= 1.0 = xx, for = --, -.....,
6 for k ===1 1,....; do
4kh = a 11- VVV (k-1)) + 2((Bk) - B(k-1jb):
>. initialization
Pick time E j0, Nh] uniformly at random.
9 Let be the largest integer such that kh I t, for all n = O...., N ...... x okhh (())) + v2(B, Bkh)
and m E [M] set
for h = 1, 1,.....5 N do
for j = 1, 1,.... min (k- 1, J and m 1,.... M (in parallel) do
let -- and x/
- 1I,
12
n.m
x n.0
M
h
Σ
V
VV + 22 /BBn+tmM//M Buh).
m 0
13
for == N 1, I,...,, N + J do
14
for n = max h - J} N and m I,...,M, M (in parallel) do
15
let j = 1: - n and n00 x 1.M
a a/.m =/,0 h
V( /2( /2(Bhh4mh/M Ban),
17 Pick time E [0,N7, Nh) uniformly at random, let the largest integer such that kh/M $ t
3 2 [WMM) (t- (WM v2(B, -B B(hs/M))
return F...
3.2 Proof sketch of Theorem 3.1:
analysis of Algorithm 1
Following [VW19 ACV24 de Bruijn identity:
ZS24 we use interpolation method to obtain a discrete time analog of
3
0 < - [| EE VV:)) (w>-))>
By Lipschitz condition. Integrating over time nh nh + (m++1) upper bound the averaged Fl along the discrete trajectory by
and summing,
M
N
2Kg 2Ld
Nh Fl(pe[[T)dt
$
+ 3L2E, Nh M
+

---

where &
max nE[N], me [M]
||
"m1il [|]
which represents the convergence error of Picard
iteration. It remains to prove the convergence of Picard iteration. The key is to decompose the emoor
during the diagonal update and upper bound the initial error. Let Eg == max E ||| -
me[Md]
2,m
By definition of Buler-Maryyama scheme, can decompose the error as
& s 2 + 21 2h²
where h the length of time slices, and L Lispehitz constant of the gradient. Thus by choosing the time length sufficiently small relative to the Lipschitz constant L, we ensure convergence along the Picard direction. As for the initial error, decompose it
E < 2E,_1 + 21 2 (|)) + 5dh,
where 1(()) is controlled by the initialization procedure using averaged Langevin Monte Carlo with large step size h = (1).
The details of the proof can be found in Appendix
4 Lower bound
In this section, we establish our lower bound (Theorem 4.1 by combining a reduction from mini- mizing the relative Fisher information to the problem of finding stationary point with the optimal adaptive complexity for this task, as established by Zhou al. [ZHT255
Theorem 4.1. Let the dimension d satisfies ((K)) consisting of L-smooth functions, such that for any 2 VLd and x. Po with (L(PollTV) S Ko for any (T lver,
((K3 There exists a function class F,
KoL Ko E2
(F, 2
Remark 4.2. This lower bound matches the upper bound in Theorem 3.1 for specific regime of 8 = VLd. The condition 2 52 2/13, arises because the lower bound construction in (ZHTS25)
lies in high dimensional regime d 2 4))
To prove Theorem 4.1 we will reduce the problem to that finding a station- ary point in parallel, and then verify the initialization condition. We first recall the reduction lemma from non-log-conee conccce sampling to non-convex optimization.
Proof of Theorem 4.1
Lemma 4.3 (CCEL*24 Lemma 16)). Let exp(-V) be S-loghsmooth density Rd. Then, for any probability measure μ.,
E, [[VI|*] s F((n||T] 2,dd.
To apply this reduction, we recall the adaptive complexity of finding stationary point which scales as O e e-²) for high dimensional regime (d= Ω (e 4)).
Theorem 4.4 (The adaptive complexity of finding stationary points ZHTSS25). Assume d (. There exits a function class F consisting of some T-smooth function with given initial point x., such that ((x") min V (w) < A, and the following holds: any (possible randomized) algorithm running within O 2-2 iterations with poly(d) queries per iteration fails to find e-upproximate point for any V E F with probability d=1(1)
We set = 4vLd. From the reduction lemma (Lemma 4.3
if we can obtain a sample from a measure i such that for πV cxp(-V), it holds that F() < Ld, then sample from μ is e-stationary point of with probability at least 1/2.
In the following, we check the initialization condition. We set initialization oracle to output a sampler from A0 Ia). Now we need to compute the value of K, = supver (L(ool)Ty). To do use the following lemma.
8

---

Lemma 4.5 (KL divergence at initialization [CGLL23, Lemma 17]). Suppose that V : R + + function such that ((0) Vnf Σ A, VV L-Lipschitz, and m = - [Il dæ co where exp(-V).. Then, for po NNO,, -L))). Lá), we have the bound
KL(Ho]|T) 2 A + d(1 V log(Lm²)),
We remind the hardness function in ZHTS225 takes form
V = poly (g(p(ar/poly)) + 2r ||01||
where poly denote any positive quantity for which both the quantity and its inverse are bounded above by polynomials in A, d, and 1/e, and poly. Furthermore g IR + IR and p Rd + 12d poly-Lipschitz, then
Vg(p(- S poly.
Thus FI(TTV poly ETy |III ((pl-/poly) S poly where NO rla. By the Donsker-Varadhan variational principle (PW25 Theorem 4.6] and the fact that satisfies the log-Sobolev inequality with poly, we have
Eny [1-1P]]
À {KL(TT log E, -xp()))-113)}
1
I poly (FI(Tv (|z) + +1}
< poly:
with À poly and E, exp(A|l I1a) S 1. Thus Ko = (L(ull|=) S A+ A Thus if Ko 2 M(d).
Ku. Since E Ld, the number of the required iteration satisfies
AL
Kg
#iteration 2
d
Finally check the requirement of dimension, d > ((Kppd)3, which is satisfied provided d > 0(K)/3)
Discussion and Conclusion
In this work, we initialize the studying of parallelize minimizing the relative Fisher information for non-log-concave sampling by showing (1) averaged Langevin Monte Carlo can be accelerated by parallelism and (2) offer a tight lower bound for specific accuracy regime. Our results rule out the possibility of designing general high-accuracy relative Fisher information minimizer via parallelism in the non-log-concave setting, contrasting with the log-concave case. Furthermore, our results offer new understanding for the theme of "sampling versus optimization" by revealing the distinct role parallelism plays in separating the two.
We believe there are several intriguing directions for future work exploring the role of parallelism in sampling versus optimization, and we conclude by highlighting few of them.
1. (Constant-dimensioon case). In the constant- minstant-dimensionall setting, is possible find stationary point in l = O(lo((//E) rounds using O 5= (1+(000(2-")) queries per round by leveraging gradient flow trapping BB20 HZ23 ZHTS25). This raises the question: can one similarly minimize the relative Fisher information within (llog(1/e) rounds by trapping the Langevin dynamics?
2. (Lower bounds beyond specifie large accuracy). Although our lower bound tight, it applies only to a specific high-accuracy regime (s = VTd). In contrast, for parallel non-convex optimization, tight lower bounds adaptive complexity, namely, (()=2), are known for finding stationary points when e < ((d1/4) [ZHT255). natural question whether similar poly(s-)) lower bounds can be established beyond this setting, particularly in the low-accuracy regime (s o(1), as by the bump function construction used for query complexity in Section of [CGLL33..

---

3. (Functional inequality case). For strongly log-coneave distributions, it is possible to design high-aceuracy samplers leveraging parallelism [YD24] ACV24 ZS24]. contrast, for non- log-concave distributions, designing general high-accuracy samplers via parallelism becomes impossible. This raises natural question: what the boundary between these two cases? A much weaker question is whether high-accuracy samplers can be designed via parallelism for distributions satisfying functional incqualities such as the log-Sobolev or Poincaré inequality.
Acknowledgment
The authors thank Sinho Chewi for very helpful conversations. HZ supported by International Graduate Program of Innovation for Intelligent World and Next Generation Artificial Intelligence Research Center. MS was supported by JST ASPIRE Grant Number JPMJAP2405.
10

---

References
[AB09] Sanjeev Arora and Boaz Barak. Computational complexity: modern approach. Cam- bridge University Press, 2009.
[AC24] Jason M Altschuler and Sinho Chewi. Faster high-accuracy log-coneave sampling via algorithmic warm starts. Journal of the ACM, 2024.
[ACV24] Nima Anari, Sinho Chewi, and Thuy-Duong Vuong. Fast parallel sampling under isoperimetry. arXiv preprint 2tt:::20000001666. 2024.
[ALPW24] Christophe Andrieu, Anthony Lee, Sam Power, and Andi Q Wang. Explicit convergence bounds for metropolis markov chains: isoperimetry, spectral gaps and profiles. The Annals of Applied Probability, 34(4):4022-4077 2024.
[ALW19] Jacob Abernethy, Kevin A Lai, and Andre Wibisono. Last-iterate convergence rates for min-max optimization. arXiv preprint arXiv: 02027, 2019.
[BCE+22] 22] Krishna Balasubramanian, Sinho Chewi, Murat Erdogdu, Adil Salim, and Shunshi Zhang. Towards a theory of non-log-concave sampling: first-order stationarity guaran- tees for langevin monte carlo. In Conference on Learning Theory, pages 2896-2923, PMLR, 2022.
[BGP17] Gábor Braun, Cristóbal Guzmán, and Sebastian Pokutta. Lower bounds on the oracle complexity of nonsmooth convex optimization via information theory. IEEE Transac- tions on Information Theory, 6377):470--4724, 2017.
[BM20] Sébastien Bubeck and Dan Mikulincer. How to trap a gradient flow. Conference on Learming Theory, pages 940-960. PMLR, 2020.
[BS18a] Eric Balkanski and Yaron Singer. The adaptive complexity of maximizing a submodular function. In Proceedings of the 50th annual ACM SIGACT Symposium on Theory of Computing. 2018
[BS18b] Eric Balkanski and Yaron Singer. Parallelization does not accelerate convex optimiza- tion: Adaptivity lower bounds for non-smooth convex minimization. arXiv preprint arXiv: /808.0380, 2018.
[BV04] Stephen P Boyd and Lieven Vandenherghe. Convex Optimization. Cambridge university press, 2004.
[CDWY20] Yuansi Chen, Raaz Dwivedi, Martin J Wainwright, and Bin Yu. Fast mixing of metropolized hamiltonian monte carlo: Benefits of multi-step gradients. Journal of Machine Learning Research, 2020.
[CEL+24] Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, and Matthew S Zhang. Analysis of langevin monte carlo from poincare log-sobolev. Foundations of Computational Mathematics, pages 1-51, 2024.
[CGLL23) Sinho Chewi, Patrik Gerber, Holden Lee, and Chen Lu. Fisher information lower bounds for sampling. In International Conference on Algorithmic Learning Theory, 2023.
[Che23] Sinho Chewi. Log-concave sampling. Book draft available at https://chewisinho. github. io, 9:17-18, 2023.
[Cle57] CW Clenshaw. The numerical solution of linear differential equations in Chebyshev se- ries. In Mathematical Proceedings of the Cambridge Philosophical Society. Cambridge University Press, 1957.
[DCWY19] Raaz Dwivedi, Yuansi Chen, Martin J Wainwright, and Bin Yu. Log-concave sampling: Metropolis-Hasting algorithms are fast. Journal of Machine Learning Research, 2019.
[DG19] Jelena Diakonikolas and Cristóbal Guzmán. Lower bounds for parallel and randomized convex optimization. In Conference on Learning Theory, 2019.
11

---

[DMM19] Alain Durmus, Szymon Majewski. and Blažej Miasojedow. Analysis of Langevin Monte Carlo via Convex Optimization. The Journal of Machine Learning Research, 2019.
[FYC23] Jiaojiao Fan, Bo Yuan, and Yongxin Chen. Improved dimension dependence of a
proximal algorithm for sampling. In Conference on Learning Theory, 2023.
[GTC24] Wei Guo, Molei Tao, and Yongxin Chen. Provable benefit of annealed langevin monte carlo for non-log-coneave sampling. arXiv preprint arXiv:2407.16936, 2024.
[H] Andrew Holbrook, Philippe Lemey, Guy Baele, Simon Dellicour, Dirk Brockmann, Andrew Rambaut, and Marc A Suchard. Massive parallelization boosts big bayesian multidimensional scaling. Journal of Computational and Graphical Staristics, 30(1):11- 24, 2021.
[HLFS21] Andrew Holbrook, Charles E Loeffler, Seth Flaxman, and Marc A Suchard. Scalable bayesian inference for self-excitatory stochastic processes applied to big american gunfire data. Statistics and computing, 31:1-15, 2021.
[HZ23] Alexandros Hollender and Emmanouil Zampetakis. The computational complexity of finding stationary points non-convex optimization. In The Thirty Sixth Annual Conference on Learning Theory, pages 5571-5572. PMLR, 2023.
[HZ25] Yuchen He and Chihao Zhang. On the query complexity of sampling from non-log- concave distributions. arXiv preprint arXiv:2502.06200, 2025.
[JKO98] Richard Jordan, David Kinderlehrer, and Felix Otto. The variational formulation of the Fokker-Planck equation. SIAM journal on mathematical analysis, 1998.
[LCH+06] Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, Fujie Huang, et al. A tutorial on energy-based learning. Predicting structured data, 100), 2006.
[LRG18] Holden Lee, Andrej Risteski, and Rong Ge. Beyond concccicyitty Provable guarantees for sampling multi-modal distributions using simulated tempering langevin monte carlo. Advances in neural information processing systems, 31, 2018.
[LST20] Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Logsmooth gradient concentration and tighter runtimes for Metropolized Hamiltonian Monte Carlo. In Conference on learning theory, 2020.
[LST21] Yin Tat Lee, Ruoqi Shen, and Kevin Tian. Structured logconcave sampling with restricted gaussian oracle. In Conference on Learning Theory, pages 2993-3050. PMLR, 2021.
[MCC+21] Yi-An Ma, Niladri S Chatterji, Xiang Cheng, Nicolas Flammarion, Peter L Bartlett, and Michael I Jordan. Is there an analog of nesterov acceleration for gradient-based memc? 2021.
[7]+ Jean-Michel Marin, Christian P Robert, et al. Bayesian Core: A Practical Approach to Computational Bayesian statistics, volume 268. Springer, 2007.
[N+18] 18] Yurii Nesterov et Lectures on convex optimization, volume 137. Springer, 2018.
[NWS19] Shinichi Nakajima, Kazuho Watanabe, and Masashi Sugiyama. Variational Bayesian learning theory. Cambridge University Press, 2019.
[PW25] Yury Polyanskiy and Yihong Wu. Information Theory: From Coding to Learning. Cambridge university press, 2025.
[RCC99] Christian Robert, George Casella, and George Casella. Monte Carlo statistical methods, volume 2. Springer, 1999.
[SB13] Olivier Sigaud and Olivier Buffet. Markov decision processes in artificial intelligence. John Wiley & Sons, 2013,
12

---

[SL19] Ruoqi Shen and Yin Tat Lee. The Randomized Midpoint Method for Log- Log-Concave Sampling. Advances in Neural Information Processing Systems, 32, 2019.
[VW19] Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32. 2019.
[Wib25] Andre Wibisono. Mixing time of the proximal sampler in relative fisher information via strong data processing inequality. arXiv preprint arXiv:2502.05523, 2025.
[YD24] Lu Yu and Arak Dalalyan. Parallelized midpoint randomization for langevin monte carlo. arXiv preprint arXiv:2402. 14434, 2024.
[ZHTS25] Huanjian Zhou, Andi Han, Akiko Takeda, and Masashi Sugiyama. The adaptive complexity of finding stationary point. Conference on Learning Theory, 2025.
[ZS24] Huanjian Zhou and Masashi Sugiyama. Parallel simulation for sampling under isoperimetry and core-based diffusion models. arXiv preprint arXiv:2412.07435, 2024.
[ZWS24] Huanjian Zhou, Baoxiang Wang, and Masashi Sugiyama. Adaptive complexity of log-concave sampling. arXiv preprint arXiv:2408. I 13045, 2024.
13

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA]. .
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
general, answering
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The main claims the abstract and introduction accurately reflect the paper's contributions and summarize the key results and methodologies, providing true overview of the research and its significance.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
14

---

Justification:
We discussed the limitations in Section and Appendix B
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specifiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We present the problem setting and assumptions in Section 2.1 For first
main result (Thcorem 3.T), a proof sketch is provided in Section 3.2, with the full proof given in Appendix A The second main result (Theorem 4.1 is proved in Section 4
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This paper focuses on theoretical results.
Guidelines:
15

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibilityy In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
This paper focuses on theoretical results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
stteeeesuummisiooooooooooo. for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//ipss.cc/publi///uuu
Codeeuumiiii wettsbbmmssiiioi ssionoolicy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
16

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: This paper focuses theoretical results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper focuses on theoretical results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This paper focuses on theoretical results.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
17

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://wwwrp...cco.u..../cccaaaa
Answer: [NA]
Justification:
I confirmed it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discussed in Section
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: This paper focuses on theoretical results.
Guidelines:
The answer NA means that the paper poses such risks.
18

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper focuses theoretical results. It does existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com /dtaaset has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper focuses on thcoretical results and we not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the detaset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper focuses on theoretical results, It does not involve crowdsourcing nor research with human subjects.
19

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper focuses on theoretical results.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLM is used only for grammar checking.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (https: hacp:p//e/aarrrssscc/oooeeeeeeee for what should or should not be described.
20

---

A Proof of Theorem 3.1
A.1 Useful facts
In this section, we first recall several useful lemmas.
Lemma A.1 (Differential inequality of KL along interpolation [BCE 22 Lemma 12)). Consider the stochastic process defined by
Dt = 3o tgo + 2 Br, fort 0,
where (Bi),z0 is a standard Brownian motion in R which independent of (æo. go). Let Me the law of x. Then
(cKL(HelIT) <
FI( (T) + (z)) Elgo xx]ll
FI( (T) + E E (x;, - gu 9u
Lemma A.2 (Initialization [BCE 22 Theorem 2J). For all . and m [M]. let H the law of w n.m then we have
(KL(P)] ST.
FI
(T)
Nh
Lemma A.3 ([CEL*22 *24, Lemma 16)). Assume that VV L-Lisschitz For any probability measure μb, it holds that
Eu V + 2dL
A.2 Decomposition via interpolation method
We denote KLn,m (L(uk, where pl,m represents the law of xi Let 2 be the linear interpolation between x and an 2 1. Le., for nh mh nh + M
(m++1)hh let
M
( (t-nil nh
(t-
mh
VV (a J-1) + 22(B. Bah4th/Ms).
p,m
M
Then Lemma A.
yields
3 O.KL(ue||T) S - Fl(ue [|)) + VV.)) VV (w
For the second term, by smooth of V.
VV (x,) - (*
L
|
J-1
Fm,m
|| x 11]
2
x
+ 21
m,m
$ 44""
n-n
nh
mh
2
[2 n, ||]
+ &LL
[|B Bun Bun+ + 2
|| ||>%,,m
J-1
M
(-nh mh
2
mh M
IF
[[VV(
VV (.
+ 8L2
( 6-nhh nh
E
F [|BB, Ba [1]] 2I | x
Taking Lh < 0.1, we have
(V. (V(
21

---

991, (1-nh-
mh
[v:(())))
+ 9T. [| B Buh+thhMM| [1]] +T.2B |1 2p
M
For the first term, by Lemma A.3
and Lh 0.1, we have
(.KL(ulITTT s
FI( |T))
$ 3 9
Fi(HelTT) + 18L (t-nh-
( M
mhh
2266 ( (t-rsh M
m/
4
M
+ 3
||
=x,mm []]]
mh 2
mh M
- - Fl(uel1TT) + 18
t t-
+
9222d (t-nh-
M
+ 2 || xmmm
Integrating it over / E
mb [nh +
M. nh +
(m+1))h M
we obtain
nn++ for 1136
h
h
KLn,m+1 KLn,m
5
Fl(pel())dt 6L
+
5L2d
+
3322
nd 37
M
M2
M
mh++ (om
L'dh²
3L2h
|1 Fm
5 2
=l(uel()dd +
E
M2
M
nh+ X
for any n E [N] and m E [M], which represents the convergence error of Picard iteration. Specifically, we assume b - & for any n E [N] and E [M]. Then by summing, we have
Now we assume there is a uniform upper bound for EE ||
2
2KL..o 2Ld Nh
Fl(Ne]IT)d <
+ 3T.
Nh. Jo
M
A.3 Convergence of Picard iteration
We will end the prove by show the uniform upper bound for E
|> x x/-111 To bound we
define E max
m= M
p,m
Lemma A.4 (Decomposition of E.). Assume Lh = To and let jc is the law of wh. We have the following decompositions and initialization estimations:
1. 8 < 28 0.028 1 for any j ......JJ and n I....,N 1:
2. 8 < 28, + 21 [|T] + 5dh, for j = 1 and n 1, I,...,N 1;
3. 8 < 0.018 for any j 2, ........ J and 0:
4. E < 21² [|] + 5dh;
Proof. For j E [J], n = I,... N - 1, m 0 M 1, we have
x n,m
2 f-1 2
n.m
+ 222
m
< 2E
x n,0
n.0
22
E
VV (( (2
n,m!
ml 0
< 2E
2 n.0
+ 2h2
max
(V (2)-2
n,m!
=1 11.-....
22

---

I 2 n-1 + 0.028
For 1,
,,..., L, m O,..., M 1, and p I,.... P. have
E
| [|mhm,m 22,ml 11
27
2E
n,0 0 1 00
1 0,0
0
2
+ 2E
M
Va + (2 Bun))
1/0 =
< 2E
21
+ 2
V )11²
+ 4dh
< 2E
|| |0
x n,0
+ 2F + 2dL) + 4dh
< 2
2h Fl(2
||T)) + 5dh.
When 0. 2 2 we have
j-1
0,m
0,10
h
m-
1
<
E
V
VV (3t
M
mm =0
22
S 122
max
E
VV 0.m0
m/=1....m
h2
max
E
20,m
m' =
When 0, = 1 we have
E
||
I 21² + 5dh.
Lemma A.5. Jf 2 N, then for = 0,....N 1 we have
N & < 200 [|)) + 5dh)0.5
Proof. By Lemma
A.4 we can recursively bound & Specifically, for n 2 and j = 1, we have
E, s +21 F((1) [|) < (2)) ((dd))))) S 2n+1 222++(22FF((((( ( (5)),
and for = 0, > 2, & <
5dh). Furthermore, for n 2 and j 2 2, by
m < cm )",if 2 n, we have
E < Σ 0.020 n2 a + 2
el
n [n+j-1 - j b-b
) 02020-b2000
2
2
b=2
aatj - 2)
5
nn + 1)
j-b - 0..00'--22000002
< (2h²FI(H²((()) + 5dh)
0.020-12n-1 12n-a
20+1
Σ
j-2
h=2
n1 n- a- -22
n + j jj- b)
j j-b '1)
< (2h"F1(H)1))) + 5dh)0.02 12
+
j-2
a=2
b=2
< 5dth))/o
n
0
+
2
j-2
j-2
e
n n
j-2
j-2
+ 5dhh)..222 =di) <
222
2
+
2 e
< (l 1 a=2
1=0
4
< 200 F1 (|10||=)) + 5dh)0.552",
where the last equation holds since 0. 23 (2j)
-
23

---

A.4 Overall bound
Combine Equation and Lemma
A.5 have
2KLo.0
2Ld
Nh. FI( S
+
(l + 5.h)0.5
Nh
M
By the convexity of the Fisher information, the averaged distribution ş (Nh) So jtdt also satisfies
2KLo.0 2Ld
(T)dl S
Nh + M
+ (00 [|=)) + 1-5dh)0.5"
We also observe the output is sampled from μ.. By Lemma
A.2 and Lh 0.1 we have
2TKLo.0
2Ld
2KL(pal| (T)
Fl(Allr)dt I
+ 600I.
2h2
+ +8I.2
5dh 0.5
N
M
Nh
2LKLo.0
2Ld
(2LLKL(
+ 320Ld 0.5
N
M
N
B
Limitations
As initial exploration of the adaptive complexity of minimizing relative Fisher information, our work still leaves a significant gap between the upper and lower bounds, particularly in the small-accuracy regime.
C Social Impacts
We present several theoretical results for minimizing relative Fisher information. While we do not see any immediate societal impact, there may be potential indirect consequences of our work that not apparent at this time.
24


Reviews:
[{"review_id": "9ueHtqDmmx", "reviewer": "Reviewer_5zmn", "summary": "This paper advances the theory of non-log-concave sampling by establishing both upper and lower bounds on the adaptive complexity required to minimize relative Fisher information. Building on the work of [BCE+22] for Langevin Monte Carlo (LMC) in the non-log-concave setting and [ZS24] for the Parallel Picard method, the paper’s central contribution is the innovative integration of the Parallel Picard method with LMC for non-log-concave distributions. This combined approach demonstrably improves adaptive complexity over parallel LMC. Moreover, the paper derives a lower bound on adaptive complexity in the large $\\epsilon$ regime.", "questions": "1. Why is the focus on the specific regime of large FI, with $\\epsilon=\\sqrt{Ld}$, particularly significant? Is it possible to extend the results of Theorem 4.1 to smaller values of $\\epsilon$? If such an extension is not feasible, it would be helpful to clarify the obstacles involved. Without this clarification, the claim of tightness for the lower bound might appear less robust, potentially weakening the perceived quality and significance of the result.\n\n2. Theorem 4.1 states the lower bound in terms of $L$ and $d$, but does not explicitly show the dependence on $\\epsilon$, even though the accuracy is constrained by $\\epsilon\\geqslant \\sqrt{dL}$. Would it be clearer to retain the $\\epsilon$ dependence in the expression on line 248, i.e. \\# iteration$\\gtrsim\\dfrac{\\Delta L}{\\epsilon^2}$, while explicitly noting the limitation $\\epsilon\\geqslant\\sqrt{dL}$.\n\n3. The absence of experimental results limits the validation and practical support of the theoretical findings.", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\nNovel Application of the Parallel Picard Method: The application of the Parallel Picard method is particularly compelling, as it circumvents challenges such as estimating the complexity of score-matching functions in diffusion models, as encountered in [ZS24]. This enables a more efficient improvement over vanilla LMC.\n\n**Weaknesses:**\nWhile parallel LMC lends itself to straightforward vectorized or matrix-based implementations, the proposed integration with the Parallel Picard method requires explicit implementation details to demonstrate its practical feasibility and validate the claimed theoretical improvements. Furthermore, for high-dimensional settings, a discussion of the space complexity of the parallel algorithm is necessary, especially in light of the absence of empirical validation.", "was_revised": true, "final_justification": "The application of the Parallel Picard method is particularly compelling and results in improved complexity. However, the lower bound is established only for a fixed value of $\\epsilon$, which limits its strength by preventing verification of tightness across varying accuracy levels. As a result, I remain somewhat negative overall.", "rebuttal": "We sincerely thank the reviewer for their thoughtful evaluation and insightful questions. We are encouraged by your recognition of our **novel application** of the parallel Picard method to achieve **efficient sampling**. Below, we address your questions and comments:\n\n\n**\"...focus on the specific regime of large FI...Is it possible to extend the results of Theorem 4.1 to smaller values $\\varepsilon$?\"**\n\nWe focus on the large Fisher Information (FI) regime because the reduction from minimizing FI to minimizing the gradient norm, formalized in Lemma 4.3, is valid only when FI is sufficiently large. This mirrors the sequential setting, where a similar reduction underpins Theorem 9 in [CGLL22]. Our Theorem 4.1 strengthens that result by extending it to the parallel setting.\n\nAs for the possibility of extending the result to the small FI regime, as in Theorem 10 of [CGLL22], we believe this would require fundamentally different techniques. Specifically, if we adopt the bump function construction from [CGLL22] and place it in an unreachable region as in [ZWS25], one can show that with $d$ iterations and $\\mathrm{poly}(d)$ queries per iteration, it is not possible to produce a sample with FI smaller than $\\exp(-cd)$, for some constant $c > 0$. However, this is strictly weaker than Theorem 10 in [CGLL22], which establishes a lower bound of $1/\\varepsilon^2$ for the total query complexity. In particular,  Theorem 10 in [CGLL22] implies that achieving such accuracy would require exponentially many queries in $d$, and since the number of queries per iteration is polynomial in $d$, the total number of iterations must also be exponential in $d$. Such result is much stronger hardness guarantee than the $d$ iteration regime we can obtain.\n \n\n\n\n[CGLL22] Fisher information lower bounds for sampling, Sinho Chewi, Patrik Gerber, Holden Lee, Chen Lu, ALT 2023,\n\n[ZWS25] The adaptive complexity of parallelized log-concave sampling, Huanjian Zhou, Baoxiang Wang, Masashi Sugiyama, ICLR 2025\n\n\n**\"...a discussion of the space complexity of the parallel algorithm is necessary...\"**\n\nThank you for highlighting the importance of the space complexity. In practice, fully parallel updates may require excessive memory. To address this, we consider a slicing window strategy, as proposed in [SBE+24], where in each iteration we update at most $W > 0$ points in parallel. When $W = 1$, this recovers the sequential method; when $W = \\frac{d^2}{\\varepsilon^4}$ (assuming $K_0 = O(d)$), it recovers our fully parallel method.\n\nUnder this framework, we obtain the following tradeoff: the space complexity is $Wd$, and the adaptive complexity becomes$O\\left(\\frac{d}{\\varepsilon^2} + \\frac{d^2}{\\varepsilon^4 W} \\log \\frac{d}{\\varepsilon^2}\\right),$ where we define the space complexity in terms of word usage rather than bit count.\n\nAs noted by Reviewer 2U73, an interesting intermediate case arises when applying averaged Langevin Monte Carlo to the algorithm in [ACV24], which updates time slices sequentially. This corresponds to $W = \\frac{d}{\\varepsilon^2}$, yielding an adaptive complexity of $O\\left(\\frac{d}{\\varepsilon^2} \\log \\frac{d}{\\varepsilon^2} \\right),$\nwhich fits naturally within the above tradeoff curve. We will incorporate the above discussion into the revised version of the manuscript.\n\n\n\n[SBE+24] Parallel Sampling of Diffusion Models, Andy Shih, Suneel Belkhale, Stefano Ermon, Dorsa Sadigh, Nima Anari, NeurIPS 2024\n\n**\"The absence of experimental results limits the validation and practical support of the theoretical findings.\"**\n\n\nThank you for the suggestion. We have completed a standard experiment on a 2-dimensional Gaussian mixture, which demonstrates that the sequential method from [BCE+22] requires approximately 2000 iterations to converge, while our parallel method achieves comparable accuracy in just 300 iterations. We will include these results in the revised version and also plan to conduct additional experiments on more realistic and representative non-log-concave targets.\n\n\n\n**\"Theorem 4.1...does not explicitly show the dependence on $\\varepsilon$, Would it be clearer to retain th dependence in the expression on line 248...\"**\n\nThank you for the suggestion. We agree it would improve clarity to include the $\\varepsilon$-dependence, and we will revise the text accordingly."}, {"review_id": "Bl4UuzWHZT", "reviewer": "Reviewer_7Qxh", "summary": "The paper studies a parallel algorithm for Langevin Monte Carlo for non-log-concave sampling. By leveraging parallelism, we can obtain a sample $\\varepsilon^2$ close to the target distribution under relative Fisher information with the adaptive complexity $O(d/\\varepsilon^2)$, which improves from the complexity $O(d^2/\\epsilon^4)$ without parallelism. The paper also shows a matching lower bound when $\\varepsilon = \\sqrt{Ld}$. It turns out that the sequential algorithm is also adaptively optimal in this regime, which rules out the possibility of a general high-accuracy sampler via parallelism.", "questions": "Questions:\n- Theorem 3.1 states the result for the averaged distribution. But this averaging is not mentioned in the statement of the theorem.\n- Algorithm 1: does line 8 initializes all $x_{n,m}^0$ identically? Also, I have difficulty parsing the setup of $n$ and $j$ in line 10 and line 14 of the algorithm. Maybe some explanations will help readers.\n- page 8 line 231-233, why is the probability at least $1/2$? I am also not sure how this is used in the lower bound proof.\n- Lemma 4.5 is not proved/referenced. And in general, the lower bound proof is very confusing to me. I think the outline of the proof is not well-stated at the beginning, which makes it easier for readers to get distracted by the cited lemmas and theorems (especially theorem 4.4 is quite novel for nonexperts). Also, when using the Donsker-Varadhan variational principle, the involved function is required to be bounded, but a quadratic function is used here. Could you clarify why this is legitimate?\n- In the proof of Lemma B.5, the equation after line 424, I am not sure how those two binomials pop out in the second inequality.\n\n\nTypos:\n- page 3 line 82, Appnedix -> Appendix\n- page 3 line 104: the potential function is first given as $f$ and later used as $V$. Notations in the lower bound section are also not unified (such as the Lipschitz constant).\n- page 5 line 160, for $m' = 1, \\dots ,M$ -> maybe $m'$ should be $m$. Also, the equation afterwards: $x_0$ should be $x_{t_n}$?\n- page 7 line 198, the interval upper bound has a typo. Also, in the equation after line 199, $\\rm{KL}_{0,0}$ is not defined in the main text.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The question of non-log-concave sampling with a parallel algorithm of Langevin Monte Carlo is interesting.\n2. The related work is clearly covered.\n3. The exposition of the technical proof of the upper bound is clear, and the obtained bound has a substantial improvement over the existing ones. A matching lower bound is also provided.\n4. The results have interesting implications. For example, a general high-accuracy sampler via parallelism is not possible, and there is a separation between optimization and sampling when using parallelism to accelerate Langevin Monte Carlo in strongly log concave vs non-log concave cases.\n\nWeaknesses:\n1. The algorithm is not clearly presented. By reading the reference [ZS24] I realized that there is parallelization both within time slices and across time slices. I would otherwise only get the part of parallelization within time slices. Currently, Figure 1 + Algorithm 1 do not have enough explanations of the algorithm, and arrows in Figure 1 are quite abstract and confusing.\n2. I am not sure how practical the assumption that poly($d$) queries can be made per iteration is, especially in high dimensions.\n3. The current exposition of the lower bound is not very friendly to a nonexpert in this field.", "was_revised": true, "final_justification": "I think the results in this paper are interesting. What prevents me from giving a higher score is mainly the readability of the paper, specifically for the description of the parallel algorithm and the lower bound. I hope that with the promised changes in writing, the paper can better reveal its theoretical value. My rating would be 4.5 if half points are allowed. And because there are a few other 5's already, I would like to keep my score as 4 to represent my evaluation of the paper.", "rebuttal": "Thank you for your detailed and positive feedback. We appreciate your recognition of our **improved upper and matching lower bounds** for the **important problem of parallel non-log-concave sampling**. We are glad you highlighted the **broader implications**, such as the **impossibility of a general high-accuracy sampler via parallelism**, and the **separation between optimization and sampling** when using parallelism in strongly log-concave versus non-log-concave settings. Below, we address your specific suggestions and questions:\n\n\n**\"...The algorithm is not clearly presented...Currently, Figure 1 + Algorithm 1 do not have enough explanations...arrows in Figure 1 are quite abstract and confusing.\"**\n\nThank you for your thoughtful feedback. We acknowledge that the current presentation of Algorithm 1 and Figure 1 may lack clarity. To improve this, we will revise Figure 1 by replacing rectangles with lines and points to represent trajectories and grid points, respectively, and use color coding to distinguish computation graphs across different iterations. In Section 3.1, we will enhance the explanation of Algorithm 1 by providing more intuition behind its design, clarifying the purpose of each line in the pseudocode, and including an illustrative example of the update step to address potential confusion. Furthermore, we will add a discussion in Appendix that reviews existing parallel methods for sampling and diffusion models. \n\n\n**\"..how practical... poly(d) queries can be made per iteration... especially in high dimensions.\"**\n\nThank you for raising this important point. For the upper bound, the total number of oracle queries per iteration is $O(d^2)$, assuming $K_0 = O(d)$, which remains practical in moderate to high-dimensional settings. To enhance scalability in practice, we consider a sliding window strategy with window size $W$, which limits the number of points updated per iteration and thereby reduces memory usage while preserving parallelism.\n\nUnder this framework, when $W = 1$, the algorithm reduces to the sequential setting; when $W = \\frac{d^2}{\\varepsilon^4}$ (assuming $K_0 = O(d)$), it recovers our fully parallel method. The resulting space complexity is $Wd$, and the adaptive complexity becomes\n$$\nO\\left(\\frac{d}{\\varepsilon^2} + \\frac{d^2}{\\varepsilon^4 W} \\log \\frac{d}{\\varepsilon^2}\\right),\n$$\nwhere the space complexity is measured in terms of word usage rather than bit count.\n\n\nAs for the lower bound, assuming algorithms that make a polynomial number of queries in $d$ is standard in the literature (e.g., [ZWS24,ZHTS25]), and this aligns with prior work on adaptive complexity lower bounds in high-dimensional settings. We will incorporate the above discussion into the revised version of the manuscript.\n\n**\"The current exposition of the lower bound is not very friendly... page 8 line 231-233, why is the probability at least $1/2$?...Lemma 4.5 is not proved/referenced... outline of the proof is not well-stated... Donsker-Varadhan variational principle...\"**\n\nThank you for the thoughtful feedback. We acknowledge that the exposition of the lower bound may not be sufficiently accessible to non-experts. In the revision, we will improve the structure of the lower bound section by adding a high-level overview at the beginning to guide the reader through the main proof strategy and clarify the logical flow.\n\nWe will expand the explanation of Theorem 4.4 and add the proper citation and context for Lemma 4.5 (which corresponds to Lemma 17 in [BCE+22]).\n\nRegarding the probability lower bound of at least $1/2$ in Lines 231–233, this follows directly from Markov's inequality. This bound is used in the reduction from minimizing the relative Fisher information to the task of locating a stationary point.\n\nRegarding the use of the Donsker-Varadhan variational principle, when $\\mathbb{E}[\\exp{g(X)}]<+\\infty$ we can still apply the Donsker-Varadhan variational principle (Theorem 4.6 in [PW22]).\n\n[PW22] Polyanskiy, Yuri, and Wu, Yihong. Information Theory: From Coding to Learning. Cambridge University Press.\n\n**\"...averaging is not mentioned in the statement of theorem 3.1.\"**\n\nThank you for your comment. We would like to clarify that the output in Line 17 of Algorithm 1 corresponds to the averaged distribution.\n\n**\"Algorithm 1: does line 8 initializes all $x_{n,m}^0$ identically? Also, I have difficulty parsing the setup of $n$ and $j$ in line 10 and line 14 of the algorithm. Maybe some explanations will help readers.\"**\n\nThank you for the question. In Line 8 of Algorithm 1, all $x_{n,m}^0$ are initialized identically for all $n$ and $m$. Regarding the indices, $n$ corresponds to the index of the time slice, while $j$ denotes the index of Picard iterations. We will clarify this in the revised version and improve the explanation of Algorithm 1 in Section 3.1 to aid readability.\n\n\n\n**\"...In the proof of Lemma B.5, the equation after line 424, I am not sure how those two binomials pop out in the second inequality...\"**\n\nThank you for catching that. You're right and the first displayed inequality is incorrect. The second inequality is the correct one, and it follows directly from the decomposition established in Lemma B.4. We will remove the first inequality and explicitly refer to Lemma B.4 in the revised proof to make this clear.\n\n\n\n**Regarding typos:**\nWe will carefully proofread the manuscript and correct all grammatical and typographical errors to improve the clarity and overall presentation in the revised version."}, {"review_id": "ozepXhV0kr", "reviewer": "Reviewer_YNYn", "summary": "The authors study the adaptive complexity of sampling from non log-concave targets and prove some novel results. In particular, when all the factors are constant except for dimension, the parallel averaged Langevin MC algorithm is shown to have an adaptive complexity of $\\mathcal{O}(\\log d)$. This apparently matches the case for strongly log-concave sampling.  In some particular regime, the lower bound of parallel LMC matches the sequential LMC, and is optimal. Unlike in optimisation, parallelism can accelerate sampling even when the target is not log-concave. The authors use the tool of relative Fisher information, introduced in another paper from 2022.", "questions": "Please address my weaknesses above. In particular:\n- Clarify the notation\n- Clarify the implication of the bound on the initial KL diveregence.\n- Why the bound on the exponential function needs to be applied.\n- Comment on why you chose not to ad any experiments.\n- No need to respond to each minor comment, unless you feel it is important or I have misunderstood (I don't).", "limitations": "Appendix C lists one sentence of limitation, pointing out the gap between the lower and upper bounds. I would also add that failing to include any experimental investigation is also a limitation.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n- The results show not only that average LMC can be accelerated by parallelism, but also show that high-accuracy (in the sense of FI minimiser) via parallelism is not possible in the case of non log-concave. \n\n**Weaknesses:**\n- Notation is at times confusing. \n    - On line 104, is $f$ the same as $V$? $V$ is also displayed without its argument when defining the normalising constant (I believe $V(x)$ might be easier to read). Same confusion about $f$ versus $V$ on line 113.\n    - $L$-log smooth is defined without stating the conditions on $L$. I believe $L$ should be a scalar. Does it need to be negative?\n    - The oracle $\\mathcal{O}$ clashes with the complexity $\\mathcal{O}$ used in the introduction.\n- The initialisation assumption on line 129 implies a condition on the overlap of the support of the initial sampling distribution versus the target distribution. This is okay, but it might be nice to explicitly mention this to give further intuition about the assumption.\n- I am trying to understand why the last line above 425 needs to be used. Why can't we just keep the form with the exponential function and fold that through the rest of the statements?\n- The paper does not contain any experiments whatsoever. Is it possible to somehow plot empirical bounds for non log concave densities?\n\n**Minor:**\n- Formatting of Appendix A is very unusual. It is titled \"Useful facts\", however just lists one single fact, which is just the variational form of the f divergence (in particular, KL divergence).\n- Lemma B.2 is not grammatically correct.\n- \"We denotes\" on line 397 should be \"We denote\"\n- Line 82, typo in \"Appendix\".\n- Line 91. \"studying\" should be \"study\", I think.\n- LMC in equation (1) is not described as Langevin Monte Carlo.\n- Sometimes \"Fisher\" is written \"fisher\"\n- Table 1, \"Quires per iteartion\" has two typos.\n- $\\lesssim$ is not defined", "was_revised": true, "final_justification": "The authors have satisfactorily answered my questions. I've looked at the other reviews and do not see any reasons to downgrade my score. In my opinion, the criticisms from Reviewer 5zmn are minor and have been well addressed by the authors.", "rebuttal": "Thank you for your positive and constructive feedback. We appreciate your recognition of **the optimal bounds** in specific regimes, the **improved algorithm** enabled by parallelism, and the implications regarding the separation between sampling and optimization, as well as the impossibility of general high-accuracy samplers. Below, we address your specific suggestions and questions:\n\n\n\n\n**\"Notation is at times confusing...Clarify the notation.\"**\n\nThank you for pointing this out. We acknowledge that the notation in some parts of the paper may be confusing, and we will revise the manuscript to ensure consistency and clarity. Specifically, we will:\n- Use $V$ to represent the potential function consistently throughout the paper.\n- Explicitly state that $L$ is a positive scalar.\n- Use $\\mathsf{Or}$ to denote the oracle and reserve $\\mathcal{O}$ exclusively for complexity notation.\n\n\n\n\n\n\n**\"The initialisation assumption on line 129 ... it might be nice to explicitly mention this to give further intuition about the assumption.\"**\n\nThank you for pointing out that it would be helpful to make the intuition behind the initialization assumption more explicit. In fact, by Lemma 32 in [CEL+24], it suffices to initialize at a point x such that the optimality gap $V(x) - \\min V = O(d)$. This condition ensures that the relative Fisher information is finite and meaningful for convergence analysis. Various methods from the optimization literature, such as gradient descent or gradient flow trapping [BM24, ZHTS25], can be used to efficiently find such a point. We will clarify this intuition in the revised manuscript.\n\n\n\n[CEL+24] Analysis of Langevin Monte Carlo from Poincaré to Log-Sobolev, Sinho Chewi, Murat A. Erdogdu, Mufan Bill Li, Ruoqi Shen, Matthew Zhang, COLT 2022\n\n[BM24] How to Trap a Gradient Flow, Sébastien Bubeck and Dan Mikulincer, COLT 2020\n\n[ZHTS25] The adaptive complexity of finding a stationary point, Huanjian Zhou, Andi Han, Akiko Takeda, and Masashi Sugiyama, COLT 2025\n\n\n**\"why the last line above 425 needs to be used....Why the bound on the exponential function needs to be applied.\"**\n\nThank you for the suggestion. We agree with your observation and will revise it to keep the exponential form and fold it.\n\n\n\n\n\n\n\n**\"The paper does not contain any experiments whatsoever. Is it possible to somehow plot empirical bounds for non log concave densities?\"**\n\nThank you for the suggestion. We have completed a standard experiment on a 2-dimensional Gaussian mixture, which demonstrates that the sequential method from [BCE+22] requires approximately 2000 iterations to converge, while our parallel method achieves comparable accuracy in just 300 iterations. We will include these results in the revised version and also plan to conduct additional experiments on more realistic and representative non-log-concave targets.\n\n\n**Regarding typos and confusing notations:**\nWe will carefully proofread the manuscript and correct all grammatical and typographical errors to improve clarity and overall presentation, and ensure that the notation is consistent throughout."}, {"review_id": "NdLKm2JmUu", "reviewer": "Reviewer_2U73", "summary": "This paper studies the adaptive complexity of sampling from a non-log-concave distribution $\\pi\\propto\\exp(-V)$ on $\\mathbb{R}^d$ with $\\nabla^2L\\preceq LI$, such that the output distribution is $\\varepsilon^2$-close to $\\pi$ in Fisher divergence. The paper proposes a parallelized algorithm based on average LMC [BCE+22] and parallel Picard method [ZS24], and provides an improved complexity upper bound; also the paper presents a lower bound based on the adaptive complexity of finding a stationary point of $V$ [ZHTS25].", "questions": "- We may not need such a formal definition of the adaptive algorithms like in Sec. 2.1, as the only concept that would appear later in presenting the main results is $\\mathsf{Comp} _ \\mathsf{R}$. They can be moved to the appendix, and you can change the way for stating Thm. 4.1.\n- In line 3 of Alg. 1, this is not the correct way to initialize a trajectory of Brownian motion, as $B _ {t+s_1}$ and $B _ {t+s_2}$ are not independent conditional on $B _ t$. The initialization should be a cumulative sum of independent $\\mathcal{N}(0,(mh/M)I)$ increments.\n- If my understanding of Alg. 1 is correct, $x^\\cdot _ {n,m}$ corresponds to time $nh+\\frac mMh$, and I hope the authors could mention this in the text for easier understanding.\n\n# Minor comments\n\n- Line 104: $f$ should be $V$.\n- Line 127: should be $\\mathsf{FI}(\\rho\\|\\pi):=\\mathbb{E} _ \\rho\\|\\nabla\\log(\\rho/\\pi)\\|^2$.\n- Lines 152 and 428: better to include the lower and upper limits of the integral.\n- Equation between lines 157 and 158: $w _ i$ should be a scalar, so do not use bold.\n- Line 158: the inequality should be on $t$'s, not $x _ t$'s: $t _ n=t _ {n+\\tau _ {n,0}}\\le ...\\le t _ {n+\\tau _ {n,M}}\\le t _ {n+1}$.\n- Line 160: $m'$ should be $m$, should add $p=0,1,...,K-1$, and $\\bf{x} _ 0$ should be $\\bf{x} _ {t _ n}$.\n- Typo in the title of Sec. 3.\n- Alg. 1, last equation: I believe $t-kh$ should be $t-\\frac{kh}{M}$ and $B _ {\\lfloor k/M \\rfloor,k-\\lfloor k/M \\rfloor M}$ should be $B _ {hk/M}$.\n- Lines 398, 403, and the following equation: $\\frac{(m+1)hh}M$ should be $\\frac{(m+1)h}M$.\n- Line 401: $\\beta$ should be $L$.\n- Line 416: no need to mention $p$.\n- Lines 419 and 424: I hope the authors could add more details to the derivation of the equations that follows. There are some missing steps that are not obvious to me.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\nThis paper studies an interesting and important problem in the intersection of non-log-concave sampling and parallel sampling, and provides a comprehensive analysis. The paper is well-written with a strong motivation and a clear structure. The main results are also clearly stated, and the proofs are provided in an organized manner. I have checked most of the proofs and did not find significant issues, though with some minor typos and notations that could be improved. Also, the discussion on future work is very insightful.\n\n# Weaknesses\n\nThis work is mainly based on the proof techniques developed in [BCE+22], [ZS24], and [ZHTS25]. Although the results (especially the matching upper and lower bounds) are very nice, the paper does not introduce outstandingly novel techniques for the proof.\n\nAlso, I'd like to point out the following issue on readability. The paper [BCE+22] introduced the averaged LMC, which is easy to understand for the community; however, the second paper [ZS24] on the parallel Picard method is relatively new and not well-known in the sampling community. For readers that are unfamiliar with parallel sampling like me, this may pose a challenge. Though I have followed most of the proof, I'm still trying to understand the basic intuition behind this algorithm. I suggest the authors to provide a more detailed explanation of this algorithm, including its motivation and key components. For instance: What's the purpose of $J$ and $N$? Why we need to split the same update rule (lines 11 & 15 in Alg. 1) into two parts with different indices? How does it improve upon [ACV24]? A more interesting question to think about is that, if one applies the averaged LMC into the algorithm in [ACV24], how would the complexity bound be compared with Thm. 3.1?", "was_revised": true, "final_justification": "This paper studies an important problem in sampling, and presents very nice results in both upper and lower bounds that improve over existing ones in the literature.\n\nAfter the rebuttal, the authors have successfully resolved all of my concerns. I hope they can include this discussion during revision.\n\nI've also read the discussion between the authors and other reviewers, especially regarding review 5zmn. Although the lower bound is only in the large error region $\\varepsilon\\asymp\\sqrt{Ld}$, I don't think this is a major shortcoming for the paper, as typically deriving lower bounds is very challenging. Also, as this is a theoretical paper, it's totally OK without experiments, just like many other theoretical papers in the field.\n\nI thus keep my recommendation for acceptance of this paper.", "rebuttal": "Thank you for your detailed and positive feedback. We greatly appreciate your recognition of our **very nice results**—with matching upper and lower bounds—as well as your appreciation of the **insightful discussion** and the paper’s **clear structure**, **strong motivation**, and **well-organized presentation of the main results and their proofs**. Below, we address your specific suggestions and questions:\n\n\n**\"...issue on readability...For readers that are unfamiliar with parallel sampling...pose a challenge...\"**\n\nThank you for your thoughtful feedback and for highlighting the importance of improving the readability of the algorithm section. We agree that the parallel Picard method, as introduced in [ZS24], may not yet be familiar to all readers in the sampling community. \n\nTo improve clarity, we will revise Section 3.1 to include a more detailed explanation of the algorithm's intuition, motivation, and structure. Specifically, we will enhance the explanation of Algorithm 1 by providing more intuition behind its design, clarifying the purpose of each line in the pseudocode, and including an illustrative example of the update step to address potential confusion.\nAdditionally we will add a section in Appendix to review existing parallel methods for sampling and diffusion models.\n\nFor your specific questions, we address as below:\n\n- Q1: What's the purpose of $J$ and $N$?\nA1: The variable $j$ indexes the number of Picard updates applied to each time slice, and $J$ is the total number of such updates required to ensure convergence along the Picard direction. The parameter $N$ denotes the number of time slices used to discretize the time direction. \n\n- Q2: Why we need to split the same update rule (lines 11 & 15 in Alg. 1) into two parts with different indices? \nA2: Our algorithm follows a diagonal-style update pattern. The first loop corresponds to updating the upper-left rectangles in Figure 1, while the second loop handles the remaining rectangles. While it is possible to merge both loops into a single unified loop, we chose to separate them for clarity and to better illustrate the structure of the computation graph.\n\n- Q3: How does it improve upon [ACV24]? A more interesting question to think about is that, if one applies the averaged LMC into the algorithm in [ACV24], how would the complexity bound be compared with Thm. 3.1?\nA3: The key distinction between [ZS24] and [ACV24] is that [ACV24] updates time slices sequentially, whereas [ZS24] performs parallel updates across time slices. As a result, [ZS24] achieves a better complexity of $O(\\log d)$ compared to the $O(\\log^2 d)$ bound in [ACV24] for the strongly log-concave case. Our paper builds on the parallel framework of [ZS24], leading to an adaptive complexity of\n$$\nO\\left(\\frac{L K_0}{\\varepsilon^2} + \\log\\left(\\frac{L d}{\\varepsilon^2}\\right)\\right).\n$$ In contrast, applying the sequential scheme of [ACV24] to our setting would result in a total adaptive complexity of\n$$\nN \\cdot \\log\\left(\\frac{L d}{\\varepsilon^2}\\right) = O\\left(\\frac{L K_0}{\\varepsilon^2} \\cdot \\log\\left(\\frac{L d}{\\varepsilon^2}\\right)\\right),\n$$\nwhich is strictly worse by a logarithmic factor. We also note that we will add a discussion about the trade-off between the adaptive complexity and space complexity as pointed out by Reviewer 5zmn. Specifically, we assume in each iteration that we update at most $W > 0$ points in parallel. When $W = 1$, this recovers the sequential method; when $W = \\frac{d^2}{\\varepsilon^4}$ (assuming $K_0 = O(d)$), it recovers our fully parallel method.\n\nUnder this framework, we obtain the following tradeoff: the space complexity is $Wd$, and the adaptive complexity becomes$O\\left(\\frac{d}{\\varepsilon^2} + \\frac{d^2}{\\varepsilon^4 W} \\log \\frac{d}{\\varepsilon^2}\\right),$\nwhere we define the space complexity in terms of word usage rather than bit count.\n\nWe will incorporate the discussion related to Q1 and Q2 into Section 3.1 to clarify the algorithm’s indexing structure and update pattern. Additionally, we will add Remark 3.4 below Theorem 3.1 to address Q3, highlighting the comparison with [ACV24] and the advantage of our complexity bound.\n\n**\"We may not need such a formal definition of the adaptive algorithms...\"**\n\nThank you for the suggestion. We agree that the formal definition in Section 2.1 may be more detailed than necessary for the main text. In the revision, we will move the formalism to the appendix and revise the statement of Theorem 4.1 accordingly to streamline the presentation.\n\n**\"In line 3 of Alg. 1, this is not the correct way to initialize a trajectory of Brownian motion...\"**\n\nWe thank the reviewer for pointing this out. We will revise the initialization step to ensure that the Brownian motion is properly constructed as a cumulative sum of independent $\\mathcal{N}(0, (mh/M)I)$ increments.\n\n**\"...$x_{n,m}$ corresponds to time $nh + \\frac{m}{M}h$, I hope the authors could mention this in the text for easier understanding....\"**\n\nWe agree with the reviewer’s interpretation: $x_{n,m}$ corresponds to time $nh + \\frac{m}{M}h$. We will clarify this in the text for better readability in Section 3.\n\n\n**Regarding minor comments**\n\nThank you for pointing out these issues. We will carefully revise the manuscript to correct all minor errors and improve the clarity, consistency, and presentation throughout."}]

Author rebuttal:

Meta-review: The authors consider the adaptive complexity of parallel sampling from non-log-concave distributions in relative Fisher information (a standard measure for this problem, similar to finding approximate stationary points in non-convex optimization). Using Picard iteration, they show improvement over sequential algorithms; they also prove a lower bound in a certain regime where parallelism does not improve.

This is a nice theoretical result with a new algorithm, and offers some insights of contrasts with parallel non-convex optimization. Reviewers found that the theoretical clarifications answered their questions. The one negative review (5zmn) cited that the lower bound was only for specific epsilon and the lack of experiments. Authors noted that in the parallel setting a more general lower bound requires new techniques, and conducted a 2-D experiment. Other reviewers agreed on the difficulty of proving lower bounds in general. The results seem adequate for a theory paper.

I remind the authors to incorporate the presentation of the algorithm and proof, as requested by reviewers.
Decision: Accept (poster)