Source-linked AI summary
Universally Utility-Maximizing Privacy Mechanisms
Arpita Ghosh, Tim Roughgarden, Mukund Sundararajan
TL;DR
The paper asks how to provide strong utility for users with different side information and preferences while preserving differential privacy. It models users with priors and loss functions and analyzes count-query mechanisms, showing that a single α-geometric mechanism, with user-specific remapping, is optimal for every rational user. The result is scoped to fixed count queries and leaves analogous guarantees for other privacy definitions, query types, and priors as open questions.
Problem
The paper seeks utility guarantees that remain near-optimal for every potential user despite differing side information and preferences, under differential privacy.
Method
The paper characterizes user-optimal private mechanisms with linear programming and shows relevant solutions derive from the α-geometric mechanism through user-specific remappings.
Results
Every rational user achieves as much utility from the α-geometric mechanism as from a differentially private mechanism optimally tailored to that user.
Takeaways & Limitations
A user-independent geometric mechanism can deliver user-specific optimal utility through post-processing while preserving the standard differential privacy model.
Takeaways & Limitations
The paper leaves open whether analogous simultaneous results hold for additive differential privacy, other query types, multiple queries, or users with priors over databases.
Abstract
from arXiv · showhide
A mechanism for releasing information about a statistical database with sensitive data must resolve a trade-off between utility and privacy. Privacy can be rigorously quantified using the framework of {\em differential privacy}, which requires that a mechanism's output distribution is nearly the same whether or not a given database row is included or excluded. The goal of this paper is strong and general utility guarantees, subject to differential privacy. We pursue mechanisms that guarantee near-optimal utility to every potential user, independent of its side information (modeled as a prior distribution over query results) and preferences (modeled via a loss function). Our main result is: for each fixed count query and differential privacy level, there is a {\em geometric mechanism} $M^*$ -- a discrete variant of the simple and well-studied Laplace mechanism -- that is {\em simultaneously expected loss-minimizing} for every possible user, subject to the differential privacy constraint. This is an extremely strong utility guarantee: {\em every} potential user $u$, no matter what its side information and preferences, derives as much utility from $M^*$ as from interacting with a differentially private mechanism $M_u$ that is optimally tailored to $u$.
1 Introduction
Organizations publish statistical aggregates such as count queries, but seemingly private publication schemes have suffered privacy attacks. Differential privacy provides a rigorous, quantifiable framework for provable protection.
- Statistical organizations publish aggregate information, including counts of individuals exceeding an income threshold.
- Prior publication schemes considered private have succumbed to privacy attacks.
- Differential privacy formalizes privacy by limiting how output probabilities change when one individual's database row changes.
2 Model
The paper studies count-query mechanisms under differential privacy and models users through priors and monotone loss functions. Users can post-process outputs, motivating user-specific remappings of a common mechanism.
- Differential Privacy: Count queries return how many database rows satisfy a fixed predicate, with neighboring databases differing in one row.
- Differential Privacy: An oblivious mechanism's output distribution depends only on the query result, and privacy constrains probabilities for neighboring query results.
- Differential Privacy: The α-geometric mechanism adds two-sided geometric noise to the true count-query result.
- Utility Model: Users are modeled by priors over query results and nonnegative loss functions nondecreasing in absolute error.
- Utility Model: A user's optimal differentially private mechanism minimizes its prior-weighted expected loss over allowable mechanisms.
- User Post-Processing: Post-processing can reduce expected loss, and the optimal remap deterministically selects the posterior-minimizing query result for each mechanism response.
3 Main Result and Discussion
For fixed count queries, database size, and privacy level, the α-geometric mechanism is simultaneously optimal for every rational user after user-specific remapping. This avoids directly tailoring the mechanism to individual preferences while retaining differential privacy under the paper's scope.
- The α-geometric mechanism is simultaneously optimal for every rational user.
- For any user, an optimal remap of the α-geometric mechanism minimizes expected loss among oblivious α-differentially private mechanisms with range N.
- Every user obtains as much utility from the geometric mechanism as from a differentially private mechanism optimally tailored to that user.
- User-specific optimization would require eliciting preferences and answering the same query differently for different users, which degrades differential privacy.
- The theorem's restriction to oblivious mechanisms is without loss of generality in a precise sense, while range N requires legitimate query-result outputs.
4 Related Work
Related work establishes privacy risks from answering many queries, develops private mechanisms for restricted query classes, and studies utility in other settings. This paper differs by combining a general user utility model with simultaneous mechanism optimality.
- Differential privacy addresses impossibility results showing that extensive accurate query answering can enable database reconstruction.
- Interactive mechanisms commonly limit the number of answered queries, while other work studies simultaneous accuracy for restricted count-query classes.
- McSherry and Talwar study utility functions for differentially private pricing queries whose neighboring databases can have very different values.
- That work does not consider priors or formulate simultaneous or individual mechanism optimality.
- Independent linear-programming work studies how expected error scales with the number of queries, rather than a general utility model.
5 Proof of Main Result
The proof reduces each user’s optimal differentially private mechanism to a linear-program vertex, characterizes its constraint structure, and shows that it can be obtained by remapping the geometric mechanism.
- Proof strategy: The proof has three steps: formulate a user-specific linear program, identify necessary conditions for optimal mechanisms, and construct a remapping of the geometric mechanism.The LP has a user-specific objective but a common feasible region.
- Vertex characterization: Every user-specific LP has an optimal solution that is a vertex, whose tight constraints uniquely determine its constraint matrix.The mechanism is represented as a matrix with query results as rows and responses as columns.
- Example: For the Figure 2 example, the optimal 1/2-differentially private mechanism is derived from the 1/2-geometric mechanism by clipping and remapping its outputs.Negative values map to 0, values above 5 map to 5, 1 maps to 2, and other values remain unchanged.
- Constraint structure: Optimal mechanisms’ constraint-matrix rows consist of some ↓’s, at most one S, and some ↑’s, with adjacent-row conditions further restricting their structure.The proof derives these patterns using loss monotonicity, optimality, and the requirement that each row be a probability distribution.
- Constraint structure: The number of S entries equals the number of Z-columns, while each non-Z column follows a prescribed sequence of ↑’s, S’s, and ↓’s.The equality uses vertex properties; the column pattern is established inductively.
- Remapping construction: There exists a remapping of the geometric mechanism whose induced constraint matrix matches that of any optimal vertex mechanism.The remapping assigns integer ranges to outputs while preserving the corresponding Z-columns and non-Z column patterns.
6 Discussion
The discussion establishes when obliviousness preserves optimality, and when allowing database-dependent mechanisms destroys the universal guarantee. It also characterizes uniqueness under a restricted range and rules out the Laplace mechanism as a universal optimum.
- 6.1 Uniqueness: The Laplace mechanism is not a universal analogue of the geometric mechanism: in the stated example, its expected loss is √α/2 versus α/(1+α) for the geometric mechanism.The resulting approximation tends to infinity as α approaches 0, ruling out Laplace for the universal guarantee.
- 6.1 Uniqueness: If the mechanism range is N, G is the unique simultaneously optimal mechanism up to a permutation of its range.Theorem 6.1 formalizes this uniqueness for fixed database size and privacy level, while the unrestricted setting also permits a range-restricted variant.
- 6.2 Obliviousness: Proposition 6.2 shows that for every user, an optimal mechanism under the database-prior objective can also be chosen oblivious.The construction averages response probabilities over databases sharing each query result while preserving privacy and avoiding greater expected loss.
- 6.2 Obliviousness: For oblivious mechanisms, averaging over databases makes expected loss depend only on the induced prior over query results, unlike database-dependent mechanisms.An adversarial database distribution can make a non-oblivious mechanism incur at least as much loss as its oblivious average.
- 6.2 Obliviousness: Theorem 6.3 shows that with priors over databases, two users can have monotone losses and distinct priors for which no mechanism is simultaneously optimal.The counterexample uses a count query, privacy level α = 1/2, and carefully chosen priors over databases of size 3.
- 6.2 Obliviousness: Obliviousness is therefore no longer without loss of generality under database priors, although restricting attention to oblivious mechanisms retains the earlier theorem.The paper explicitly contrasts Proposition 6.2 with Theorem 6.3.
7 Future Directions
The paper identifies open questions about whether simultaneous optimality extends beyond its current privacy, query, and prior assumptions.
- The simultaneous-optimality result is established for fixed count queries under the paper’s differential privacy framework, leaving other privacy definitions open.
- Whether a single mechanism can achieve an analogous result for other query types or multiple queries remains unresolved.
- For users with priors over databases, the paper leaves open whether a single mechanism can provide positive guarantees such as simultaneous approximation.