REVIEW 2 major objections 5 minor 12 references
On the Structure of Replicable Hypothesis Testers
T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Replicable testers for symmetric properties can be assumed to accept iff a deterministic statistic exceeds a uniform random threshold, without losing accuracy or samples.
desk verdict A substantial and largely sound paper: the canonical-properties theorem and chaining lower bound are real tools, but the Gaussian lower bound rests on an unproved folklore bound and the closeness claims should be softened. 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 mechanism is the canonical threshold format: an algorithm that draws $r \sim \mathrm{Unif}[0,1]$ and outputs accept if and only if $r \le f(X)$ for a deterministic $f: X^s \to [0,1]$. The construction defines $f(X)$ as the acceptance probability of the original algorithm on input $X$, then averages $f$ over permutations of the sample order and of the domain labels; the averaged $f$ keeps the accept/reject distribution unchanged on every distribution, inherits $\rho$-replicability, and gains $\rho$-permutation-robust replicability. A companion chaining lemma (Lemma 5.1) shows that if consecutive distributions in a chain have total variation distance at most $0.5$, then a canonical tester that is $2/3$-reliable on the two endpoints must fail replicability when the chain has length about $1/\rho$, which is what turns the canonical form into lower bounds.
What would settle it
Compute or numerically bound $\mathrm{TV}(\chi^2_k,\ \chi^2_k + t)$ for $t = 0.001\sqrt{k}$ at large $k$ (say $k \ge 10^4$) and check whether it stays below $0.1$; if it ever exceeds $0.1$, the chain construction in Lemma 7.14 that supports the replicable Gaussian mean testing lower bound breaks.
Extended reading notes
Core claim
The paper's central claim is Theorem 1.2: if a $\rho$-replicable algorithm tests a symmetric property of discrete distributions over $[n]$ with $s$ samples and accuracy $1-\delta$, then there is another $\rho$-replicable algorithm with the same sample count and accuracy that accepts exactly when a deterministic function $f(X)$ of the input exceeds a uniform random threshold in $[0,1]$; this $f$ is invariant to sample order and to element labels, and the algorithm is $\rho$-permutation-robust replicable, meaning its output stays stable even when the underlying distribution is replaced by a permutation of itself. This confines the whole problem of symmetric replicable testing to the choice of a single label-invariant statistic, and it removes the freedom of a replicable algorithm to use arbitrary internal randomness per input.
Load-bearing premise
The Gaussian lower bound relies on an unproved folklore bound on the total variation distance between a chi-square distribution $\chi^2_k$ and its shift by up to $0.001\sqrt{k}$; if that bound's constant or scaling is wrong, the claimed $\sqrt{d}/(\alpha^2\rho)$ term could fail.
Editorial extensions
If this is right
- Lower bounds for symmetric replicable testing problems only need to be proven against label-invariant threshold algorithms; the previously restricted lower bound of Liu and Ye holds in general.
- A general expectation-gap estimator converts any tester whose statistic has known expectation and bounded variance into a replicable one with $O(1/\rho^2)$ worst-case overhead, removing a $\log(1/\rho)$ factor from prior black-box reductions.
- Coin testing and closeness testing get constant-factor optimal replicable sample complexity, with closeness testing addressed for the first time, and uniformity testing gets replicability for free in the large-domain regime where $n \gg 1/(\epsilon^6\rho^2)$.
- Gaussian mean testing admits a polynomial-time replicable algorithm using $\tilde{O}(\sqrt{d}/(\alpha^2\rho) + \sqrt{d}/(\alpha\rho^2) + 1/(\alpha^2\rho^2))$ samples, improving the previous inefficient $\tilde{O}(\sqrt{d}/(\alpha^2\rho^2))$ bound.
- Replicable hypothesis selection with multiplicative approximation $3$ uses $O(\log^5 n/(\epsilon^2\rho^2))$ samples in the worst case and $O(\log^5 n/(\epsilon\rho))$ in expectation, and the improved coin tester implies better replicable sampling for any problem that uses coin testing as a black box.
Reading between the lines
- If the canonical form is right, the cost of replicability for a symmetric problem is determined by how spread out the test statistic $f$ is under near-null distributions; lower bounds could also be attacked by showing that every such $f$ must have large spread.
- The Gaussian tester's filtering of 'bad' distributions (large covariance in one direction or many large inner products) could plausibly be lifted to other high-dimensional replicable estimation tasks, such as covariance testing or estimation under arbitrary distributions.
- Proving or sharpening the folklore chi-square shift bound would settle the gap between the Gaussian mean testing upper and lower bounds; a counterexample to that bound would break the claimed $\sqrt{d}/(\alpha^2\rho)$ term.
- The improved in-expectation coin tester suggests a general 'replicability for free' regime for any non-replicable problem whose optimal sample complexity is much larger than $1/\rho$, whenever the problem admits an expectation-gap analysis.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops general structural and technical tools for replicable hypothesis testing. Its main results are: (i) a canonical-form theorem (Theorem 1.2) asserting that any replicable tester for a symmetric discrete property can be replaced, with the same sample count and accuracy, by a random-threshold algorithm that is order-invariant, label-invariant, and permutation-robustly replicable; (ii) a chaining lower-bound theorem (Theorem 1.3) that converts a chain of pairwise TV-close distributions into a replicability lower bound; (iii) a general ``expectation-gap'' framework for converting non-replicable estimators into replicable testers, yielding constant-factor-optimal or near-optimal bounds for coin, uniformity, and closeness testing; and (iv) a polynomial-time replicable Gaussian mean testing algorithm with a new upper bound plus a matching-in-leading-terms lower bound, together with a replicable hypothesis-selection algorithm. The paper is broad, with detailed proofs of the new structural claims and quantitative applications summarized in Table 1.
Significance. If the results hold, this is a significant advance in the young area of replicable distribution testing. The canonical reduction answers an open question of Liu and Ye and gives a clean target class against which lower bounds can be proved; the chaining framework systematizes the dominant lower-bound strategy; and the expectation-gap framework gives a reusable recipe for porting non-replicable testers. The Gaussian mean testing upper bound is notable as the first polynomial-time algorithm of its kind with a decoupled 1/ρ^2 term, and the hypothesis-selection result demonstrates a useful reduction to coin testing. The paper also ships unusually detailed proofs for the structural lemmas. The main caveats are two load-bearing gaps, both of which appear repairable: an unproved folklore chi-square total-variation bound used in the Gaussian lower bound, and an incomplete symmetrization argument in the matching-based filter of the Gaussian upper bound.
major comments (2)
- [§3.2, Prop. 3.7; §7.5, Lemma 7.14] Proposition 3.7 is stated as folklore without proof or citation, and it is the key ingredient in Lemma 7.14 for showing that the norms of empirical means from consecutive Gaussian means are TV-close. The bound dTV(χ²_k, χ²_k + t) ≤ 0.1 for 0 ≤ t ≤ 0.001√k is plausible and can likely be proved by a Hellinger or characteristic-function argument, but the Gaussian lower bound Theorem 1.10 would fail if the constant or scaling were wrong. The paper needs either a complete proof or an exact citation, including the small-k regime, and the statement should be given for signed |t| ≤ 0.001√k because Lemma 7.14 applies it to shifts that are random and signed.
- [§7.3, Lemma 7.7] The symmetrization proof of Lemma 7.7 does not, as written, establish the claimed existence of a fixed µ1 with the stated high-probability concentration for MS(X', Y'). The proof bounds |MS(X, Y) − µ1(X)| and |MS(X, Y') − µ2(Y')| separately and then appeals to the triangle inequality, but it never controls |µ1(X) − µ2(Y')|; µ1 depends on the first fixed X and µ2 depends on the fixed Y'. A correct argument needs an additional concentration step showing that these conditional expectations are close to a common value for most X and Y'. Since Lemma 7.7 underlies Step B of the Gaussian mean testing upper bound, the algorithm's correctness and replicability for arbitrary distributions are not fully supported as currently written.
minor comments (5)
- [Abstract and §1] There are typos such as ``defined by by'' in the abstract and ``alterate'' in Section 6.3.1; these should be corrected.
- [§7.5, Lemma 7.13] In the weak-replicability part of Lemma 7.13, the displayed inequality has the direction reversed: weak replicability gives Pr[A2(X;r) ≠ A2(X';r)] ≤ ρ, so the final line should conclude that the inequality probability is at most ρ, not at least 1−ρ.
- [§6.2, Corollary 6.9] In the proof of Corollary 6.9, ``δ = exp(1/ρ)'' should read ``δ = exp(−1/ρ)'' to match the stated failure probability exp(−1/ρ).
- [§5.1.2, Theorem 1.4] The proof invokes ``Lemma 4.3 in [LY24]'' informally with the phrase ``ignoring logarithmic factors''; the lemma, its parameters, and the precise logarithmic dependence should be stated formally so that the claimed tildes are checkable.
- [§7.4, Algorithm 7.1] In Step C of Algorithm 7.1, the text ``Y1,...,Ysa'' contains a typo, and the reuse of the names X1,...,Xs,Y1,...,Ys after Steps A and B is confusing; the fresh samples should be renamed.
Circularity Check
No circularity: the derivation chain is self-contained; the unproved folklore TV bound is a completeness gap, not a circular step.
full rationale
I walked the claimed derivation chain and found no step in which a prediction or first-principles result reduces, by the paper's own equations or by a load-bearing self-citation, to its own inputs. The canonical random-threshold reduction (Lemma 4.5) defines f(X) as the acceptance probability of the given algorithm; this is a transformation that preserves accuracy by construction and then proves replicability, rather than importing the target conclusion as an input. The chaining lower bound (Theorem 1.3 and Lemma 5.1) derives a contradiction from explicit indistinguishability assumptions and does not redefine the lower bound as the assumption. The expectation-gap upper bounds (Theorems 6.4, 6.15, 6.17, 6.21) compute sample complexity from stated expectation, variance, and gap conditions, with no fitted parameter renamed as a prediction. The Gaussian mean testing upper bound uses concentration and variance estimates derived in the paper, and the lower bound uses a sufficient-statistic reduction (Lemma 7.12) plus a chaining argument; both steps are proved rather than assumed. Self-citations such as [LY24], [HIK+24], and [Nar22] are either prior results being improved or external statistical lemmas, and they are not used to assume the new theorem being proved. The one noteworthy gap is Proposition 3.7, an unproved folklore bound on the total variation distance between chi-square and shifted chi-square distributions; it is load-bearing in Lemma 7.14 for the Gaussian lower bound. This is a correctness or completeness concern, not circularity: the bound is an external analytic fact stated as an assumption, and it does not encode the paper's conclusions, so it does not raise the circularity score.
Assumptions & free parameters
assumptions (7)
- standard math Pinsker's inequality and standard Chernoff, Hoeffding, and Bernstein concentration bounds (Theorem 3.4).
- domain assumption Valiant's wishful-thinking lemmas for symmetric distribution-testing lower bounds (Theorems 5.4 and 5.6).
- domain assumption Folklore total-variation bound between a chi-square and a shifted chi-square (Proposition 3.7).
- domain assumption Empirical mean is a sufficient statistic for an identity-covariance Gaussian (Proposition 3.9).
- domain assumption Analysis of the collision statistic for uniformity testing (Lemma 6.18 from [DGPP19]) and of the chi-square style closeness statistic (Lemma 6.19 from [CDVV14]).
- standard math Concentration inequality for submodular functions of independent random variables (Theorem 3.5, from [BLM00]).
- standard math Variance bound for bounded random variables (Theorem 3.6, from [BD00]).
Cite this review
Pith. "Pith review of On the Structure of Replicable Hypothesis Testers." pith.science (2026). https://pith.science/paper/FYJWNBJI
@misc{pith2026250702842,
author = {Pith},
title = {Pith review of: On the Structure of Replicable Hypothesis Testers},
year = {2026},
howpublished = {\url{https://pith.science/paper/FYJWNBJI}},
note = {Machine review of arXiv:2507.02842}
}
abstract
A hypothesis testing algorithm is replicable if, when run on two different samples from the same distribution, it produces the same output with high probability. This notion, defined by by Impagliazzo, Lei, Pitassi, and Sorell [STOC'22], can increase trust in testing procedures and is deeply related to algorithmic stability, generalization, and privacy. We build general tools to prove lower and upper bounds on the sample complexity of replicable testers, unifying and quantitatively improving upon existing results. We identify a set of canonical properties, and prove that any replicable testing algorithm can be modified to satisfy these properties without worsening accuracy or sample complexity. A canonical replicable algorithm computes a deterministic function of its input (i.e., a test statistic) and thresholds against a uniformly random value in $[0,1]$. It is invariant to the order in which the samples are received, and, if the testing problem is ``symmetric,'' then the algorithm is also invariant to the labeling of the domain elements, resolving an open question by Liu and Ye [NeurIPS'24]. We prove new lower bounds for uniformity, identity, and closeness testing by reducing to the case where the replicable algorithm satisfies these canonical properties. We systematize and improve upon a common strategy for replicable algorithm design based on test statistics with known expectation and bounded variance. Our framework allow testers which have been extensively analyzed in the non-replicable setting to be made replicable with minimal overhead. As direct applications of our framework, we obtain constant-factor optimal bounds for coin testing and closeness testing and get replicability for free in a large parameter regime for uniformity testing. We also give state-of-the-art bounds for replicable Gaussian mean testing, and, unlike prior work, our algorithm runs in polynomial time.
Reference graph
Works this paper leans on
-
[1]
[ABB24] Saba Ahmadi, Siddharth Bhandari, and Avrim Blum. Replicable online learning. arXiv preprint arXiv:2411.13730,
-
[4]
Collision-based testers are optimal for uniformity and closeness
[DGPP19] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Collision-based testers are optimal for uniformity and closeness. Chicago Journal of Theoretical Computer Science , 2019, May
work page 2019
-
[5]
Property testing for differential privacy
[GM18] Anna C Gilbert and Audra McMillan. Property testing for differential privacy. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages 249–
work page 2018
-
[9]
On the Computational Landscape of Replicable Learning
[KKVZ24] Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas, and Felix Zhou. On the computational land- scape of replicable learning. arXiv preprint arXiv:2405.15599 ,
-
[10]
Improved replicable boosting with majority-of-majorities
[LMS25] Kasper Green Larsen, Markus Engelund Mathiasen, and Clement Svendsen. Improved replicable boosting with majority-of-majorities. arXiv preprint arXiv:2501.18388 ,
-
[11]
[L V21] Jasper C.H. Lee and Paul Valiant. Uncertainty about uncertainty: Optimal adaptive algorithms for estimating mixtures of unknown coins. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) ,
work page 2021
-
[2003]
Repli- cable learning of large-margin halfspaces
[KKL+24] Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, and Felix Zhou. Repli- cable learning of large-margin halfspaces. arXiv preprint arXiv:2402.13857 ,
-
[2015]
Testing symmetric properties of distributions
[Val11] Paul Valiant. Testing symmetric properties of distributions. SIAM J. Comput., 40(6):1927–1968,
work page 1927
Show all 12 references
-
[2018]
The Complexity of Verifying Loop-Free Programs as Differentially Private
[GNP20] Marco Gaboardi, Kobbi Nissim, and David Purser. The Complexity of Verifying Loop-Free Programs as Differentially Private. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), vol...
2020
-
[2020]
59 [HIK+24] Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, and Christopher Ye
Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. 59 [HIK+24] Max Hopkins, Russell Impagliazzo, Daniel Kane, Sihan Liu, and Christopher Ye. Replicability in high dimensional statistics. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1–8. IEEE,
2024
-
[2023]
Borsuk-ulam and replicable learning of large-margin halfspaces
[BHH+25] Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak. Borsuk-ulam and replicable learning of large-margin halfspaces. arXiv preprint arXiv:2503.15294 ,
-
[2025]
Stability and Replicability in Learning
[CMY23] Zachary Chase, Shay Moran, and Amir Yehudayoff. Stability and Replicability in Learning . In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2430–2439, Los Alamitos, CA, USA, November
2023
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.