- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies the expected number of queries needed to sample, at prescribed TV accuracy, from a family P_θ, using an oracle that returns a normalized smoothed score at one scale shared by all coordinates, corrupted by fresh Gaussian noise of precision at most B. Theorem 1 gives matching rates in three precision regimes for two product families. The main result, Theorem 3, shows that two Blackwell-equivalent placements of m spatial coordinates have optimal costs differing by a factor \sqrt{log m}.
Critical strengths
The upper and lower bounds match, and the lower bounds cover adaptive protocols with random stopping. The block-wise witness converse and the chi^2 cancellation under shared activation are careful arguments that may apply elsewhere.
Critical weaknesses
-
No realistic experiments, and no motivation for the ICLR community. The paper frames its results as statements about the cost of score-based sampling but provides no evidence that they hold in practice. The paper contains no experiments with a trained diffusion model or with realistic data such as images. In particular, it does not test whether the effect it predicts, that sampling cost depends on how the data’s features are spread across scales, appears in practice. Even within the model, no simulation shows at what dimension the \sqrt{log m} separation becomes observable. The paper also does not explain why the problem matters to the ICLR community or which design choice the results inform.
-
Limiting target class. Theorem 3 concerns m rescaled copies of one weakly perturbed one-dimensional mixture, padded with known coordinates independent of θ. All targets are products, which excludes the dependence across scales that characterizes practical multiscale data. The lower bounds extend to larger target classes, but the separation does not, because its upper bound relies on product structure.
Questions for authors
see my comments above
2 comments
Weakness 1: Theoretical contribution, sampling design, and finite dimension
Thank you for asking us to clarify the contribution and its relevance to diffusion sampling. This is a theoretical paper on the query complexity of sampling from noisy scores. For two explicit target families, we characterize how scale layout and observation precision determine sampling cost through matching lower bounds and explicit sampling constructions under an oracle with fresh independent Gaussian observation noise. Experiments with trained image models would address the complementary empirical question of whether and how this mechanism manifests in learned samplers, beyond the scope of the present theoretical study.
Evaluating a vector at a common noise level is central to diffusion sampling, and reducing the number of evaluations is the objective of methods such as DPM-Solver. Section 1 connects our normalized score to noise prediction through .
Theorem 3 isolates the effect of scale layout on sampling cost. Dividing spatial coordinate by its public radius changes a common smoothing scale into the relative scale . Under the theorem's precision and spacing conditions, clustering active radii lets one query serve several coordinates, whereas sufficient separation prevents that saving. This changes the optimal query cost while preserving the complete target experiment, ambient dimension, precision cap, and average TV requirement under the uniform prior. The lower bounds allow adaptive queries and random stopping, so the result applies beyond a particular solver.
Two existing results make the design connections concrete. Proposition 14 allows a separate smoothing scale in each coordinate of the Fourier construction. With this modified interface, sufficiently large constant normalized precision depending only on the fixed spacing parameter permits exact generation in one query. Corollary 13 considers both target families without a precision cap: for each positive relative price of cumulative observation precision, a suitable precision held fixed across queries attains the optimal order of the combined cost of calls and precision. Thus the analysis addresses the choice of a shared noise scale and the allocation of observation quality. Representation choices also have a practical precedent in the wavelet conditional model of Guth et al. (2022).
For the finite dimension question, Section 5 gives a concrete asymptotic separation. Its parameter sequence fixes and a sufficiently small relative TV tolerance , takes , and , and sets . Both layouts have ambient dimension . For sufficiently large , their optimal costs have orders and , with comparison constants depending on . These asymptotic rates do not specify the first dimension at which the gap becomes numerically visible. Figure 1 illustrates the theory schematically. Appendix I supplies the clustered construction's expected cost , where the integer must satisfy its precision feasibility condition and is chosen for the prescribed joint TV error.
Weakness 2: Why the controlled product construction is informative
Thank you for asking about the role of the target class. The product construction enables a controlled comparison of oracle access with the full statistical content of the target held fixed. The coordinates are independent conditional on the hidden parameter, so the separation identifies a source of sampling difficulty that is present even without dependence between target coordinates.
The rescaled copies make this control exact. Dividing each active coordinate by its public radius and discarding inactive coordinates yields the same independent canonical factors in both layouts,
νθr=21+εθrN(1,1)+21−εθrN(−1,1).
Conversely, public rescaling and independently generated inactive base coordinates reconstruct either target. Both transformations are independent of the hidden signs. They establish Blackwell equivalence, preserving every statistical decision problem based on a target sample (Section 5 and Appendix K).
Padding provides a second control by keeping the ambient dimension identical. Conditional on a public query action, the inactive response coordinates have a known law, including their Gaussian noise, and can be simulated internally. Appendix K thus accounts for the full returned vector while keeping information about the hidden signs confined to the active coordinates.
Product structure also makes the attaining sampler and its joint error explicit. The construction combines exact coordinate synthesis with independent block outputs. Shared activation saves queries within a block and introduces dependence among its output coordinates. Section 4 and Appendix I expand the product densities, match the coordinate marginals to cancel the terms involving one coordinate, and control the remaining interactions to obtain joint TV accuracy. For the clustered layout in Theorem 3, a feasible integer block length has order ℓB(m)=min{m,1+log(1+εB)} in the stated high precision regime. This gives a saving of order ℓB(m) over coordinate thinning at the required accuracy.
The extension to a larger class has two distinct parts. With the same oracle and the original average TV requirement on our hard subfamily, its lower bound remains valid for expected queries averaged under the uniform prior on that subfamily. A matching separation for dependent targets additionally requires an attaining construction for that class under the chosen accuracy and cost criterion.