Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries

Motivation

• Randomness complexity is a practical DP resource constraint, illustrated by the estimated 7.2 ×10^14 random bits used in the US Census deployment.It can determine the practical applicability of DP algorithms alongside space, time, and utility.Source: §1 · p. 3

Problem

• The central question is whether randomness complexity and utility have an inherent tradeoff when answering DP linear queries.Prior mechanisms suggest a tension between low randomness and low error.Source: §1 · p. 3

Main result

• O(log d) expected random bits and O(d/ε) expected ℓ∞-error are simultaneously achievable for answering d linear queries with ε-DP.This matches the optimal error bound and is tight for randomness complexity when ε ≤1/d.Source: §1.1 · p. 3

Method

• The mechanism applies the exponential mechanism to secluded-partition cells, scoring each cell by its minimum distance from f(X).Using the minimum distance to any point in a cell, rather than to its representative, is important to the analysis.Source: §1.2 · pp. 4–5

Technical overview

• A multi-scale secluded-partition uses one partition across scales, with k_d(ℓ) = d^O(1) · 2^O(d/ℓ), enabling the randomness-efficient construction.The resulting partition has only d^O(1) cells, yielding O(log d) output entropy and randomness.Source: §1.2 · p. 5

Extensions

• The approach extends to a broad family of K-norms, including ℓp-norms with ℓp-error O(d/ε) using O(log d) random bits.The extension relies on the existence of multi-scale secluded-partitions for sufficiently well-behaved norms.Source: §1.2 · p. 6

Efficient mechanism

• The efficient ℓ∞ mechanism has expected error O((d log d)/ε) and randomness complexity O(log d), an O(log d) factor above the optimal-error mechanism.Its explicit multi-scale secluded-partition construction closes the efficiency gap at the cost of the larger error bound.Source: §1.1 · p. 4, §1.2 · p. 6

Convex Geometry

• A δ-net is a finite subset whose points approximate every element of a set within distance δ under a specified norm.Source: §2.1 · p. 6
• An absorbing disk is convex, symmetric, and absorbing, and its gauge defines a norm when it contains no nontrivial subspace.The resulting ∥· ∥K-norm subsumes all ℓp-norms considered in the paper.Source: §2.1 · p. 6

Differential Privacy

• Differential privacy requires neighboring datasets to induce output probabilities differing by at most an e^ε multiplicative factor for every measurable event.For countable output spaces, it suffices to check each output separately.Source: §2.2 · p. 7

Sensitivity

• The sensitivity of f is the supremum norm distance between f(X) and f(X′) over neighboring datasets, while a sensitivity polytope contains every such difference.A sensitivity polytope K implies sens∥· ∥K(f) ≤1.Source: §2.2 · p. 7

Entropy and Randomness

• Randomness complexity is the supremum expected number of random bits used, whereas output entropy is the supremum Shannon entropy of the mechanism’s output distribution.An optimal DDG-tree sampler uses at most H(p)+2 expected random bits, enabling entropy bounds to control randomness complexity.Source: §2.2 · p. 8

MSSP Framework

• A multi-scale secluded partition is a single partition that satisfies secludedness guarantees simultaneously for every scale ℓ∈[d].This strengthens the requirement that each scale may use a different partition.Source: §3 · p. 8

Existential Construction

• The existential construction samples points on a flat torus, proves covering and secludedness through nets and Chernoff bounds, then periodically extends the set across Rd.Source: §3.1 · pp. 9–10
• Theorem 3.2 establishes an MSSP for any norm induced by a symmetric set, with kd(ℓ) = O(d log d · e^d/ℓ).The construction uses a linear transformation and a randomly sampled covering set whose Voronoi cells form the partition.Source: §3.1 · p. 10

Explicit Rounding Construction

• The explicit rounding scheme induces a partition with unit ℓ∞ displacement, satisfying a kd-MSSP guarantee of kd(ℓ) = (ℓ + 1)^O(d/ℓ).Its rounding function is efficient, supporting the later polynomial-time mechanism.Source: §3.2.1 · pp. 11–12, §3.2 · p. 11, §3.2.2 · p. 13

Partition Properties

• For the induced partition, the number of cells within relative scale γ is bounded by m(d)e^2λ(d)γ for γ∈[1/d,1], and by kd(1)(3γ)^d for γ≥1.Source: §3.3 · p. 14

Main Mechanism

• The mechanism samples a partition cell using an exponential score based on the distance from f(X) to that cell, then outputs its representative.The partition is scaled with ρ = Cd/ε.Source: §4 · p. 15
• Theorem 4.1 gives an ε-DP mechanism with expected ∥· ∥K-error O(d/ε) and randomness complexity O(log d).The result applies to functions with sens∥· ∥K(f) ≤1.Source: §4 · p. 15

Privacy

• Privacy follows because the distance-to-cell score has sensitivity at most 1, making the exponential-mechanism instantiation ε-differentially private.Source: §4.1 · p. 16

Utility

• The expected error combines at most 2ρ from the representative’s cell diameter with the expected distance from f(x) to the sampled cell.Source: §4.2 · p. 16

Randomness Complexity

• The mechanism has randomness complexity O(log d) because the sampled partition cell has entropy O(log d), and output entropy upper-bounds expected random-bit usage.Source: §4.3 · p. 17

Efficient Partition Sampler

• Rejection sampling selects partition cells with probability proportional to exp(−ε⌈∆P(f(X))⌉/2), using annuli and enumerated candidate cells.The sampler first determines an appropriate distance scale, then enumerates and samples from the corresponding annulus.Source: §5 · p. 18, §5.2 · pp. 20–21

Efficiently Enumerating Partitions

• Partition cells can be enumerated efficiently within distance annuli, with at most Nm = (d + 1)^7(m + 2) cells in annulus m.The enumeration runs in poly(d) · Nm time, and exact distances to candidate cells can be computed in polynomial time.Source: §5.1 · pp. 18–20

Privacy and Randomness

• The mechanism is ε-DP and uses O(log d) expected random bits.The randomness analysis bounds the expected cost per round and applies the resulting estimate to the full sampler.Source: §5.3 · p. 22, §5.5 · p. 23

Utility

• O((d log d)/ε) expected ℓ∞-error is achieved by scaling the partition parameter as ρ = C d log d/ε.The algorithm’s error is bounded by 2ρ plus the expected distance from f(X) to the sampled partition cell.Source: §5 · p. 18, §5.4 · p. 23

Running Time

• The expected running time is poly(T(f, X), 1/ε), where T(f, X) is the time required to evaluate f on X.This follows from efficient distance computation, annulus enumeration, and the sampler’s expected number of rounds.Source: §5.1 · pp. 18, 20, §5.6 · p. 23

• O(log d) randomness is paired with nearly optimal error, essentially resolving the main open questions from.Source: §6 · p. 24
• The efficient mechanism has ℓ∞-error O(d log d/ε), a factor O(log d) above the optimal bound, while retaining O(log d) randomness complexity.Source: §6 · p. 24
• O(log d) randomness complexity is known to be tight only when ε ≤1/d, leaving larger-ε optimality unresolved.Source: §6 · p. 24
• The algorithms are efficient only for ℓ∞-sensitivity, leaving efficient mechanisms for all K-norms or all ℓp-norms as an open direction.Source: §6 · p. 24
• Under a polylogarithmic worst-case randomness constraint, approximate-DP mechanisms incur at least eΩ(d^1.5/ε) error, while the paper’s pure-DP algorithm achieves O(d/ε).A gap of eΩ(d) remains relative to the upper bound without that worst-case randomness constraint.Source: §6 · p. 25
• The authors report using AI for construction, formalization, proof drafting, figure generation, and proof checking, while verifying correctness and originality.Source: AI Disclosure Statement · p. 25