- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies sample complexity when a denoising sample returns estimates at several neighboring noise levels in one request. To explore this question, the authors consider the DGP of a uniform distribution over iid. random sign vectors; the noising mechanism flips a pre-specified number of coordinates. The paper contributes a seemingly novel radial information budget that takes into account the overlap (in ranges of hidden codebook sizes over which a query can be informative) between neighboring noise levels. Lower bounds are computed that allow adaptive query points, band widths, and stopping times. One takeaway is that for fixed denoising accuracy, successful approximate sampling would require at least returned estimates in the worst case.
Critical strengths
- Interesting mathematical contribution. The main technical hurdle in the paper is perhaps the adaptive query setup. The authors address this by considering a null transcript generated using a target-independent denoiser, which is then coupled with the actual responses up to the first disagreement. I find the interaction of band-overlap geometry with this approach for adaptivity very interesting and clever.
Critical weaknesses
-
Connection to diffusion sampling is not clear. The paper introduces a DGP whose noising mechanism is to flip a number of coordinates of a uniform vector over a random codebook. It is unclear how this connects to the common diffusions, e.g. Gaussian-noising diffusions and discrete diffusions. For instance, what kinds of high-level takeaways can we make for the usual diffusion settings with the same adaptive query setup?
-
No matching upper bounds. For the particular setup of the paper, I wonder if the radial budget should approximately capture the overall sampling difficulty in this model. Specifically, if I were to sample effectively with prespecified TV error, for instance, what would the radial budget have to be? Is it going to be the same asymptotic rate in dimension as the lower bound given in the paper?
I am leaning acceptance due to the paper's conceptual depth. On the other hand, I think that overall, although the paper is very mathematically interesting, its' obscure relationship (at least to me) with the broader literature diffusion sampling, even compared to e.g. Xun & Price et al. (2026) makes me a little unconfident in its' impact for the community.
Questions for authors
I have no further questions or concerns.
3 comments
Response to W2: Tightness, the radial budget, and prescribed sampling accuracy
Thank you for recognizing the radial budget as a potentially useful measure of sampling difficulty and for asking about a matching algorithm. Our results establish a necessary budget with a sharp geometric foundation. A matching sampling upper bound remains open. We have revised Section 6 to distinguish geometric tightness, necessary sampling resources, and the algorithmic sufficiency question.
Geometric tightness. Proposition 13 gives matching bounds when the radii lie in a fixed compact Hamming branch and each informative window has width of order :
=\Theta\!\left(\frac{b+H}{d}\right).$$ The windows describe hidden codebook rates at which a shell response can be informative. Neighboring windows overlap, so their union pays for the displacement across the band plus one common window width. This explains the additive dependence on $b$ and $H$. The matching estimate concerns the union diameter under these assumptions. **Meaning of the radial budget.** For a declared cap $R_\star$ on returned shell estimates, the radial charge is $$\mathcal B_\star=\sum_t(b_t+\Lambda_\star),\qquad \Lambda_\star=1+\log d+\log(1+R_\star)+p\log(1/\varepsilon).$$ Here $b_t$ is the band half width. This sum bounds the rate coverage charged to the queries, with neighboring estimates within each band accounted for through their union. The proof follows an entire null transcript independent of the target and couples it to actual responses. It therefore allows the point, band width, and stopping decision to depend on previous answers. This turns the geometric estimate into a necessary resource law for adaptive sampling. The budget also charges repeated coverage, so a query policy must choose how to turn its available budget into new information. Establishing that an optimal policy succeeds at the lower bound scale requires a sampler using the permitted responses and a guarantee for its complete output law conditional on each relevant fixed codebook. In particular, the sampler must reproduce the frequencies in the empirical target, including multiplicities. Finding one support point alone does not establish that sampling guarantee. **Budget for a prescribed TV accuracy.** The denoising error $\varepsilon$ and the desired sampling error $\tau$ are different parameters. The latter measures $$d_{\mathrm{TV}}\bigl(\mathcal L(\widehat X\mid S),\nu_S\bigr).$$ Theorem 2 first fixes $R_\star$ and constructs a hard distribution of targets and accurate response families before choosing the algorithm. Every adaptive algorithm satisfying both $R\le R_\star$ and $\mathcal B_\star\le c_{\mathrm{bud}}d$ on every possible transcript path has TV error at least $0.9$ on at least $0.9$ of these instances. Thus, for any $\tau<0.9$, achieving TV error at most $\tau$ on more than $0.1$ of these hard instances, while retaining the entry cap, requires some possible path with $\mathcal B_\star>c_{\mathrm{bud}}d$. This is a worst case path requirement. The corresponding necessary dimension scales are: | Resource | Necessary order under the respective hard distribution and cap conditions | | --- | --- | | Radial budget | $\Omega(d)$ | | Returned shell estimates | $\Omega(d/(\log d+p\log(1/\varepsilon)))$ | | Requests with fixed half width $b$ | $\Omega(d/(b+\Lambda_b))$ | Here $\Lambda_b=1+\log d+\log(1+b)+p\log(1/\varepsilon)$. The last row applies where Corollary 4 admits a positive integer query cap. The hard distribution is indexed by the declared cap in the corresponding theorem or corollary. At fixed $p$ and $\varepsilon$, the necessary estimate count is of order $d/\log d$. These bounds apply to every desired TV tolerance below $0.9$ under the stated success requirement. Whether the same dimension scales are sufficient, and how an achievable budget depends on $\tau$, remains the matching algorithmic question. The established contribution is the necessary radial resource law that survives fully adaptive access, supported by the sharp overlap geometry. Thank you for helping us articulate both the proved resource scales and the precise target for an upper bound.Thank you for addressing my concerns. I will retain my score in favor of the mathematical content.
Response to W1: Connection to binary diffusion and the broader takeaway
Thank you for recognizing the interaction between band geometry and adaptive queries, and for asking us to make the connection to standard diffusion clearer. We have added a precise mathematical connection to independent binary flips in Proposition I.1, together with a proof and an explicit description of the information supplied by each interface.
Suppose every coordinate flips independently with probability q, and let K be the number of flips. Conditional on K=k, the flipped coordinates form a uniformly chosen subset of size k. This is exactly the fixed energy channel in our paper. The standard posterior mean can therefore be expressed as a mixture of our shell means,
mS,qflip(x)=∑k=0dwk(S,x,q)mS,k(x)
wk(S,x,q)=∑j=0dNS,j(x)qj(1−q)d−jNS,k(x)qk(1−q)d−k
Here NS,k(x) counts codeword occurrences in shell k, including multiplicity. These are posterior weights after observing x. The known binomial distribution of K before observing x does not generally supply them. Our oracle returns the shell means, without these occupancies or weights.
Appendix I gives a small exact example of this distinction. At x=(1,1), a codebook containing two copies each of x and −x, and a codebook containing all four binary vertices, return the same full shell list (x,0,−x). With q=1/4, their bit flip posterior means are respectively (4/5)x and (1/2)x. Thus the list at one point does not determine the standard posterior at that point. The example isolates the information needed to combine shell means at the observed point.
We also checked the identity by two independent computations over all observations for 180 codebooks and four flip probabilities. The codebook is the statistical unit, with 20 codebooks in each dimension and size setting.
The RMSE is weighted by the actual observation distribution and normalized by d. The proof establishes the identity, while these checks verify its implementation.
The broader takeaway is that access to several neighboring noise levels can contain overlapping information. Our result shows how to charge this overlap while allowing the next point, band width, and stopping decision to adapt to earlier answers. This distinguishes fewer requests from fewer returned denoising estimates. For standard diffusion, it motivates examining both the information returned across nearby levels and the weights used to combine it. Transferring the sampling lower bound to standard binary or Gaussian diffusion would additionally require a reduction matching the actual oracle access and accuracy assumptions. Section 6 and the new interface comparison in Appendix I now separate this transfer question from the exact binary channel identity. Thank you for helping us make the broader implication more precise.