Pith. sign in

REVIEW 3 major objections 5 minor 11 references

Extremal bounds for Gaussian trace estimation

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The worst-case tail of the Gaussian trace estimator over any spectral constraint considered here is a Gamma tail, provided the conjectured threshold for the tail region holds.

desk verdict Genuinely new F-majorization result for indefinite matrices, but the advertised quantitative bounds are conditional on unproven tail-location conjectures; worth refereeing as a solid contribution with honest limitations. read the letter →

arxiv 2411.15454 v1 pith:O232LSNO submitted 2024-11-23 math.ST cs.NAmath.NAmath.PRstat.TH

Eric Hallman This is my paper · ORCID
classification math.STcs.NAmath.NAmath.PRstat.TH MSC 60E1515A42
keywords GaussiantraceestimationextremaltailboundsmajorizationGammarandomvariableseffectiverankstableindefinitematricesrandomizednumericallinearalgebra
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper seeks the worst possible tail behavior of the Gaussian trace estimator, the randomized estimator $\frac{1}{m}\sum_{j=1}^{m} z_j^T A z_j$ for the trace of a real symmetric matrix $A$. The claim is that, among all positive semidefinite matrices with a given effective rank, and among all symmetric matrices with a given 2-norm and Frobenius norm, a single maximally skewed spectrum dominates every other spectrum in the majorization order, and the estimator's tails are then bounded by those of a Gamma variable. If the claim is right, sample sizes for relative or absolute error tolerances can be read from Gamma quantiles rather than from looser concentration inequalities. The majorization and extremal-matrix parts are proved; the exact place where the Gamma bound starts to apply is left as Conjectures 1 and 2, so the practical range of the bounds is not yet established.

What carries the argument

The argument runs on the majorization order on eigenvalues—partial sums of the largest entries dominate those of a less-skewed vector with the same total—extended in Definition 5 to an indefinite version using squared positive and negative parts. Lemmas 1 and 2 decompose any majorization step into transfers between two coordinates, so CDFs can be compared along a linear interpolation $Y(t)$. The Laplace transform of the CDF reduces the comparison to the sign of a derivative of a density of the form $Y(t)+\nu_j\psi+\nu_k\psi'$, where $\psi,\psi'$ are exponential; unimodality (relative error) or convexity (absolute error) of that density determines where in the tail the ordering holds. Infinite divisibility of Gamma variables then lets the discrete $m$-sample chi-squared structure be replaced, in the limit, by general finite linear combinations of Gamma variables, yielding the Gamma worst cases in (4) and (5).

What would settle it

Take the explicit worst-case matrix $A_{\mathrm{rel}}(\mu)$ of (2), fix $m$, and evaluate the tail probability at $\varepsilon = 2/(m\mu)$; if $\Pr(|\mathrm{tr}_m^G(A)-\mathrm{tr}(A)| \ge \varepsilon\,\mathrm{tr}(A))$ exceeds $\Pr(|X-1|\ge \varepsilon)$ with $X\sim \mathrm{Gamma}(m\mu/2,m\mu/2)$, then Conjecture 3 is false and Theorem 6's stated range collapses. The analogous absolute test evaluates $\varepsilon = 2\lambda/m + \sqrt{2\varphi^2/m + (2\lambda/m)^2}$ against $2\Pr(X-\mathbb{E}[X]\ge \varepsilon)$ with $X\sim \mathrm{Gamma}(m\rho/2,m/(2\lambda))$.

Watch

Extended reading notes

Core claim

On the author's own terms, the central result is that the Gaussian trace estimator's tail probabilities are extremized by specific spectra, and these extremal tails are Gamma-distributed. For a nonzero SPSD matrix $A$ with effective rank $\mu = \mathrm{reff}(A)$, Theorem 6 states there is a threshold $\varepsilon_{\mathrm{rel}}$ such that for every $\varepsilon \ge \varepsilon_{\mathrm{rel}}$, $$\Pr(|\mathrm{tr}_m^G(A)-\mathrm{tr}(A)| \ge \varepsilon\,\mathrm{tr}(A)) \le \Pr(|X-1|\ge \varepsilon),$$ with $X \sim \mathrm{Gamma}(m\mu/2, m\mu/2)$. For a symmetric $A$ with $\|A\|_2=\lambda$ and $\|A\|_F=\varphi$, Theorem 7 states there is a threshold $\varepsilon_{\mathrm{abs}}$ such that for every $\varepsilon \ge \varepsilon_{\mathrm{abs}}$, $$\Pr(|\mathrm{tr}_m^G(A)-\mathrm{tr}(A)| \ge \varepsilon) \le 2\Pr(X-\mathbb{E}[X]\ge \varepsilon),$$ with $X \sim \mathrm{Gamma}(m\rho/2, m/(2\lambda))$ and $\rho=\varphi^2/\lambda^2$. The specific worst-case matrices are (2) and (3). Theorems 6 and 7 are conditional on the tail regions actually starting at the conjectured thresholds, since the author proves only pessimistic lower bounds in Theorems 3 and 5 and leaves Conjectures 1 and 2 open.

Load-bearing premise

The promised worst-case bounds apply only for error tolerances above a threshold whose value is not proved; if the conjectured thresholds are wrong, the paper does not actually tell the user how large the tolerance must be for the Gamma bound to hold.

Editorial extensions

If this is right

  • For SPSD matrices, the relative-error bound depends on the product $m\,\mathrm{reff}(A)$, so increasing the effective rank has the same tail effect as increasing the sample count.
  • For indefinite matrices, the absolute-error bound is governed by the stable rank $\rho=\varphi^2/\lambda^2$; if Conjecture 4 holds, the tolerance needed for the bound to apply shrinks to $\varphi$ as $m\to\infty$.
  • The extremal spectra are explicit and universal within their classes: (2) for relative error, (3) for absolute error, and its negative for the lower tail.
  • Within the tail region these bounds are tighter than the existing concentration inequalities, though the size of that region remains conjectural.
  • The absolute bound carries a factor 2 because the upper and lower tails are controlled by opposite extremal matrices, $A_{\mathrm{abs}}$ and $-A_{\mathrm{abs}}$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If Conjectures 1 and 2 are proved, the Gamma bounds become explicit minimax statements over the matrix class: within the tail region, no matrix with the same spectral summary statistics can force a larger tail probability than the displayed Gamma worst case, making the bounds usable as certificates in sample-size arguments.
  • The same two-coordinate interpolation machinery could locate the missing thresholds: Conjectures 1 and 2 are statements about the first point where a density of a Gamma mixture plus two exponentials stops being monotone or convex, so they could be settled by a one-dimensional optimization over the two-coordinate transfer rather than by a new proof idea.
  • A numerical extension would test whether the majorization ordering also holds for the normalized Gaussian estimator, where each sampled vector is divided by its length; the Gamma structure is lost, but the same interpolation and Laplace-transform comparison might still order the tails, which the paper notes is plausible.
  • A direct simulation at the conjectured threshold would settle the practical value of the bounds quickly: for a noninteger effective rank, the empirical tail probability of the extremal matrix at $\varepsilon=2/(m\mu)$ can be compared with the Gamma bound before any new theorem is attempted.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies tail probabilities of the Gaussian trace estimator for real symmetric matrices. It introduces eigenvalue majorization orders for two matrix families (positive semidefinite matrices with bounded effective rank, and symmetric matrices with bounded 2-norm and fixed Frobenius norm), proves CDF monotonicity in the tail regions (Theorems 2 and 4), identifies candidate extremal matrices (A_rel and A_abs), and proposes Gamma-distribution worst-case bounds for relative and absolute errors (Theorems 6 and 7). The paper is transparent that the exact locations of the tail regions are not proved: Section 1.2 states that it has so far been beyond the author's ability to prove where these regions begin, and the practical thresholds are left as Conjectures 3 and 4. The passage to the limiting Gamma families via infinite divisibility in Section 3.3 is also asserted rather than formally justified. The advertised practical bounds are therefore conditional, although the majorization framework and the proofs of Theorems 2 and 4 are substantial.

Significance. If the conjectured threshold locations and the infinite-divisibility approximation were established, the paper would provide essentially tight, parameter-free worst-case tail bounds with explicit extremizers, and the absolute-error result for indefinite matrices (Theorem 4 with Lemma 2) appears to be novel. The Laplace-transform and unimodality machinery is elegant, and the proofs of Theorems 2 and 4, apart from the threshold questions, are credible. The paper is also unusually candid about its own limitations, which helps the reader separate what is proved from what is conjectured. However, the central practical content of Theorems 6 and 7 is not yet derived: the thresholds epsilon_rel and epsilon_abs are unknown, and the limiting step from fixed (alpha,beta) families to the general families Q_rel(mu) and Q_abs(lambda,phi) lacks a formal argument. The current contribution is therefore a promising framework plus conditional results, not a complete derivation of the advertised extremal bounds.

major comments (3)
  1. [Section 1.2, Theorems 6-7, Conjectures 3-4] The central practical statements are conditional on unproven threshold conjectures. Theorem 6 asserts existence of epsilon_rel and Theorem 7 asserts existence of epsilon_abs, but no location for these thresholds is proved. Section 1.2 explicitly states that it has so far been beyond the author's ability to prove exactly where the tail regions begin. The values in Conjecture 3 (epsilon_rel <= 2/(m mu)) and Conjecture 4 (epsilon_abs <= 2 lambda/m + sqrt(2 phi^2/m + (2 lambda/m)^2)) are precisely the missing locations, and Theorems 3 and 5 give only pessimistic lower bounds on xupper and xhat_upper, i.e., bounds in the opposite direction. Consequently the chains of inequalities in Theorems 6 and 7 do not yield usable bounds until these conjectures are resolved. Either prove the conjectures or provide an alternative way to locate the tail regions, or revise the abstract and Section 5 to present these as conditional results.
  2. [Section 3.3] The infinite-divisibility limit used to pass from the fixed-parameter families Q_rel(mu; alpha,beta) and Q_abs(lambda,phi; alpha,beta) to the general families Q_rel(mu) and Q_abs(lambda,phi) is not formally justified. Lemma 3 proves only the inclusion Q_rel(mu; alpha,beta) subset of Q_rel(mu; alpha/T,beta), and similarly for Q_abs. The subsequent claim that, for sufficiently large T, the fixed-parameter sets contain distributions arbitrarily close to any distribution in Q_rel(mu) or Q_abs(lambda,phi), and that therefore any bounds pass to the limit, requires a topology on the distribution families and a continuity argument for the supremal tail probability. No such argument is given. Since the identification of the extremal Gamma distributions in (4) and (5) rests on this step, it is load-bearing for Theorems 6 and 7.
  3. [Section 5, first paragraph] The chain of reasoning leading to Theorems 6 and 7 is not fully traced. The text states that 'employing the infinite division strategy of Section 3.3' shows that the Gaussian trace estimators for A_rel and A_abs are tail-bounded by the Gamma distributions in (4) and (5), but this step is not expanded. In particular, it is not shown that the extremal element of Q_rel(mu) or Q_abs(lambda,phi) is indeed the claimed Gamma variable, nor that the majorization monotonicity of Theorems 2 and 4 survives the limiting construction. A rigorous proof should either derive (4) and (5) directly from Lemma 3 with an explicit approximation argument or state the required limit theorem.
minor comments (5)
  1. [Abstract and Section 5] The phrase 'derives extremal tail bounds' overstates the proven content; consider rewording to indicate that the bounds are derived conditional on conjectured tail-region locations, or add a caveat near Theorems 6 and 7.
  2. [Definition 10] The inequality '0 < lambda <= 1/sqrt(alpha) phi' is not readable as printed; based on Theorem 4 it is presumably meant to be '0 < lambda <= phi/sqrt(alpha)', and the displayed formula should be corrected.
  3. [Lemma 3] The statement contains a typographical artifact ('bracehtipupleft /bracehtipdownright') in the repeated vector; the intended notation with an underbrace or similar should be restored.
  4. [References] References [5] and [6] appear to be the published and preprint versions of the same work; please merge them or note the relationship explicitly.
  5. [Appendix A.2, proof of Theorem 4] The step 'by the definition of xhat_upper, the density function is convex on (xhat_upper, infinity)' would benefit from a sentence explaining why the second derivative cannot change sign again after its last inflection point; otherwise the reader cannot see that convexity, rather than mere absence of inflection points, is guaranteed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the extremal bounds are derived from explicit majorization arguments, not from fitting or self-citation.

full rationale

The claimed extremal tail bounds are not circular. The derivation chain is: majorization order on spectra (Definitions 4-5) to CDF monotonicity via Laplace transforms (Theorems 2 and 4) to application to explicit extremal matrices (Theorems 6 and 7). No parameter is fitted to the quantity being predicted: the extremal matrices (2) and (3) are explicit functions of mu, lambda, and phi, and the Gamma bounds follow from the majorization inequalities. The paper explicitly identifies Theorem 2 as a restatement of the external result [8] and does not present it as new; this reduces novelty but is not circular. Section 1.2 candidly states that the exact start of the tail regions is unproved and left as Conjectures 1-4, and Section 3.3's infinite-divisibility limit argument is asserted rather than rigorously proved; these are rigor and completeness gaps, not reductions of the conclusions to their inputs. The bibliography contains no self-citations by the author, so no load-bearing self-citation exists. The practical value of Theorems 6 and 7 is conditional on unproven conjectures, but that is an open-problem issue, not circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The proofs rely on standard results about Gamma variables, majorization, and Laplace transforms. There are no fitted constants. The main unsupported input is the infinite divisibility approximation step in Section 3.3 and the unproven tail-location conjectures, which are recorded as gaps rather than hidden assumptions.

assumptions (3)
  • standard math Unimodality of linear combinations of Gamma random variables (cited from [10, Thm. 4])
    The CDF monotonicity argument in the proof of Theorem 2 requires the density of Q_lambda + lambda_j psi + lambda_k psi' to increase then decrease; this is imported as a known theorem rather than proved here.
  • standard math Majorization sequence lemma (Lemma 1, citing [7, 12.5a])
    Allows reducing a general majorization comparison to consecutive vectors differing in two coordinates; stated without proof.
  • domain assumption Infinite divisibility approximation (Section 3.3)
    The paper asserts without a full limiting argument that distributions in Qrel(mu) and Qabs(lambda, phi) are arbitrarily close to distributions in the fixed-parameter families, so tail bounds transfer to the general Gamma mixtures.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Extremal bounds for Gaussian trace estimation." pith.science (2026). https://pith.science/paper/O232LSNO

@misc{pith2026241115454,
  author       = {Pith},
  title        = {Pith review of: Extremal bounds for Gaussian trace estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O232LSNO}},
  note         = {Machine review of arXiv:2411.15454}
}
read the original abstract

This work derives extremal tail bounds for the Gaussian trace estimator applied to a real symmetric matrix. We define a partial ordering on the eigenvalues, so that when a matrix has greater spectrum under this ordering, its estimator will have worse tail bounds. This is done for two families of matrices: positive semidefinite matrices with bounded effective rank, and indefinite matrices with bounded 2-norm and fixed Frobenius norm. In each case, the tail region is defined rigorously and is constant for a given family.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

  1. [8]

    Sz´ ekely

    Farbod Roosta-Khorasani and G´ abor J. Sz´ ekely. Schur pro perties of con- volutions of gamma random variables. Metrika, 78(8):997–1014, 2015. 17

    work page 2015

  2. [1]

    On randomized trace estima tes for indefinite matrices with an application to determinants

    Alice Cortinovis and Daniel Kressner. On randomized trace estima tes for indefinite matrices with an application to determinants. Foundations of Computational Mathematics , 22(3):875–903, 2022

    work page 2022

  3. [2]

    Don’t use gaussians in stochastic trace estima- tion

    Ethan N Epperly. Don’t use gaussians in stochastic trace estima- tion. https://www.ethanepperly.com/index.php/2024/01/28/, Jan

    work page 2024

  4. [3]

    Epperly, Joel A

    Ethan N. Epperly, Joel A. Tropp, and Robert J. Webber. Xtrac e: Making the most of every sample in stochastic trace estimation. SIAM Journal on Matrix Analysis and Applications , 45(1):1–23, 2024

    work page 2024

  5. [4]

    Hutch++: Optimal stochastic trace estimation

    Raphael A Meyer, Cameron Musco, Christopher Musco, and Dav id P Woodruff. Hutch++: Optimal stochastic trace estimation. In Symposium on Simplicity in Algorithms (SOSA) , pages 142–155. SIAM, 2021

    work page 2021

  6. [5]

    Improved variants of the hutch++ algorithm for trace estimation

    David Persson, Alice Cortinovis, and Daniel Kressner. Improved variants of the hutch++ algorithm for trace estimation. SIAM Journal on Matrix Analysis and Applications , 43(3):1162–1185, 2022

    work page 2022

  7. [6]

    Improved variants of the hutch++ algorithm for trace estimation (preprint), 2022

    David Persson, Alice Cortinovis, and Daniel Kressner. Improved variants of the hutch++ algorithm for trace estimation (preprint), 2022

    work page 2022

  8. [7]

    Academic Press, 1992

    Josip E Peˇ cari´ c and Yung Liang Tong.Convex functions, partial orderings, and statistical applications . Academic Press, 1992

    work page 1992

Show all 11 references
  1. [9]

    Sz´ ekely, and Uri M

    Farbod Roosta-Khorasani, G´ abor J. Sz´ ekely, and Uri M. Ascher. Assessing stochastic algorithms for large scale nonlinear least squares proble ms using extremal probabilities of linear combinations of gamma random variab les. SIAM/ASA Journal on Uncertainty Quantification , 3...

    2015

  2. [10]

    Sz´ ekely and Nail K

    G´ abor J. Sz´ ekely and Nail K. Bakirov. Extremal probabilities for gaussian quadratic forms. Probability Theory and Related Fields , 126(2):184–202, 2003. 18

    2003

  3. [2024]

    Accessed: 2024-11-01

    2024

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.