Source-linked AI summary
Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries
Surendra Ghentiyala, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
TL;DR
The paper addresses randomness complexity as a practical resource constraint in differentially private algorithms. It develops an ε-DP algorithm for answering d linear queries using an MSSP-based construction, achieving O(d/ε) error with O(log d) randomness, while an efficient version incurs an O(log d) error increase.
Problem
Differential privacy algorithms require random bits, and deployments such as the US Census show that randomness complexity can constrain practical applicability alongside space, time, and utility.
Method
The paper develops an ε-DP algorithm based on a randomness-efficient analogue of the ||·||_K-norm mechanism, using an MSSP construction and an explicit MSSP for an efficient ℓ∞-norm implementation.
Results
O(d/ε) error and O(log d) randomness are achieved for the pure-DP algorithm, while the computationally efficient mechanism has O((d log d)/ε) error and O(log d) randomness.
Takeaways & Limitations
The algorithm essentially resolves the main open questions from while leaving a computational efficiency gap and broader randomness–utility questions open.
Takeaways & Limitations
The O(log d) randomness bound is known to be tight only when ε ≤ 1/d, and the efficient mechanism remains a factor O(log d) off the optimal error bound.
Abstract
from arXiv · showhide
We study the question of answering linear queries with differential privacy using few (expected) random bits. We provide a randomness-efficient analog of the $\| \cdot \|_K$-norm mechanism of Hardt and Talwar [HT10]. For the $\ell_\infty$-error, our algorithm can answer $d$ linear queries with $O(d / \varepsilon)$ error using $O(\log d)$ random bits, improving upon algorithms of Canonne et al. and Ghentiyala [CSV25, Ghe26]; this is optimal when $\varepsilon \le 1/d$. We also provide a computationally efficient version of our algorithm, albeit with an $O(\log d)$ multiplicative increase in the error.
1 Introduction
The paper asks whether differential privacy can answer linear queries with both low randomness complexity and high utility. It shows that O(log d) expected random bits suffice for optimal ℓ∞-error, while an efficient mechanism incurs an O(log d) error factor.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
2 Preliminaries
The preliminaries define the geometric, privacy, sensitivity, entropy, and randomness-complexity concepts used to analyze the mechanisms. They also connect output entropy to expected random-bit usage through DDG-tree sampling.
- Convex Geometry: A δ-net is a finite subset whose points approximate every element of a set within distance δ under a specified norm.
- Convex Geometry: 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.
- 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.
- 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.
- 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.
3 Multi-Scale Secluded Partitions
This section develops multi-scale secluded partitions, which simultaneously control partition-cell coverage and the number of cells intersected at multiple scales. It gives both an existential geometric construction and an explicit rounding-based construction.
- 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.
- 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.
- Existential Construction: 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.
- 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.
- 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.
4 Low Randomness Mechanism for any ∥· ∥K-norm
The paper uses an MSSP partition with exponential-mechanism sampling over partition cells to obtain differential privacy, low expected norm error, and low randomness. The mechanism achieves O(d/ε) expected error with O(log d) randomness under unit sensitivity.
- 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/ε.
- Main Mechanism: 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.
- Privacy: Privacy follows because the distance-to-cell score has sensitivity at most 1, making the exponential-mechanism instantiation ε-differentially private.
- 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.
- 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.
5 Efficient Mechanism for ℓ∞-norm
The efficient mechanism preserves differential privacy while making partition-cell sampling computationally tractable. It achieves expected ℓ∞-error O((d log d)/ε), O(log d) expected randomness, and polynomial expected running time.
- 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.
- 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.
- 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.
- 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.
- 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.
6 Conclusion and Open Questions
The paper presents an ε-DP mechanism with nearly optimal error and randomness complexity, while identifying efficiency, norm-generalization, and approximate-DP gaps that remain open.
- O(log d) randomness is paired with nearly optimal error, essentially resolving the main open questions from.
- 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.
- O(log d) randomness complexity is known to be tight only when ε ≤1/d, leaving larger-ε optimality unresolved.
- The algorithms are efficient only for ℓ∞-sensitivity, leaving efficient mechanisms for all K-norms or all ℓp-norms as an open direction.
- 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.
- The authors report using AI for construction, formalization, proof drafting, figure generation, and proof checking, while verifying correctness and originality.