Pith. sign in

REVIEW 5 minor 29 references

A pure ε-differentially private mechanism can release k statistical queries with expected worst-coordinate error at most a constant times sqrt(log(2T) log(2k)/(εn)), matching the conjectured square-root lower bound.

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 · deepseek-v4-flash

2026-08-04 03:35 UTC pith:L6EMM4CU

arxiv 2607.20418 v2 pith:L6EMM4CU submitted 2026-07-22 cs.DS cs.CR

Pure-DP Statistical Query Release at the Conjectured Square-Root Rate

Jack Fitzsimons This is my paper
classification cs.DS cs.CR MSC 68P2768W20
keywords statistical query releasepure differential privacymultiplicative weightslikelihood envelopeworst-case errorHamming ball dominationquery releaseformal verification
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.

The paper proves that pure differential privacy can release k statistical queries over a universe of size T with expected worst-coordinate error at most a constant times min{1, sqrt(log(2T) log(2k)/(εn))}, where n is the database size—matching the square-root scaling of known lower bounds in high-dimensional regimes and settling a long-standing open problem. The construction runs a private multiplicative-weights transcript that only selects which signed query to fix each round, then replaces the transcript's probability mass function by a distance-penalized likelihood envelope: a transcript is weighted by the largest likelihood it receives under any database, exponentially discounted by that database's Hamming distance from the true input. This envelope is pure ε-DP by construction; the proof's work is showing it does not shift too much probability to inaccurate transcripts, via a likelihood-level domination of each Hamming ball by a small auxiliary family of PMW laws, with moment bounds for nearby balls, a mixture bound for distant balls, and radius blocking to avoid an extra 1/ε factor. The same envelope, with a uniformly sampled query and private sign selection, gives expected normalized Euclidean error at most a constant times min{1, sqrt(log(2T)/(εn))}, with no dependence on k. A machine-checked formalization accompanies the proof and verifies the finite mechanisms, pure privacy after decoding, and both displayed bounds.

Core claim

The paper's central claim is that the conjectured pure-DP query-release rate is achievable in the worst-coordinate metric: for every finite universe D, every finite query family Q, every database size n≥1, and every ε>0, there exists a pure ε-differentially private mechanism with output in R^Q such that the supremum over databases of expected worst-coordinate error is at most 129e·min{1, sqrt(log(2T) log(2k)/(εn))}. This matches the square-root lower-bound dependence in the regimes where lower bounds are known. The paper also proves an envelope-based information-theoretic mechanism with normalized Euclidean error at most 62e·min{1, sqrt(log(2T)/(εn))}, independent of the number of queries, r

What carries the argument

The central object is the distance-penalized likelihood envelope. For a database x and transcript ω, the paper defines ep_x(ω)=max_y e^{-(ε/2)d_H(x,y)} p_y(ω), where p_y is the selection-only private-multiplicative-weights transcript distribution on database y and d_H is Hamming distance; after normalization, the resulting distribution is pure ε-DP because replacing one row changes every discounted likelihood by at most e^{ε/2}. To control the utility loss from normalization, the proof establishes a likelihood-level domination bound: over the Hamming ball of radius R around x, the maximum transcript likelihood is at most e^{κR²/m} times the maximum over an auxiliary family V_{x,R,m} of at mo

Load-bearing premise

The utility proof assumes the private multiplicative-weights analysis—regret bounds, softmax selection error, and integer likelihood-ratio moment bounds—remains valid for arbitrary antisymmetric surrogate target vectors that no database realizes and whose coordinates may lie outside [-1,1]; the likelihood-level domination and the integer moment bound both require this extension.

What would settle it

The decisive check is the integer likelihood-ratio moment bound: search small instances for an admissible target v with d*(v,a(x))≤R that violates sum_ω p_x(ω)(p_v(ω)/p_x(ω))^r ≤ e^{A_R r²}; since this bound is used verbatim in the envelope utility proof, a single violation would invalidate the claimed rate.

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

Share X Bluesky LinkedIn Reddit HN

If this is right

  • If correct, the result closes the worst-coordinate query-release gap: pure DP now matches the square-root dependence on 1/n that approximate-DP mechanisms achieve in standard high-dimensional regimes.
  • The bounds hold uniformly for every finite T, k, n, and ε, with shifted logarithms and an outer minimum covering degenerate cases such as singleton universes or single queries.
  • In the normalized Euclidean metric, the envelope mechanism achieves error sqrt(log T/(εn)) independent of k, confirming that the number of queries need not enter this rate.
  • Markov's inequality converts the expected-error guarantees into constant-probability accuracy at the same asymptotic rate, and repetition with a median can reduce failure probability at the cost of a sqrt(log(1/ζ)) factor.
  • The machine-checked formalization verifies pure privacy after deterministic decoding and the displayed all-regimes bounds, making the theorem's proof mechanically auditable.

Where Pith is reading between the lines

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

  • The envelope construction is not tied to the specific PMW dynamics: any base transcript distribution whose likelihoods satisfy finite-order ratio moment bounds could be plugged in, suggesting the approach may transfer to other oracle-based private selection rules.
  • The radius-blocking technique—grouping Hamming radii into blocks of width Θ(1/ε) to remove a would-be 1/ε factor in the error—is a reusable analysis pattern for any distance-penalized envelope mechanism, not just query release.
  • The largest obstacle to practical use is computational: the envelope maximizes over all T^n databases and the transcript space has size (2k)^J, so an efficient implementation would need to approximate the envelope or shrink the code family; this is open in the paper.
  • Because the proof routes through antisymmetric surrogate targets that need not be real databases, a natural stress test is whether the moment bounds survive for sparse or extreme targets; if they do not, the constants or proof structure would need adjustment.

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

0 major / 5 minor

Summary. The paper addresses the Nikolov–Ullman pure-DP statistical query release problem. It constructs, for every finite universe D, query family Q, database size n, and privacy parameter ε>0, a pure ε-DP mechanism whose expected worst-coordinate error is at most 129e·min{1, sqrt(log(2T)log(2k)/(εn))}, matching the known lower-bound scaling in the regimes where those bounds apply. The construction first generates a selection-only PMW transcript, then replaces the transcript distribution by a Hamming-discounted likelihood envelope over all databases, and finally decodes deterministically. The utility proof is built from a likelihood-level Maurey domination lemma, integer-order likelihood-ratio moment bounds, a mixture argument for distant Hamming balls, and a blocked-radius summation that avoids an extra 1/ε factor. A secondary theorem recovers the normalized Euclidean rate 62e·min{1, sqrt(log(2T)/(εn))}. The paper also reports a companion Lean 4 formalization of both mechanisms, their pure-privacy proofs, and the displayed all-regimes bounds.

Significance. If correct, the paper closes a long-standing gap between approximate-DP and pure-DP query release and resolves the stated open problem in the expected-error formulation. The proof is unusually careful: the main bound is derived with explicit constants and no fitted parameters; the all-regimes statements avoid customary nondegeneracy conditions; and the claimed Lean 4 formalization of the finite constructions, privacy proofs, and final bounds is a substantial verification asset. The underlying ideas—likelihood-level Maurey domination, grouping Hamming radii at the privacy scale, and the envelope metric-extension viewpoint—are likely to be reusable. The potential weak point flagged in the stress test, namely that admissible surrogate targets may leave [-1,1] and need not correspond to any database, does not materialize: Proposition 3.2 controls the utility robustly through d*(a,a(x)), and Lemma 6.1 uses only the corresponding δ bound, so the unbounded-coordinate issue is explicitly addressed.

minor comments (5)
  1. [§9] Before (9.8), the text says 'put R = min{R, n}', which reassigns the same symbol used in H_R^(2) and in the subsequent estimates. Use a separate symbol such as \bar R or R_cap to avoid a self-referential definition.
  2. [Lemma A.1] In the proof, the expression '=atanh(a/2)' should be typeset as '= a·tanh(a/2)' to avoid being misread as the inverse hyperbolic tangent function arctanh.
  3. [§7] The subscripted variable u_ε is visually cramped in displays such as '2euεα0'. Insert spacing, e.g., '2 e u_ε α_0', so the subscript ε is not misread as an extra multiplicative factor.
  4. [§1.1] The constants 129e and 62e should be explicitly identified as 129·e and 62·e, with e denoting the base of natural logarithms, either in the theorem statements or in a preliminary notation paragraph.
  5. [§11] The Lean development is described as ancillary material and a SHA-256 digest is given. A persistent artifact DOI or repository link would make the formalization more accessible to readers who wish to verify the machine-checked claims.

Circularity Check

0 steps flagged

No significant circularity: the upper bound is derived from an explicit mechanism and proof, not assumed or fitted.

full rationale

The paper's central claim, Theorem 1.1, is an existence result proved by constructing an explicit envelope mechanism and deriving its expected worst-coordinate error. The construction does not define its private output in terms of the target error, and the final bound is not an input to the proof. Parameters J, eta, and gamma are chosen as explicit closed-form functions of T, k, epsilon, and n (Eq. 8.3) solely to satisfy the inequalities derived in Sections 5-7; this is parameter balancing, not data fitting or prediction-from-fit. The envelope (Eq. 4.1) is defined from the base PMW transcript and Hamming distance, not from the claimed error bound. Utility is proved by independent estimates: Maurey domination (Lemma 5.1), integer likelihood-ratio moment bounds (Lemma 6.1), near/far ball estimates, and blocked summation (Lemma 7.1). None of these identities is equivalent to the final bound by construction; each is a separate analytic inequality. The paper makes no load-bearing self-citations: the references to prior work, including Nikolov's JL mechanism and the lower bounds of Hardt and of Lyu-Talwar, are used only as context or comparison. The companion Lean formalization is additional independent evidence rather than a substitute for the proof. The discussion section openly identifies limitations, such as the information-theoretic nature and the lack of optimal confidence dependence, which are correctness concerns, not circularity. The weakest point noted by the reader - that admissible surrogate targets need not be realized by any database - is a potential mathematical gap in the proof, not a circular definitional relationship. Overall, the derivation chain is self-contained and the claimed result is not presupposed.

Axiom & Free-Parameter Ledger

7 free parameters · 5 axioms · 0 invented entities

No free physical parameters or invented ontological entities. The 'envelope' and 'admissible surrogate targets' are mathematical proof constructions, not commitments to new entities with independent empirical handles. The listed free parameters are explicit proof constants and mechanism hyperparameters, chosen analytically rather than fitted to data.

free parameters (7)
  • J (Theorem 1.1 PMW rounds) = ceil(98 log(2T)/α²)
    Explicit construction choice in §8; balances Hedge regret against envelope-growth condition. Not fitted to empirical data; part of mechanism design.
  • η (Theorem 1.1 selection strength) = 57 log(2k)/α
    Chosen in §8 to control the softmax selection error; explicit proof parameter.
  • γ (Theorem 1.1 update step) = α/7
    Chosen in §8 to balance PMW update discretization; explicit proof parameter.
  • J (Theorem 1.2 PMW rounds) = ceil(20000 log(2T)/α⁴)
    Parameter balance for the normalized Euclidean version in §9.
  • γ (Theorem 1.2 update step) = α²/96
    Parameter balance for Theorem 1.2 in §9.
  • c0 (envelope-growth constant) = 1/900
    Hand-chosen in §7 so that 5√c0 = 1/6; used to keep ball-likelihood growth below the envelope penalty.
  • B (radial block width) = max{1, ceil(3/ε)}
    Radial blocking scale chosen in §7 to eliminate the otherwise unavoidable 1/ε discretization loss.
axioms (5)
  • standard math Finite probability spaces and standard inequalities: Hoeffding, Jensen, Hölder, Rényi divergence properties.
    Used throughout §2 and Appendix A; finite spaces make all sums and maxima finite.
  • standard math PMW/Hedge regret bound and softmax gap tail bound.
    Lemma A.2 and Lemma A.3; standard multiplicative-weights potential argument used for base PMW utility.
  • standard math Maurey's empirical method applies to transcript likelihoods with ℓ∞ row moves.
    Lemma 5.1 uses random row moves to dominate Hamming-ball likelihoods by a family of size (T²+1)^m.
  • domain assumption Data universe D is finite, queries map D to [-1,1], adjacency is one-row replacement, databases have fixed size n.
    §1.1; the privacy definition, the envelope metric, and the PMW update all depend on these assumptions.
  • domain assumption PMW softmax selection gives positive mass to every transcript under every admissible target.
    The envelope construction and normalizer Z_x ≥ 1 require common support across neighboring databases; guaranteed because each round uses a softmax with positive weights.

pith-pipeline@v1.3.0-alltime-deepseek · 18589 in / 31084 out tokens · 233519 ms · 2026-08-04T03:35:09.562153+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Pure-DP Statistical Query Release at the Conjectured Square-Root Rate." pith.science (2026). https://pith.science/paper/L6EMM4CU

@misc{pith2026260720418,
  author       = {Pith},
  title        = {Pith review of: Pure-DP Statistical Query Release at the Conjectured Square-Root Rate},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L6EMM4CU}},
  note         = {Machine review of arXiv:2607.20418}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Nikolov and Ullman asked whether k statistical queries on a universe of size T can be released under pure differential privacy with expected worst-coordinate error at the square-root rate suggested by known lower bounds. We prove their conjectured upper bound. For every database size n and privacy parameter $\varepsilon>0$, there is an $\varepsilon$-differentially private mechanism with expected error $O(\min\{1,\sqrt{\log(2T)\log(2k)/(\varepsilon n)}\})$. This matches the lower-bound dependence in the standard high-dimensional regimes where those bounds apply; the shifted logarithms and outer minimum make the upper bound valid without additional parameter assumptions. The construction starts from a selection-only private multiplicative weights transcript, then replaces its probability mass function by a distance-penalized likelihood envelope. To prove that the modification preserves accuracy, a likelihood-level Maurey argument upper-bounds each Hamming-ball maximum by a small family of auxiliary PMW laws. Renyi moment bounds control nearby balls, a direct mixture bound controls distant balls, and grouping radii at the privacy scale prevents an additional $1/\varepsilon$ factor in the error. The mechanism is information-theoretic. A companion Lean 4 development machine-checks the finite construction, pure privacy after deterministic decoding, and the displayed all-regimes upper bound.

Review history (2 revisions) →

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

29 extracted references · 4 linked inside Pith

  1. [1]

    Journal of the ACM , volume =

    Avrim Blum and Katrina Ligett and Aaron Roth , title =. Journal of the ACM , volume =. 2013 , doi =

    2013

  2. [2]

    Theory of Cryptography Conference , series =

    Mark Bun and Thomas Steinke , title =. Theory of Cryptography Conference , series =. 2016 , doi =

    2016

  3. [3]

    Theory of Cryptography Conference , series =

    Cynthia Dwork and Frank McSherry and Kobbi Nissim and Adam Smith , title =. Theory of Cryptography Conference , series =. 2006 , doi =

    2006

  4. [4]

    Foundations and Trends in Theoretical Computer Science , volume =

    Cynthia Dwork and Aaron Roth , title =. Foundations and Trends in Theoretical Computer Science , volume =. 2014 , doi =

    2014

  5. [5]

    Schapire , title =

    Yoav Freund and Robert E. Schapire , title =. Journal of Computer and System Sciences , volume =. 1997 , doi =

    1997

  6. [6]

    Theory of Cryptography Conference , series =

    Anupam Gupta and Aaron Roth and Jonathan Ullman , title =. Theory of Cryptography Conference , series =. 2012 , doi =

    2012

  7. [7]

    2011 , type =

    Moritz Hardt , title =. 2011 , type =

    2011

  8. [8]

    42nd Annual ACM Symposium on Theory of Computing , pages =

    Moritz Hardt and Kunal Talwar , title =. 42nd Annual ACM Symposium on Theory of Computing , pages =. 2010 , doi =

    2010

  9. [9]

    Rothblum , title =

    Moritz Hardt and Guy N. Rothblum , title =. 51st Annual IEEE Symposium on Foundations of Computer Science , pages =. 2010 , doi =

    2010

  10. [10]

    Journal of the American Statistical Association , volume =

    Wassily Hoeffding , title =. Journal of the American Statistical Association , volume =. 1963 , doi =

    1963

  11. [11]

    30th IEEE Computer Security Foundations Symposium , pages =

    Ilya Mironov , title =. 30th IEEE Computer Security Foundations Symposium , pages =. 2017 , doi =

    2017

  12. [12]

    2021 , month = jul, url =

    Aleksandar Nikolov and Jonathan Ullman , title =. 2021 , month = jul, url =

    2021

  13. [13]

    Rothblum and Salil P

    Cynthia Dwork and Guy N. Rothblum and Salil P. Vadhan , title =. 51st Annual IEEE Symposium on Foundations of Computer Science , pages =. 2010 , doi =

    2010

  14. [14]

    Advances in Neural Information Processing Systems , volume =

    Moritz Hardt and Katrina Ligett and Frank McSherry , title =. Advances in Neural Information Processing Systems , volume =. 2012 , url =

    2012

  15. [15]

    45th Annual ACM Symposium on Theory of Computing , pages =

    Aleksandar Nikolov and Kunal Talwar and Li Zhang , title =. 45th Annual ACM Symposium on Theory of Computing , pages =. 2013 , doi =

    2013

  16. [16]

    46th Annual ACM Symposium on Theory of Computing , pages =

    Mark Bun and Jonathan Ullman and Salil Vadhan , title =. 46th Annual ACM Symposium on Theory of Computing , pages =. 2014 , doi =

    2014

  17. [17]

    Towards Instance-Optimal Private Query Release , booktitle =

    Jaros. Towards Instance-Optimal Private Query Release , booktitle =. 2019 , doi =

    2019

  18. [18]

    Proceedings of the 2023 ACM--SIAM Symposium on Discrete Algorithms , pages =

    Aleksandar Nikolov , title =. Proceedings of the 2023 ACM--SIAM Symposium on Discrete Algorithms , pages =. 2023 , doi =

    2023

  19. [19]

    57th Annual ACM Symposium on Theory of Computing , pages =

    Xin Lyu and Kunal Talwar , title =. 57th Annual ACM Symposium on Theory of Computing , pages =. 2025 , doi =

    2025

  20. [20]

    Advances in Neural Information Processing Systems 38 , pages =

    Yingyu Lin and Erchi Wang and Yi-An Ma and Yu-Xiang Wang , title =. Advances in Neural Information Processing Systems 38 , pages =. 2025 , url =. 2503.21071 , archivePrefix =

    arXiv 2025

  21. [21]

    Duchi , title =

    Hilal Asi and John C. Duchi , title =. 2020 , howpublished =. 2005.10630 , archiveprefix =

    Pith/arXiv arXiv 2020

  22. [22]

    2018 , howpublished =

    Christian Borgs and Jennifer Chayes and Adam Smith and Ilias Zadik , title =. 2018 , howpublished =. 1810.12518 , archiveprefix =

    Pith/arXiv arXiv 2018

  23. [23]

    Chayes and Adam D

    Christian Borgs and Jennifer T. Chayes and Adam D. Smith and Ilias Zadik , title =. 59th Annual IEEE Symposium on Foundations of Computer Science , pages =. 2018 , doi =

    2018

  24. [24]

    52nd Annual ACM Symposium on Theory of Computing , pages =

    Alexander Edmonds and Aleksandar Nikolov and Jonathan Ullman , title =. 52nd Annual ACM Symposium on Theory of Computing , pages =. 2020 , doi =

    2020

  25. [25]

    Proceedings of Thirty Eighth Conference on Learning Theory , editor =

    Badih Ghazi and Crist. Proceedings of Thirty Eighth Conference on Learning Theory , editor =. 2025 , url =. 2502.14809 , archivePrefix =

    Pith/arXiv arXiv 2025

  26. [26]

    Fixed-Parameter Tractability of Private Synthetic Data Generation , booktitle =

    Badih Ghazi and Crist. Fixed-Parameter Tractability of Private Synthetic Data Generation , booktitle =. 2026 , eprint =

    2026

  27. [27]

    Proceedings of the 58th Annual ACM Symposium on Theory of Computing , series =

    Aleksandar Nikolov and Haohua Tang and Jonathan Ullman , title =. Proceedings of the 58th Annual ACM Symposium on Theory of Computing , series =. 2026 , month = jun, doi =. 2605.08358 , archivePrefix =

    Pith/arXiv arXiv 2026

  28. [28]

    48th Annual IEEE Symposium on Foundations of Computer Science , pages =

    Frank McSherry and Kunal Talwar , title =. 48th Annual IEEE Symposium on Foundations of Computer Science , pages =. 2007 , doi =

    2007

  29. [29]

    Gilles Pisier , title =. S. 1980--1981 , note =

    1980