Pith. sign in

REVIEW 3 major objections 6 minor 22 references

Spectral DPPs built from Laplacian eigenfunctions deliver Monte Carlo and minibatch rates set by intrinsic dimension on manifolds and graphs.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-11 00:37 UTC pith:CYB23KY6

load-bearing objection Solid spectral program that delivers intrinsic-dimension DPP rates on manifolds and graphs; the graph claims sit inside a real but acknowledged Calder–Trillos window, not a hidden collapse. the 3 major comments →

arxiv 2607.06644 v1 pith:CYB23KY6 submitted 2026-07-07 stat.ML cs.LGmath.PR

Fast determinantal sampling on general spaces and diffusion geometry

Hoang-Son Tran , Pranav Gupta , Subhroshekhar Ghosh This is my paper
classification stat.ML cs.LGmath.PR MSC 60G5562D0558J5005C5047D07
keywords determinantal point processesspectral samplingvariance reductionWeyl's lawgraph Laplaciansintrinsic dimensionMonte Carlominibatches
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Determinantal point processes can sample minibatches and quadrature nodes with better mean-square-error exponents than independent sampling, but prior rate proofs mainly live in Euclidean space and track ambient dimension. This paper constructs projection DPPs from the first n eigenfunctions of a Markov diffusion generator—the Laplace–Beltrami operator on a compact Riemannian manifold, or a graph Laplacian on an ε-graph or k-nearest-neighbour graph—and proves that the variance of linear statistics of Lipschitz functions decays like n to the power 1 minus 1 over intrinsic dimension, up to logs. The same spectral bound yields Monte Carlo rules on manifolds and minibatch estimators from data living near a low-dimensional submanifold whose accuracy improves as n to the power minus one-half minus one over twice the intrinsic dimension. A reader facing high-dimensional data that is effectively low-dimensional therefore obtains sampling guarantees that automatically improve with the true geometry rather than the ambient Euclidean dimension.

Core claim

Projection DPPs of rank n built from the first n eigenfunctions of a Markov generator L satisfy a master variance bound controlled by the eigenvalue counting function of L. Whenever those eigenvalues obey a Weyl law of spectral dimension d_int, the variance of linear statistics of Lipschitz test functions is O(n^{1-1/d_int} polylog n). Specializing to compact Riemannian manifolds and to graph Laplacians of ε- and k-NN graphs on manifold-supported data yields Monte Carlo and minibatch mean-square-error rates of order n^{-1/2-1/(2 d_int)}, matching known Euclidean rates with ambient dimension replaced by intrinsic dimension.

What carries the argument

Theorem 3.1, the master variance bound for spectral DPPs of a Markov generator L. It controls Var[S_n(f)] by a spectral counting quantity R_{L,α}(n) obtained from L^{2} commutator estimates between fractional powers of L and multiplication operators; Weyl’s law and graph-to-manifold spectral sandwiches then convert the bound into an intrinsic-dimension rate.

Load-bearing premise

For the graph results, a high-probability geometric event must hold so that the graph Laplacian spectrum sandwiches the continuum spectrum with relative energy error strictly below one-quarter while the leading Weyl term still dominates the counting-function bound.

What would settle it

On a known compact manifold of dimension m (circle or 2-sphere), form the rank-n spectral DPP from the continuum Laplacian or from a well-tuned ε- or k-NN graph on N i.i.d. samples and check whether the empirical variance of a fixed Lipschitz linear statistic yields a log-log slope near 1-1/m rather than 1.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Minibatch and coreset constructions on manifold-supported data can replace ambient dimension by intrinsic dimension in the sample-size exponent.
  • Monte Carlo integration on compact Riemannian manifolds admits DPP quadrature rules whose mean-square error improves over independent Monte Carlo by a factor roughly n^{-1/m}.
  • Geometric random graphs (ε-graphs and k-NN) inherit the same intrinsic-dimension variance reduction once their spectra are close enough to the continuum Laplacian.
  • The commutator and Dirichlet-form estimates supply a reusable template for other Markov generators whose spectra obey Weyl-type asymptotics.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same spectral construction should extend to other diffusion operators (weighted or anisotropic Laplacians) once a two-term Weyl law is available.
  • The explicit regime where the leading Weyl term dominates the relative-error quantity E(λ) can guide practical choice of ε or k.
  • The density-insensitivity of the k-NN spectral constant suggests k-NN spectral DPPs may be preferable when the sampling density is unknown or highly nonuniform.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper constructs projection DPPs from the first n eigenfunctions of a Markov diffusion generator L (Laplace–Beltrami on compact Riemannian manifolds, or graph Laplacians on ε-graphs and k-NN graphs) and proves variance reduction for linear statistics of Lipschitz test functions. A master bound (Theorem 3.1) controls Var[S_n(f)] via an L² commutator estimate for L^α and the eigenvalue counting function of L. On manifolds this yields Var = O(n^{1-2α/m}) and Monte Carlo MSE of order n^{-1/2-α/m} (Theorems 4.1, 4.3). On geometric graphs, almost-isometries from Calder–García Trillos are used to sandwich the discrete counting function between continuum Weyl laws, giving Var[S_n(f)] = O(n^{1-1/m}(log n)^2) on a high-probability event under an explicit relative-error regime E(λ)<1/4 (Theorems 5.8–5.9, 5.16–5.17). Experiments on the circle and sphere support the predicted exponents.

Significance. The work supplies the first explicit, intrinsic-dimension rates for DPP-based Monte Carlo and minibatch sampling on manifolds and on standard geometric graphs, matching the Euclidean exponents of m-OPEs and wavelet DPPs with ambient dimension replaced by d_int. The master commutator argument (Lemma 3.2 / Theorem 3.1) is clean and reusable; the link to Weyl’s law and Dirichlet forms is natural. The graph results rest on a carefully stated high-probability regime rather than on informal continuum limits, which is a genuine technical advance over purely asymptotic consistency statements. If the regime is practically attainable, the paper gives a usable spectral recipe for repulsive minibatches on manifold-supported data.

major comments (3)
  1. Section 1.3 and the abstract claim minibatch accuracy ε ~ n^{-1/2-1/(2m)} for k-NN and ε-graphs, yet Theorems 5.8, 5.9, 5.16 and 5.17 only bound Var[S_n(f)] for Lipschitz f. The unbiased minibatch estimator used in §5.3 (and in the continuous case, Theorem 4.3) is a linear statistic of the weighted function f/π with π_i = K_n(i,i). On the manifold the authors verify that wf remains Lipschitz (proof of Theorem 4.3); the analogous control of ∥Γ(f/π)∥_∞ and of the lower bound on π_i is missing for the graph kernels. Without it the claimed accuracy rate for minibatches is not fully proved.
  2. The graph rates (Theorems 5.8–5.9, 5.16–5.17) hold only when the relative energy/isometry error satisfies E(λ)<1/4 (or E_k(λ)<1/4) and the leading Weyl term still dominates, i.e., inside the window (29)/(47) under Assumptions 5.1/5.10. The paper never quantifies how large this window is for typical (N,m) or how often standard choices of ε or k land inside it. A short calculation or numerical map of admissible (ε,k,n) would make the practical scope of the intrinsic-dimension claim transparent; without it the strongest applied statements remain conditional on a regime whose size is opaque.
  3. Theorem 4.3 invokes the derivative form of Hörmander’s spectral-function estimate to obtain sup |∇K_n(x,x)| = O(n) and thereby Lip(wf)=O(1). The citation is to [12], which treats the pure Laplace–Beltrami operator. The generator used here is the drifted operator L = -Δ_g - ⟨∇log ρ, ∇⟩_g with ρ ∈ C^{1,1}. A one-line justification that the same gradient bound continues to hold for this lower-order perturbation (or a reference that covers it) is needed for the Monte Carlo rate to be rigorous when ρ is non-constant.
minor comments (6)
  1. The title’s adjective “Fast” is never justified by a complexity claim; the paper concerns statistical rates, not sampling runtime. Consider renaming or adding a brief complexity remark.
  2. Figures 1–6 lack axis labels, legends that distinguish ε-graph from k-NN, and reported slope values with standard errors. Adding these would make the experimental section self-contained.
  3. In Definition 1 and throughout, the spectral DPP is defined with respect to the reference measure μ; on graphs μ_N is the empirical measure, so the kernel matrix is with respect to the discrete inner product (1/N)∑. A single clarifying sentence would prevent confusion with the un-normalized counting-measure convention common in discrete DPP literature.
  4. Typo in the proof of Theorem 5.15: “max 2, ˆlambda” should be “max(2, ˆλ)”.
  5. Assumption (A3) is verified for the two running examples, but the constant 2 appearing in (1) is never tracked into C_α[f]; a remark that the constant is absorbed into the universal C of later theorems would help.
  6. References [15] and [21] are cited as 2026 preprints; if they are still unpublished, a brief note on arXiv identifiers already present is fine, but ensure consistency of year formatting.

Circularity Check

0 steps flagged

No circularity: variance rates follow from a new commutator bound plus external Weyl laws and Calder–García Trillos graph convergence, not from self-defined or fitted quantities.

full rationale

The central derivation is self-contained and non-circular. Theorem 3.1 bounds Var[S_n(f)] for any spectral DPP of a Markov generator L by the eigenvalue counting function R_{L,α}(n) via an L^{2} commutator estimate on [L^α, M_f] (Lemma 3.2, proved from Dirichlet-form identities and the spectral theorem). On manifolds this is specialized by the external pointwise Weyl law of Huang–Zhang (Prop. 4.2) to obtain the intrinsic-dimension rate of Thm. 4.1; the Monte-Carlo MSE of Thm. 4.3 is then an immediate consequence. On graphs the same master bound is combined with the external high-probability sandwich of Calder–García Trillos [7] (Props. 5.5/5.13) that relates the graph counting function to a continuum Weyl law, again yielding the claimed rates (Thms. 5.8–5.9, 5.16–5.17) under an explicit regime E(λ)<1/4. No parameter is fitted to data and then re-used as a “prediction”; the experiments merely measure empirical slopes against the theoretically predicted exponents. Self-citations to the authors’ earlier DPP papers supply only background and are not load-bearing for any rate. The derivation therefore reduces neither by definition nor by self-citation chain to its own inputs.

Axiom & Free-Parameter Ledger

3 free parameters · 4 axioms · 1 invented entities

The central rates rest on standard spectral geometry (Weyl), mild Dirichlet-form hypotheses (A1–A3), and the high-probability graph-to-manifold spectral convergence package of Calder–García Trillos, plus free tuning of the fractional power α and graph length-scale parameters. No new physical entities are postulated; ‘spectral DPP of L’ is a mathematical construction whose properties are proved from those inputs.

free parameters (3)
  • α ∈ (0, 1/2)
    Fractional power in the commutator bound and in R_{L,α}(n); chosen by the analyst, with rates approaching the optimal exponent only as α→1/2−, at the cost of constants that blow up.
  • graph scales ε (or k), δ̃, θ
    Must satisfy Assumptions 5.1/5.10 so that E(λ)<1/4 on the high-probability event G; canonical choices are given but remain free design parameters that control both probability and the size of lower-order terms.
  • density family parameter a (experiments)
    Used only in numerical density-sensitivity plots; not part of the theoretical claim but fitted/chosen for the figures.
axioms (4)
  • domain assumption L has compact resolvent with orthonormal eigenbasis and eigenvalues →∞ (A1); algebraic core contains eigenfunctions (A2); bounded-multiplier estimate (1) for the carré du champ (A3).
    Stated in §2.3; verified for drifted Laplace–Beltrami and finite weighted graphs, but required for the master theorem.
  • standard math Pointwise / two-term Weyl laws for the continuum operators Δ_ρ and Δ_ρ^{NN} (Prop. 4.2, Lemmas 5.6, 5.14).
    Imported from spectral geometry literature; used to convert eigenvalue counting into the n^{1−2α/m} rate.
  • domain assumption High-probability almost-isometries and Dirichlet-energy comparisons between graph and continuum via ∞-OT maps (Props. 5.2–5.4, 5.11–5.12 from Calder–García Trillos [7]).
    Load-bearing for all graph rate theorems; the paper does not re-prove them.
  • domain assumption Compact Riemannian manifold without boundary, smooth (or C^{1,1}) positive density, data i.i.d. from μ.
    Standing geometric hypotheses in §§4–5.
invented entities (1)
  • Spectral DPP of L (rank-n projection onto first n eigenfunctions of a Markov generator) independent evidence
    purpose: Defines the sampling kernel used for all variance-reduction claims on manifolds and graphs.
    A mathematical construction rather than a physical postulate; properties are derived from (A1)–(A3) and spectral asymptotics. Independent evidence is the proved variance bounds and the numerical match on T¹/S².

pith-pipeline@v1.1.0-grok45 · 35868 in / 3458 out tokens · 52450 ms · 2026-07-11T00:37:32.489959+00:00 · methodology

0 comments
read the original abstract

Determinantal point processes have recently emerged as a kernel-based alternative to standard independent sampling for constructing efficient minibatches, coresets, and other compact representations of large-scale datasets. In particular, sampling mechanisms based on DPPs are believed to demonstrate better approximation properties compared to classical i.i.d. samplers, even at the scale of the exponent. One of the key strengths of DPP based samplers is that they can be deployed over very general spaces, in contrast to more classical sampling methods beyond i.i.d. which tend to work in very well-structured settings, principally Euclidean spaces. In this work, we establish explicit rate guarantees for determinantal sampling in spaces that extend far beyond known Euclidean setups, focusing on spectral kernels obtained from eigenspaces of naturally associated Laplacian and other Markov diffusion operators. This includes, in particular, Riemannian manifolds and weighted networks. In determinantal sampling from compact Riemannian manifolds, we establish sampling rates that automatically pick up the intrinsic dimensionality $d_{\text{int}}$ of the underlying manifold. In the setting of networks, we investigate DPP-based samplers on the celebrated k-nearest neighbour graphs, as well as weighted random geometric graphs, and demonstrate a similar improved dependence on the intrinsic dimensionality of the data. Overall, our approach achieves guarantees of $\big(\text{sample size}\big)^{-\frac{1}{2}-\frac{1}{2d_{\text{int}}}}$ that match known rates on Euclidean spaces of comparable dimension. In terms of techniques, we connect to the celebrated Weyl's Law for manifold spectra, and leverage tools from the theory of Markov diffusions and Dirichlet forms as well as certain ingredients from the theory of pseudodifferential operators, which could be of independent interest in this area.

Figures

Figures reproduced from arXiv: 2607.06644 by Hoang-Son Tran, Pranav Gupta, Subhroshekhar Ghosh.

Figure 1
Figure 1. Figure 1: circle with uniform measure [PITH_FULL_IMAGE:figures/full_fig_p045_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: circle with ρ = 1 + 0.6z [PITH_FULL_IMAGE:figures/full_fig_p045_3.png] view at source ↗
Figure 6
Figure 6. Figure 6: density sensitivity on the [PITH_FULL_IMAGE:figures/full_fig_p046_6.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages · 2 internal anchors

  1. [1]

    Springer, 2014

    Dominique Bakry, Ivan Gentil, Michel Ledoux, et al.Analysis and geometry of Markov diffusion operators, volume 103. Springer, 2014

    work page 2014

  2. [2]

    Bardenet, S

    R. Bardenet, S. Ghosh, and M. Lin. Determinantal point processes based on orthogonal polynomials for sampling minibatches in sgd.Advances in Neural Information Processing Systems, 34:16226–16237, 2021

    work page 2021

  3. [3]

    Small coresets via negative dependence: Dpps, linear statistics, and con- centration.Advances in Neural Information Processing Systems, 37:84329–84349, 2024

    R´ emi Bardenet, Subhroshekhar Ghosh, Hugo Simon-Onfroy, and Hoang Son Tran. Small coresets via negative dependence: Dpps, linear statistics, and con- centration.Advances in Neural Information Processing Systems, 37:84329–84349, 2024

    work page 2024

  4. [4]

    Monte carlo with determinantal point pro- cesses.The Annals of Applied Probability, 30(1):368–417, 2020

    R´ emi Bardenet and Adrien Hardy. Monte carlo with determinantal point pro- cesses.The Annals of Applied Probability, 30(1):368–417, 2020

    work page 2020

  5. [5]

    Belhadji, R

    A. Belhadji, R. Bardenet, and P. Chainais. Kernel quadrature with determi- nantal point processes. InAdvances in Neural Information Processing Systems (NeurIPS), 2019

    work page 2019

  6. [6]

    A graph discretization of the Laplace–Beltrami operator.Journal of Spectral Theory, 4(4):675–714, 2014

    Dmitri Burago, Sergei Ivanov, and Yaroslav Kurylev. A graph discretization of the Laplace–Beltrami operator.Journal of Spectral Theory, 4(4):675–714, 2014

    work page 2014

  7. [7]

    Improved spectral convergence rates for graph laplacians onε-graphs and k-nn graphs.Applied and Computational Har- monic Analysis, 60:123–175, 2022

    Jeff Calder and Nicolas Garcia Trillos. Improved spectral convergence rates for graph laplacians onε-graphs and k-nn graphs.Applied and Computational Har- monic Analysis, 60:123–175, 2022

    work page 2022

  8. [8]

    Monte Carlo integration of non-differentiable functions on $[0,1]^\iota$, $\iota=1,\dots,d$, using a single determinantal point pattern defined on $[0,1]^d$

    J.-F. Coeurjolly, A. Mazoyer, and P.-O. Amblard. Monte Carlo integration of non-differentiable functions on [0,1] ι,ι= 1, . . . , d, using a single determinantal point pattern defined on [0,1] d.arXiv preprint arXiv:2003.10323, 2020

    work page internal anchor Pith review Pith/arXiv arXiv 2003

  9. [9]

    Walter de Gruyter, 2011

    Masatoshi Fukushima, Yoichi Oshima, and Masayoshi Takeda.Dirichlet forms and symmetric Markov processes, volume 19. Walter de Gruyter, 2011

    work page 2011

  10. [10]

    Nicol´ as Garc´ ıa Trillos, Moritz Gerlach, Matthias Hein, and Dejan Slepˇ cev. Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace–Beltrami operator.Foundations of Computational Mathematics, 20(4):827–887, 2020

    work page 2020

  11. [11]

    A variational approach to the con- sistency of spectral clustering.Applied and Computational Harmonic Analysis, 45(2):239–281, 2018

    Nicol´ as Garc´ ıa Trillos and Dejan Slepˇ cev. A variational approach to the con- sistency of spectral clustering.Applied and Computational Harmonic Analysis, 45(2):239–281, 2018. 47

    work page 2018

  12. [12]

    The spectral function of an elliptic operator

    Lars H¨ ormander. The spectral function of an elliptic operator. InMathematics Past and Present Fourier Integral Operators, pages 217–242. Springer, 1968

    work page 1968

  13. [13]

    J. B. Hough, M. Krishnapur, Y. Peres, and B. Vir´ ag. Determinantal processes and independence.Probability surveys, 2006

    work page 2006

  14. [14]

    Pointwise weyl laws for schr¨ odinger operators with singular potentials.Advances in Mathematics, 410:108688, 2022

    Xiaoqi Huang and Cheng Zhang. Pointwise weyl laws for schr¨ odinger operators with singular potentials.Advances in Mathematics, 410:108688, 2022

    work page 2022

  15. [15]

    Jaquard and N

    H. Jaquard and N. Keriven. Statistical consistency of discrete-to-continuous limits of determinantal point processes, 2026

    work page 2026

  16. [16]

    Springer, 2021

    Matthias Keller, Daniel Lenz, and Radoslaw K Wojciechowski.Graphs and dis- crete Dirichlet spaces, volume 358. Springer, 2021

    work page 2021

  17. [17]

    Kulesza and B

    A. Kulesza and B. Taskar. Determinantal point processes for machine learning. Foundations and Trends in Machine Learning, 2012

    work page 2012

  18. [18]

    Linear statistics of deter- minantal point processes and norm representations.International Mathematics Research Notices, 2024(19):12869–12903, 2024

    Matteo Levi, Jordi Marzo, and Joaquim Ortega-Cerd` a. Linear statistics of deter- minantal point processes and norm representations.International Mathematics Research Notices, 2024(19):12869–12903, 2024

    work page 2024

  19. [19]

    R. Lyons. Determinantal probability measures.Publications Math´ ematiques de l’Institut des Hautes ´Etudes Scientifiques, 2003

    work page 2003

  20. [20]

    O. Macchi. The coincidence approach to stochastic point processes.Advances in Applied Probability, 7:83–122, 1975

    work page 1975

  21. [21]

    State-of-art minibatches via novel DPP kernels: discretization, wavelets, and rough objectives

    Hoang-Son Tran, Pranav Gupta, R´ emi Bardenet, and Subhroshekhar Ghosh. State-of-art minibatches via novel dpp kernels: discretization, wavelets, and rough objectives.arXiv preprint arXiv:2605.13127, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  22. [22]

    Tremblay, S

    N. Tremblay, S. Barthelm´ e, and P.-O. Amblard. Determinantal point processes for coresets.Journal of Machine Learning Research, 20(168):1–70, 2019. 48

    work page 2019