Pure-DP Statistical Query Release at the Conjectured Square-Root Rate
2026-07-22 • Data Structures and Algorithms
Data Structures and AlgorithmsCryptography and Security
AI summaryⓘ
The authors address a question by Nikolov and Ullman about how well statistical queries on large data can be answered privately without too much error. They show it is possible to create a privacy mechanism that meets the expected best error rates under pure differential privacy, improving on previous bounds. Their method modifies an existing approach using multiplicative weights and carefully controls errors using advanced mathematical tools. They also verified their method rigorously with computer proofs to ensure privacy and accuracy hold under all conditions.
differential privacystatistical queriesmultiplicative weightsexpected errorpure differential privacyMaurey argumentRenyi divergenceHamming distanceinformation-theoretic privacyprivacy parameter
Authors
Jack Fitzsimons
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.