REVIEW 5 minor 21 references
Discretized Approximate Ancestral Sampling
T0 review · 0 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read This paper introduces DAAS, a sampling method for Fourier Basis Density Models that reaches any target accuracy at $O(1/K^2)$ error and costs $O(S+K \log K)$ for $S$ samples.
desk verdict A correct, clean sampler for Fourier basis densities with explicit O(1/K^2) error bounds; the one hand-wave in the boundary proof checks out, so this deserves a serious referee. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The triangular kernel $w_1(x) = \max(0, 1 - |x|)$ acts as the interpolation filter. The compound distribution $q(x) = \sum_{k=0}^{K-1} p[k] \frac{K}{2} w_1(\frac{K}{2}(x-x_k))$ coincides with the piecewise linear interpolation of $p$ at $x_k = -1 + 2k/K$, and this coincidence is what turns a sampling procedure into an interpolation error problem. The argument also relies on the band-limited structure of the FBM: the second-derivative bound $\max |p''(x)| \le \pi^2 N(N+1)(2N+1)/6$ follows from the coefficient properties of the truncated Fourier series, and this bound feeds directly into the standard $\frac{M}{2K^2}$ interpolation error estimate.
What would settle it
Run Algorithm 1 for a simple FBM with $N=1$ and $K=3$, compute the exact density of the output distribution on the edge interval $[-1, -1+2/3)$ by convolving the discrete ancestor masses with the triangle kernel under the modulo map, and compare it pointwise with the piecewise linear interpolant of $p$ on that interval; any pointwise difference, or a violation of $|p(x)-q(x)| \le \pi^2/(12K^2)$ at the edges, would contradict Proposition 2 and Theorem 1.
Extended reading notes
Core claim
The central claim is Theorem 1: for an FBM density $p$ with $N$ frequency terms and the triangle-kernel DAAS distribution $q$ on $K$ grid points, the divergences satisfy $D_{TV}(p,q) \le \pi^2 N(N+1)(2N+1)/(12K^2)$ and $D_{W_1}(p,q) \le \pi^2 N(N+1)(2N+1)/(6K^2)$, with the constants given in Appendix E. The key step is Proposition 2, which shows that $q$ is the piecewise linear interpolation of $p$ at the grid points: within each interval $[x_k,x_{k+1}]$ only the neighboring triangular kernels contribute, and their weighted sum reproduces the linear interpolant. Proposition 1 guarantees that the discrete masses $2p(x_k)/K$ form a valid probability distribution for $K > 2N$ equally spaced points, so Algorithm 1 is well-defined. The $1/K^2$ rate then follows from the classical interpolation error bound once the second derivative of $p$ is bounded by $\pi^2 N(N+1)(2N+1)/6$.
Load-bearing premise
The proof that the compound distribution equals piecewise linear interpolation assumes the triangular kernels 'appropriately wrap around' at the boundaries of $[-1,1)$, but does not verify that the modulo operation in Algorithm 1 produces exactly the same wrapped triangles at the edges; if it does not, the $O(1/K^2)$ interpolation bound would not cover the edge intervals.
Editorial extensions
If this is right
- For any FBM and any tolerance $\epsilon$, choosing $K > \sqrt{\pi^2 N(N+1)(2N+1)/(12\epsilon)}$ guarantees the sampled distribution is within $\epsilon$ total variation of the target.
- The cost is $O(K\log K)$ for the initial FFT evaluation of the grid plus $O(S)$ for the $S$ samples themselves, giving $O(S + K\log K)$ overall and linear time when $S \gg K$.
- The explicit constants remove guesswork from hyperparameter selection: users can compute $K$ directly from the model's frequency count and their accuracy requirement.
- DAAS can be used to warm-start ULA or MALA chains, combining the speed of the approximate sampler with the asymptotic exactness of MCMC at the price of additional score-function evaluations.
- The analysis gives a quantitative argument for triangular noise over uniform or higher-order B-spline kernels, matching the empirical finding that $w_1$ minimizes KL divergence for a given $K$.
Reading between the lines
- The proof never uses the specific FBM parameterization beyond boundedness of the second derivative, so the same $O(1/K^2)$ guarantee and the same algorithm should apply to any circular density with bounded second derivative, with the constant replaced by the corresponding bound.
- The boundary condition is the delicate point: the paper asserts that the triangle kernels 'appropriately wrap around' at $\pm1$, but does not prove that the modulo operation in Algorithm 1 produces exactly that wrapped kernel; a mismatch would require a corrected constant on the edge intervals while likely preserving the overall rate.
- Using B-spline kernels of degree $D$ should yield $O(1/K^{D+1})$ error by standard spline interpolation theory; the paper's experiments with the quadratic kernel hint at this, though no such bound is stated.
- Since sampling cost is independent of $N$ once $K$ is fixed, DAAS may make FBM practical as a latent prior in deep generative pipelines where fast approximate sampling matters more than exactness.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces Discretized Approximate Ancestral Sampling (DAAS), a two-step sampler for Fourier Basis Density Models (FBMs). DAAS evaluates the FBM density p at K equally spaced grid points, samples an index from the discrete weights p[k] = (2/K)p(x_k), and adds i.i.d. triangular interpolation noise, with an optional ULA/MALA refinement step. The central theoretical claim is Theorem 1: for the triangle-kernel version, the total variation and Wasserstein-1 distances between the target FBM density p and the DAAS sample density q are O(1/K^2), with explicit constants given in Appendix E. The proof route is Proposition 1 (exact quadrature identity), Proposition 2 (the compound distribution equals the periodic piecewise linear interpolant of p on the grid), Property 7 (interpolation error bound from a second-derivative bound), and Appendix E (integral estimates). The experiments show the expected decrease of divergence as K grows, compare the triangle kernel with other B-spline kernels, and compare DAAS with rejection sampling and Langevin-based MCMC baselines.
Significance. If the main theorem is correct, DAAS is a practically attractive sampler for FBMs: it has explicit, non-asymptotic accuracy bounds, no free parameters, and a cost of O(S + K log K) for producing S samples once the K grid values are computed. The explicit constants in Appendix E, pi^2 N(N+1)(2N+1)/(12K^2) for total variation and twice that for Wasserstein-1, are directly usable for choosing K. The derivation is clean and non-circular: Proposition 1 is an exact quadrature identity, Proposition 2 identifies the triangle-kernel compound with piecewise linear interpolation, and the error bounds follow from standard interpolation estimates. The stress-test concern about the boundary wrap does not invalidate the theorem; a direct calculation closes the gap, so I treat it as a presentation issue rather than a soundness issue. The paper gives credit to the prior FBM model and to the thesis that first formulated discretization-based sampling for band-limited circular densities, and the empirical study, while limited, is consistent with the theory.
minor comments (5)
- [Appendix C (Proposition 2)] The proof verifies the interpolation identity on interior intervals only and asserts that the triangle kernels 'appropriately wrap around' the boundaries without displaying the edge calculation. Please add x_K = x_0 + 2, p[K] = p[0], and verify the last interval explicitly: for s = K(x - x_{K-1})/2, the wrapped kernels give q(x) = p(x_{K-1})(1-s) + p(x_0)s, matching the periodic linear interpolant. The direct calculation closes the gap, but it should be written in the paper.
- [Appendix D (Property 3)] The displayed proof of Property 3 is corrupted: Equation (43) contains unreadable tokens, and the step 'In particular, with max[x1,x2]p(x)=||p(x)||_infinity' is not justified for arbitrary pairs of zeros, so the lower bound x2 - x1 >= 2/(pi N) does not follow as stated. Since Property 3 is not used in the proof of Theorem 1, this does not affect the main claim, but the property and its proof should be corrected or its scope explicitly restricted.
- [Figure 3 caption] The caption says 'considering 10 randomly initialized FBMs' whereas Section V-A reports 20 different trials for each configuration; these numbers should be aligned.
- [References] References [4] and [5] are the same article and should be consolidated into a single bibliographic entry.
- [Theorem 1] The theorem statement asserts the existence of constants C1 and C2 without indicating their dependence on N; since Appendix E provides the explicit values, stating them in the theorem itself would improve readability and would make the hyperparameter guidance in the abstract fully self-contained.
Circularity Check
No significant circularity: Theorem 1's O(1/K^2) bounds are derived from standard interpolation error and explicit derivative bounds, not from fitted values or self-referential definitions.
full rationale
The central claim is Theorem 1 (Eqs. 18–19). Appendix E derives the TV and Wasserstein bounds directly from the pointwise interpolation error bound in Property 7, which is the standard piecewise-linear interpolation estimate |p(x)-q(x)| ≤ M/(2K^2) with M = sup|p''|. Property 6 computes M explicitly from the FBM expansion (8) and the coefficient inequality |c_n| ≤ c_0, which is proved from the autocorrelation definition via Cauchy–Schwarz in Property 5. No quantity is fitted, back-solved, or calibrated against the target p or the sampled q; the constants depend only on N and π. Proposition 2 bridges Algorithm 1's triangular-kernel mixture to piecewise linear interpolation, and even though the boundary wrap is only asserted as 'appropriately wrapping around at the boundaries' rather than verified in Appendix C, that is a presentational/rigor gap, not a circularity: the wrapped edge interval is a direct calculation using the same kernel formula, not an input assumption that forces the theorem. The self-citations to the authors' earlier FBM paper [1] and to [13] define the model and provide a summation lemma, but Appendix B proves that lemma in-line, so those citations are not load-bearing to the O(1/K^2) result. No 'prediction' is statistically forced, no ansatz is smuggled in via self-citation, and no known empirical pattern is merely renamed. The corrupted equation fragment in Appendix D.C (Property 3) concerns an unrelated zero-spacing property and does not affect the derivation of Theorem 1. The main derivation is self-contained against standard external results (Bernstein's inequality, interpolation theory), so the appropriate finding is no significant circularity.
Assumptions & free parameters
assumptions (5)
- standard math A real-valued function on the circle is non-negative iff its Fourier coefficients are positive semi-definite (Herglotz's theorem).
- standard math Bernstein's inequality for trigonometric polynomials of degree N: ||p'||_inf <= pi N ||p||_inf.
- standard math Standard piecewise linear interpolation error bound for C^2 functions: |p(x)-q(x)| <= (sup|p''|)/(2K^2) on intervals of length h = 2/K.
- domain assumption The FBM density is exactly band-limited: p is a trigonometric polynomial of degree at most N with no frequencies beyond N.
- standard math Alias sampling can sample from a discrete distribution in O(1) per draw after O(K) setup.
Cite this review
Pith. "Pith review of Discretized Approximate Ancestral Sampling." pith.science (2026). https://pith.science/paper/R6IV3R4D
@misc{pith2026250506098,
author = {Pith},
title = {Pith review of: Discretized Approximate Ancestral Sampling},
year = {2026},
howpublished = {\url{https://pith.science/paper/R6IV3R4D}},
note = {Machine review of arXiv:2505.06098}
}
read the original abstract
The Fourier Basis Density Model (FBM) was recently introduced as a flexible probability model for band-limited distributions, i.e. ones which are smooth in the sense of having a characteristic function with limited support around the origin. Its density and cumulative distribution functions can be efficiently evaluated and trained with stochastic optimization methods, which makes the model suitable for deep learning applications. However, the model lacked support for sampling. Here, we introduce a method inspired by discretization--interpolation methods common in Digital Signal Processing, which directly take advantage of the band-limited property. We review mathematical properties of the FBM, and prove quality bounds of the sampled distribution in terms of the total variation (TV) and Wasserstein--1 divergences from the model. These bounds can be used to inform the choice of hyperparameters to reach any desired sample quality. We discuss these results in comparison to a variety of other sampling techniques, highlighting tradeoffs between computational complexity and sampling quality.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
A. De la Fuente, S. Singh, and J. Ballé, “Fourier basis density model,” in 2024 Picture Coding Symp. (PCS) ,
work page 2024
-
[2]
Communication in the presence of noise,
C. E. Shannon, “Communication in the presence of noise,” Proceedings of the IRE , vol. 37, no. 1, pp. 10– 21, 1949
work page 1949
-
[3]
Fast inverse transform sampling in one and two dimensions
S. Olver and A. Townsend, Fast inverse transform sampling in one and two dimensions, 2013. arXiv: 1307. 1223 [math.NA]. [Online]. Available: https://arxiv. org/abs/1307.1223
work page Pith review arXiv 2013
-
[4]
Approximating inverse cumulative distribution functions to produce approximate random variables,
M. Giles and O. Sheridan-Methven, “Approximating inverse cumulative distribution functions to produce approximate random variables,” ACM Transactions on Mathematical Software, vol. 49, no. 3, pp. 1–29, 2023
work page 2023
-
[5]
Approximating inverse cumulative distribution functions to produce approximate random variables,
M. Giles and O. Sheridan-Methven, “Approximating inverse cumulative distribution functions to produce approximate random variables,” ACM Transactions on Mathematical Software, vol. 49, no. 3, pp. 1–29, Sep. 2023, ISSN : 1557-7295. DOI: 10.1145/3604935. [On- line]. Available: http://dx.doi.org/10.1145/3604935
doi:10.1145/3604935 2023
-
[6]
J. E. Gentle, Random number generation and Monte Carlo methods. Springer, 2003, vol. 381
work page 2003
-
[7]
G. H. Givens and J. A. Hoeting, Computational statis- tics. John Wiley & Sons, 2012
work page 2012
-
[8]
Brownian dynamics as smart monte carlo simulation,
P. J. Rossky, J. D. Doll, and H. L. Friedman, “Brownian dynamics as smart monte carlo simulation,” The Journal of Chemical Physics , vol. 69, no. 10, pp. 4628–4633, 1978
work page 1978
Show all 21 references
-
[9]
Langevin diffusions and metropolis-hastings algorithms,
G. O. Roberts and O. Stramer, “Langevin diffusions and metropolis-hastings algorithms,” Methodology and computing in applied probability , vol. 4, pp. 337–357, 2002
2002
-
[10]
Langevin diffusions and the metropolis- adjusted langevin algorithm,
T. Xifara, C. Sherlock, S. Livingstone, S. Byrne, and M. Girolami, “Langevin diffusions and the metropolis- adjusted langevin algorithm,” Statistics & Probability Letters, vol. 91, pp. 14–19, 2014
2014
-
[11]
An algorithm for sampling from bandlimited circular probability distributions,
M. Olofsson, “An algorithm for sampling from bandlimited circular probability distributions,” KTH, School of Engineering Sciences (SCI), 2023
2023
-
[12]
Brockwell and R
P. Brockwell and R. Davis, Time Series: Theory and Methods (Springer Series in Statistics). Springer New York, 2013, ISBN : 9781489900043. [Online]. Available: https://books.google.com/books?id=DJ_lBwAAQBAJ
2013
-
[13]
Gillman, D
N. Gillman, D. Aggarwal, M. Freeman, S. Singh, and C. Sun, Fourier head: Helping large language models learn complex probability distributions , 2024. arXiv: 2410 . 22269 [cs.LG]. [Online]. Available: https : / / arxiv.org/abs/2410.22269
2024 arXiv
-
[14]
An efficient method for generating dis- crete random variables with general distributions,
A. J. Walker, “An efficient method for generating dis- crete random variables with general distributions,” ACM Transactions on Mathematical Software (TOMS), vol. 3, no. 3, pp. 253–256, 1977
1977
-
[15]
Queffélec and R
H. Queffélec and R. Zarouf, On bernstein’s in- equality for polynomials , 2019. arXiv: 1903 . 10801 [math.CA]. [Online]. Available: https://arxiv.org/abs/ 1903.10801
2019 arXiv
-
[16]
Ralston and P
A. Ralston and P. Rabinowitz, A first course in numer- ical analysis. Courier Corporation, 2001
2001
-
[17]
The distribution of means for samples of size n drawn from a population in which the variate takes values between 0 and 1, all such values being equally probable,
P. Hall, “The distribution of means for samples of size n drawn from a population in which the variate takes values between 0 and 1, all such values being equally probable,” Biometrika, pp. 240–245, 1927
1927
-
[18]
Y . W. Teh, A. Thiéry, and S. V ollmer, Consistency and fluctuations for stochastic gradient langevin dynamics ,
-
[21]
(65) Since c0 > 0, ∣cn∣≤c0 for n= 1, 2,...,N . F . Bounded first and second derivatives Property 6: For any non-constant FBM density p(x), we have that ∣p′(x)∣ and ∣p′′(x)∣ are bounded. Proof: Given that the density defined in (8) is k times continuously differentiable (k > 3)...
-
[2015]
[Online]
arXiv: 1409.0578 [stat.ML]. [Online]. Avail- able: https://arxiv.org/abs/1409.0578. 6 APPENDIX A POSITIVITY Proposition 3: Let {ak}N k=0 be a sequence of complex numbers. We define the sequence {cn}N n=0 by cn = N−n ∑ k=0 aka∗ k+n, n = 0, 1,...,N. (20) Then, for f as defined i...
-
[2024]
DOI: 10.1109/PCS60826.2024.10566409
2024
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.