Computational Bottlenecks for Denoising Diffusions
Authors: Viet Vu
Andrea Montanari
Venue: ICLR 2026 Poster (2026)
Keywords: denoising diffusions
computational bottlenecks
information-computation gap
spiked Wigner model
score matching
Primary area: learning theory
TL;DR: We investigate failure of sampling in diffusions for high-dimensional distributions with an information-computation gap.

Abstract: Denoising diffusions sample from a probability distribution $\mu$ in $\mathbb{R}^d$ by constructing a stochastic process $(\hat{\mathbf{x}}_t:t\ge 0)$ in $\mathbb{R}^d$ such that  $\hat{\mathbf{x}}_0$ is easy to sample, but the distribution of $\hat{\mathbf{x}}_T$ at large $T$ approximates $\mu$. The drift $\mathbf{m}:\mathbb{R}^{d}\times\mathbb{R}\to\mathbb{R}^d$ of this diffusion process is learned by minimizing a score-matching objective. 

Is every probability distribution $\mu$, for which sampling is tractable, also amenable to sampling via diffusions? We address this question by studying its relation to information-computation gaps in statistical estimation. Earlier work in this area constructs broad families of distributions $\mu$ for which sampling is easy, but approximating the drift $\mathbf{m}(\mathbf{y},t)$ is conjectured to be intractable, and provides rigorous evidence for intractability.

We prove that this implies a failure of sampling via diffusions. First, there exist drifts whose score matching objective is superpolynomially close to the optimum value (among polynomial time drifts) and yet yield samples with distribution that is very far from the target one. Second, any polynomial-time drift that is also Lipschitz continuous results in equally incorrect sampling.

We instantiate our results on the toy problem of sampling a sparse low-rank matrix, and further demonstrate empirically the failure of diffusion-based sampling. Our work implies that caution should be used in adopting diffusion sampling when other approaches are available.

Published as a conference paper at ICLR 2026
COMPUTATIONAL BOTTLENECKS FOR DENOISING DIFFUSIONS
Andrea Montanari & Viet Vu
Department of Statistics, Stanford University Stanford, CA 94305, USA (montanar, vietvu01) (artuuu00ssssttttt @stanford.edu
ABSTRACT
Denoising diffusions sample from a probability distribution ş in IR by construct-
ing stochastic process (æt t 2 0) in I& such that žy is easy to sample, but the distribution of ær at large T approximates μ.. The drift m Rd x R + Rd of this diffusion process is learned by minimizing score-matching objective.
Is every probability distribution μr, for which sampling is tractable, also amenable to sampling via diffusions? We address this question by studying its relation to coormation-compuattinn
gaps statistical estimation. Earlier work in this area constructs broad families of distributions, for which sampling is easy, but approx- imating the drift m 1) is conjectured be intractable, and provides rigorous evidence for intractability.
We prove that this implies a failure of sampling via diffusions. First, there exist drifts whose score matching objective is superpolynomially close to the optimum value among polynomial time drifts and yet produce samples with distribution that is very far from the target μr. Second, any polynomial-time drift that is also Lipschitz continuous results in equally incorrect sampling.
We instantiate our results on the toy problem of sampling sparse low-rank matrix, and further demonstrate empirically the failure of diffusion-basee sampling. Our work implies that caution should be used adopting diffusion sampling when other approaches available.
INTRODUCTION
1.1 BACKGROUND
Diffusion sampling (DS) (Song & Ermon, 2019; Ho et al., 2020) has emerged as central paradigm in generative artificial intelligence (AI). Given target distribution j on Fd we want to sample
~ μ.. Diffusions achieve this goal by generating trajectories of stochastic process (œ;) whose state T. at large approximately distributed according to j.. This suggests a natural question:
Q: Are there distributions for which sampling via diffusions fails even if sampling from is easy?
In order to explain how DS might fail, it is useful to recall the setup and introduce some nota- tions'. The basic DS approach implements approximation of the following stochastic differential equation (SDE), with initialization yo O:
dy: m f) + dBi.
(1)
myy () = [xx to Vig y)
where (Bt) is Brownian motion (BM) and in Eq. (2) x ~ μ is independent of g ~ N(O, It).
It is not hard show that, if yt is generated according to the above SDE, then there exists x ~ μ and an independent standard BM (W.)220 (different from (Bt)20) such that
yt = f. + W.
(3)
We follow the formulation of Montanari (2023), which does require time reversal (c.f. Appendix B)

---

Published as a conference paper at ICLR 2026
Therefore, running the diffusion (1) until some large time T, and returning yr yr/T m T) yields a sample approximately distributed according to μ..
In practice, the function m is generally not accessible (cf. discussion below (6)), and is replaced by an approximation m t). We can implement an Euler discretization of the SDE (I):
Dita Dr in 1) V
(4)
with A small stepsize, and (λ)) Mii N(O, Ia). After iterating (4) up to a large time T, we output बτ - ri mūrr We refer to Ør as a difsusion sample.
Diffusions reduce the problem of sampling from distribution y to that of approximating the conditional expectation m (Eq. (2)) by m. The mapping y + my t) is the Bayes-optimal
estimator of x in Gaussian noise:
m(.,t) arg min ((1(p(y))- -x1 x=²}.
(5)
co: -2
In words, we are given a Gaussian observation y: ~ N(tx, tIa) (for a single t) and want to estimate as to minimize mean square error (MSE). This is also known as the "score-matching objective'.
The minimization in Eq. (5) has to be modified for two reasons: First, in general we do not know the distribution of æ over which the expectation in (5) is taken; we only have sample (æ,)ign ad p. We thus replace the MSE by its sample version:
minimize
((B..)) -x;|l 2:11? subj. to P N
(6)
where yi. = Lae, + Vlg, for (g.)isn Wid N(O, La). The minimization in (5) must be restricted to function class N (e.g. neural nets). A (near)-optimal solution to (6) will be m..
Second, to efficiently implement the generative process (4), mn should be computable in poly- nomial time. For this reason, N must be a set of such functions. This is a purely computational constraint, and is present even if we have access to j (i.c., for N = oo).
Most of the literature on diffusion sampling studies how samples quality deteriorates because of finite sample size N or non-vannen non-vanishing step size A. Here we focus on a more fundamental limitation that arises because m must be computable in polynomial time (the second remark above).
A key remark here is that the ideal drift m t) is the Bayes-optimal denoiser, see (5). Namely it is the optimal function estimate æ with prior distribution μu from noisy observations Ye ratio (SNR) of this denoising problem. We will
N(ta, tIa): t can be interpreted as the signal-to-note say that an information-cone coomuution-comppuatiion gap arises for this problem (at SNR there exists a constant gap(t) > 0 such that, for all polynomial-time algorithms vn, if d is large enough
((Il( xm13} 2 inf E (11()()))) - =+ + gap(t).
Recent literature provides many instances of statistical estimation problems for which an information-compuaate gap is shown to exist (Brennan et al., 2018; Bandeira et al., 2022; Ce- lentano & Montanari, 2022; Schramm Wein, 2022) conditional on certain widely accepted con- jectures. We stress that the conditiionll/onjectura nature of these results is, so far, unavoidable, situation analogous to classical complexity theory that relies on PANNP. Several of the problems for which a gap arises take the form of estimating æ ~ y from observations y: fx + vig.
Koehler & Vuong (2024) already pointed out informally that denoising problems presenting an infornation-computtion gap can result into a failure of DS. a concrete example, they suggested the spiked Wigner model (c.f. next section). While this informal remark is natural, making it math- ematically precise is far from obvious. In fact -strictly speaking- the remark is false. If sampling from a is easy, then the drift m f) can be constructed to return (for all 2 to) fixed random sample x ~ μ.. Then the diffusion will sample correctly. However such m will be very far from an optimal denoiser. (See Proposition 2.1 for formal version of this counter examle.)
We also note that several earlier papers provided examples of probability distributions μ from physics and Bayesian statistics for which Gibbs sampling is expected to succeed, but DS appears
2

---

Published as a conference paper at ICLR 2026
to fail (Montanari al., 2007; 2024). None of these papers presented a formal claim either.
& Semerjian, 2009; Ghio et al., 2024; Huang et al.,
The present paper fills this gap in the literature. We prove two general results that hold for any distribution j that presents a certain version of information cooemaatoo-commutationn gap (see formal statements below). First, prove that there exists drifts that are approximate optimizers of the score matching objective (6) among polynomial time algorithms (up to an sub-polynomially small error) and yet lead to completely incorrect sampling. Second, we show that every polynomial-time computable drift that is a near optimum of score matching and is also Lipschitz continuous leads to incorrect sampling. Finally, we ilustrate the applicability of our theorems by studying a toy example, namely sampling a sparse low-rank matrix.
We emphasize that this failure of DS is of computational of nature and purely related to the requirement to approximate the Bayes optimal denoiser m( t) by polytime computable function.
1.2
SUMMARY OF RESULTS
Recall that the Wasserstein-1 distance between two measures ML, H2 on Rd is defined as
/ ||||| 22112 (dæ)), (d2),,
Wi (a), inf vEC(aL
with the infimum taken over couplings on μl and μ22 Given random vectors X1, X2 we denote by X2) the Wi-distance of their distributions. We prove lower bounds on the W1 show incorrect sampling. Since we only consider distributions, μ supported on vectors with bounded norm, a lower bound on W1 implies lower bounds on TV distance and KL divergence. Hence our impossibility results are stated in strong form.
As a running examplerapplication, we will let μ to be the following distribution over n X n sparse low-rank matrices. Let Ba.. ;= {u E =1V [| = k} be the set of 0/ + (1/VR) unit vectors with & nonzero entries (|/w]]o denotes the number of nonzeros in u). We define the target distribution μ = Mn, to be the distribution of x uu when u ~ Unif( x..)) Note that æ E Rax= is a matrix that we identify with a vector in Rd for d = n². Sampling from μ is trivial: just sample a vector with entries in {0, 1/VE, 1/V/ and exactly non-zero entries, and let uu However, rigorous evidence supports the claim that for certain scalings of k, t with n- wowppoomill-iiiiiiiiioo algorithms cannot approach the Bayes-optimal error (Butucea et al., 2015; Ma & Wu, 2015; Cai al., 2017; Brennan et al., 2018: Schramm & Wein, 2022).
We will prove two sets of main results that hold for distributions such that the denoising problem presents an information-coomputtii gap:
1. (Theorem 1, Corollaries 3.2, D.1) Near optimizers of score-matching can sample incorrectly. We prove that there exists m _R x IR- + g=xx such that:
M1. mi )) can be evaluated in polynomial time.
M2. The estimation eтror achieved by mn (namely, Ell t) x0|²)) is close to the optimal estimation error achieved by polynomial-time algorithms. Hence m will be near min- imizer of the mote-matching objective (5) (integrated over t).
M3. Samples ेा generated by the discretized diffusions (4) with drift m tt) at some large time
T have distribution that is very far from the target ya ('as far as it can be' in W, distance.)
2. (Theorem 3, Corollary 5.1) All (sufficiently) Lipschitz score-matee matchin optimizers sample incor- rectly. More precisely, we prove that any denoiser that near optimizes the score matching among polytime algorithms, acts optimally on pure noise data, and is C/I-Lipschitz for 41 (for any constant C' a suitable 41), samples incorrectly.
Additionally, (Theorems 2,5 5), we prove a reduction from estimation DS. Namely, if accurate, polytime DS is possible, then near Bayes optimal estimation of x from ye fx vtg must also be possible in polynomial time for all t. The contrapositive of this statement implies that if an information-computttioo gap exists, then (near)-correct DS is impossible in polynomial time.
Roadmap. The rest of the paper is as follows. In Section we motivate our setting and assumptions, and discuss some limitations of our results. In Section 3 state formally our results (for technical
3

---

Published as a conference paper at ICLR 2026
reasons state two separate results depending the growth of & with n.) Section 4 presents the general reduction from estimation to diffusion sampling. Section 5 proves that all Lipschitz score matching optimizers fail. Section 6 provides numerical experiment of neural network m that outperforms (conjectured) asymptotically optimal denoisers for finite n, yet still samples poorly.
Notation, Throughout, On < b, means a,/bu, - O. We refer to Appendix A for notations.
DISCUSSION
Setting. Our results indicate that standard application of denoising diffusions methodology will fail to sample from μ when the associated denoising problem presents gap. The example fn,k of sparse low-rank matrices shows that DS can fail in cases in which sam- pling from μ is trivial.
Our example also shows that the latent structure of the distribution can be exploited to construct better algorithm. Namely, one use diffusions to sample Unif(Bn,e) (the posterior expec- tation myy 1) is polytine-computable) and then generate such latent structures from data can be hard general, both statistically and computationally.
uu _ On the other hand, identifying
Limitations. We prove that there exists drifts m(. .t) that lead to poor sampling, despite being nearly optimal (among poly-time algorithms) in terms of the score matching objective (5). In par- ticular, these bad drifts will be near optimal solutions of the problem of (6), long as . only contains polytime methods and is rich enough to approximate them. We further exclude the exis- tence of Lipschitz drifts rí () that also satisfy conditions M1 and M2 but yield good generative sampling.
In principle there could still be non-Lipschitz polytime drifts that optimizers and sample well. However if such drifts exist, our results suggest that minimizing the score matching objective is not the right approach to find them (since the difference value with bad drifts will be superpolynomially small).
score matching
Correct samplers violating M2. If we drop condition M2, i.e. we accept drifts that bad for the score-matching objective, then it is possible to construct drifts that can be evaluated in polynomial time and yield good sampling. This is stated formally below and proven in Appendix J.
Proposition 2.1. Suppose that discretized SDE (gEa JEZO per (4) is generated, with step size A and noise stream 2, i.i.d. N(O, Inxn). Then for every n,k, there exists func- tion mn(y.)) = vnly (yy 1; $1) paramelrized by 21 (with no additional randomness) such that: 0 (sub-optimal score- matehnatching): (i)) (m x) = 0 for all 2 O (m((r,t) t) is an approximate sample of x); (ÿe/t is an approximate sample of x at large time).
(i) ([l.
(y., == 2(1 o(1)) uniformly for every
(iit) Timg-roc Wi
The drift constructed in this proposition has very poor value of the score-matching objective.
Further related work. A number of groups proved positive results on diffusion sampling. Alaoui al. (2022); Chen et al. (2023b); Montanari & Wu (2023); Lee al. (2023); Benton al. (2023) provide reductions from diffusion sampling to score estimation. Chen et al. (2023a); Shah et al. (2023); Mei & Wu (2025): Li al. (2024) give end-to-end guarantees for classes of distributions μ..
The computational bottleneck that we study here has been observed before in the context of cer- tain Gibbs measures and Bayes posterior distributions Ghio et al. (2024); Alaoui et al. (2023); Huang et al. (2024), and random constraint satisfaction problems Montanari et al. (2007); Ricci- Tici--Terssnghi & Semerjian (2009) (the later papers use sequential sampling rather than diffusion sampling).
Our work provides an approach to rigorize the latter line of work.
3 NEAR-OPTIMAL POLYTIME DRIFTS WITH INCORRECT DIFFUSION SAMPLING
Given an arbitrary polytime computable drift my. we will construct different polytime drift m, with nearly equal score matching objective and yet incorrect sampling. In Subsection 3.1, we state
4

---

Published as a conference paper at ICLR 2026
assumptions and general result. In Subsection 3.2, we apply the general theorem to the example of sampling sparse low-rank matrices. We also indicate several other similar examples.
In what follows (æ, 3/)) will always be distributed according to the ideal diffusion process of (3), which also satisfies (2). In particular a ~ p. 3/: = tæ + Wt, for (Wi)e20 a BMM On the other hand, (it) will denote the process generated with the implemented procedure (4).
3.1 GENERAL RESULT
Throughout, we will consider distributions μ that are supported on (1) == f R | S 1}. We will state our assumptions and results having in mind the case of measures that are roughly centered:
f p(dz) = O, although this condition is not formally needed.
Our first main assumption is that any polynomial-ting timme algorithm to estimate from Yr ~ N(ta, tLa) fails when t below a certain threshold tal. When t/tag 1. we expect that polytime algorithms will not perform better (in score-matching. c.f. (5)) than the best constant estimator of a, namely [x) In the case [[Eea--paa))) Rs O, follows that polytime algorithms mgg with good score-matching will have small norm (1:,, t).. This small-norm property is captured by our assumption. More details are discussed at the beginning of Subsection 3.2.1, and Proposition C.I.
Assumption (Small norm below threshold). Let yt = tæ + for (x, (We)sa)) ~ f 8 BM. Then, there exists function mn N + R (which we refer to 'rate") ") such that (d) oa(1) and, for any E, Y > 0,
P(I t)ll 2 2)) = (()(d))
Our second assumption is that polytime detection is reliable for & above lug. By detection, consider the following hypothesis testing problem. Given y Rd,, we test if y is distributed as tæ + VEN Ia) or N(a, tIa) for ||a]] small, where might depend on the Gaussian noise.
Assumption 2 (Hypothesis testing succeeds above threshold). For E (0, 1), define Aale) {a E Rd |a| < c- We assume there exists 6, 172 : N + R (which we refer to as rates), and a polytime binary test function Φ IRd x Rz0 + {0, 1} such that:
1. (Sharp detection threshold) o(d) (1).
2. For the process (y: = tæ + Wt). & rejects with high probability
P()(y,,)) = 0)dt (()(d))
(1+0)
3. Uniformly over the set Aa(c), & fails to reject with high probability. Namely:
P 3t (1 5) such that sup a(a + W.) =1 =o()). AEAa(c)
Remark. Since try to state our theorem in the strongest form, Assumptions and 2 do not take the same form as the information commuiioonncmmutaiiion gap (7). Nevertheless, it can be proven that (for a broad class of problems) these assumptions cannot hold unless an information-computatie gap is present. We leave this point for future work.
Discussion of the assumptions. Before stating our main results, we address the validity of the assumptions.
Assumption is expected to hold for 'reasonable' polytime computable drifts in distribu- tions f with an information-coe computiionnommtttiiionn gap (c.f. Subsection 3.2.1 and Proposition B. More precisely, in such problems no polytime computable estimator mo(3) t) achieves correlation with the target æ bounded away from zero, and therefore its loss is decreased by shrinking it to near zero.
5

---

Published as a conference paper at ICLR 2026
Assumption 2 concerns the existence of certain efficient hypothesis test o. We can lever- age the literature on information comppaattiinoottatttiinn gaps to determine the (conjectured) opti- mal efficient algorithm m (3. t), and construct e to test for large values of (y t), y)- Specifically, ply. 1) = 1 fr. 2/,,t for some c E (0. 1). The rationale as follows: the maximum likelihood problem for the model y/: tæ B, is find ø maximize (ě, y). For t above the algorithmic threshold, efficient estimators in yy, t) can approxi- mate the (inefficient) MLE very well for the alternative model yt. leading large values of (r t), Mt) = (x. ya) (in particular, it is t ot))) Note that the MLE is in turn very close the true signal æ in this regime.
The worst-case Type I error guarantees can be checked directly with this o. and Condi- tion 3 holds for the examples observation to show this: for the null model a + B₁, we have
listed in Subsection 3.2.2. Below, employ simple
(m + Br,t), Bi) S sup (a', + B.) ||a|lop .'Esupp()))
sup (e', B:)
a' e'Expp(()
where supp(u) is the support of μ. For distributions with an information informatoonccomputationn gap, x' is often "structured" vector (c.f. sparsity and examples in points (i) and (ii) of Subsection 3.2.2); as pure noise B, does not favor any structure, we have
sup (a' B:) < t = (a. B,, B,) S clay + o(t) x'' ('upp((())
for of Condition 3. Choosing c, c, have succeeded in constructing ø.
We state our first main result. It stipulates that we can construct a polytime algorithm which has "essentially" the same score-matching objective my yet yields bad samples.
Theorem 1. Let J be a probubility measure supported Assume that there exist lagg = Lag(d)
B²(1) such that
lim d-fd- I || p(dx) = =a mo IRd x IR + IR, and functions mi (d), 8(d), (2()) = oa(1), such that following conditions hold: (i) supy, [y f)ll < 1. (ii) Assumption I holds with rate mn (d). (iti) Assumption 2 holds with
drift
rates 8(d).
Then there exists a modified drift in such that M1. m( .) can be evaluated in polynomial time.
M2. If y: = lax + Be is the true diffusion (equivalently given by (7)), then
B Blli, t) (mo((i.)))l?]dd = ((n v mz()).
M3. For any step size A An > O, we have incorrect sampling:
inf (2
Wi(fi(D,,)) 2 a - oa()).
(8)
The proof is presented in Appendix G. The main idea is to let my 1) be mn ()1 ma(y.)))
for & (1 - aag. and m (y, t) t) for t Z (1 + tug. with small constants (7,s) and test Φ.
Remark. makes sense to assume that []ma((,)]] S 1. Since supp(n) S (1) and the latter is convex set, projecting any my onto this set yields a smaller MSE.
3.2 EXAMPLE: SAMPLING LOW-RANK MATRICES
We state two separate results for the probability distribution μ = Pn.. described in the introduction, depending on the scaling of l with in Section 3.2. 1 assume /ni < k n; while in Appendix D we assume k < Vn. Indeed, the nature of the problem changes at the threshold k x vn..
A crucial role will be played by the following threshold
22
log
12 Kz
i vπ
Lale (n,, k) =
(9)
<

---

Published as a conference paper at ICLR 2026
It is expected that for < (1 (n, k) and 8 any fixed constant, no polytime algorithm can estimate x significantly better than the estimator mull = E[æ] se for k < n (see Conjecture 3.1).
Since | 1 for μe, the Bayes denoiser m t) my does not depend on t (this can be seen by Bayes rule). From now on, we refer to x = az|| |- as the Frobenius norm.
3.2. MODERATELY SPARSE REGIME: vn & Ck
Assumption I states that, for y: = tæ + W,, the estimated drift (y::)) should have small norm with high probability. This condition holds under the well-accepted Conjecture 3.1 below on information-computation gaps. fact, a simple consequence of this conjecture is that any polytime in matching this enror must satisfy m yr, t)]13)
(1) (see Proposition C.I).
Conjecture 3.1. For vn & k & n, there exists K & such that the following holds for any my RRux n x + Ruxn be any sequence of polytime
kns with kn S lin & n. Let algorithms (polynomial time in n). Then for any ō > 0, we have
inf (S(1-5)aug
IB (1 (yr, - m=1²) 2 1 on (1).
(10)
We refer to Ma & Wu (2015); Cai et al. (2017); Hopkins et al. (2017); Brennan et al. (2018); Schramm & Wein (2022); Kunisky et al. (2019) for evidence towards this conjecture. Next, we provide the following implication of Theorem 1, whose proof is in Appendix H.
Corollary 3.2. Assume vn & k < n. so that tug (n, k) == n/2 per (9). Let m. be an arbitrary poly-time ulgorithm such that supy, [| ()]l S and Assumption holds with rate ip such that 7i < n <n-DvD > O. Then there exists an estimator in such that:
M1. m(.) can be evaluated in polynomial time.
M2. !f y/ = tx + -B is the true diffusion (equivalently given by (1)), then, for every > 0,
E muy,, mo(y.. O(n
M3. There exists 8 (1) such that, for any step size A A, >> 0, we have incorrect sampling:
inf Wi(m t),x) x)) 2 - (1). IEN- (EN-112(1
(11)
To connect the last corollary with the introduction, we recall two facts from the literature on submatrix estimation: (i) The Bayes estimator m achieves small MSE in large interval above tug (Proposition 3.3); (ii) No polytime estimator is expected to perform better than the null estimator below tas (Conjecture 3.1). Regarding (i), we state a characterization of the Bayes optimal error. The proof is analogous to the main result Butucea et al. (2015), which considers the case of asymmetric matrices. (For k < nt < 5/6, see also Barbier et al. (2020).)
Proposition 3.3 (Modification of Butucea et al. (2015)). Let m(y) be the posterior mean estimator in Eq. (2). Assume 1 l < n, and define taayes (n, k) == 2h (n/))) Then, for any 8 > we have (1- m x [| 1 on (1), suP:2 ((Ilm(y))) x||2] = o, (1).
In other words, for 2k log(n/ k) < < the optimal estimator can estimate the signal accurately, but we expect that no polytime algorithm can achieve the same.
3.2.2 VERY SPARSE REGIME: & VR, AND OTHER EXAMPLES
In the very sparse regime
< Vn, we prove a result similar Corollary 3.2 (Corollary D.
Other examples. We mention few examples where it is relatively straightforward to apply The- orem 1, following the blueprint in Corollary 3.2. (i) Sampling low rank tensors, e.g. I = 00 e (R7)88_ 2 3 when u ~ Unif([+1/ Vn, - -1/vm)") or is uniform the unit sphere; the corresponding denoising problem is known as tensor PCA (Montanari & Richard, 2014) (in this
case d = nº). (ii) Sampling elements of random linear subspaces of (0, 13:
Gu mod 2,

---

Published as a conference paper at ICLR 2026
where G E {0, 10,1 is fixed (known) uniformly random matrix and u Unif (0. 1)) ==
for r E (0, 1) constant; the corresponding denoising problem amounts to decoding random lin- codes (Richardson & Urbanke, 2008; Ghazi & Lee, 2017) (this example fits our framework after centering). We give two classes of examples for which applying Theorem requires additional tech- nical work (defer future publications): (dii) Sampling from Bayesian posteriors, e.g. posterior of a low-rank plus noise estimation problem that presents an anformation-computatinn gap (Lelarge & Miolane, 2017; Montanari Wu, 2023; Ghio et al., 2024); (iv) Sampling solutions of random constraint satisfaction problems (Montanari et al., 2007; Ghio et al., 2024).
REDUCTION OF ESTIMATION TO DIFFUSION-BASED SAMPLING
To complement previous results, we prove a general reduction: if diffusion sampling can be per- formed in polynomial time with sufficient accuracy, then we can perform also denoising. The con- trapositive of this statement aligns with results in previous sections.
To avoid unessential complications, in this section we assume μ to be supported on the unit sphere gd-1 = {x || = 1}. We denote by P the law of (Br where ye given by Eq. (1) and by p the law of (Ü.)OSeTT which is the discretized diffusion trajectory defined in (4) (interpolated linearly outside N. A).
It is further useful to define TT. to be the law of the SDE interpolating that of (4):
dø: = m iū (( dt + ddB,,
(12)
where [t]a == max(s N. s t}.
Theorem 2. Assume that mn..) )) has complexity x and that for any T
sddd, Ad, DEL (PT S
Then for any 0 there exists algorithm randomized algorithm m4 with complexity (Nx T/A) that approximates the posterior expectation:
[l (y) -m 12] 2
(13)
Here -2= (0) and (0) := EPI m/y N(O, (Od)-'La) Palully is the expected TV distance between Par Paly and the convolution of P
The proof of this result is presented in Appendix T. along with a modification.
ALL LIPSCHITZ POLYTIME ALGORITTMS FAIL
In Section 3 (Theorem and Corollary 3.2) we proved that there exist near-optimizers of the score matching objective that perform poorly. However, we did not rule out the possibility that the optimal (in the sense of score-matching) polytime drift in will perform well. We next show that this is not the case, under an additional assumption, namely that the drift m Lipschitz continuous for t 2 (1 +1++0 8)ga Proof is given in Appendix W. (We assume the Lipschitz constant to be C/t,, because the input of the denoiser y: = + W,, and hence the two I-dependent factors cancel.)
Theorem 3. Let f be supported on (1) = {a || S 1}, ʃ p(dx)) = O, and lim inf [[=]]a(dæ) = a > O. Let in R2d x R20 - Rd be a polytime denoiser such that sup,, [ t)ll < 1 (below W, is standard BM);
m is nearly optimal, namely for yt = tx + W., and every > 0
sup (5(1-))(a
B(lmm((..)) 12 ||[|~| o(t,TT')
(14)
sup (2(+)))aa
B(llm((y)))) m0||3] =
(15)
and that for every 2 0, c [-1,1], Elllm(, 1]| B(llem(y:))) =x|1]] + o(1
8

---

Published as a conference paper at ICLR 2026
2. (m is small pure noise.) For some d o(1), and every A O(1), we have
E
Blllm(WW, o(1)
CEN-A Valg (1+
3. ml(-.) is C/t--ipschitz for some constant C and all 2 (1+ +1+ 8)
Then, for every constant Co 0 and step size A = O(1):
inf (o,
Wi Wi t), x)) 2 o(1)
Remark. The sum in Condition of Theorem is a discretized integral; when small enough, this is essentially equivalent stating that
(W,, o(1)
(1+6)
For applications of this theorem (c.f. Corollary 5.1, we have an upper bound B[l]m)(, t)]l s (t) with en (t) decreasing (for & 2 fay + 8)), so that for every A,
Σ
(B, t)11 S A Ga (1 + 5))
(t)ddt on(()
(27(1+6)
(1+t)))))))
so that the specific value of A does not matter, as long A = 0(1.
We apply the above theorem to our running example of sampling sparse low-rank matrices. In order to make sure that condition 2 in the theorem is verified, we introduce variant Pn, of Mn.* (all conclusions stated for μa, c.g., Theorem Corollaries 3.2, D.1 hold for Fn,* well.) Letting yo. be the centered version of poak: we define V,, = 50 + Pa, In words, with probability 1/2 we 2
let æ = 0 and with probability 1/2 we draw æ = 5 - [[[=], ã pn,ks a sparse rank-one matrix, as in previous sections. As mentioned, this mixture distribution Pn,k mainly to satisfy condition 2 of Theorem 3. Indeed, we have the following decomposition
Egg ( t) x=|
Fe 2 (1 t) 201 E m W., t)11?)
2
which shows that, to get m t) = a under the mixture distribution, we also need m (W,t) t) ~ 0. More concretely, we can get explicit rates on B[]l[WW [)] for above laig by enforcing that mn. cannot be improved by multiplying by certain hypothesis tests. The full result is as follows.
Corollary 5.1. Assume kn exists as in Conjecture 3.1. Let k- = kn be such that kn V Vn S kn < (moderately sparse regime). Let my be a polytime denoiser such that for some ö on(1), and every fixed constant > 0:
ma is nearly optimal, namely (for ye = tæ + W. We standard BM)
sup (1(1)))
E(liin(yte,) () - x 21 - B[[|=|]]] = (1))
(16)
sup
E Elllmiu t) - = o., (1),
(17)
(2(1))
and further, for any 2 (1+ + 8)t the MSE of mn smaller or equal than the MSE of (()i())) for any polytime function c(-) of the maximum eigenvalue of (y: +
y 1 22, and than the MSE of Pam for Pg the projection onto the unit ball.
2. f,,(-.t) gaxx paxn is C/t-CCistchiie for some constant C and all 2 (1 + 8)tag
Then, for every constant Co > O, and step size A = =(():
1
inf ceN-Anfo.Com)
(i(mn(yr (), z - on.
(18)
2

---

Published as a conference paper at ICLR 2026
350
Dutfacinn
Spedtrll Alporshm
Projection
0.-
250-
transttann cated
0.3
XS5
100
0.1
08
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
0.006
0.000
0.00.
0.012
time 2.
Figure 1: Generating sparse rank-one matrices x ~ Aa,k using denoising diffusions, for ni 350, k 20. Left: MSE of various denoisers (vertical line corresponds to the algorithmic threshold tate.) Right: Frobenius norms of generated samples.
The proof is given in Appendix X. We note that the error of polytime denoisers in (16) (and sampling error of Eq. 18) is 1/2 instead of 1 because the best constant denoiser achieves error 1/2.
Corollary 5.1 does rule out the possibility that there exists near-optimizer of score match- ing that violates the Lipschitz condition and samples well. However, for 2 (1 + 8)t accurate estimation is possible with Lipschitz algorithms, and indeed many natural methods are this class (e.g. neural nets with bounded number of layers and suitable operator norm bounds on the weights.)
6 NUMERICAL ILLUSTRATION
The theory developed in the previous section yields concrete prediction of the failure mode of DS when applied to the distribution Jin.k (1/2)6o + (1/2)μn.ı (with (n, the law of x uu! Un.,(B..x)) Namely (for large n. and / < k < n)::
Given sufficient model complexity and training samples, we expect the learnt denoiser m. (1, to achieve MSE close to 1/2 for t < (1 8)g and close to 0 for t (1 + d
We expect DS based on such a denoiser to generate samples concentrated around 0.
We tested these predictions in numerical experiment. We considered three polytime denoisers:
(a) The spectral-plus peeetallppuss-proecctoon denoiser of Algorithm 2:
(b) A modification of the latter whereby the eigenvector calculation replaced by 25 iterations
of power method;
(c) A learned graph neural network (GNN) (Scarselli et al., 2008; Kipf Welling, 2016).
We carry out experiments with denoiser (b) because é iterations of power method can be approxi- mated by an f-layers GNN. Hence, method (b) provides a baseline for GNN denoisers.
Figure 1, left frame, reports the MSE achieved by the three denoisers (a). (b). (c) as a function 20. As GNNs are coamutatioo-eqqivartti
of t/n, for n 350, all possible outcomes, for n 350 and k = 20. We observe that the GNN denoiser outperforms both the spectral algorithm and its approximation via power iteration. However, none of the three approaches can overcome the barrier at taee n/2, while they perform reasonably well above that threshold. This confirms the prediction at point 1 above.
we are training on z 3% of
On the right, we plot the histogram of Frobenius norms of samples generated with the GNN denoiser. These values are close to O, which confirms the prediction at point above. By using ||e 1-Lipschitz test function, obtain that the Wasserstein distance between diffusion samples and the target distribution at least 0.48 (the asymptotic prediction from theory is 0.50).
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Ahmed EI Alaoui, Andrea Montanari, and Mark Sellke. Sampling from the sherington-kirkpatrice gibbs measure via algorithmic stochastic localization. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 323-334. IEEE, 2022.
Ahmed El Alaoui, Andrea Montanari, and Mark Sellke. Sampling from mean-field gibbs measures via diffusion processes. arXiv:2310.08912 2023.
Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. Ann. Probab, 33(1):1643316977 2005.
Afonso S. Bandcira and Ramon van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries. The Annals of Probability, 44(4), July 2016. ISSN 0091-1798. doi: 10. 10.1214/15-aop1022
URL http: /ttp://xxxxxo doi org/ / 10. 121 11/ 15-A0P1025
Afonso S Bandeira, Ahmed El Alaoui, Samuel Hopkins, Tselil Schramm, Alexander S Wein, and Ilias Zadik. The franz-parisi criterion and computational trade-offs in high dimensional statistics. Advances in Neural Information Processing Systems, 15:33831-33844 2022.
Jean Barbier, Nicolas Macris, and Cynthia Rush. All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation. Advances Neural Information Processing Sys- tems, 33:14915-14999 2020.
Joe Benton, Valentin De Bortoli, Arnaud Doucet, and George Deligiannidis. Linear convergence bounds for diffusion models via stochastic localization. arXiv::308. wrXiv:2308.03666 2023.
Matthew Brennan, Guy Bresler, and Wasim Huleihel. Reducibility and computational lower bounds for problems with planted sparse structure. In Conference On Learning Theory, pp. 48-166. PMLR, 2018.
Cristina Butucea, Yuri Ingster, and Irina A Suslina. Sharp variable selection of a sparse submatrix in a high-dimensional noisy matrix. ESAIM: Probability and Statistics, 19:115-134, 2015.
Tony Cai, Tengyuan Liang, and Alexander Rakhlin. Computational and statistical boundaries for
submatrix localization in large noisy matrix. The Annals of Statistics, 45(4):1403-144 2017.
Michael Celentano and Andrea Montanari. Fundamental barriers to high-dimensional regression with convex penalties. The Annaly of Statistics, 50(1):170-199)) 2022.
Hongrui Chen, Holden Lee, and Jianfeng Lu. Improved analysis of score- score-based generative modeling: User-friendly bounds under minimal smoothness assumptions. In International Conference Machine Learning, pp. 4735-4763 PMLR, 2023a.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is easy as learning the score: theory for diffusion models with minimal data assumptions. In International Conference on Learning Representations, 2023b.
Yash Deshpande and Andrea Montanari. Sparse pea via covariance thresholding. Journal of Machine Learning Research, 17(141):1-41, 2016.
Badih Ghazi and Euiwoong Lee. Lp/sdp hierarchy lower bounds for decoding random Idpe codes. IEEE Transactions Information Theory, 64(6):4423 4437, 2017.
Davide Ghio, Yatin Dandi, Florent Krzakala, and Lenka Zdeborová. Sampling with flows, diffusion, and autoregressive neural networks from a spin-glass perspective. Proceedings of the National Academy of Sciences, 121((7):c23118100)
2024.
Ulrich G Haussmann and Etienne Pardoux. Time reversal of diffusions. The Annals of Probability, pp. 1188-1205. 1986.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-6851, 2020.

---

Published as a conference paper at ICLR 2026
Samuel B Hopkins, Pravesh K Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, and David Steurer. The power of sum-of-squares for detecting hidden structures. In 2017 IEEE 58th Anmual Symposium Foundations of Computer Science (FOCS), pp. 720-731. IEEE, 2017.
Brice Huang, Andrea Montanari, and Huy Tuan Pham. Sampling from spherical spin glasses in total variation via algorithmic stochastic localization. arXiv:2404, 15651,, 2024.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 160.0029770 2016.
Frederic Koehler and Thuy-Duong Vuong. Sampling multimodal distributions with the vanilla score:
Benefits of data-based initialization. In The Twelfth International Conference on Learning Rep- resentations, 2024.
Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In ISAAC Congress (International Society for Analysis, its Applications and Computation), pp. 1-50. Springer, 2019.
Holden Lee, Jianfeng Lu, and Yixin Tan. Convergence of score-based generative modeling for general data distributions. In International Conference Algorithmic Learning Theory, pp- 946-985. PMLR, 2023.
Marc Lelarge and Léo Miolane. Fundamental limits of symmetric low-rank matrix estimation, 2017.
URL https: /awiiiiiiivv///av org/ abs/1611 03888.
Gen Li, Zhihan Huang, and Yuting Wei. Towards a mathematical theory for consistency training in diffusion models. M:XXi:2402.07822 2024.
Zongming Ma and Yihong Wu. Computational barriers in minimax submatrix detection. The Annals of Statistics, pp. 1089-1116, 2015.
Song Mei and Yuchen Wu. Deep networks as denoising algorithms: Sample-efficiet learning of dif- fusion models in high-dimensional graphical models. IEEE Transactions on Information Theory, 2025.
Andrea Montanari. Sampling, diffusions, and stochastic localization. arXiv, 2023.
Andrea Montanari and Emile Richard. A statistical model for tensor pea. Advances in neural information processing systems, 27, 2014.
Andrea Montanari and Yuchen Wu. Posterior Sampling High Dimension via Diffusion Processes. arXiv:2304. /449, 2023.
Andrea Montanari, Federico Ricei-Tersenghi, and Guilhem Semerjian. Solving constraint satisfac- tion problems through belief propagation-guidee guided decimation. arXiv:0709.1667, 2007.
Hoi Nguyen, Terence Tao, and Van Vu. Random matrices: tail bounds for gaps between eigenvalues. Probability Theory and Related Fields, 167, 04 2017. doi: 10.1007/00044000016669933
Minyu Peng. Eigenvalues of deformed random matrices. arXiv: /tt.//025.0022.. 2012
Federico Ricci-Tersenghh and Guilhem Semerjian. On the cavity method for decimated random straint satisfaction problems and the analysis of belief propagation guided decimation algorithms. Journal of Statistical Mechanics: Theory and Experiment, 2009(09):P00011, 2009.
Tom Richardson and Ruediger Urbanke. Modern coding theory. Cambridge University Press, 2008.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. IEEE transactions neural networks, 20(1):61-80, 2008.
Tselil Schramm and Alexander S Wein. Computational barriers to estimation from low-degree polynomials. The Annals of Statistics, 5033):1833-1858 2022.
Kulin Shah, Sitan Chen, and Adam Klivans. Learning mixtures of gaussians using the ddpm objec-
tive. Advances in Neural Information Processing Systems, 1e1199666964499 2023.
12

---

Published as a conference paper at ICLR 2026
Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In Interna- tional Conference on Learning Representations (ICLR), 2021.
13

---

Published as a conference paper at ICLR 2026
A NOTATIONS
Throughout the paper it will be understood that we are considering sequences of problems indexed by n. where æ E |R and the sparsity index k k, diverges as well. We write f(n) < g(n) or f(m = (()) if [(n)/((n] + 0 and f(n E g(n) or f() = O(g(n)) if f(n)/g(n) S C for a constant C. Finally f(n) = (g(()) or (n) x g(n) if S f(n)/g(n) C.
We write W GOE(n) if W = W is random symmetric matrix with (Waj)ssign in- dependent entries Wa: N(O, and Wij ~ N(0, 1) for < j- We say that (W. 1 O)is GOE(n) process if W. E Ruxx is a symmetric matrix with entries above and on the diagonal (i. : < S n; (i(i, S n; ( 2 0) forming collection of n(n + 1)/2 independent BMs.
We use C, Ct... to denote absolute constants, whose value can change from line to line.
B EQUIVALENCE TO THE TIME-REVERSAL FORMULATION
In this section, explain the relationship between the (time-forward) formulation of Eqs. (1), (2) and the time-reversal setup of Song et al. (2021); Song & Ermon (2019). Regarding the latter, we recall the Crnstein-Ulleneed process:
dz, -Z,ds + v2dB,
(19)
with Zo = x: ~ μ4, the target distribution and (B.) standard Brownian motion. Marginally, we have Z, d e . + -I- e1-e-22g g, with g ~ (0, I) independent of æ. At large time-horizon S co, 3s approximately follows I), which is easy to sample from.
We obtain a sampling process by time-reversing the SDE of Eq. (19). Specifically, let S oo be another large time-horizon, and consider time-change function f: [0, S] - [0, 7] strictly decreasing, continuous, such that t(0) = T, t(S) = O. Let be its inverse. Then, by time-reversing, mean the process (Za()))= Tj, starting with the initial condition Zs.
We can write a fore-forward process Y, = Ze(t)- It is known from Haussmann Pardoux (1986) and Tweedie's formula that (Y,) follows the SDE:
dY F(t, Y,)dt + 22)
(20)
where the drift is given by
y e 20(1) Ble B((e-(()) s(t) Zo(e) = y) -w ss((t)
2
F(t, v)
Note the resemblance between the conditional expectation Eíe- xz| (z)() = y) of the previous display and the definition of m in Eq.
(2). Now, we take = T = 00, and a specific time-change ((s) = 1/(e2* 1). The resulting process Y, has initial observation Y. Z NO, I), and
Eq. (20) becomes
dy. = = -r Vi( +1) ml m( t)dt + Vi(1 + +t)
dB,
Now, letting y: = V1(1 t)Y,, employing Ito's lemma on Y, and the function f(y, 1) Vi(I +yy, we obtain that y. follows the SDE of Eq. (I). The fact that we can write y. lx + B, as a process comes from the fact that y: = V + t) Z) This connection between denoising diffusions and stochastic localization stems from the specific time-change formula of t(-).
The treatment in Song et al. (2021) uses a finite time horizon S and consider the linear time- change formula t(s) = S - s. Then, (Y.) follows the SDE of Eq. (20) with |s(()) = 1 and drift
2
F(s v) y 2V VPPS-s(U) y 1+ 1+e-2(S 2(S-)) El (S--(S)))pp Zs_ = yy] y--
14

---

Published as a conference paper at ICLR 2026
It is important to note that other time-change functions t(-) (and thus s(-)) will not change conclusions. The computational bottleneck of recovering a from noisy observations a(t) + {()) for some functions a(-), (--) depends only att)/3(t), which is continuous and increasing with t from O to oo; moreover, our proof technique purely relies on controlling the discretized/generatee SDE up the computational threshold, which then should apply other time-change functions. We chose the formula t(s) = =1/(e²> 1) for notational convenience.
C A SIMPLE CONSEQUENCE OF CONJECTURE 3.
We state and prove the following proposition.
Proposition C.1. Suppose that Conjecture 3.1 holds for a distribution with Ex~ull<>) 1. Then for any sequence times in I (1 8)
Elllin(ye. t) - x: 12] = o(1) = Elllm +)11)) o(1)
In words, if m is optamal in score matching for S (1 - 5) at then (| t)l is small.
Before giving the proof, we remark that the full Conjecture 3.1 needed. It suffices for m to have weaker property; namely, that for any fixed constants E [-1, and 5 E (0,
inf Blleem((r..) æ a=|²²] (1-))0)
o(1)
Proof. Fix e [-1, 1] to be constant chosen later. From the property of m. we get from Cauchy- Schwarz that
-) -||+=|1|| < o(1) E (m +) S o(1)
We use Conjecture 3.1 for the sequence of estimators cmn which states that uniformly over t <
(1 aagg Bl () - x 2 - o(1 + Bl]l - (), -o(1)
Suppose for sake of contradiction, that lim sup,-+50 [m (y., xلل1 0. Without loss
of generality, we consider the subsequence (nz) such that (m x), B/2. Along this
subsequence, we have
4c² cB -o(1)
for all c E [-1, However, we know that this is not true for small enough; specifically, take c < 8/8 so that we have cc3/2 2 -01), contradiction. Hence (3 x)) = o(1). From the property of m. obtain the conclusion.
D APPLYING THEOREM 1 TO VERY SPARSE MATRICES
As mentioned in Section E.3, state and prove an analogous version of Corollary 3.2 in the very sparse case. One different aspect from the moderate case is that k can be smaller asymptotically: in particular, i can be sub-polynomial in n. Therefore, we first give modification of Assumption
Assumption 3. Consider kn & < for kn Conjecture 3.1. Let y: tx for (W.) sBM independent of x. Then a near-optimal estimator mi (y, t) in score-matching satisfies: for every pair (7,5) E 10,
P (l) t)ll 2) dt Okk-D)
for every fixed D > O.
Corollary D.1. Assume (log < k < n, so that tag (n, k) : 1:2 log(n/k?). Let my be an arbitrary poly-tine algorithm such that sup,, g.t m t) S and Assumption holds. Then there exists an estimator in such that
M1. ml.) ) can be evaluated in polynomial time.
15

---

Published as a conference paper at ICLR 2026
M2. y: tx Bi is the true diffusion (equivalently given by (1)). then, for every D 0,
B Bll (io ()1 =O
M3. There exists å on (1) such that, for any step size A A, O, we have incorrect sampling:
inf 12(-61
Wi(m t), x) 2 on on).
(21)
Proof. By the blueprint Theorem 1, find (a sequence of) hypothesis tests d indexed by t such that Assumption 2 holds. We choose a rate 5n = (1) slow enough, and En be the resulting sequence, such that Proposition 1.1 holds. We now describe (), based Algorithm 1, from time = 5al = (1 + o}h² log(n/k²)
upto L m:
Let v(1 + En log(n/k2). Compute y+ y + in and y = - vt/eng, with g ~ N(O, I). Then, compute A+ = (y+ + (21//2v(), and A_ = (y- + y (2V()
Let v be the leading eigenvector of ns (++))) Then, let = A_ v. Let $ be the set of indices of é with largest magnitude, and compute w such that wi (L/VR) sign(()))n()))))..)
Finally, reject iff (w, yu) 2 St, for some B > c.
From Proposition I.I, we know that
sup (14+)))
P(urly: 1) # x) < n
for every D > O. On the event that w(y,tt) = we get that (wr(y,,) (), (3) 1)) = (wo(s,))) W.w(yn ()) L
sup
(e, W.o)
for (W,) standard Brownian motion. From Lemma H.1, we get that with error probability at most for some D, we get that
(w(ye, t). yew t)) = + (w(y,, W.w f)) 2 2t t 2 = t(1 o(1))
11
Therefore, we obtain that for 3 < 1,
sup P(o(y, t) 0) < n 12 (2+45))a)
for any D > 0. After time ( n, we use the same tests Φ1, 62 as documented in the proof of Corol- lary 3.2, as / > + ()(n)), where n/2 is the algorithmic threshold of the moderately sparse case. The reason we can do this is that the spectral method, as in Algorithm 2. works even when k < v (although the threshold for this algorithm is asymptotically worse than 22 log(n/k2)), Fur- thermore, the size of the perturbation
Ad(c) is at most ||||| < ct = ck2 log(n/ (n/ k2) < c(n/2).
Consequently, the first condition of Assumption 2 holds with rate n for every D > 0. To deal with the second condition, note simply that is a k-sparse vector. A close inspection of the proof of Corollary 3.2 shows that it does not really matter how w is computed; the main idea is simply that for all Ad(c),
(w. (a B.)w) < ||a|| + (w. B,w)) clang + (w. B.w) S clag + C [lo
(")
n2
for each t. Of course, we have to bound this simultaneously for all f, and this is done in the proof Corollary 3.2; c.f. Appendix H.
of [
16

---

Published as a conference paper at ICLR 2026
E CONCRETE EXAMPLES: DENOISERS FOR SPARSE LOW-RANK MATRICES
E.1 ALGORITHMS
In this section, provide the detailed pseudocode for Algorithms and 2. In Algorithm the following soft-thresholding function, with a parameter s:
(v) = sygn(y) (1yl t, 0) = sign t)+
Algorithm Submatrix Estimation Algorithm (very sparse regime)
Input: Data yı: time i; parameters 8,
2: Output: Estimate of æ: m ()
3: Let gt ~ N(O, t x and compute yr,+ := y: + Vegi, yt.- == Yt gi/V=
4: Symmetrize: A,, = (yr,+ + y. (222/ A, (v1,- +
(2.))
5: Compute top eigenvector ( (A,+)) denoted if by 1t
6: Ift 2 tale V 1 and a1 (17 (A,,+) k + Vi
continue; otherwise return m t) := 0
7: Compute the vector 0, = Ar,-u 1t
8: Let be the set of l indices of largest values of [ and compute vector such that wi = sign sign((r,))) (
9: return my 1) = 1
Algorithm Submatrix Estimation Algorithm (moderately sparse regime)
Input: Data yı time t: parameter
2: Output: Estimate of æ: m
3: If Z falg- continue; otherwise return m( t) =
4: Symmetrize: A, = (y: + /22/)
5: I 2 n² and (A,) I vi/2, return 0; otherwise continue
6: Compute top eigenvector of A,, denoted if by 12
7: Compute Š by = { E [m] |0,, 2 Vk
8: Compute vector w such that W; = sign (v. 1
9: return m www / if |$| k/2; otherwise return 0
E.2 MODERATELY SPARSE REGIME: vn <
Since Theorem 3.2 is somewhat abstract, complement it with explicit example of m: namely, is a modification of a standard spectral estimator. While achieving near optimal estimation error (among polytime algorithms), m fails generate samples from the correct distribution.
Proposition E.1. Assume /n < k < so that taig (n, (n, = n/2 per (9). Then the estimator m defined in Algorithm satisfies the following:
M1. m(-) can be evaluated in polynomial time.
M2. For any 8 > O, there exists c = c(5), C = CC) such that
inf [((lm(((. - x = - (1), 15(1
sup E(Iimyy, t) - x1 $ Ce Ce ennk 12(1+8)6
M3. For any A 0. we have incorrect sampling: infreN-a (i = o, (1).
Therefore, we enforce that m 0 for < tagg- Recall that this implies Assumption holds trivially. Regarding the specific design of m, Algorithm uses thresholded spectral approach. We compute the leading eigenvector of (the symmetrized version of) ye. call it v, E R". We then estimate the support S of the latent rank-one matrix x using the entries of v, with largest magnitude.
17

---

Published as a conference paper at ICLR 2026
E.3 VERY SPARSE REGIME: le Vn
We have an analogous result for the very sparse regime, where the sparsity level k: < Vn.
Proposition E.2. Assume (logn)3/2 S k & VT, and note that here Lag(n, k) = k2 log(n//2)), per (9). Then the randomized estimator m R - B=xx of Algorithm I satisfies the following:
M1. ml can be evaluated polynomial time.
M2. For any and D > 0:
inf (( a=|2)] on (1),,
(((lm(((,))) -x11²) n- (24445
sup
15(1- ala
M3. For any A 0, we have incorrect sampling: infren (m 1), a:) = On (1)-
The pseudocode for the estimator ri(.) that constructed in the above given as Algorithm 1. This is based standard approach in the literature Deshpande & Montanari (2016); Cai et al. (2017), with some modifications to allow for its analysis in the diffusion setting. The main steps follows: (1) Perform Gaussian data splitting of yt into yt yt.,, see Line of Algorithm 1, with most of the information preserved in yr (2) Use entrywise soft thresholding 7/s (1(2)) = reduce the noise in the symmetrized version of yt (3) Compute first estimate of the latent vector 1s by the principal eigenvector of the above matrix. (4) Refine this estimate using the remaining information yr.-.
(|>] - 5)+ sign(z)
We point out that Proposition 3.3 remains true in the regime vn < k < n, and hence we observe a gap between taig (n, k) and taaess k) in this regime as well.
F PROOF OF PROPOSITION E.1
F.1 PROPERTIES OF THE ESTIMATOR r).))
Proposition F.1. Assume vn & k < n, and note that in this case (ng = n/2. Let ml be
the estimator of Algorithm 2 with input parameter For every 5 > 0. there exists >> 0 such that
sup (2
[[m((,,t)
==1 S C -ne /64k
(22)
The proof of this proposition is standard, and will be presented in Appendix O. We note that the rate in Equation (22) gets slower the closer & is to it is super-polynomial if n >> k log
By definition, when vn & & n and < (n, k), the Algorithm 2 returns my f) = 0, so we automatically have the following result.
Proposition F.2. For any fixed 8 > O, and S (1 10-)) 8) we have (m t) 2
F.2 AUXILIARY LEMMAS
The following lemmas are needed for the analysis of the generated diffusion. Their proofs are deferred to Appendices Q S.
Lemma F.3. Let W, be GOE process. Then for each time to 2 0,
P max USts
Wellop 2 16
< 2exp (-32n).
Lemma E44 Let W, be a GOE process, and let v, be any eigenvector of W. every t 2 0. Define the set
A(e; C) { 8: i:lsis
CVlog(n/k)
vn
Then for any C we have
P (IA(v; C) maxt (k,kk/m)) - (exp(-(113)
As consequence, using this eigenvector, in will evaluate to 0 per line 8 of Algorithm 2.
18

---

Published as a conference paper at ICLR 2026
Lemma F.5. Let W. be GOE process, and,for each t, let v, be top eigenvector of Wt. Then for any times to S ti, with probability at least 1 - 2 exp( -32n),
sup StSt
(0, W vz) (.W).,)) S 32 n(11 -6).
Lemma F.6 (Concentration for deformed GOE model). Consider the model Y = Ovv + W for W /OE(n)/ /n and 0 >> a constant, unit vector. Let (Y) be the top eigenvector Y. Define (x", =²) = (0 + 1/0,1 - 1/6²). For any closed set F such that d((x", ,u"), F) > 0, there exists a constant > 0 such that
PP
E exp(-en)
for all n large enough.
We only Lemma F.6 for the alignment (1n (Y), w)
F.3 ANALYSIS OF THE DIFFUSION PROCESS: PROOF PROPOSITION E.
We will prove Theorem E.1 for > 2 C ///oo///k)/(m/////// for some sufficiently large constant C.
Suppose that we generate the following diffusion, with (zz)120 standard ni-diiensional BM, and ÿo 0:
VIa Vie-1)a 1)A A m (i ())) (Z1a
=((-1)a)-
We will prove that the generated diffusion never passes the termination conditions (c.f. Algorithm 2, lines 3, 5, 8).
F.3.1 ANALYSIS UP TO AN INTERMEDIATE TIME
Define Ineeween = n Following the strategy with Section 1.2, will first show that m up to fieeween with high probability by analyzing only the noise process (in short, if r = 0 always, generated diffusion coincides with the noise process). Our strategy is of the same nature as that of Section 1.2. Indeed, we will attempt to prove that m = O simultaneously for all i, with high probability. In this phase (0 < t S fneweem) we will show that [$ < k/2 (c.f. definition in Algorithm 2, lines 7, 8) for
toeweem: with high probability (v, the top eigenvector of A., c.f. Algorithm 2). Note that line 5 of Algorithm 2 is not relevant in this phase. We first show this for a sequence of time points (te)e21, then control the in-between fluctuations. We can set 1 to any value in [0, n 2), as the algorithm returns 0 if < lagg n/2 anyway. We denote the GOE process
W, B, + B
VtA.
It is clear that the eigenvectors of W. and A, coincide.
We choose the following time points:
t
1 n
To exceed baween n², we will need n values of l. By union bound from Lemma F.4 (recall also the definition of the set A(v; C*) from this Lemma),
P (31 e n. |A(v,; C*I 2 max{ Vk, k2 /nt) s o (exp(-(1/3)n 1/4 66gg))))))))) (23)
Next, we will control the in-between fluctuations; specifically, we would like to show that srxte IA(r;; C²) < Co max (Vk, k2/ /2/n simultaneously for many values of & (with high probability), for some constant Co > O. Our approach is as follows.
(i) Let v. be top eigenvector of W. If is close to lz, then v, is an approximate solution to the equation (in v):
t W. f, v (W..)
19

---

Published as a conference paper at ICLR 2026
(ii) can be written in the coordinate system of the orthonormal eigenvectors U1, "ul... [n of Wt,, corresponding to decreasing eigenvalues \1(W.) 2 ... 2 An (W,)). Namely, 8, = U,, V,, n U.," up with ||w]|| =
(iii) Let be (sufficiently large) constant integer with S S n. The first components of w take up 1 o(1) in Lg-norm by (i) and (ii) with overwhelming probability, from which we can simply use triangle incquality to upper bound | C'] according Lemma F,4 for u1, Um, which incurs only a constant factor of error probability, by union bound.
Define Pa. P (1)) Xr(Wi) S n -11/2) for any C" > 0 (here we take 7).
We use the following result (we have accounted for the scaling). Lemma F.7 (Corollary 2.5, Nguyen et al. (2017)), Let W1 (1/V2)GOE((). For any fixed 1 12 1, C' > 0, there exists constant = coll, C") such that
IP (>)(w))) A1+i (Wi) - 2" C' 1/2 -1/2
S con -2
We materialize our approach above. We can write, with U,, w:
oa W., w Du. (Du)eu
We then obtain that p
T. - (W,,) S
A1 < Vtnn 3/2 w
1=8
with probability at least 1 - Pn 2 con from Lemma F.7 and Wt, v 2 W1. Now from Lemma F.5, we know that with probability at least 2 2exp(-32n)
8 W2 (W,,) 2 -32 - /n(et+++= te)
With probability at least 1 - con 2 eexp( -32m), both of these statements are true, uniformly over 4 S t & 1,+1, leading to
le+1 - tt V
2 n2
3/2
tt
8
simple bit of algebra shows that
l+11 le < 2n
512 = Σ
n
w < 128n -1
te
1=8
Consider the first 7 cigenvectors { of Wt. Let
A U A(uresi C).
From Lemma F.4 and a union bound, that |A| < 7 Vk, kk,k3/n with probability at least 1 ((ex((-(1/3)a 1/4). For every j E AS, we have
|uyl $ Σ / wosl-luee.4.
|wsl- CVlog(n/k))
|wm| S
C² C'Vlog(n/k))
128
<
O"
log(n/k)
Vn
vn
n1
for a large enough constant
C" O. This means that with probability at least
O(n -8),
AA C*)l < 7 max (VT, 12 /n) < k/2
sup S
From Equation (23) and a union bound over E 2 1, we know that with high probability, AA(v; C) < 7 max{ Vk, k2/n /n]
sup 2
for some absolute constant C > 0, meaning that m 0 up betwees as long
C /log(n///
Vn/k
20

---

Published as a conference paper at ICLR 2026
F.3.2 ANALYSIS THE INFINITE HORIZON
We will prove that simultaneously for all n², Algorithm 2 always terminates line or that A (W,) I 1/2. Similar to Subsection F.3.1, we choose the following sequence of time points for all
f = =2
By standard Gaussian concentration and the Bai- Yin theorem, we get, for instance, the following tail bound (constants are loose) for all x 2 0:
We V
(- x²²
IP
A1
2 4vn+ < 2
(-2
Set Vi Since t 2 n², we have x 2 n/8, and x + 4yn S 2x for n large enough. Consequently,
W
Vl
P
A1
S 2 expp (-c1t)
for some universal constant C) >> 0. A union bound for the chosen points gives:
P
W
/
2 2
exp
(-c1t(2)) = 2 eep((-cnn
Σ expl exp((-a(e-1)) 2 exp(-cin²)
(24)
Next we control the in-between fluctuations. From a simple modification Lemma F.3, we have
A1 (W.r)) A (W.) 2 16 (0/ ((2) ((2))-1((m S 2exp (-32nl?²
P
sup
SASA (2)
so that by union bound
sup (1)(
An
W (2) An (W:) 2 16 (6V(1(2) )
S eex((-32n)
(25)
Consider the intersection of events described in Equations (24) and (25):
A = 1621::1 W (00 2 (2) /4 U 1221:
J
\ W (
A (W.) > 16 / (1/2)
(22) (2
sup
1 (ig())
For each & 2 n², let & be largest such that l 5 < 12
On A, we have
(2)
(2)
(2)
(W.)
+ 16 (1/ ( 1 n
2
16
for n large enough, since (221 2 n² >> n. Hence the algorithm always returns O with high probabil- ity, and we are done.
G PROOF OF THEOREM
We define mn follows:
mo t)1 mno... mno (y,()
ift S (1 - ta)
m 1)
if (1 - 7)42gg <1 < (1 + 8)
(noo f)d(y, 1)
ift 2 (1 1 +8)
First, we check that Condition M2 holds.
[ Elll Elllit( t) - mo. d)
21

---

Published as a conference paper at ICLR 2026
(1 1-11 Mak
E Ell t) molye. mmlyy.t))lddt +
E Blllm(yr,t) t) -31, 2)]
aa
/ P(o(y,t)= = 0) dt
PP P t)ll E)dt +
(1+5)aal
-0 (d) + (22
where in (a) we use the fact that Φ is binary and Conditions i), iz) and ait.1). Secondly, we check
that Condition M3 holds. To reduce notational clutter, assume that t lu is an integer. Then, we can write
VI
B
m m(aa,
(26)
where the drift accumulation term is bounded by, from Condition i):
m úن i
S E1 - 2) + (7 + 5)tale S. fals
for every (0, 1) by taking E, small enough, 5 = oa(). Suppose that from Condition iii.2),
the event {ō(a + B,) = for all / 2 41, a E Ac(c)} holds. Then clear that (ū (1) = <(ūr; (1) 0 by definition of m. Suppose the inductive hypothesis that tis, + i
for all 0 < S k. Then from Eq. (26), we get that +(++++)) +(+ E Aa(c) and so m (e) (1++)), + (I: + 1)4) = O. Consequently, m = for all = E 2 41 By Condition mi..2), the preceding event holds with high probability, so that for each / = A 2 4, m (,, t) with high probability. By boundedness of m and definition of the Wasserstein-1 distance used on the function f()) = we obtain that W (m (g.. t), x) 2 a - o(1). The proof ends here.
H PROOF OF COROLLARY 3.2
H.1 AUXILIARY LEMMAS
We will the following lemmas, whose proofs are deferred Appendix I..
Lemma H.1. Let W ~ GOE(n, 1/2), and C' > v2 some positive constant. Then we have
-C2/2+2
P
max v
Ke, Wo) 2 C log
1 k
<
2
11
k
We state the following non-asymptotic result from Peng (2012).
Lemma H.2 (Theorem 3.1, Peng (2012).). Let y tuu + GOE(n, 1/n), and denote by X (1)
the top eigenvulue of y. Letting E(0) = 0 + 0 0-1, the following holds for every 2 and 0 > 1:
(n 1)(0 1)a² + Sexp
(n - 1)(0 1)
P (1) < E(0)
S exp
1602
(0 1)3
In Appendix L, we will use the last lemma to prove the bound below.
Lemma H.3 (Alignment bound). Let = Buu + GOE(n, 1/n), where 0
VI+5. Let vn be
the top eigenvector of y. Then, there exist constants C. >> 0 such that the following holds for any 5 = 5n with n & & 1 for some c > 0 small enough:
(1(0,, u)) < c5²) < Ce 1/
(27)
We also use the following lemma, which is implied in the proof of Lemma F.4.
Lemma H.4. Let g ~ N(O, I,) and define the set
Lig: C) {i fi:lsismo n, losl CV (Vo((n//))
Assume Vn < & Then, for any C. large enough, there exists C. such that
[ 2 (vKV k2 ) < C.e-n
22

---

Published as a conference paper at ICLR 2026
H.2 PROOF OF COROLLARY 3.2
Let ô = On (1) be a parameter to be chosen later and recall that lag n122. We define m as follows:
my f)1 (mls.. m).
if (1 (agg
if (1 - fa1s
< (1 + 8)
m =
mo ()61
(1 + 6)
1 < n
(3
ift 2 n²
where $1, R x R20 + {0, 1} are defined below and ry is given in Assumption 1. It will be clear from the constructions below that Φ1, de can be evaluated in polynomial time. To establish the relationship between Corollary 3.2 and Theorem 1, we make few remarks:
Assumption is used in (29);
By defining the hypothesis test á such that
(3,() (2(
if (1 S < nd ift 2 n²
s(y, 1)
we recover the desired properties of Assumption 2, with 7/2 72(m) = D) for any > 0.
In order to prove claim M2, we need to bound (O, oc), whereby, for ta S to.
Jn (1a (b) = /"'
An
[l (3t, dt
to
Setting f (1 + aay and to n2 write
(0, - (0,4)) + + (x(,,
(28)
and will bound each of the three terms separately.
Bounding t,( By Assumption know that
(1 (1-2)66
(n,,tt,) $
P(Imao(, t)ll > E) dt O(n-D),
(29)
00
for every D 0.
Bounding Jn (2). For matrix y E Raxx and time point I, we define di (y, () according to the following procedure:
1. Compute the symmetrized matrix A (1/2)(++))
2. Compute its top eigenvector v (choose at random if this is not unique).
3. Let S S [n] be the k positions in v with the largest magnitude, and define è E R" with
0; (1/Vi) sign(w) liss
4. Compute the test statistic 8 = (6, Ao), and return 1 if 2 B1; 0 otherwise.
Here (0, 1) a fixed constant be chosen later.
We will show that (1.. = 1 with overwhelming probability for the true model
to + B.. Define
A, + v! luut W.
where we recall that u (n2,()2,,)) and W, is GOE(n) process, Let vt. ú; be the top eigenvector and thresholded vector of A,, respectively.
We have
8t (6,, A,oi) t (u, 2 (6,, W.o.).
(30)
23

---

Published as a conference paper at ICLR 2026
Using Lemma H.1, we know that (ö,, W & 4 klog(n/k) vt with probability least 1 66
say. Further
2t (or, u.u v (0,, u)² w
where uo is uniformly random unit vector orthogonal to u, independent of (m;, u). Alternatively, there exists g N(0, In),, independent of (wi u) so that:
(I, uu )g
11 wu )gl
For every 1 S S n, we have
I((I, uu }g); $ 19d ((, g)1
Vk
Since by assumption &: (og(n/)) < n, with probability at least - C1 exp(-k/2), ((,gg) - v log(n/k) and [I( uu )gll vn/2, so that
V log(n/k).
E C)
|us| S (2C+2)
Therefore, by using Lemma H.4 and k llg(n/k) > n 1/222 we get that with probability at least 1 - C. exp((=l (Aww; C*I S max( k2/n) for some constant C > O, where
A(w; C) = i: i:lsis 2 CV log(n/k)
n
By Lemma H.3, we know that with probability at least 1 - C. exp(-cn for some C., > O, (V+g(1+))), u)} 2 co2. Since (v,, u) is stochastically increasing with t (Fact O.2), we actually have that for any 1 2 (1 Maggg with the same probability (v,, u2) 2 cd
On the event & == (1,, u)I 2 cō²), further suppose without loss of generality that (Ve, u²) > 0. As consequence of the result above, if E supp(u) and & A( C), then
co²
Us > 0, i & A(w;;
= oe,i 2
C
V
log(n/h).
Vk
n
c82
u, 0, A(w;
ot,t
CV
log(n/k).
Vk
Similarly, if & supp(u) u), then
O, i Alw; = 10,,1 S CV. log(n/k).
We next choose 8n such that
(lt/n)log(n// < 8, < Hence, we conclude that i E supp(u) A(w:; C) = à. sign( u)) ue
(31)
whence
1(u,, 0/)l 2 A(w: C)I = (1),
(32)
with probability at least - C. expp-n1/44 1/4 1/433/33/////)))33 On this event, by Eq. (30) we obtain that
> 2- (1 (1)
4 Vklog(n/k) Vt
For 2 (1 8)tuu 81 (1 + 6)m/2, we this implies that, for any fixed B E (0, 1), with probability at least 1 C. exp(expp/ppp /33) (possibly adjusting the constant C.).
Recalling that m 1) = mo () (3t, !) for t E [11, 12). and [ 1)ll < 1, we have, for t = (1+ t)tge to n as defined above.
22
E m t) mo (y, 1) S /" (( t) = =0) s C.n e/n (33)
Jn (tt,, 12) =
24

---

Published as a conference paper at ICLR 2026
Bounding (t2, oo). When 2 t2, simple eigenvalue test. For matrix y, and time point t, we define (2(y. t) according to the following procedure:
1. Compute symmetrized matrix A (1/2) + y²).
2. Compute top eigenvalue (A).
3. Return if X1 (A) t/2, and 0 otherwise.
Under the true model ye = tx B₁, we have:
(A,) 2t t Welllo 2 t f2/3 2
with enror probability given by
Wellop 2 (2/0) - Cexp (-ct1/3)
for constants C,c> 0. Thus, we get that
1 PellWo 2 (213) dl SC. /
e-al/s dt
(12 00) 2
< -a I -on
(34)
Claim M2 of Theorem 3.2 follows from Eqs. (29), (33), (34).
We finally consider claim M3. Equation (4) yields, for every f 2
ÚES
m (i 1)2) VA
gia.
(35)
We define
m.
())) 4 = [as + 0)/A].
(36)
We further define the following auxiliary process for 2 444 = [4/AAA:
Ú: m., Br,
(37)
where (B, t t2 0) is a BM such that B₁a = VA 9.A- In particular, ÿe, 9r,4-
From triangle inequality, using Assumption the condition (y t)]lF < 1, and that by construction ||m[ f)]l I & for t S (1 Tug. we get
|m]l= S se(1 7) + (7 + 8)
We claim that (with high probability) Φi (3,, t) 0 simultaneously for all t E [t,, tel- As consequence, recalling the definition of m,, we obtain that ÿ. ÿ. for all & E [2]. In order to prove the claim, define, for é 1:
To ( 2-1 e 14) t2)
For every [1,, 12), consider the thresholded vector G. in the definition of the Φ1. We know that
(0,, 0.) (Ü,, mo;) + (0,, B. s E(1 - t + (r + d)tale + max (v, B.v). Jeft,
(38)
Using Lemma H. we get that
-2222-2
n2 1(v, B,oo 2 Gylog olgg
v2
P max vef..
k
25

---

Published as a conference paper at ICLR 2026
Note that [Tal n2, whence
-C2/242
P 3t E Tn: max veRn.k
1ev W,, 2) 2 C k
log
n
vtz
2
n1
n1
k
For E [le, lett), we have
max feStSte11
max wE
(0, W
max Ko, Wo "
max seSt
I Wtellop
Using Lemma F.3, we get that maxt, w. Wee llop S 16 (le+1 - 44)m = 16 with proba-
bility at least expp( 32n). Taking union bound over Tai we get that
-C3/2+2
P
M E [4,42]
max (o, W 2 C.P log vE
n k
n S
n + 2n e 32n
k
for possibly a different constant C > 0.
Using Eq. (38) and the last estimate, obtain that
-03/242
3t [21 : (0,, 0.),) 2 buttag + C log
1 k
Vt
11 S
no.
2n
k.
(39)
where bn := = 7) + (y + 8n). Since 8n = on (1), we have bn + - -)= + %. Further, by choosing 7, 8 small enough, get that lim sup, bn < e/2,, say. Hence, we get that for 2 l1, and all n large enough
batat / (1) ())
for the constant of Assumption 2. Therefore Eq. (39) implies that Φ1 (ūt, t) = 0 simultaneously for all E [2], with high probability, by choosing B c. We conclude that, with high probability ÿ: Y: throughout& t E [ti,t2]
Finally, we extend the analysis to l E [|2, oc) by proving that, with high probability, dz(ū.. 1) = 0 and hence ÿ, Ut. for all / (/2, oo). We use (for A. (ý: + 7. )/2, W. (B, + B, )/2)
(A.) & c(1 T) + (5 + 7) t A (W))
(40)
Following exactly the argument as in the proof of Proposition E.1 (in particular, Subsection F.3.2), we get that A1 (W,) S t/3 simultaneously for all 2 t2. with high probability. On this event, (At) 1/2 with high probability (because t/6 >> (1 7) e) + (7 + 8)t,))) Hence, with
high probability Φ2 t) and hence ÿt = ÿ. for all E [12, 00).
We thus proved that, with high probability, 9: Jr for all t 2 t = (1 - 5) whence m 1) 0 as well (because (1. 1) for E [1, and Φ2 1) = for E (l2, o))).
Claim M3 thus follows.
I PROOF OF COROLLARY E.2
1.1 PROPERTIES OF THE ESTIMATOR m).)
Proposition I.1. Assume (logn)² < k < vn and let ml be the estimator defined in Algorithum
Recall that in this case, bug 12 log(n/k3 kk2). Then for any 8 > there exists > O such that,
letting s = /(1 + E) log(n// (n/)), we have
sup 12(+)))
P(m(,,, t) # x) Pn)
(41)
for any fixed D >
26

---

Published as a conference paper at ICLR 2026
The proof of this proposition is modification of the one in Cai et al. (2017), and will be presented in Appendix K. Note that Proposition 1.1 directly implies the first inequality in Condition M2v of Theorem E.2, as || t) æ I 2.
By definition, when < fag. the algorithm will return vn = 0, so we automatically have the following, which implies the second inequality in Condition M2v.
Proposition L.2. For any fixed O, and t I (1 - aag.. we have ( t) æi| = 1.
In the proof of Theorem E.2, we will also make use of the following estimates, whose proof is deferred to the Appendix N. Lemma 1.3. Let (we : t 2 0) be process defined as
1 wi 2 [ Vegi) + (B, + V
where B,g are independent n²- dimensiion BMs, and 0 S & < 1. Then, for any 0 I to S t1, and t 0, 121,
P
max SoSts
||w, wolld 2 4/ -11-100) n n) 2 -- n2//4
(42)
P(Ilwel 2 4V18. n) 2 n²x/4
(43)
1.2 ANALYSIS OF THE DIFFUSION PROCESS: PROOF OF COROLLARY E.2
We are left to prove that Condition M3v of Corollary E.2 holds.
For that purpose, make the following choices about Algorithm 1:
(C1) We select the constants in the algorithm to be En on (1) and 8n / (1+ (1+ En) log(n/k²).
We will use the shorthands s = Sn and Exs unless there ambiguity.
(C2) The process (9:):20 used in Algorithm 1 follows n dimeesisil BM.
Note that Propositions I.1, 1.2 hold under these choices, and in particular gr. ~ N(0, (Ixx)) at all times. Also the sequence of random vectors gea. É e N can be generated via g 9(1-1)a +
v A for some i.i.d. standard normal vectors }90)
Letting (z, 122 standard BM in Raxn, and ÿo 0 we can rewrite the approximate diffusion (4) as follows (for / E ..
Ú++A ÿr + m ()r, + (Z1+4 - 2x))
(44)
We further define
wi = 2 [2z + Veg.) + (zt + Veg:)
(45)
It is easy that (e(e)w, 0) is GOE(n) process for c(s) == ((1 e)/2)-1/2, The key technical estimate in the proof of Theorem F.2, Condition M3v is stated in the next proposition.
Proposition L.4. Let (w, 2 0) be defined as per Eq. (45), and assume En (1) and Sn v (1 + En) log(n/k²). Further, assume k C(logn) n)5/2 for some sufficiently large abso-
lute constant C' > 0. Then
lim IP [[In S S ft/s v1 /4+////21)=1111
(46)
Before proving this proposition, let us show that it implies Condition M3v of Theorem E.2. Indeed we claim that, with high probability, for all e E N, m Úr,, LA) = 0 and Ú.A = ΣzA- This is proven by induction over f. Indeed, if it holds up certain & 8-11 1 N, then have ÿEΛ zea by Eq. (44) whence it follows that A w VE, for t A (c.f. Algorithm 1, line 4) and therefore vin ( t) = 0 by Proposition 1.4 (because the condition in Algorithm I, line 6, is never passed).
We therefore have
inf W, (m ()), 2 Pmm (A) = 0) = - (1)
(47)
E20
E20
This concludes the proof of Theorem E.2. We next turn proving Proposition 1.4.
27

---

Published as a conference paper at ICLR 2026
Proof of Proposition 1.4. We follow strategy analogous the proof of the Law of Iterated Loga- rithm. We choose a sparse sequence of time points {te)=11 and (i) establish the statement jointly for these time points, and (ii) control deviations in between. In particular, consider
to = (1 (1+ f-1 n2
for all / 1.
We first show that simultaneously for all E 2 we have max,, (wn))// Vtl I St Vlogn. We have, by sub-gaussianity of (wi,); and union bound (here account also for the where i = j, in which there is an inflated variance), along with e = on (1): using the bound 2ry 2 +
when x, y 2 1 for le y log n. Taking a union bound once again over E, have
exp (-8.
8 n23
P [221 < ( S ((mt) 8/ Vlogn
Sn
6
1
t=
We have, as the summands form a decreasing function of integer:
-88 1 n33 ( )) sc / exp
8x
exp
dx < Cn3
(48)
P=0
We thus obtain that
3/4 Vlogn 3). (3621,1 i,j S n: ((1r,)s)) 2 8t
(49)
The point of this calculation is that simultaneously for all l Z we can truncate the entries of Ms (w.,// Vvx) by 81 1/4 Vlog without worry.
Namely, for each 2 1, 0r = s0 Vlogn a we define wi. E 2xn by
(Waewee/ (Wt))
if (wre/ /tte) S 0r: if no(wir/ /tt) 02. if no n [T -
(wi, )ig =
De
(50)
-1
By Eq. (49), we have
P P n,ww,,// Vtt) + wr,) = O -8)
(51)
We have from Bandeira & van Handel (2016), for every 0: for some absolute constant c > 0, where
cx2
P [1 2 40 +x) S nxxp
(52)
0
2 max
E (1i 5
E
ne
Wtt
(53)
vtz
ig
max SS
(w Dayl S 8///4
1/4
Vlogn.
(54)
It can be seen from an immediate Gaussian calculation that, for i * j and Z ~ N(O, 1):
Wt
2
I I+E
E
4z
P
2 > z + dz
J0
2
(a)
( (2 + 8)2
4z
exp
dz
1 ++
(b) 1
82
82
exp
exp
$
1
28

---

Published as a conference paper at ICLR 2026
Here in (a) employ the Mill's ratio bound, and (b) follows from 2 and + Proceeding analogously for the diagonal entries of 77 tt), we obtain that vn /xeexp==>* /22(11/111111///11111111 E))) k by definition of
We set x = k/3 + /te/(3s). Since a > a, we have 40 + a S (3/2) n, are sufficiently large. Using Eq. (52) obtain that, for some universal constants c, C, e" 0:
2
k
Vle
+
3s
(a)
ck
dit 1/2
P
| llap 2
+
S exp
exe
2
2s
641
1/2
log
slogn
s log
In step (a), we simply expand the squared term in the numerator and drop the quadratic term in k. Now, taking union bound over f 2 1, we get that (similar to Eq. (48))
vt
d'k s log n
3221 1: t lop 2
+
S nexp
exp
2
2s
s² log
t=1
d'
(O(1)+
d
S nexp
+
exp
dr
s log
s2ns log
dkk
0 exp
logn
= om. (1),
where the last estimate holds if A: > C(log n) 5//2 for some sufficiently large C > 0. In conclusion, using the last display and Eq. (51) we have shown that
Wxe
k
VlE
PP
38
2
1/4
-nn(1)
(55)
28
op
Now we control the in-between fluctuations. Noting that (7s(-) is 1-Lipschitz function, we have the following crude bound:
Wt
Wie
Wtr Vte
Vi
7/s
VTe
SeSttee
Vt
up
maXt,
|w: willF ll
+ || l| (Te Vtets
Vle
From Lemma I.3, we obtain that
P
max NeStSte11
|no no (wr, /Tto
2 4n 4n
/le41
te + 4n Vte (1-
4e 4n-1//11
te42
By definition L2, simple algebra reveals that (we also use the fact that n 1/2 < 8-1);
4n Vteti - te 4n vte.
(1-VELh
te Vte
te+1
2s
By union bound over é 1,
k
12
P
38
1:
max 155t54111
\n/(we/V)) - nowwe /Vtee)/()))))))
>
+
op
2
2s
n
te
exp
8
8
1=1
8
e-1) 2
=4cxp(-oe -
Σ
exp
1 +
8
3
1=1
29

---

Published as a conference paper at ICLR 2026
<4cxp(-n2/8) 0(1) (O(1)+
x
exp (-
x²² 8n
dx
((exp(-n"/8)n) = =(1).
Using this estimate together with Eq. (55), conclude that with high probability the following holds simultaneously for all 2 1. Letting & be largest such that te S to
vt S
Vt
op no w/ //t/ - (ln.(ww,,//)) up + +|]n(wwe/V)) - no /Vte)
- k
op
and this finishes the proof.
We remark that Assumption (C2) the proof above is technically not needed, meaning that the additional noise stream Jr can in fact be discarded entirely: an appropriate thresholding of ey, the top eigenvector of 17 (Ar,+), as in Algorithm 2, will also suffice to satisfy all conditions of Theorem E.2, although will not be recovered exactly; some o(k) positions outside the support of x will also be chosen, at most. The reason for this is that the alignment (,, u) close inspection of our proof of Proposition I.1. Regarding the proof of Proposition 1.4 above, one can easily realize that even if ε = 0, it will go through without any modification. We choose to keep our formulation of Algorithm 1 as faithful the original work of Cai al. (2017) as possible to discuss a variety of approaches, and leave this to the interested reader.
- (1) already, from
J PROOF OF PROPOSITION 2.1
We take the first row &1, and let A = {. 2in] Let rank(215) denote the rank of 21 with respect the elements of A. Then since 21j N(0, 1) across j. the collection of the first ranks A& = {ri, rkk constitutes a sample without replacement from [n]. Construct e a binary vector such that v2 1 if and only if i E Ag, and let be randomized-sign vector version of
(1/vk)v. Let
my uu x²'
(56)
then it is clear that my t; 21) ~ x and is independent of x: (as it is a function of only 21). The identity from (i) follows accordingly. To that this error is clearly sub-optimal compared to polynomial time algorithms, observe that m = 0 is a polynomial time drift, which achieves error every L.
Point (it) also follows immediately. Indeed, for every E 2 0,
W1 (ira Wi .z) =
Lastly, regarding point (iii), note that since is not dependent on t, we have, for every / 2 1,
Uis = Die-1)A + Ax' +
A
Simple induction gives
ÚEA (lA)x' + VA
j=1
We take the coupling of (Dra/(EA), x)) such that x' = x. Then by definition of the Wasserstein-2 metric,
n
We(Dra/(eA) )² S
AA
It is clear that as l + 0o, this quantity converges to 0. Hence are done.
K PROOF OF PROPOSITION I.1
We conduct our analysis conditional on u (recall that = uuT), and S be the support of u. Let
Ao = VluuT and notice that
A Ao + ++ Z, A Ao
(57)
30

---

Published as a conference paper at ICLR 2026
where of (1+ (1++))1 e)/2, o2 (1+ e)((2) and Z, W GOE(n) are independent random matrices.
We have
(A(,)) = Ao + ( B + (B E[])
(58)
where
Bi 77 Vi. u,y + 0 o+2is) Vt u.uy (a 2ig)
(59)
Our first order of business is to analyze E B) i $ S or j $ S. we have TE| B,y] = 0. On the other hand, if j E S, then
ii Case 1: uel = 1/k
In this case, we have B[B,,] -b + bili=s where (below G ~ N(O, 1))
Vt by -E-EE/ -E Vt h G I f: bi b1:= Vt + /200,) -10 -n(Yt + to+G)}
(vt
(60)
Recalling that 0+ is bounded and bounded away from 0 (without loss of generality we can assume E < 1/2) and 8, Wt/k-s grows with n, k so that 77s (Vi/k+ Ziz) Vi/k+ Zij -8 with high probability; hence [Be s| os(s) (as Zij o(s) with high probability). Noting that [Byl _ 2s, we get bo = s(1 + o(1) and bj o(s) (distribution on diagonal is different).
(ii) Case 2: u,4 - By similar reasoning, have [[B bo = s(1 (1))
We can thus rewrite
no (A,+) = (Vi- kbo) Uu +b, Ps + 1o(+)(++)++ + (BEBBB) (61)
where (Ps) if i= S and = 0 otherwise.
Next, we analyze the operator norm of . Let 2 (Zig) Sisn be defined as
Σ., (o,, 11mm.00 Z,,)1 Cloon).
(62)
for some constant C' > 0; we have maxijsn /z, < C'log with error probability at most exp(-c(log n) < n D for any fixed D > 0. We have 2 ne (). By Bandeira & van Handel (2016), there exists an absolute constant c > such that for every a > 0:
cu2
P (
oo 40 + u) S nexp
(63)
L
where
10 E/7 (Z1
02 max
(64)
max 6,55
120iloo C Clog
(65)
An immediate Gaussian calculation yields, for i
(o+ /- 4z. P(o 2 + s)dz S Cee- (/046)
(66)
for some constant C1 > 0.
Proceeding analogously for (o(o Zzz) and substituting in Eq. (63), we get ²² < n /21(1 + +)}. Applying Eq. (63) there exists an absolute constant C, C² such that, by taking C'k, with probability at least 1 exp(-ck'* -exp((=d2/(ooggn]]
(a, 21)lp s (Vvieexpp=>" - 32/((1 + s)) v Vlogn)
(67)
31

---

Published as a conference paper at ICLR 2026
< c(k kv Vlogn) I Ck.
(68)
Note that the error probability is at most exp(-ck), because we already know that & >> (log n)²
Lastly, consider E[ By Eq. (59) we know that the entries of this matrix are independent with mean 0 and bounded by 2s, hence subgaussian. Further only a k x k submatrix is nonzero, so that
B - B
B|)p, CiVks,
(69)
with high probability (for instance, the operator norm tail bound above can be applied once more, which gives an error probability of at most C Cexp(-ck) for some absolute constant C, c 0).
Summarizing, proved that
No mo(Ai.+) (Vt- kbb) uu T + +A,
(70)
A lop S C(k vis) S C'k.
(71)
where in the last step used k
> (log n)
Recall that vs denotes the top eigenvector of n/ (A,,-) By Davis-Kahan,
Ck
min ||0, aull S
(72)
AE 1-1,11
Vt kbo
SVl
Ck
(73)
Vi (1+
(
E,
(74)
where in (a) we used the fact that bo = + o(s) and in (b) the fact that 2 (1 + 8)A2 log(n/k²) k)²),
whereby we can assume 5 2 Cs for C' a sufficiently large absolute constant. Recalling the definition of the score 0y:
ē. A.. 22 = Vtu(u, vx) + +a_ We, where we know that G = We, ~ N(O. I,) by independence of W and vy. Assuming to be definite that the sign of the eigenvector is chosen that the last bound holds with +1, get that (us v2) 2 e²_ We get that for every j E S:
t 1o-16,]12(11)))
_ t C
Uj > 21, 5²)
logn n
(75)
k
" < t - (1 - 2²) / Go, s -(1 - e²)
+
log
(76)
k
where union bound to get |Gyl I C'logn for all < n. with probability at least 1 exp(-c(logn)) )) Similarly, for all i $ S
| oa
logn
These calculations reveal that: (i) the entries with the largest magnitudes are the elements of and (ii) if u, and हt, share the same sign for all i E S. On this event, | () 2=| O.
Lastly, claim that the top eigenvalue of (A,,+) is larger than h + vt/s. From triangle inequality applied to Eq. (61), we have
A (Ar ))
(Vi kbb) bi (1n 2) BE-]BBB].... op
(77)
IS Iv3 IE
(Vt (1 (1+ -C---kks
(78)
Vi - (1 + Coe)ks
(79)
eks.
(80)
Here (a) follows from Eqs. (68) and (69), (b) because h: > and 8 > 1 and (c) follows by
taking 8 > Ce for C a sufficiently large absolute constant. The claim follows because ks > k and 2) is super-polynomially small rate.
ks > Vl, and that
32

---

Published as a conference paper at ICLR 2026
L AUXILIARY LEMMAS FOR SECTION H
L.1 PROOF OF LEMMA H.1
We let B N(O, 1,2) so that W (B //2. For v E In, we have (v, We) (v, (v)
N(O, 1). We thus have, by Gaussian tail bounds and a triangle inequality:
P(ko.Woo) Wo)l C
n (+) k:
(- C²
[n
71
log
S
2 2exp
log
2
k:
Taking the union bound over v E 2n gives the desired statement, since the cardinality of this set (*)
L.2 PROOF OF LEMMA H.3
Using Lemma H.2, take --1144 say, and 0 41+6 8 for 5 no for some small enough co > 0, to get that
(0) 1/4
n 2/m) s &Cexp(-cnVii).
for some absolute constants
C,c>
We have the following identity, letting W ~ GOE(n, 1/n):
t, v1)² 8 (u, (>1 (y) W) 0 [111 w
By standard Gaussian concentration, we know that, for any > 0
P [(] llop 2 2) < (exxp(ccAA)))
In this incquality, we take
A
4 (0 + 11/ 2/n-2)
-2/1
Note that with v1 + and on (1), we know that + 1/0 ( so that A O(82)
if 8 2 n with & 1/8. Hence, by union bound on the two concentration inequalities,
IP (Amin (3) w) 2A)= S Cexp(-en-/3)
and on the complement of this event, we know that
41
(0), u)²
0 (
since = 2(1), and so (w,, u)] = 2(02).
M PROOF OF PROPOSITION F.
In our proof, we will use the following elementary facts.
Fact M.1. For any deterministic unit vector u, a unit vector is uniformly random on the orthog-
onal subspace to if and only if (v, u) = 0 and v a Qu for every orthogonal matrix Q such that Qu u.
Fact M.2. Let A be a symmetric matrix, and u a unit vector. Denote B,, wruu A, and let v(a) be top eigenvector of B.. Then f(a) = ((((),, u)) is an increasing increasing.funccion of a > 0.
Let u Uni Recall that A, = Viuu + VtW where W ~ GOE(n, 1/2).
We conduct our analysis conditional on u. Let v, be a top eigenvector of A. For
+
6),/ 2, (0, u) a.g. (1 + 8), so that with high probability (v, u)| 2 (6/(2VI 6). Fact O.2 to obtain the same result. By choosing such that 28
t > (1 + 22,
33

---

Published as a conference paper at ICLR 2026
y 0/(1 + d), we know from standard concentration of the alignment (Lemma F.6) that (0,, a)) 2
2e with probability at least (xp(-cn) for some c > 0 possibly dependent on (e, 6).
(U), u u
By rotational invariance of W, w. 10 (Ve, u)ul
is uniformly random the orthogonal
subspace to hence, there exists N(0, I,), such that
(In uu )g
we II wu }gll
Since II(I,, uu )gl| uug)gl
llg'll for some g' N(O, In- we have, for some constant 0,
v1 1gll uu
P (I,, uu
exp (-en)
Further, for every S S n,, we know that
((,, g) Vk
I((I, - uu )))aa)))==
Igal + ||//||00 Ku, g)و S lasl
We next show that, with the claimed probability, only few entries of w, can have large magni- tude. As a result, less than l entries of can be estimated incorrectly (with = 1 if < n/ log n).
Define é = In exp(-an, an n2/k]] 2 1 (with on sequence to be chosen later) and ( as the f-th largest value among the Igil's. s. We have
abs
P (1 g)l vnan) S exp (- 110k
2
Furthermore, from a union bound, we get that
2 naa
11
2nd on
[(0) 2
exp
V
k
em
2nd On
exp
h
2nd an
+ Elog n
+ +t).
exp
k
By definition, we know that l max (nexp(-an, an n/k), 1}. so that
2nan
n
2nan
nu
log
1 2
min flog n, on nn/k} - 2
k L
k
2k
as long as na, > k. This means that
2 2
(- 100
P
96
z
I exp
Vk
2k
Define the set
An(1) {i S n:
an
[wel 2 6
k
By the bounds above we have
P (1)n < 6 1) on - n -o00 na,
Suppose that (w,, u)) 2 also holds, and suppose without loss of generality that (v,, u) 2 2s. Then, we have (as long as 6/an (9/10)s)
(Vr, u)
6Van
s i S, sign(va) > 0,,
i S & A.(()) 0 mi
Vk
V
Vk
UU 4
6 /
e S,i & A,,)), u <0 U2s
+
<
iie sisin((v)) < 0.
Vi:
Vi
Vi
34

---

Published as a conference paper at ICLR 2026
Analogously, for i & S, & (t),,, we have
6 E
vk
and we obtain that at most & positions could be mis-identified.
Next, we show that the termination condition (Line 5, Algorithm 2) does trigger for each t 2 3 (with high probability). We write
+ Vi Viuu" B: BB 2/l
A.
2
From Weyl's inequality:
B: + B
(A 2 V1
2
From standard operator norm results for GOE matrices (as (B, + B/ GOE(n)), we know
that || (B, + (22/ S n with probability at least exp(-cni) -cn)) for some >> 0. Hence
A1 (A, Vt 2/n vt/2 n² >
We obtain that
( (c-1
nan 1-1 + exp
(-x) k ))
E [1 t) - x1|² ==12]=00 =0
=0(epp(n==>/6kk
where we picked an > ²² /64 satisfying the bounds outlined above. namely (i) 6 S 0.9E, and (ii) nan 2 k. Notice that na,/ >> log(naa, if na, >> k. and
1 S n exp( (aan n2/k).
N PROOF OF LEMMA I.3
Proof. By the Markov Property, know that max, 1 maxogist=1-4 l|w.l.. By Gaussian concentration, we have
worle
x
P max ||w]|F 0StStel1-f4
E max || ||
- exp
4(te+1 - te)
This be proven, e.g. by discretizing the interval [0, te+1 employing standard Gaussian concentration on vectors (then pushing r > oo). As the argument is standard, we omit the proof for brevity.
te] into equal-length intervals and
Now we bound E (maxogeste - [wo.ll]] martingale, that from Doob's inequality:
We know that w | is a non-negative sub-
E
max
1|w
< 4B||
- s 9(te+1 tz)n²
so that from Mauchy-Schwarg
[maxostStej1-te 1 ||m S S3 - Ten. Hence as 4 2
||00 -:,,,,;ll 2 41 45)le m S 2exp
n244
IP
max
65K54-1
The second tail bound follows immediately (at least, the proof would be analogous to the preceding display).
O PROOF OF PROPOSITION F.
In our proof, we will use the following facts; since they are elementary, we omit the proof. Fact O.1. For any deterministic unit vector unit vector is uniformly random the orthogonal subspace to u if and only if (v, u) = and v ~ Qu for every orthogonal matrix Q such that Qu- u.
35

---

Published as a conference paper at ICLR 2026
Fact O.2. Let A be symmetric matrix, and unit vector. Denote Ba v(a) be a top eigenvector of Ba. Then f(a) = (o(a), |
auuu A. and let is an increasing function of a > 0.
We suppose that t 2 (1+8) n/2 instead of (1 (1+ 8)n/2 for notational convenience. Let be unit vector of random signs generated from uniformly random set 5 C [n] of size k. Since scaling does not change the eigenvectors, we instead consider the matrix
A
E Vuuu
B (B.+BB)
t uuu Wn
Y
2/
where it is clear that v 2W ~ GOE(n).
We conduct our analysis conditional on u. Let Ve be a top eigenvector of Y, We know that vō
when & = =11 + 5)m/2, (v,, u) S. V V++8" so that with high probability (0,, u) 2
2vI+8
If & 2 (1 + 6)m/2, we can use Fact O.2 to obtain the same result. By choosing e such that 2 < / (5(1++)), we know from standard concentration of the alignment (Lemma F.6) that (we, u) 2 2: with probability at least exp(-cn) for some > 0 possibly dependent on (e, 6).
By rotational invariance of Wn. we know that vr ~ Qu, for any orthogonal matrix Q such that Qu We obtain that v, (vr; u/u also has this property, by Fact O.1, get that
D1 (V,, u)u is uniformly random on the orthogonal subspace to u. We can write, with |00 (v,, ull
N(0, I:):
(Ln uu gg
W0 I1(1, uu )gll
We first deal with the denominator. From triangle inequality, know that (I,,, uu )u > |gوl| - u gll = [g] - Ku, g)l. Since (u, g) ~ N(O, 1). we have from standard sub-cxponential concentration Iglil that
[[L,, -ia--uujn
wu vu))gl= S
exp (-on)
for some constant 0. For every 1 I i n, we know that
ku, g)
I((In wu }g); < 1gil + |///|o0 Ku,, g)و S 19:1
Vk
Define 8 = |neexppaan n/k)] 2 1 and g(t) as the E-th largest value among the lg.l's. We have
P (((u,,)) g)1 vnan) S exp (-12)
700
Furthermore, from union bound, we get that
P
g(E)
ahs
2 Taa
12
exp
2nl
en
exp
2nl an
exp
2né an
elog +e
Vi
k
k
By definition, we know that E 2 max {n expeppaa an m/kk) 1}. so that
2nan
n k log
2nan min flog ni, an - -1/k) - 12
7a
k
as long as nan > k. With probability at least exp(-cn)= - exp(-nan./h nnn//k) exp( /n),//2), have that at most L --1 positions i in "bad" set A have |wal 6 6//n/k k. Suppose that (u,, u)l 2 2e also holds, and suppose without loss of generality that (ve, u) 2 22. Then, we have
(vt, u)
6
ie S & A, u;
+ Die S, sign(vw) >
Vk
VI
VK
i S,i 4 A, < < 24 5
6
<
E
+ +i S, sign(vw)) <
VT:
V
36

---

Published as a conference paper at ICLR 2026
long ay < 3z/4, say. Analogously, for i & i & A, we have
Oid - 6yan
Vk
and we obtain that at most L positions could be mis-identified.
For completeness, we show that the termination condition (Line 5, Algorithm 2) does not trig- ger for each 2 n² (with high probability). We write
A: Y: + y
( B, BB++Bi 2/
Vtuut
2v
From Weyl's inequality:
(A)) 2 Vt - B: + B.
2/t
From standard operator norm results for GOE matrices (as (B, + B/)/ GOE(n)), we know
that || (B, + (2 & 2/70 with probability at least - exp(-cr)) for some c >> 0. Hence A (A,) 2 VI - 2 v1/2 as 2 n² >>
We obtain that
l (1-11 + exp (- Rich )
[1in(y,,)) 22 =
O (exp(-an n/kh)
where we notice that na,/ >> log (og(nan//) if na, >> k.
P PROOF OF LEMMA F.3
By Gaussian concentration, we have
x
P
max 0515t141 t,
| -
max 0515644166
[WWlloo 2 x
S exxp
2(1
This can be proven, c.g. by discretizing the interval [0, te+1 - te] into r equal-length intervals and employing Gaussian concentration vectors (then pushing > oo). As the argument is standard, we omit the proof for brevity.
To evaluate E|maxosist4114 W Welloph we recognize that |Wellop is submartingale, that from Doob's ' inequality:
E
max 05156+1-44
[Wallep < 4E [I[W te41 [
Once again from Gaussian concentration,
-I2
P W llop - E|]l Wi [lo]] 2 x) 2exp
so that IP (II) W tea1 -2 1lop lp Blll W W 2 x) < 2 2xx (-22/(2(te+11)0 -t))) Hence
WWeii-telll is (1--1 (0) subauuaaannn,,, implying that Var( W llop) S 6(le+1 - Le). As
[[[ Weeer--n (lppp)
4(le+1 te)n (one can obtain this from the Bai- Yin Theorem along with
sub- babggaussianity, for instance), we get that E [ < 16(te+1 tz)n eventually as n gets large. From Schwarz inequality, we get that
I|Wollop] < 18 linn
max 0S1St441-
We conclude that
max 0S15te41-1
WWlloop 2 16 (1/+1 - -()m)
22exp (-32n)
37

---

Published as a conference paper at ICLR 2026
PROOF OF LEMMA F.4
First, by orthogonal invariance of Wt, we know that ie uniformly random over the unit sphere gm-1 We can write, using ! N(O, I,), the following representation
9
9
As in the statement of the Lemma, we define the following set. for IR" and C' >> 0:
A(v;C) i: i:lsisn,lul Cvlog(n/h))
vn
As with the proof of Proposition F.I, we first deal with the denominator exponential concentration gives
||g||: indeed, sub-
P
0 1=1
n
<
2exp((nn/8)
(81)
2
This leads us to define another set
B(g: = - iisiii 2 C Collog(n/
Let Pn. = P(lgi Coloo(n/kk)), then we have [[g C)I Bin(n, Pn). From Gaussian tail bounds, we know that Pr. I /2 We now use a Chernoff bound of the following form: for every 2 [E], where X Bin(n. (n. p), then
F(X 2 x) S exp (-z/3)
It is clear that np, < k2/n I max 3// /n, vk) when C > 2, so that we have
p ( C*I 2 maxt kk,k2/m)) /m)) exp (-
km)) s exp (-1
Therefore, with each fixed t. by union bound with probability at least O(exp(-Vrt) have, for possibly different C 0, A(u;; C)I & max Vk, k² ///).. Our proof ends here, as max Vk, /n] < k/2 for vn < < n.
R PROOF OF LEMMA F.5
We know that
0. T Wi, W.O: - 1i (W, W.)o
=XI(W,; v,(W. Wr.o.
=Wi(W,,)) of (W, W., (Ai(W,) - \wW)))
from which we obtain from Weyl's inequality that
sup &S150
0. W,,,, D2 (W.) 2
sup 4gg1s0+1
IW Weolop 322 /(141111111111 4z)n
with probability at least 2exp(-32n)
S PROOF OF LEMMA F.6
By Weyl's inequality, W + >1 (Y (with Y = SouT + W) is 1-Lipschitz function and therefore,
by Borell inequality (and Baik al. (2005)), letting (x) == 0 + 1/0, for any E > 0.
((AI(( X. xx) > a) < 2e n
(82)
38

---

Published as a conference paper at ICLR 2026
To prove concentration of (w) (Y), u)?, note that simple linear algebra yields (v) (Y), 0/2 = (0,
(83)
It is therefore sufficient to prove that F(W) concentrates around value that is bounded away from Fix Eo > 0 such that 2 350 < (0) and define the event
: [W: Wlp S so, |1 Am S =
(84)
By the Bai- Yin law and Gaussian concentration (plus the above concentration of x1). PPE) 2 ) for some c(e)) > 0. Further, it is easy to check that F(W) ) is Lipschitz on E, whence the concentration of (u, vn (W))² follows by another application of Borell inequality.
T PROOFS OF REDUCTION RESULTS
T. 1 PROOF OF THEOREM
We state and prove more detailed version of Theorem
Theorem 4, Assume that . has complexity x. and that for any S 0d, PP (PT S
T.A
(where PT.A is the continuous time process obtained by Brownian- interpolation of Eq. (4)). N
Then for any o > there exists an algorithm with complexity O(x . T/A),, that takes as input N(O, I), and outputs &. such that
y og. (z,g) g)
E||Pa øly Pl S 2 + Eo =
(85)
where (o = ElP N(O, La) PalulITv is the expected TV distance between Paly and the convolution of Payy with Gaussian with variance 1/(d).. As consequence, there exists randomized algorithm my+ with complexity X-xTTAB that approximates the posterior expectation:
(l (z) ) mz) (1) 23 +2
(86)
Proof. The algorithm consists in running the discretized diffusion (4) with initialization Vt. = =y/o² at t = to == 1/o". To avoid notational burden, we will assume (T to)/ to an integer. Let 97, be generated by the discretized diffusion with initialization at ÿo t 0. Note that the distribution of ÿt. is the same the one of lox + Vig and hence by Assumption (b), and Pinsker's 's inequality
|PPro - Po; || S V 22 DKL Dea(Por, oi, (1 s Dm
(P T.A (PT)
S
V
E
(87)
Hence it. 0%, can be coupled so that P(úr, * vt,)) S Ve/2.
We extend this to a coupling of (0) ). and (Wr)oSSSTT in the obvious way: we generate the two trajectories according to the discretized diffusion (4) with the same randomness é. Therefore T..... [IP()) < and Pinsker's inequality yields P(yr # / S ve/2, for yr Tx + VTg' with (z,g') a & N(O, We conclude by triangle inequality P(yr * ûr) I 2///2, which coincides with the claim (85).
F(JT + 9T) I Ve/2. Another application of the assumption DRL. (P
Finally, Eq. (86) follows by generating N i.i.d. copies 21...., Ey using the above procedure, and letting myy be their empirical average.
T.2 PROOF OF THEOREM
The next statement makes a weaker assumption on the accuracy of the diffusion sampler (transporta- tion instead of KL distance), but in exchnage assumes the approximate drift m to be Lipschitz. We note that Lip(m(- ., t)) = sup, [[Cov(x) y/ = y) lop. and the latter of (1/dd) (for instance) if the coordinates of weakly dependent under the posterior.
39

---

Published as a conference paper at ICLR 2026
Theorem 5. Assume that m has computational complexity x and satisfies the following: (a) For every 2 1/0², y + myyyt) is L/d-Liishhit (b) There is a stepsize such that W Wi(P p S E for any T S 0d.
there exists an algorithm with complexity O(x T/A), that takes input y x + og. (x.g) na s0 N(O, 1), and outputs G. such that
Then for any
1
(lly. S 22
+
V0 =:E.
(88)
As consequence, Eq. (13) holds also in this case with the new definition of
The algorithm consists running the discretized diffusion (4) with initialization Dt, = y/o² at f = tu == 1/o². To avoid notational burden, we will assume (T - to)/ A to be an integer. Let yi. be generated by the discretized diffusion with initialization at ÿo at / O. Note that the distribution of Stg is the same the one of tg + vig and hence by Assumption (6).
W (P Sig Pær,) S W (P T P7. E
(89)
In other words there exists a coupling of 0%, and St, such that Eliir, 0t.112 S.
We extend this coupling (Ør SEST and (gr) SEST in the obvious way: we generate the two trajectories according to the discretized diffusion (4) with the same randomness 2, A simple recursive argument (using the Lipschitz property of m, Assumption (a)) then yields
Dr S 1311(1+18) (1+ T/A B 1
ES e
(90)
(See for instance Montanari & Wu (2023) or Alaoui et al. (2023) for examples of this calculation.)
Let now yr 4 Tx + vT'g' for (x,g') μ & N(O, I). Another application of Assumption (a) implies that this can be coupled to D7 so that E yr ø7 I E. and therefore
B yr ll < 2 LT/dg.
(91)
As output, we return å ÿr /T. Using Elyrr
x1| Ellg /VTllVVT and T Od,
x - -|| < 2e OL
+ /0
(92)
Since the coupling has been constructed conditionally y, the claim (88) follows.
Finally, Eq. (13) follows by generating N i.i.d. copies 01,... &n using the above procedure, and letting myy be their empirical average.
U PROOF OF LEMMA H.1
We let B N(O, I,2) so that W (B + BT)/2. We consider a non-random vector v fitting the description, and note that
(0. Woll 1 (10 Bv) + ((v BTb)]}
We know that (v, Bv), (v. BTD) ~ N(O. 1). We thus have, by Gaussian tail bounds and triangle inequality:
P (v. Woyl 2 C log
"1 (*) < 2 exp
(- log
C2
)
71
k
Union bounding over the set all such vectors gives us the desired statement, as the cardinality of this set is 2
40

---

Published as a conference paper at ICLR 2026
V PROOF OF LEMMA H.3
Proof of Lemma H.3: Using Lemma H.2, we can take x = n n114 say, and vI+d for
5 = On (1), get that
((A(()) 50 n 2/n) - C eexp(-ont/2)
for some absolute constants C,c> 0.
We have the following identity, letting W GOE(M, 1/n):
1
u, 01 2 (u, (A1 W) u 2 8² ( -
By standard Gaussian concentration, we know that
P ([] op 2 2 a) S C -cnx
We take
0 1/0 n 1/4 2/n
Note that with 0 = V and = (1), we know that 0 + 1/0 - = =0(3)), so that x = O
if 8 >> n 1/88 Furthermore we have, by Theorem above,
P (AmminAA1 (A1 w) s 2x) I C Ceep(-cc!!"
and on the complement of this event, we know that
4r O(8*)
(U1,
02
since 0 = 2(1), and so (e),, u)) (20²). Hence we are done.
W PROOF OF THEOREM 3
The optimality of mn with respect to scalings em implies, by Pythagoras' theorem: Blllm(g: () æ= [[] (lllm ()1),
whence, using assumption (16), we obtain that
sup (E(11>)fag
Elllm 0)1 = o((_5))
(93)
Recall that (j:) is the generated diffusion, defined in (q.(4). From Girsanov's formula on [0, (1 tatge we get that:
KL (ww))eaaa, (l (aaaa
Σ
([(m))))))) o(1)
2
IENAn(O. (1000.11-)5000 mad
From Eq. (98), get from Markov's inequality that with high probability,
A
Σ
| = (0)
| = olyt))))
AENAn(O. (4 Fag
where (a) follows by Cauchy-Schwarz. By Pinsker's inequality on Eq. (99), we obtain that the same event holds for (9t) with high probability:
Σ
t) = ol Tate)
(ENAN (ggg
Fix constant Eg > 0 to be chosen later. By taking the constant 7 to be close enough to 1, get
that for ts == min(2 (AA L 2 8)tma))
jt. = Bi, +A
Σ
(,, = B
1ENAn(0,6]
41

---

Published as a conference paper at ICLR 2026
with P([|moll 2 Entaia) o(1). Next couple (g) : tb) to (il tc) defined by letting Vi = Bi, and, for E NA n [to, 00),
Ue+ V. + m +) + Bi+ B..
By the assumed Lipschitz property rn and Gromwall's lemma:
(1 CA
1 - -9:1-
II
||mol
d'ENAn(tua)
moll
S C"En
(94)
Ealg
where the last inequality holds for some absolute constant C' and all / < Clag on the high proba- bility event |mmlll
I Egtaig-
We are now in position to finish the proof of the theorem. We couple the process (0) : t 12 to)
defined above with (B, t 2 tb) get
KL (L(B+alll++a & (L(B CB, A
Using KL(B,,, l 0, summing the last inequality over l. and applying Pinsker's inequality we obtain, with C' suitably large constant
sup (eNAn)aag(++0)))
TV( B.) = o
(95)
as long as
Σ
B[ m B 1)] o(1)
Consequently, by using the function m, along with Eq. (15), get that for some C, on),),
sup rENANIfa
PI f)ll 2 Cx) o(1)
Putting together this bound and Eq. (94) (which holds with high probability) we obtain from the Lipschitz property of m.
max (f
( 1)I 2 so) o(1),
(96)
(we absorb Co from Eq. (94) into so/2 is arbitrary). Hence
inf rElfag Cl))
Wi Wi t), 2 co o11
By taking 0, we obtain the claim of the theorem.
X PROOF OF COROLLARY 5.1
In order to simplify some of the formulas below we center Pn,ke Namely, we redefine fo,, to be the distribution of æ = uu. E[uuT] when u ~ Unif B,,,))
Throughout this proof, C' denotes generic constant which depends on the constants in the assumptions, and is allowed to change from line to line. We will write E,, for expectation under Mn.k and EE for expectation under 7 = 1, 1500 Further y: = t WW, where the distribution of x is either Hn,, or Pa.k as indicated.
The optimality of m. with respect to scalings cm,, implies, by Pythagoras' theorem: E m (y:,4) !) 2= } = [[ B{ ( (y:. 1)
(y::
whence, using assumption (16), we obtain that
sup
Biilmm, (yi, +) on 11
(97)
5 (1(1))
42

---

Published as a conference paper at ICLR 2026
By Law of Total Probability, we have
1 2 R. Boman. (y: ()]13] 2 Bllli We: ()13)
E Bll (3t, 1)11]]
from which we get
sup mi m.n (W (2,t))l9] on (n (S(1-7)41g
(98)
From Girsanov's formula [0, (1 Hatel we get that
(e (ttp://..___.allloooeeeeaaaaaa.. KL (WW (W..)exsanoo.uu--W.a))
A
Σ
E m. (W,, (),
on
1ENAn(0(1111)a)))
(99)
due the fact that Eai n/2. From Eq. (98), we get from Markov's inequality that with high probability,
A
Σ
m. (W,, (1)
A
Σ
t)ll on(v)))
BENAN 774gl
(ENANjO(11-)4a))
where (a) follows by Cauchy-Schwarz. By Pinsker's inequality on Eq. (99), we obtain that the same event holds for (g:) with high probability:
A
Σ
(er, on (v)).
2
AENAnDo. Mat
Fix a constant Eo > 0 to be chosen later. By taking the constant 7 to be close enough to 1, we get
that for to == min fA 2 (1 ))
U = Bd, + A
E
(.. = my + B
(ENAN(0.4)
with Po|mm 2 Enn) (1), and (gt) is the generated diffusion, defined in Eq,(4). Next couple ( 2 to) to (u) t 2 to) defined by letting df, = BB, and, for E NA n [to, o0),
Ults df + m. t)A + B++ Br.
By the assumed Lipschitz property of m and Gromwall's lemma:
(1+ CA ||mol
1/ - 9 S
II
('ENAn(4.4)
moll S C'ean,
(100)
Eagg
where the last inequality holds for some absolute constant C' and all < On (2C)) the high probability event ||mol| S en..
In order to finish the proof, state and prove useful lemma. In nutshell, m. resists improvements from eigenvalue hypothesis tests:
Lemma X.1. Under the assumptions of Theorem 5.1, assume that 8, vanishes slowly enough. Then, for Z (1 + aag
(B., < Ce (Vi- /Ca
(101)
Proof. Let (1(1)) be the maximum eigenvalue of (y,, yT)/ 12, x. /2(Vi= + Vlny 2 and o(yr) = 1(A1(Hr) > (t)... Concentration results about spiked GOE matrices imply, for all
t 2 (1 =ttt
Pr. (o(v)) = =0) < Ce nlvi noo-ti- IC P(O(B,) =) < C eeepp - - (Vi - v (aag
Cn
(102)
43

---

Published as a conference paper at ICLR 2026
(To simplify notations, omit the dependence of & on on t.)
By assumption, the MSE of mn (31,,) t) is not larger than the one of m, (y.. ())().) Letting ((y) == ((y)): Elllmi(ye 1) 2= < { (yr, ()(()))))))))))))))))))))))))( ==1?
EE' { -) x(]()(y)) [ (
() =x((((m))) PL, (p( 0),
(103)
whence
B(Ilm((ye 6) = x1 ((y1) s PP 0)
(104)
On the other hand
- E [[] my 1)11
2 B m B, ((
BBllinnB (B, 0 - (o(, =
(105)
Putting together Eqs. (102), (104), (105), we obtain (eventually adjusting the constant C)
B (B, }) - (()(B,) = 1) + PP.M ( 0)
S C exp { _ (Vi v (ine'))
From Lemma X.1, Condition 2 of Theorem 3 is satisfied. Hence we are done.
Y DETAILS OF NUMERICAL SIMULATIONS
Our GNN architecture uses node embeddings that are generated by 3 iterations of the power method and message passing layers. Each message passing layer comprises of the 'message' and 'node- update' multi-layer perceptrons (MLPs), both of which are 2-layer neural networks with LeakyReLU nonlinearity. We simply use the complete graph with self-loops for node embedding updates. We find that 'sediing' the node embeddings with iterations of power method is crucial for effective training.
During training of the denoiser, sample time points t follows: choose time threshold t,, and sample so that times t t, are picked with total probability 0.95 (and times S f, are picked with total probability 0.05). Within each interval (0, f.] and (f., T), times chosen random. This allows the neural network to initially prioritize learning in a low-noise regime. Several fine- tuning steps are taken, for which is gradually decreased refine the network on lower SNR.
Empirically, training directly with 10 layers difficult, due to its depth. We find that training initially with layers, then subsequently introducing the later layers results in more stable training.
We train such a network using N 30000 samples æ; from the distribution Th, and evaluate their MSE on Nest 15000 samples.
44


Reviews:
[{"review_id": "tboayvAnIf", "reviewer": "Reviewer_Bgxf", "summary": "The paper's primary contribution is to rigorously prove that a computational bottleneck, not just a statistical one, limits the power of denoising diffusion models. The authors prove that not all easily-sampled probability distributions can be efficiently learned by these models. They construct a specific counterexample based on the sparse submatrix estimation problem, which is conjectured to be hard. This shows that even a nearly-perfect, efficiently-computed drift function will fail to generate accurate samples, thus identifying a fundamental gap between what is statistically possible and what is computationally feasible for this class of generative models.", "questions": "1. Would considering the 'average complexity' via diffusion over a class of easily-sampled distributions be more meaningful than focusing on 'bad' extreme counterexamples like the sparse submatrix prior?\n2. Do your have conclusions about the training procedure in this paper, or does it imply that for the provided counterexample, the training of diffusion models will always fail due to its inherent computational hardness?\n3. Is it possible this specific computational bottleneck is just an artifact of this particular formulation of diffusion sampling, or does it represent a fundamental hardness that alternative generative models like flow-matching models could not bypass?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper's core strength is its novel perspective, shifting the analysis of diffusion models from standard statistical limits to the overlooked statistical-computational gap.\n2. The authors construct an excellent counterexample using exactly the sparse submatrix estimation to provide a distribution that is easy to sample from directly but computationally intractable for a diffusion model to learn.\n3. Supportive simulations clearly validate the theory, showing that a computationally-bounded diffusion model fails to generate accurate samples from this \"hard\" distribution, just as the authors predict.\n4. The paper's argument is mathematically rigorous, employing formal, well-established proofs.", "weaknesses": "1. The paper's organization is not straightforward; the structure is relatively loose, which makes the argument hard to follow.\n2. The planted clique counterexample feels specific, which makes it difficult to connect this theoretical computational bottleneck to the broad success of diffusion models on real-world data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "F2es72Gqzk", "reviewer": "Reviewer_uMuZ", "summary": "In this paper, the authors study the feasibility of sampling with diffusion models. More precisely, they are interested in answering the following question: \"Are there distributions such that, there exist almost optimal denoisers that can be computed in polynomial time and for which diffusion sampling fail?\" They answer this question by the affirmative. The paper proceeds as follows:\n\n* In  Theorem 1, they show that for any arbitrary polynomial time denoiser which satisfies two generic assumptions, there exists a modified denoiser for which the diffusion sampling fails. In Corollary 3.1, they apply Theorem 1 to the case of sparse random matrix measures. Other sparse examples are considered \n\n*  While Theorem 1, shows that \"good denoiser does not imply good sampling\", in Theorem 2 they show that \"good sampling implies good denoiser\".\n\n* In Theorem 3, they show that under an additional Lipschitz condition, the results can be strengthen to show that *any* polynomial time algorithm which is nearly optimal for the denoising task will lead to poor sampling quality.\n\nThe authors conclude the papers with toy numerical experiments.", "questions": "* \"l. However if such drifts exist, our results suggest that minimizing the score matching objective is not the right approach to find them (since the difference in value with bad drifts will be superpolynomially small).\" (l.186) This is an interesting remark. There is some evidence that diffusion models fail at approximating the score. First, they are trained on the empirical measure hence the target distribution is the \"optimal\" target gives a fully memorizing denoiser.  Second, due to neural network approximations they often fail to correctly approximate the true denoiser. I would be keen to understand how the authors deal with that intrisic limitation of diffusion models and how this would affect their analysis. \n\n* In Proposition 2.1., I do not understand why we can have equality to 0 in (ii).\n\n* Could you provide more details regarding the construction of the drift in Proposition 2.1? (the construction of a drift which is a bad approximation to the true denoiser but gives good diffusion sampling results). \n\n* Before Theorem 1 I think it would be worth providing just a few sentences regarding the validity of Assumption 2 and Assumption 1. At this stage it is very much unclear for the reader if those assumptions are easy or not to satisfy.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "* The paper is theoretically strong. I have to command the quality of the writing (apart from the introduction of diffusion models and some notation choice discussed in the \"Weaknesses\" section). Even though I am not a domain expert on stochastic localization and random matrix theory, the paper was pleasant to read and the ideas clearly exposed. \n\n* The results presented in the papers will be of great interest for the theoretical diffusion model community. Those results indeed fill a gap in the literature regarding what can be achieved with diffusion models.", "weaknesses": "* One of my main pain point with the paper is the choice of following the notation and convention of [1]. While I understand that it might be easier for the authors who seem to familiar with the techniques developed in [1] to build their theory on top of this framework it severely limits the adoption of the work, as it has to be translated back into \"classical\" diffusion model framework (see [2, 3, 4] for a (non-exhaustive) list of papers which adopt the classical diffusion model convention). The burden of the explanation and communication should be on the authors and not on the readers.\n\n* In my opinion, the strongest result is Theorem 3 but there is little discussion on how realistic is the Lipschitz assumption the authors consider. I found Corollary 5.1. to be very hard to read. To come back to the Lipschitz justification I am not sure I understand the following sentence \"We assume the Lipschitz constant to be C/t, because the input of the denoiser is yt = tx + Wt, and hence the two t-dependent factors cancel.)\".\n\n* Something that is unclear to me is the generality of the results presented in the paper. While Theorem 1 is very general it is not quite clear to me how to apply them beyond the sparse random matrix measure studied by the authors. In particular, I am wondering how specific those results are. To further specify my question: is (one of) the contribution(s) of the paper 1) the identification of a set of measures under which the assumptions stated in the general Theorems are valid thereby showing some limitations of diffusion models 2) the statement that most data distributions (even the ones considered in practice) fall under the category of the general Theorems thereby showing the much more stronger statement that diffusion models are flawed. It would be good to clarify  the scope of the paper in that respect. \n\n[1] Montanari (2023) -- Sampling, diffusions, and stochastic localization\n\n[2] Conforti et al. (2024) -- KL Convergence Guarantees for Score diffusion models under minimal data assumptions\n\n[3] Li et al. (2024) -- O(d/T) Convergence Theory for Diffusion Probabilistic Models under Minimal Assumptions\n\n[4] Chen et al. (2022) -- Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nHJ3pLdYZn", "reviewer": "Reviewer_6LQL", "summary": "This paper addresses a very interesting question: Can denoising diffusions efficiently sample from any distribution $\\mu$ for which sampling is otherwise tractable?\n\nThe paper presents a rigorous negative answer by showing that diffusion samplers inherit the computational hardness of the underlying denoising task. The core mechanism of diffusion relies on learning the drift term $m(y,t)$, i.e. the Bayes-optimal denoiser. If this denoising problem exhibits an Information-Computation Gap (ICG), a regime where the statistically optimal error is low, but no polynomial-time algorithm can achieve it, then the authors show that diffusion sampling based on score-matching must fail.\nThe paper includes several key theoretical results.\nTheorems 2 \\& 5): Efficient diffusion sampling implies efficient near-Bayes-optimal estimation. The contrapositive confirms the central thesis: computational hardness in denoising implies diffusion sampling fails.\nTheorem 1: The paper proves the existence of polynomial-time drifts that are super-polynomially close to the optimum (among poly-time algorithms) in the score-matching objective, yet produce samples maximally far from the target $\\mu$ (in Wasserstein distance). So the standard training objective is insufficient and potentially misleading when an ICG exists.\nTheorem 3: The paper shows that any poly-time, near-optimal drift satisfying a mild any \\emph{Lipschitz} near-optimizer fails to sample correctly. Furthermore, \\emph{Corollary~5.1} provides a concrete sufficient condition: a $C/t$-Lipschitz drift fails when $t \\ge (1+\\delta)\\,t_{\\mathrm{alg}}$.\n\nThese results are illustrated using the sparse PCA model where sampling is trivial but denoising is conjectured to be hard below a threshold $t_{\\mathrm{alg}}$. Empirical results show that the diffusion process produces degenerate samples.\n\nThis work is very significant. It goes beyond analyzing statistical generalization or discretization errors, identifying fundamental limits of denoising diffusions.", "questions": "Alternative Objectives: Proposition 2.1 suggests that score matching is the root cause of the failure when ICGs are present. Does this motivate the development of alternative training objectives for diffusion models that do not strictly enforce denoising optimality, particularly at low SNR (small $t$)?\n\nOptimization: Theorem 1 implies that the score matching loss landscape possessing near-optimal solutions (in the poly-time class) that are bad for sampling.  Do we know anything about whether standard optimization methods are likely to find these bad near-optimizers rather than potential good ones?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Originality. The paper goes beyond the previous analysis of diffusion samplers devoted to KL/Wasserstein bounds or generalization arguments. It provides an interesting computational perspective. In particular, it identifies the information-computation gap as the key problem for correct diffusion sampling; it shows that even near-optimal score-matching drifts (among poly-time methods) can sample the wrong distribution and it establishes reductions from diffusion sampling to denoising.\n\nQuality: Theorems 1--3 are stated with clear hypotheses, and Appendix proofs are thorough. The proofs are relatively easy to follow given the technicality of arguments.\n\nClarity: The paper is well-written. Assumptions specifying the ICG gap are stated clearly. The paper separates neatly the main conceptual arguments in the main text from the proofs. The figures nicely illustrate the theoretical claims.\n\nSignificance: This is a very interesting paper explaining when diffusion samplers fail for computational reasons—even when sampling from $\\mu$ is itself easy. They also specify when positive results (which rely on accurate scores or favorable distribution classes) do not apply.", "weaknesses": "Dependence on assumptions: The main results depend on Assumptions 1 and 2, which do not hold unless an ICG is present. This aligns with predictions for models like Sparse PCA, the underlying hardness remains conjectural in the general case.\nIt would help to map Assumptions 1 and 2 to specific hardness conjectures in the literature.\n\nRobustness of Theorem 1: Th 1 shows that sampling can fail when the drift is $O(n^{-D})$ close to the optimum among poly-time algorithms. This is a fairly stringent definition of near-optimality. How robust are the results to this assumption? even an heuristic argument would be good. \n\nConstruction of the Drift (Theorem 1) The drift $\\hat{m}$ constructed to prove Theorem 1 is somewhat artificial. While this demonstrates the insufficiency of the score matching objective, it does not demonstrate that such deceptive drifts arise naturally during standard training procedures (e.g., gradient descent on neural networks).\n        \\item \\emph{Actionable Insight:} Discuss whether standard optimization dynamics are likely to find these specific deceptive local minima, or if this is primarily an existential proof. Are there architectural choices or regularization techniques that might steer optimization away from these solutions?\n    \\end{itemize}\n\nLipschitz assumption. Th 3 establishes a negative result for Lipschitz drifts, specifically requiring a $C/t$-Lipschitz condition for $t \\ge (1+\\delta)t_{\\mathrm{alg}}$. However, non-Lipschitz drifts might succeed.\n It would be good to clarify whether this Lipschitz condition is key to the failure of just a technical requirement. Are the typical architectures used in practice (e.g. your GNN in section 3) satisfy this specific $C/t$-Lipschitz property?\n    \nApplicability of the results. The analysis focuses on distributions where the ICG is well understood, e.g. Sparse PCA. How are these findings translate to standard distributions meet in physical systems; e.g. Lennard-Jones or \\phi^4? \nIt would be beneficial if the authors could discuss even informally the characteristics of  distributions that might lead to a ICG. \n\nMinor point: The authors follow a non-standard presentation of diffusion models (the one originating from stochastic localization). I know this is equivalent but i think it hurts the readability of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)