arXiv CSopen access

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

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

arXiv:2607.20418v1 [cs.DS] 22 Jul 2026

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 [NU21]. We prove their conjectured upper bound. For every database size n and privacy parameter ε > 0, there is an ε-differentially private mechanism with expected error ( r )! log(2T ) log(2k) O min 1, . ε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 (PMW) transcript. At the desired parameters this base transcript is accurate and has good finite-order privacy-loss moments, but direct pure-DP accounting for it gives only the older cube-root tradeoff. We therefore replace its probability mass function by a distancepenalized likelihood envelope: a transcript receives the largest likelihood it has under any database, discounted exponentially by that database’s Hamming distance from the true input. After normalization, this yields the pointwise likelihood-ratio bound required for pure DP. 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. Rényi moment bounds control nearby balls, a direct mixture bound controls distant balls, and grouping radii at scale 1/ε prevents an additional 1/ε loss. The mechanism is information-theoretic. A companion Lean 4 development machinechecks the finite construction, pure privacy after deterministic decoding, and the displayed all-regimes upper bound.

1

1

Introduction

Suppose a curator wants to publish many averages of the same private database. For a single average, sensitivity is O(1/n), so sensitivity-calibrated noise is small. Answering k averages independently, however, incurs cumulative privacy cost. The query-release problem asks whether the curator can exploit the fact that all answers come from one empirical distribution. Formally, let D be a finite data universe, let Q be a nonempty finite family of bounded functions q : D → [−1, 1], and let x = (x1 , . . . , xn ) ∈ Dn . The answer to q is n

Fq (x) =

1X q(xi ), n

F (x) = (Fq (x))q∈Q .

i=1

We seek one private random vector that approximates every coordinate of F (x). This is the statistical-query release problem in differential privacy [DMNS06, DR14]. The gap addressed here is between approximate and pure privacy. Approximate DP allows an additive δ > 0 term in the privacy inequality, whereas pure DP sets δ = 0. Private multiplicative weights and iterative database constructions achieve n−1/2 -type accuracy under approximate DP [HR10, GRU12, HLM12]. The classical pure-DP small-database method gives only a cube-root upper bound for worst-coordinate error [BLR13]. Nikolov and Ullman isolated this gap as Open Problem 1 on DifferentialPrivacy.org. Their statement explicitly focuses on expected error, while noting that query-release algorithms often also provide high-probability guarantees [NU21]. In precisely this expected-ℓ∞ sense, they conjectured the pure-DP rate r log k log T , εn and noted that it would match the known lower-bound scaling in the standard high-dimensional regimes [Har11, NU21]. Our main theorem establishes this conjectured upper bound uniformly over all parameter choices. The corresponding lower bounds apply in nondegenerate high-dimensional regimes. The obstacle is a mismatch between the privacy information supplied by PMW and the privacy guarantee we need. At the square-root parameters, a selection-only PMW transcript is accurate and its privacy loss has good finite moments. Such moment bounds underlie concentrated and approximate DP, but pure DP requires a pointwise likelihood-ratio inequality for every transcript. Conditioning on a likely “good” privacy-loss event does not repair this mismatch: two neighboring datasets could retain different supports. Nor can we union-bound over nearby databases, because even a small Hamming ball may contain exponentially many of them. We repair the transcript distribution itself. Let Px be the distribution of the selection-only PMW transcript on database x, and let px (ω) be the probability of transcript ω. Before releasing anything, form the unnormalized envelope pex (ω) = maxn e−(ε/2)dH (x,y) py (ω). y∈D

(1.1)

For a fixed transcript, the expression asks how likely that transcript could be under any database, but charges a factor e−ε/2 for each changed row. Moving the input x by one row changes every discounted likelihood by at most eε/2 . The same is true of their maximum. After dividing by the total envelope mass, the changing normalizer costs a second eε/2 , and the resulting transcript mechanism is pure ε-DP. This factor-two normalization pattern mirrors the metric-extension geometry of Borgs, Chayes, Smith, and Zadik [BCSZ18a]. 2

There is also a direct differential-privacy antecedent. If each reference law Py is a point mass at a deterministic statistic f (y), then for every ω in the range of f , (1.1) becomes   ε pex (ω) = exp − min dH (x, y) , 2 y:f (y)=ω which is exactly the discrete inverse-sensitivity mechanism studied by Asi and Duchi after normalization [AD20]. Here the reference laws are instead nondegenerate PMW transcript distributions, and the central utility question is whether their likelihood envelope remains close enough to the original PMW law. Privacy follows directly from the metric form of the envelope; utility is the main technical issue. Because the envelope pointwise dominates the original PMW mass function, it may assign additional probability to transcripts that decode to inaccurate answers. Utility therefore reduces to two questions: how much total probability mass the envelope adds, and how much error-weighted mass it adds. The rest of the proof answers both questions without enumerating the databases in a Hamming ball.

1.1

Main theorem

Throughout, databases have fixed size and two databases are adjacent when one row is replaced, equivalently when their Hamming distance is one. A randomized mechanism is pure ε-differentially private if, for neighboring x, x′ and every subset E of its output space, P[M (x) ∈ E] ≤ eε P[M (x′ ) ∈ E].

(1.2)

Theorem 1.1 (The conjectured pure-DP query-release upper bound). There is a universal constant C > 0 with the following property. Let D be finite with T = |D| ≥ 1, let Q be nonempty and finite with k = |Q| ≥ 1, let n ≥ 1, and suppose every q ∈ Q maps D to [−1, 1]. For every ε > 0, there exists a randomized mechanism M with output in RQ that is pure ε-differentially private and satisfies ( r ) log(2T ) log(2k) sup E ∥M (x) − F (x)∥∞ ≤ C min 1, . (1.3) εn x∈Dn The mechanism has finite output support. It is information-theoretic: both the transcript space and the maximum in (1.1) are finite, but they may be exponentially large.

1.2

Construction and proof strategy

The mechanism consists of three steps. Likelihood domination will be used to bound the utility loss introduced by the second step. 1. Define the selection-only PMW transcript distribution. Starting from the uniform synthetic distribution on D, repeatedly use the exponential mechanism to select a signed query on which the synthetic distribution disagrees with the private database. Update the synthetic distribution in the direction indicated by that signed query. The transcript ω records only the selected query indices and signs; it contains no numerical answers. 2. Replace the transcript distribution by its privacy envelope. For every possible transcript, compute (1.1), sum these weights to obtain a normalizer Zx , and sample the transcript from pex /Zx . This is the transcript sampled by the private core of the mechanism. 3

3. Decode publicly. The selected queries determine every PMW update, so the entire synthetic trajectory can be replayed from the transcript. Output the query answers of the average synthetic distribution. This deterministic decoding does not spend privacy. The first step supplies utility, but its direct pure-DP bound exceeds the target privacy budget. The second step supplies pure privacy but can distort the first distribution. The proof is therefore about showing that the distortion is small where the decoder’s error is large. The utility quantity. Fix the true database x, and let Lx (ω) denote the worst-coordinate error of the answer decoded from transcript ω. Since the normalized mechanism samples with probability pex (ω)/Zx , its expected error is 1 X pex (ω)Lx (ω). Zx ω The pointwise majorant contains the accurate base mass px , and this also shows Zx ≥ 1. Normalization can nevertheless shift probability toward inaccurate transcripts. It remains to bound the extra unnormalized mass and extra error-weighted mass contributed by databases y ̸= x. Likelihood-level domination for a Hamming ball. Consider databases within Hamming distance R of x. Their query-answer vectors differ from that of x by averages of at most R elementary row replacements. For the utility analysis, a likelihood-level Maurey argument upper-bounds the maximum transcript likelihood over every database in this ball by the maximum over a small family of auxiliary PMW laws. The family is obtained by sampling m row replacements and has at most (T 2 + 1)m descriptions. Although the sampling law for a particular database depends on that database, its support family depends only on x, R, and m. A fixed-transcript log-sum-exp and Hoeffding estimate gives the pointwise domination, at multiplicative cost  2 ρR 8Jη 2 exp , ρ= . 4m n2 Here J is the number of PMW rounds and η is the exponential-mechanism selection strength. The auxiliary answer vectors need not correspond to real databases, and a maximizing vector may depend on the fixed transcript. This is why the PMW analysis is first extended to antisymmetric surrogate targets; they are analytical interpolation points, never possible outputs or private inputs. Why there are two distance regimes. After this domination, two different estimates are available. For a nearby ball, finite-order Rényi bounds control the maximum likelihood over the codebook, and Hölder’s inequality transfers the base PMW L2 error bound. For a distant ball, this moment estimate becomes expensive. There it is better to replace the maximum by the sum of the codebook likelihoods; each is a probability distribution of total mass one. Optimizing the codebook size in either regime gives ball growth p exp{O(R ρ log(T 2 + 1))}. The PMW parameters are chosen so that this growth is much slower than the envelope penalty e−εR/2 . Here is the quantitative interface proved later. Define the radius-R ball maximum HR (ω) =

max y:dH (x,y)≤R

py (ω),

κ= 4

2Jη 2 , n2

L = log(T 2 + 1).

The moment and mixture regimes together give X

HR (ω) ≤ e

√ 5R κL

,

ω

X

HR (ω)Lx (ω) ≤ e

ω

√ 5R κL

  8R . α0 + n

Why radii are blocked. Summing the resulting estimate separately over every integer radius would still introduce an unwanted factor 1/ε. We instead group radii into blocks of width Θ(1/ε). Within a block, the outer radius bounds the likelihood growth while the inner radius supplies the privacy penalty. The block weights then have constant total mass and constant block-index-weighted mass. Concretely, for B = max{1, ⌈3/ε⌉} and Rj = (j + 1)B, the envelope satisfies the pointwise block bound n−1 X pex (ω) ≤ px (ω) + e−(ε/2)(jB+1) HRj (ω). j=0

Since a block has width Θ(1/ε), multiplying its radius by the 1/n contribution to error gives O(1/(εn)). The resulting explicit bounds are 1 ≤ Zx ≤ 1 + 2e,

X

pex (ω)Lx (ω) ≤ 3eα0 +

ω

288e , εn

where α0 is thepbase PMW error. Balancing the PMW round, selection, and update parameters makes α0 = O( log T log k/(εn)) and absorbs the remaining linear term. Sections 3–8 present these components and their analysis in order: base transcript, privacy envelope, Hamming-ball likelihood domination, near/far estimates, blocked summation, and parameter choice. The explicit parameter verification is isolated in section 8; the preceding sections establish the mechanism and structural estimates.

1.3

Context and comparison with prior work

The closest results differ in privacy notion, error criterion, or computational model. Line of work

Guarantee

Relation to this result

Prior pure-DP upper bounds

O((log T log k/(εn))1/3 )

Net mechanisms, pure PMW, and MWEM retain exponent 1/3 [BLR13, Har11, HLM12]. These lower bounds are stated under explicit high-dimensional parameter conditions [Har11, LT25]. These guarantees permit δ > 0; MWEM also has the separate pure cube-root analysis [HR10, GRU12, HLM12]. Its inherited utility guarantee is restricted to the starting subset [BCSZ18a]. Information-theoretic; polynomial-time implementation remains open.

worst-coordinate error

Known lower bounds

Square-root worst-coordinate error in nondegenerate regimes

Approximate-DP PMW/MWEM

Square-root-type dependence on 1/n, with δ-dependent factors

Metric extension

Extends an already pure metric-DP mechanism at factor-two privacy cost The conjectured square-root expected ℓ∞ error under pure DP

This work

5

Known generic pure-DP mechanisms have cube-root worst-coordinate error: the net mechanism, interactive pure PMW, and MWEM give O((log T log k/(εn))1/3 ), up to their stated probability terms [BLR13, Har11, HLM12]. Convex-geometric, factorization, Johnson–Lindenstrauss, and instanceoptimal mechanisms give strong workload-sensitive or average-error guarantees [NTZ13, ENU20, Nik23, BBNS19]. PREM gives relative-error synthetic release under pure and approximate DP; that work explicitly relates its purely additive gap to the universal pure-DP problem [GGK+ 25]. Nikolov, Tang, and Ullman’s online factorization theorem treats nonadaptively chosen query streams using a Gaussian (ε, δ)-DP mechanism, while their adaptive small-dataset result also uses approximate DP [NTU26]. These results address different error objectives, privacy notions, or interaction models from the offline pure-DP guarantee considered here. A contemporaneous study by Ghazi, Guzmán, Kamath, Knop, Kumar, and Manurangsi gives fixed-parameter tractable synthetic-data algorithms when the query-incidence graph has bounded treewidth. Its general pure-DP guarantee retains the cube-root sparse-regime term and it separately identifies the optimal universal pure-DP rate as open, so its computational and structural contribution is complementary to the rate proved here [GGK+ 26]. For worst-coordinate error, PMW, boosting, and iterative database constructions explain why n−1/2 -type accuracy is possible once approximate privacy is allowed [DRV10, HR10, GRU12, HLM12]. Hardt’s lower-bound proof is a discrete adaptation of the geometric packing argument of Hardt and Talwar [HT10, Har11]. For every fixed c > 0, it constructs, for fixed ε, sufficiently large n, and k > n1+c , a workload with error ! r log k log(T /n) Ω εn with constant probability [Har11]. Thus it is also an expected-error lower bound up to a constant. Building on the fingerprinting-code lower-bound program of Bun, Ullman, and Vadhan [BUV14], Lyu and Talwar more recently prove, under explicit high-dimensional hypotheses, that target error α requires ! p log T log(1/δ) log k n=Ω εα2 for ℓ∞ release [LT25]. A pure-DP mechanism is also (ε, δ)-DP; choosing δ = 2/T in the admisp sible regime recovers α = Ω( log T log k/(εn)). These lower bounds establish tight square-root dependence under their stated high-dimensional assumptions. Lin, Wang, Ma, and Wang recently gave a randomized-postprocessing framework that, under stated conditions, purifies approximate DP [LWMW25]. Its query-release application has cube-root dependence. The present argument instead uses the exact convex form of a fixed PMW transcript likelihood to prove the Maurey domination in Lemma 5.1. This is the step that turns local moment control into a globally pure law without losing the desired rate. The envelope uses the same factor-two normalization accounting as the private-extension theorem of Borgs, Chayes, Smith, and Zadik [BCSZ18a, BCSZ18b]. Applying that theorem with H = Dn would first require pointwise privacy of the base family; for proper H, its inherited utility statement is confined to H. For our PMW reference family, a direct pointwise privacy-loss bound costs 4Jη/n and yields the cube-root tradeoff. At the square-root parameters we instead retain finite-order likelihoodratio moments and prove directly that the resulting envelope has bounded normalization overhead and error-weighted mass. The factor-two geometry is inherited; the proof-specific ingredients that produce the new rate are the likelihood-level Maurey domination and blocked utility analysis.

6

2

Analytic tools

Write dH (x, y) = |{i : xi ̸= yi }| for replacement Hamming distance on Dn . For a probability distribution µ on D and a function P h : D → R, write h(µ) = d∈D µ(d)h(d). Thus q(µ) and s(µ) are ordinaryP expectations of a query and a signed query. For a probability mass P on a finite set, EP G = ω P (ω)G(ω) and ∥G∥Lr (P ) = (EP |G|r )1/r for 1 ≤ r < ∞. All logarithms are natural. All probability spaces below are finite, so probabilities and expectations reduce to finite sums. The analysis concerns how transcript likelihoods change with the database and how many likelihoods must be controlled simultaneously. For probability masses P, Q on a common finite support, the order-r Rényi divergence, r > 1, is   X 1 P (ω) r Dr (P ∥Q) = Q(ω) log . r−1 Q(ω) ω We use Rényi divergence as a compact way to record moments of the likelihood ratio P/Q, equivalently the exponentiated privacy loss; the final mechanism is proved pure DP directly [Mir17, BS16]. We use four finite-space lemmas, stated and proved in section A. First, a log-likelihood ratio bounded in [−a, a] has Dr (P ∥Q) ≤ ra2 /2, and these bounds add over adaptive rounds (Lemma A.1). This turns the sensitivity of one PMW selection into a transcript moment bound. Second, Hedge regret is at most log(T )/γ + γJ/2 (Lemma A.2); this is the deterministic potential argument behind PMW utility. Third, a softmax draw from K scores has gap tail Ke−ηu and L2 gap at most 4 log(2K)/η (Lemma A.3); this controls the error from privately selecting a violated query. Finally, if Da (Pi ∥P0 ) ≤ aA, Hölder’s inequality bounds the maximum of N likelihoods by a factor exp{log(N )/a + (a − 1)A} times the conjugate Lb (P0 ) norm, where b = a/(a − 1) (Lemma A.4). This last fact is what lets one small fixed surrogate family upper-bound an entire nearby Hamming ball.

3

The signed selection-only PMW transcript

This section constructs the accurate base transcript previewed in section 1.2. PMW maintains a synthetic distribution and repeatedly searches for a query on which its answer disagrees with the private database. Some PMW presentations additionally release a noisy numerical answer at each round. Here the transcript omits these measurements: once a signed query has been selected, a fixed Hedge update determines the next synthetic distribution. The finite transcript therefore contains only query indices and signs. This distinction matters. MWEM selects an inaccurate query by the exponential mechanism and separately releases a Laplace-noised numerical answer; basic composition gives its pure-DP cube-root guarantee, while advanced composition gives a separate approximate-DP analysis [HLM12]. Our selection rule is likewise an exponential mechanism over signed queries [MT07], but it releases no measurement. The resulting finite transcript law is an analytic input to the envelope, not itself the final private mechanism. To encode both the inaccurate coordinate and the direction of its error, give each query two signs. It is useful to retain distinct query indices even when two queries coincide as functions. Define S = Q × {−1, +1},

7

K = |S| = 2k.

For s = (q, σ) ∈ S, write s(d) = σq(d) and −s = (q, −σ). Thus s : D → [−1, 1] and the involution has no fixed point. The positive copy is favored when the synthetic answer to q is too small; the negative copy is favored when it is too large. An admissible target is an antisymmetric signed-answer vector a = (as )s∈S satisfying a−s = −as . A dataset x induces the target n 1X a(x)s = s(xi ). (3.1) n i=1

Admissible targets serve as analytical inputs to transcript distributions. They need not lie in [−1, 1]S or equal a(y) for any database y; they are neither private inputs nor released outputs. Some will arise by averaging row changes. The PMW selection rule depends only on the target coordinates, so it remains well-defined at these interpolation points. To measure their scale, define n d∗ (a, b) = max |as − bs | . (3.2) 2 s∈S Then d∗ (a(x), a(y)) ≤ dH (x, y): replacing one row changes every ordinary query answer by at most 2/n, and the factor n/2 converts this answer-space change back to Hamming units. Fix a number of rounds J ≥ 1, selection parameter η > 0, and update parameter 0 < γ ≤ 1. Set µ0 to be uniform on D. After selecting st , update the synthetic distribution by µt−1 (d)eγst (d) . γst (z) z∈D µt−1 (z)e

µt (d) = P

(3.3)

At round t, the preceding selections have fixed µt−1 . Sample st ∈ S according to Pa (st = s | s<t ) = P

exp{η(as − s(µt−1 ))} , u∈S exp{η(au − u(µt−1 ))}

(3.4)

then apply (3.3). The transcript space is Ω = S J . Write Pa for its law and pa (ω) > 0 for its mass function. For one-round intuition, suppose a = a(x) and Fq (x) > q(µt−1 ). Then the positive copy (q, +1) has positive discrepancy and the update factor eγq(d) shifts synthetic mass toward records with larger q-value. If the synthetic answer is too large, the negative copy has the corresponding discrepancy and reverses the update. Thus a signed selection specifies both what is inaccurate and how to correct it. Formula (3.4) is precisely an exponential-mechanism soft maximum of these discrepancies. The base answer is the query vector of the average pre-update synthetic distribution, J−1

µ̄(ω) =

1X µt , J

Ans(ω) = q(µ̄(ω)) q∈Q .

(3.5)

t=0

Averaging is the online-to-batch step: Hedge controls the average discrepancy over the selected rounds, and linearity turns that control into a bound for every query at µ̄. Only the signed-query transcript is random; no numerical measurements are released during these PMW rounds.

3.1

Extended Rényi control

We next quantify how the transcript distribution changes when its target changes. The quantity ρ below is the quadratic privacy-loss cost of all J selections. When a = a(x) and b = a(y), the right-hand side grows with the square of the Hamming distance. We prove the stronger statement for all admissible targets because the likelihood-domination argument will create targets that are not datasets. 8

Proposition 3.1 (Transcript Rényi bound). Define ρ=

8Jη 2 . n2

(3.6)

For all admissible targets a, b and every r > 1, Dr (Pa ∥Pb ) ≤ rρd∗ (a, b)2 .

(3.7)

Proof. Put ∆ = maxs |as − bs | = 2d∗ (a, b)/n. At a common preceding transcript, every logit in (3.4) changes by at most η∆. The selected logit and the log normalizer therefore each change by at most η∆. The two conditional laws have pointwise log likelihood ratio at most 2η∆ = 4ηd∗ (a, b)/n in absolute value. Apply the adaptive part of Lemma A.1 for J rounds and substitute (3.6). Proposition 3.1 bounds finite-order moments of the base transcript’s privacy loss. It does not provide pure privacy at the target parameters: converting it to a pointwise likelihood-ratio bound would recover the linear composition cost. The moment bound also applies to the surrogate targets used in section 5.

3.2

Second-moment utility and robustness

The selected query is unlikely to be far below the largest current discrepancy. Hedge turns this per-round statement into accuracy of the average synthetic distribution. We prove a second-moment, rather than only an expected-error, bound because the near-ball argument will later pair the error with a likelihood ratio using Hölder’s inequality with exponent at most two. Fix a dataset x and an admissible target a. Define ∆x (a) = max |as − a(x)s | = s∈S

2d∗ (a, a(x)) , n

and, at round t, Dt (s) = as − s(µt−1 ),

Dt⋆ = max Dt (s), s∈S

Gt = Dt⋆ − Dt (st ).

(3.8)

Here Dt⋆ is the largest current signed discrepancy and Gt is the selection gap: how far the softmax draw falls below that maximum. Because Dt (−s) = −Dt (s), we have Dt⋆ ≥ 0. Proposition 3.2 (Robust PMW utility). Let Lx (ω) = ∥Ans(ω) − F (x)∥∞ , Then ∥Lx ∥L2 (Pa ) ≤

L0 = log T,

LS = log(4k).

L0 γ 4LS 4d∗ (a, a(x)) + + + . γJ 2 η n

(3.9)

The first three terms in (3.9) are respectively the PMW costs for the initial Hedge potential, update discretization, and private query selection. The final term measures robustness to analyzing a surrogate target a instead of the true dataset target a(x). Proof. Conditionally on the past, (3.4) is a softmax on the scores Dt (s). Since log(2K) = log(4k) = LS , Lemma A.3 and the tower property give ∥Gt ∥L2 (Pa ) ≤ 4LS /η. Minkowski’s inequality therefore gives J 1X 4LS Gt ≤ . (3.10) J η t=1

L2 (Pa )

9

Use the empirical distribution of x as the comparator in Lemma A.2. Pointwise in the transcript, L0 γ 1X Dt (st ) ≤ + + ∆x (a), J t γJ 2 1X ⋆ L0 γ 1X Dt ≤ Gt . + + ∆x (a) + J t γJ 2 J t

(3.11)

For every s ∈ S, as − s(µ̄) =

1X ⋆ 1X Dt (s) ≤ Dt . J t J t

Apply this once to s and once to −s to bound the absolute difference between s(µ̄) and as . A final triangle inequality from a to a(x) contributes another ∆x (a). Take the L2 (Pa ) norm, use (3.10), and substitute 2∆x (a) = 4d∗ (a, a(x))/n.

3.3

A reusable base bound

For later use, define a common upper bound for the three base-PMW terms. For arbitrary J ≥ 1, η > 0, and 0 < γ ≤ 1, define   log T γ 16 log(4k) α0 := 2 + + . (3.12) γJ 2 η The constants leave enough slack for both the L2 estimate here and the integer likelihood-ratio moments used later. In particular, Proposition 3.2 and L1 ≤ L2 give ∥Lx ∥L2 (Pa(x) ) ≤ α0 ,

EPa Lx ≤ α0 +

4d∗ (a, a(x)) . n

(3.13)

These inequalities hold for every admissible target a; the target need not be realized by a dataset. The explicit choices of J, η, and γ are postponed to section 8.

4

The transcript envelope

We now define the final private transcript mechanism. For each possible transcript, take its likelihood under every dataset and discount that likelihood by the dataset’s Hamming distance from x. The largest discounted likelihood is the envelope at x. For dataset targets, abbreviate Px = Pa(x) and px = pa(x) . Let λ = ε/2 and define X pex (ω) = maxn e−λdH (x,y) py (ω), Zx = pex (ω). (4.1) y∈D

ω∈Ω

The final transcript mass function, transcript law, and released answer are pbx (ω) =

pex (ω) , Zx

ω ∼ Pbx ,

M (x) = Ans(ω),

(4.2)

where Pbx denotes the distribution with mass function pbx . Both maxima and sums are over finite nonempty sets. Moreover Zx ≥ 1 because the maximum includes y = x and px sums to one. Every base transcript has positive mass under every target because each selection is a softmax draw. The construction therefore keeps common support throughout; it never conditions on a data-dependent “good” event. 10

Proposition 4.1 (Pure privacy of the envelope). The transcript law Pb in (4.2) is pure ε-differentially private. Hence so is M . Proof. If dH (x, x′ ) = 1, the triangle inequality gives, pointwise in ω, e−λ pex′ (ω) ≤ pex (ω) ≤ eλ pex′ (ω). Summing gives the same two-sided comparison between Zx and Zx′ . Consequently e−2λ ≤ pbx (ω)/b px′ (ω) ≤ e2λ . Since 2λ = ε, summing this pointwise bound over any event proves pure DP. The answer is deterministic postprocessing of the transcript. Privacy did not use an upper bound on Zx . The rest of the paper proves the stronger pair of estimates   X 1 . (4.3) Zx = O(1), pex (ω)Lx (ω) = O α0 + εn ω

5

Likelihood-level domination for a Hamming ball

The envelope in (4.1) ranges over all T n datasets. For its utility analysis, we pointwise upper-bound the likelihood maximum over every database in a Hamming ball by a small family of answer-space surrogates. For each competing database y, a y-dependent random surrogate supported on one family depending only on x, R, and a code length m has mean a(y). Thus the same support family works for every y in the ball. Its size is at most (T 2 + 1)m , independent of n. The sampling device is a finite ℓ∞ instance of Maurey’s empirical method [Pis81]. Here it is applied directly to likelihoods: a fixed-transcript log-sum-exp and Hoeffding estimate implies that some surrogate, possibly depending on the transcript, has likelihood nearly as large as the database it represents. Fix a dataset x, an integer radius R ≥ 1, and an integer code length m ≥ 1. For c = (d, d′ ) ∈ D × D, define the admissible row-move vector δc (h) = h(d′ ) − h(d)

(h ∈ S),

and let δ0 = 0. Define the finite target family ( ) m R X Vx,R,m = a(x) + δci : ci ∈ {0} ∪˙ (D × D) . mn

(5.1)

i=1

Every v ∈ Vx,R,m satisfies d∗ (v, a(x)) ≤ R, and |Vx,R,m | ≤ (T 2 + 1)m .

(5.2)

The disjoint union notation treats the zero move as a separate label; different labels may define the same target, which only improves the bound. Lemma 5.1 (Likelihood Maurey bound). For every y ∈ Dn with dH (x, y) ≤ R and every transcript ω ∈ Ω,  2 ρR py (ω) ≤ exp max pv (ω). (5.3) 4m v∈Vx,R,m

11

Proof. Let h = dH (x, y). Make a list of length R containing the h row-move vectors
s(yi ) − s(xi ) s∈S (xi ̸= yi ) and R − h zero vectors. Draw W1 , . . . , Wm independently and uniformly from this list, and put m

R X V = a(x) + Wi . mn

(5.4)

i=1

Then EV = a(y) coordinatewise and V is supported on Vx,R,m . Fix ω = (s1 , . . . , sJ ). Once the full transcript is fixed, every synthetic iterate µt−1 is fixed. The negative log likelihood gω (a) = − log pa (ω) has the form " # J X X η(au −u(µt−1 )) gω (a) = Cω + log e − ηast , (5.5) t=1

u∈S

P

where Cω = η t st (µt−1 ) is independent of a. Consider one log-partition and let wu be its softmax weights at a(y). Jensen’s inequality and then Hoeffding’s lemma give X E log wu eη(Vu −a(y)u ) u∈S

≤ log

X

wu Eeη(Vu −a(y)u ) ≤

u∈S

Indeed, for fixed u,

2η 2 R2 . mn2

(5.6)

m

Vu − a(y)u =

R X (Wi (u) − EWi (u)), mn i=1

and each Wi (u) lies in [−2, 2], an interval of length four. Because EV = a(y), the expectation of each selected term −ηVst is exactly −ηa(y)st . Sum (5.6) over J rounds and use ρ = 8Jη 2 /n2 to obtain ρR2 Egω (V ) ≤ gω (a(y)) + . 4m Equivalently, ρR2 log py (ω) ≤ E log pV (ω) + . 4m Exponentiation and the geometric-mean/arithmetic-mean inequality give 2

2

py (ω) ≤ eρR /(4m) EpV (ω) ≤ eρR /(4m) max pv (ω). v∈Vx,R,m

This is (5.3). Remark 5.2. The Maurey bound is independent of k because it uses no union bound over queries. Fixing the complete selected-query transcript before viewing (5.5) as a function of the target absorbs adaptivity without an additional term.

12

6

Maximal likelihood on a Hamming ball

Maurey domination leaves a maximum over a finite family of target vectors. We must bound both its total mass and its error-weighted mass. For nearby targets, likelihood-ratio moments control the maximum. For more distant targets, we instead upper-bound the maximum by a sum of probability laws. Fix a dataset x and an integer radius R ∈ N with R ≥ 1. Write HR (ω) =

max y:dH (x,y)≤R

py (ω),

L = log(T 2 + 1),

and introduce the transcript moment coefficient κ and the resulting radius-R moment scale AR : κ=

2Jη 2 ρ = , 2 n 4

AR = κR2 .

(6.1)

Thus the Maurey factor in (5.3) is eAR /m . The quantity HR is the maximum over the closed ball and will upper-bound each annulus whose outer radius is R. Lemma 6.1 (Integer likelihood-ratio moment). If v is an admissible target with d∗ (v, a(x)) ≤ R, then every integer r ≥ 1 satisfies   X pv (ω) r 2 px (ω) ≤ eAR r . (6.2) p (ω) x ω Proof. Condition on a transcript prefix at round t, and write πxt and πvt for the resulting softmax kernels. Since the synthetic iterate is determined by the prefix, their logits differ only through δs = vs − a(x)s ∈ [−2R/n, 2R/n]. Therefore πvt (s) eηδs = . πxt (s) Eπxt eηδ ηE

δ

Jensen’s inequality lower-bounds the denominator by e πxt . Hoeffding’s lemma therefore gives  2 2 2  t r 2r η R πv rη(δ−Eπt δ) x ≤ Eπxt e ≤ exp . Eπxt t πx n2 Iterating conditional expectation over J rounds multiplies these moment costs, giving (6.2) because AR = 2Jη 2 R2 /n2 .

6.1

Nearby databases: likelihood-ratio moments

Suppose AR ≤ L. Apply Lemma 5.1 with code length m = 1, and write V = Vx,R,1 . Set &r ' L rR = + 1. AR

(6.3)

Then rR ≥ 2, r

L ≤ rR < AR

r

L + 2, AR

and consequently p L + AR rR ≤ 4 AR L. rR 13

(6.4)

√ √ √ Indeed, the first term is at most AR L, while AR rR ≤ AR L + 2AR ≤ 3 AR L. Put Λv = pv /px ; the common softmax support makes this ratio well defined. The Maurey bound and (6.2) give !1/rR HR ≤ eAR px max Λv ,

≤

max Λv

v∈V

v∈V

X

LrR (Px )

EPx ΛrvR

≤ eL/rR +AR rR .

v∈V

For the conjugate exponent bR = rR /(rR − 1) ≤ 2, Hölder’s inequality and monotonicity of probability-space norms give ∥ϕ∥Lb (Px ) ≤ ∥ϕ∥L2 (Px ) . Therefore every nonnegative ϕ satisfies R

 L + AR rR ∥ϕ∥L2 (Px ) . HR (ω)ϕ(ω) ≤ exp AR + rR ω 

X

(6.5)

The three exponents the Maurey, cardinality, and likelihood-moment costs. Since √ are respectively √ AR ≤ L, AR + 4 AR L ≤ 5 AR L. Taking ϕ = 1 and ϕ = Lx , respectively, gives √ √ X X HR (ω) ≤ e5 AR L , HR (ω)Lx (ω) ≤ e5 AR L α0 . (6.6) ω

6.2

ω

Distant databases: a mixture bound

Suppose instead that AR > L, and choose ( &r mR = max 1, After the Maurey step, use max ≤

AR L

') .

(6.7)

P . Since the code family has at most emR L members, X HR (ω) ≤ eAR /mR +mR L .

(6.8)

ω

Every code target lies within target distance R of the center, so (3.13) gives EPv Lx ≤ α0 + 4R/n. We use the uniform bound α0 + 8R/n below to cover the regime boundary. Hence   X 8R . (6.9) HR (ω)Lx (ω) ≤ eAR /mR +mR L α0 + n ω The ceiling bounds imply p p AR + mR L ≤ 2 AR L + L ≤ 3 AR L, mR

(6.10)

where the last inequality uses L ≤ AR . Combining the near and far cases gives the uniform ball estimate used for every radial block: X

√

HR (ω) ≤ e5 AR L ,

ω

X

HR (ω)Lx (ω) ≤ e

√ 5 AR L

ω

14



8R α0 + n

(6.11)

 .

7

Radial blocking and envelope utility

We now sum (6.11) in blocks of radius Θ(1/ε), the scale over which the envelope penalty changes by a constant factor. Fix 2Jη 2 c0 ε2 c0 = 2−20 , κ= ≤ . (7.1) n2 L This condition makes the growth of every ball likelihood small compared with the envelope’s distance penalty. Log-cost decomposition. The following ledger summarizes the preceding argument for the radius-R ball. Its entries are additive contributions to the logarithm of the ball bound; mR and rR are the optimized code length and moment order from section 6. Table 1: Log-cost ledger for the radius-R ball bound. Contribution Maurey smoothing Code cardinality Likelihood moment Envelope penalty

Near: moment

Far: mixture

AR L/rR AR rR −εR/2

AR /mR mR L none −εR/2

p √ When AR ≤ L, one Maurey move and rp L/AR make the positive cost at most R ≃ √ 5 AR L; the errorPfactor is α0 . When AR > L, mR ≃ AR /L makes the positive cost at most 3 AR L; after max ≤ , each mixture law has total mass one, so there is no likelihood-moment cost, and the prefactor is α0 + 8R/n. By (7.1), both positive costs are at most εR/100, well below the envelope penalty. A radius-by-radius summation would incur an additional factor 1/ε. Indeed, even an exact-radius estimate decaying as e−49εR/100 would give, for 0 < ε ≤ 1,   X XR 1 −49εR/100 −49εR/100 e = Θ(1/ε), e =Θ 2 . n ε n R≥1

R≥1

This loss comes from discretizing radii, not from a union bound over datasets, which Maurey domination has already avoided. Blocking at width B ≃ 1/ε removes exactly this discretization loss: the rigorous argument uses the outer radius of a block for the positive ball cost and its inner radius for the negative envelope penalty. The resulting block weights have constant total mass, and their (R/n)-weighted contribution is O(B/n) = O(1/(εn)). Set the integer block width B = max{1, ⌈3/ε⌉},

θ = εB.

Then θ ≥ 3. If 0 < ε ≤ 1, then θ ≤ 4; if ε > 1, then B ≤ 3 and θ ≤ 3ε. For j ≥ 0, let Rj = (j + 1)B.

(7.2)

(7.3)

The envelope-growth condition gives 5

q √ √ θ(j + 1) ARj L ≤ 5 c0 εRj = 5 c0 θ(j + 1) ≤ , 100 15

(7.4)

because

√

c0 = 2−10 and 5/1024 ≤ 1/100. Thus (6.11) becomes   X θ(j + 1) HRj (ω) ≤ exp , 100 ω    X 8B(j + 1) θ(j + 1) α0 + . HRj (ω)Lx (ω) ≤ exp 100 n ω

(7.5)

Every y ̸= x belongs to a unique block indexed by   dH (x, y) − 1 j= <n B and satisfies jB + 1 ≤ dH (x, y) ≤ (j + 1)B. Consequently, pointwise in the transcript, pex (ω) ≤ px (ω) +

n−1 X

e−(ε/2)(jB+1) HRj (ω).

(7.6)

j=0

Define the large-ε damping factor ( 1, uε = e−ε/3 ,

0 < ε ≤ 1, ε > 1,

(7.7)

and define the combined block weight   o n ε θ(j + 1) . Φj = exp − (jB + 1) exp 2 100

(7.8)

Lemma 7.1 (Finite blocked-radius summation). For every j ≥ 0, Φj ≤ euε e−jθ/3 .

(7.9)

Consequently, for every integer N ≥ 0, N −1 X

N −1 X

Φj ≤ 2euε ,

(j + 1)Φj ≤ 4euε .

j=0

(7.10)

j=0

Proof. See section A.5. The damping factor also satisfies 9 Buε ≤ . ε

uε ≤ 1,

(7.11)

For ε ≤ 1, this uses B ≤ 4/ε. For ε > 1, it uses B ≤ 3 and εe−ε/3 ≤ 3. We can now sum the block bound. The central base law has mass one and expected loss at most α0 . Combining (7.6), (7.5), and Lemma 7.1 gives X

pex (ω)Lx (ω) ≤ α0 + α0

ω

n−1 X j=0

≤ α0 + 2euε α0 + ≤ 3eα0 +

288e . εn

16

n−1

8B X Φj + (j + 1)Φj n j=0

32eBuε n

(7.12)

Here 2e and 4e come from (7.10), while 288e = 32e · 9 also uses (7.11). Repeating the same calculation with Lx replaced by 1 gives the normalizer estimate 1 ≤ Zx ≤ 1 + 2euε ≤ 1 + 2e.

(7.13)

The lower bound follows from pex ≥ px . Since Zx ≥ 1, normalization can only decrease the unnormalized error bound, and therefore E ∥M (x) − F (x)∥∞ ≤ 3eα0 +

8

288e . εn

(7.14)

Parameter regimes and proof of the main theorem

Ignoring constants, the parameter balance is as follows. To target error α, take γ = Θ(α), J = Θ(log T /α2 ), and η = Θ(log k/α). The first two choices balance Hedge regret, and the third controls the exponential-mechanism selection error. Then α0 = O(α), while the envelope-growth condition reduces to α2 = Ω(log T log k/(εn)). We now verify explicit integer choices. Put LD = log(2T ), 21

2

2 LD LQ ≤ εnα ,

LQ = log(2k),

(8.1)

0 < α ≤ 1.

(8.2)

The positive logarithms exceed 1/2, including when T = 1 or k = 1. Choose   128LQ 16LD α J= , η= , γ= , α2 α 4 32LD 16LD ≤J ≤ . 2 α α2

(8.3) (8.4)

For the base PMW error α0 defined in (3.12), the three displayed contributions are at most α/2, α/4, α/4, so α0 ≤ α. For L = log(T 2 + 1) and κ = 2Jη 2 /n2 , the round bound, L ≤ 2LD , and the square of (8.2) give κ≤

220 LD L2Q n2 α 4

,

220 κL ≤

240 LD L2Q L n2 α 4

≤

241 L2D L2Q n2 α 4

≤ ε2 .

Hence the envelope-growth condition holds: 2Jη 2 2−20 ε2 ≤ . 2 n log(T 2 + 1)

(8.5)

The sample premise, LD LQ > 1/4, and α ≤ 1 also give 1 ≤ α, εn E ∥M (x) − F (x)∥∞ ≤ 3eα0 +

(8.6) 288e ≤ 512eα. εn

(8.7)

p Finally set τ = LD LQ /(εn). If 2048τ ≤ 1, take α = 2048τ . Then εnα2 = 222 LD LQ , so (8.2) holds with factor-two slack and (8.7) is at most 220 eτ . If 2048τ > 1, use the separate deterministic zero-output mechanism. Its error is at most one and its one-point output law is 0-DP; also 1 ≤ 220 e min{1, τ }. Thus Theorem 1.1 holds in all regimes with C = 220 e. The nontrivial branch is private by Proposition 4.1, followed by deterministic postprocessing. 17

9

Discussion and limitations

The theorem addresses the expected-ℓ∞ formulation of Open Problem 1. Markov’s inequality gives constant-probability accuracy at the same asymptotic rate. For failure probability ζ, running O(log(1/ζ)) independent copies with the privacy budget divided among them and taking a coordi
1/2 natewise median preserves pure ε-DP and incurs an additional O( log(1/ζ) ) error factor. The single-run envelope analysis does not establish optimal confidence dependence. The mechanism is information-theoretic. The envelope maximizes over Dn , and its transcript space has size (2k)J ; the proof does not yield a polynomial-time implementation. Finding an efficient pure-DP mechanism with the same universal rate remains open. Finally, Theorem 1.1 is uniform over all finite parameter choices, but it is not an all-regimes minimax theorem. The outer minimum and shifted logarithms cover degenerate cases correctly; they do not assert matching lower bounds there. For instance, a singleton universe permits exact release, and a single query admits the sensitivity-calibrated Laplace mechanism.

10

Formal verification

Sections 3–8 together with Appendix A give a standalone analytic proof. A companion Lean 4 development, pinned to Lean and Mathlib 4.28.0, machine-checks a finite formalization of the mechanism and the integer likelihood-ratio moments used in the proof. It verifies normalization, pure privacy before and after the dataset-independent decoder, the integer parameter choices, and the explicit all-regimes expected-error bound. Its main declaration is optimal_pureDP_decoded_ statistical_query_release_rate, with constant ( r ) log(2T ) log(2k) 220 e min 1, . εn The Lean development checks the finite, integer-order specializations used by the main theorem; several analytic lemmas are stated in more general form. Reproducibility instructions, axiom audits, and a paper-to-Lean crosswalk are provided with the companion artifact.

11

Conclusion

We prove the conjectured expected-ℓ∞ pure-DP query-release upper bound posed by Nikolov and Ullman. The transcript envelope converts the useful local behavior of selection-only PMW into a globally pure-DP law without paying either the number of datasets or an additional 1/ε factor. The proof analyzes the envelope using randomly sampled row changes, uses likelihood-ratio moments only for nearby databases, switches to a mixture bound farther away, and sums blocks rather than individual Hamming radii. The resulting expected worst-coordinate error is ( r )! log(2T ) log(2k) O min 1, . εn Generative-AI disclosure. OpenAI Codex and Harmonic Aristotle were used in connection with Lean formalization and proof search. OpenAI Codex also provided editorial feedback on clarity and organization. The author takes responsibility for the paper and accompanying formalization.

18

A

Supporting analytic lemmas

The following proofs support the finite-space estimates invoked in the main likelihood-envelope argument.

A.1

Bounded likelihood ratios

Lemma A.1 (Bounded likelihood ratio to Rényi divergence). Suppose P, Q have common support and P (ω) e−a ≤ ≤ ea for every ω. Q(ω) Then, for every r > 1, 1 Dr (P ∥Q) ≤ ra2 . (A.1) 2 The same estimate composes adaptively: if each of J conditional kernels has the displayed likelihoodratio bound with the same a, then the transcript laws obey Dr (P ∥Q) ≤ Jra2 /2. Proof of Lemma A.1. Under P , put Z = log(P/Q). Thus Z ∈ [−a, a]. The sharp two-point extremal bound for a bounded likelihood ratio gives ea − 1 EP Z = KL(P ∥Q) ≤ a a = a tanh(a/2) ≤ a2 /2. e +1 The extremal inequality follows by replacing each value of P/Q ∈ [e−a , ea ] by a mean-preserving random value at an endpoint and using convexity of u 7→ u log u. Hoeffding’s lemma [Hoe63] for Z ∈ [−a, a] now gives, with t = r − 1, log EP etZ ≤ tEP Z +

t2 a2 t(1 + t)a2 ≤ . 2 2

Since Dr (P ∥Q) = t−1 log EP etZ , this proves (A.1). For adaptive composition, factor the transcript likelihood ratio into its conditional ratios, apply the corresponding conditional moment estimate at the last round, and iterate the tower property. The logarithmic moment costs add.

A.2

Hedge regret

Lemma A.2 (Hedge). Let µ0 be uniform on D. Given functions st : D → [−1, 1], define µt recursively by (3.3), where 0 < γ ≤ 1. Then every probability distribution µ∗ on D satisfies J X t=1

log T γJ st (µ∗ ) − st (µt−1 ) ≤ + . γ 2

(A.2)

Proof of Lemma A.2. The change in relative entropy is KL(µ∗ ∥µt ) − KL(µ∗ ∥µt−1 ) = log Eµt−1 eγst − γst (µ∗ ). Hoeffding’s lemma bounds the logarithm by γst (µt−1 ) + γ 2 /2. Sum over t, use nonnegativity of the final relative entropy, and note that KL(µ∗ ∥µ0 ) ≤ log T . This is the multiplicative-weights potential argument [FS97].

19

A.3

Softmax selection gap

Lemma A.3 (Softmax gap). Let z1 , . . . , zK ∈ R, and sample I with probability proportional to eηzi , where η > 0. For G = maxi zi − zI , P(G ≥ u) ≤ Ke−ηu ,

∥G∥L2 ≤

4 log(2K) . η

(A.3)

Proof of Lemma A.3. The total softmax weight of indices at least u below the maximum is at most Ke−ηu times the weight ofR a maximizer. This proves the tail. With u0 = (log K)/η and the ∞ tail-integration identity EG2 = 0 2uP(G ≥ u) du, Z ∞ (log K)2 + 2 log K + 2 . EG2 ≤ u20 + 2K ue−ηu du = η2 u0 The square root is at most 4 log(2K)/η.

A.4

Rényi maximum

Lemma A.4 (Rényi maximum). Let N ≥ 1, and let P0 , P1 , . . . , PN have common finite support and masses p0 , p1 , . . . , pN . Suppose, for some a > 1 and A ≥ 0, Da (Pi ∥P0 ) ≤ aA

(1 ≤ i ≤ N ).

(A.4)

For every nonnegative G, with b = a/(a − 1), X ω

 max pi (ω)G(ω) ≤ exp

1≤i≤N

 log N + (a − 1)A ∥G∥Lb (P0 ) . a

(A.5)

P Proof of Lemma A.4. Set Ri = pi /p0 . Pointwise, (maxi Ri )a ≤ i Ria , while
EP0 Ria = exp (a − 1)Da (Pi ∥P0 ) ≤ ea(a−1)A . Thus ∥maxi Ri ∥La (P0 ) ≤ N 1/a e(a−1)A . Hölder’s inequality gives (A.5).

A.5

Finite blocked-radius summation

Proof of Lemma 7.1. The exponent in (7.8) is ε jθ θ(j + 1) − − + . 2 2 100 If ε ≤ 1, use θ ≤ 4 to bound this by 1 − jθ/3. If ε > 1, use θ ≤ 3ε to bound it by −ε/3 − jθ/3. These are exactly the two cases represented by uε , with one common factor e. This proves (7.9). Since θ ≥ 3, 1 e−θ/3 ≤ e−1 < . 2 The finite geometric estimates N −1 X j=0

−j

2

≤ 2,

N −1 X j=0

therefore prove (7.10). 20

(j + 1)2−j ≤ 4

References [AD20] Hilal Asi and John C. Duchi. Near instance-optimality in differential privacy, 2020. [BBNS19] Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, and Thomas Steinke. Towards instance-optimal private query release. In Proceedings of the 2019 ACM–SIAM Symposium on Discrete Algorithms, pages 2480–2497. SIAM, 2019. [BCSZ18a] Christian Borgs, Jennifer Chayes, Adam Smith, and Ilias Zadik. Private algorithms can always be extended. arXiv:1810.12518, 2018. [BCSZ18b] Christian Borgs, Jennifer T. Chayes, Adam D. Smith, and Ilias Zadik. Revealing network structure, confidentially: Improved rates for node-private graphon estimation. In 59th Annual IEEE Symposium on Foundations of Computer Science, pages 533–543. IEEE, 2018. [BLR13] Avrim Blum, Katrina Ligett, and Aaron Roth. A learning theory approach to noninteractive database privacy. Journal of the ACM, 60(2):12:1–12:25, 2013. [BS16] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, volume 9985 of Lecture Notes in Computer Science, pages 635–658. Springer, 2016. [BUV14] Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In 46th Annual ACM Symposium on Theory of Computing, pages 1–10. ACM, 2014. [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, volume 3876 of Lecture Notes in Computer Science, pages 265–284. Springer, 2006. [DR14] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014. [DRV10] Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In 51st Annual IEEE Symposium on Foundations of Computer Science, pages 51–60. IEEE, 2010. [ENU20] Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman. The power of factorization mechanisms in local and central differential privacy. In 52nd Annual ACM Symposium on Theory of Computing, pages 425–438. ACM, 2020. [FS97] Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119–139, 1997. [GGK+ 25] Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, and Sushant Sachdeva. PREM: Privately answering statistical queries with relative error. In Nika Haghtalab and Ankur Moitra, editors, Proceedings of Thirty Eighth Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, page 2460. PMLR, 2025. Full version: arXiv:2502.14809.

21

[GGK+ 26] Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, and Pasin Manurangsi. Fixed-parameter tractability of private synthetic data generation, 2026. [GRU12] Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release. In Theory of Cryptography Conference, volume 7194 of Lecture Notes in Computer Science, pages 339–356. Springer, 2012. [Har11] Moritz Hardt. A Study of Privacy and Fairness in Sensitive Data Analysis. Ph.d. thesis, Princeton University, 2011. Technical Report TR-915-11. [HLM12] Moritz Hardt, Katrina Ligett, and Frank McSherry. A simple and practical algorithm for differentially private data release. In Advances in Neural Information Processing Systems, volume 25, pages 2339–2347. Curran Associates, Inc., 2012. [Hoe63] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. [HR10] Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacypreserving data analysis. In 51st Annual IEEE Symposium on Foundations of Computer Science, pages 61–70. IEEE, 2010. [HT10] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In 42nd Annual ACM Symposium on Theory of Computing, pages 705–714. ACM, 2010. [LT25] Xin Lyu and Kunal Talwar. Fingerprinting codes meet geometry: Improved lower bounds for private query release and adaptive data analysis. In 57th Annual ACM Symposium on Theory of Computing, pages 2374–2385. ACM, 2025. [LWMW25] Yingyu Lin, Erchi Wang, Yi-An Ma, and Yu-Xiang Wang. Purifying approximate differential privacy with randomized post-processing. In Advances in Neural Information Processing Systems 38, pages 144259–144316, 2025. [Mir17] Ilya Mironov. Rényi differential privacy. In 30th IEEE Computer Security Foundations Symposium, pages 263–275. IEEE, 2017. [MT07] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Annual IEEE Symposium on Foundations of Computer Science, pages 94–103. IEEE, 2007. [Nik23] Aleksandar Nikolov. Private query release via the johnson–lindenstrauss transform. In Proceedings of the 2023 ACM–SIAM Symposium on Discrete Algorithms, pages 4982–5002. SIAM, 2023. [NTU26] Aleksandar Nikolov, Haohua Tang, and Jonathan Ullman. Online matrix factorization, online private query release, and online discrepancy minimization. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC ’26, pages 2302–2313. ACM, June 2026. [NTZ13] Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: The sparse and approximate cases. In 45th Annual ACM Symposium on Theory of Computing, pages 351–360. ACM, 2013. 22

[NU21] Aleksandar Nikolov and Jonathan Ullman. Open problem: Optimal query release for pure differential privacy. DifferentialPrivacy.org, https://differentialprivacy. org/open-problem-optimal-query-release/, July 2021. Accessed July 21, 2026. [Pis81] Gilles Pisier. Remarques sur un résultat non publié de B. maurey. Séminaire d’analyse fonctionnelle, pages 1–12, 1980–1981. Exposé no. 5.

23