PaperlayerView exact revision on arXiv

Source-linked AI summary

Extremal Mechanisms for Local Differential Privacy

Peter Kairouz, Sewoong Oh, Pramod Viswanath

arXiv:1407.1338v3cs.IT

TL;DR

The paper studies how to maximize statistical utility while protecting locally private data from analysts. It characterizes optimal mechanisms through staircase mechanisms and a finite linear program, then shows that binary and randomized response mechanisms cover the extreme privacy regimes and approximate the intermediate regime.

  • Problem

    The paper addresses the trade-off between sharing data for statistical utility and protecting individuals under local differential privacy.

  • Method

    It characterizes optimal privatization mechanisms using staircase mechanisms and reduces privacy–utility optimization to a finite-dimensional linear program.

  • Results

    Binary and randomized response mechanisms are optimal in the high- and low-privacy regimes, respectively, and well approximate the intermediate regime.

  • Takeaways & Limitations

    The framework provides explicit optimal or near-optimal privatization mechanisms for information-theoretic utilities including f-divergences and mutual information.

  • Takeaways & Limitations

    The generalization to approximate differential privacy is limited: the treatment applies only to binary alphabets, while larger input alphabets remain an open question.

Abstract

from arXiv · show

Local differential privacy has recently surfaced as a strong measure of privacy in contexts where personal information remains private even from data analysts. Working in a setting where both the data providers and data analysts want to maximize the utility of statistical analyses performed on the released data, we study the fundamental trade-off between local differential privacy and utility. This trade-off is formulated as a constrained optimization problem: maximize utility subject to local differential privacy constraints. We introduce a combinatorial family of extremal privatization mechanisms, which we call staircase mechanisms, and show that it contains the optimal privatization mechanisms for a broad class of information theoretic utilities such as mutual information and $f$-divergences. We further prove that for any utility function and any privacy level, solving the privacy-utility maximization problem is equivalent to solving a finite-dimensional linear program, the outcome of which is the optimal staircase mechanism. However, solving this linear program can be computationally expensive since it has a number of variables that is exponential in the size of the alphabet the data lives in. To account for this, we show that two simple privatization mechanisms, the binary and randomized response mechanisms, are universally optimal in the low and high privacy regimes, and well approximate the intermediate regime.

1. Introduction

The paper frames local differential privacy as a privacy–utility optimization problem for statistical inference and information preservation. It develops extremal mechanisms and identifies when simple mechanisms are optimal or approximately optimal.

  • Problem formulation: The central problem is maximizing released-data utility subject to local differential privacy constraints.The framework targets settings where both data providers and analysts want useful statistical analyses while preserving privacy.
  • Motivation: Local privacy protects individuals even from analysts, while released data must retain utility for statistical analysis.Clients privatize their data before analysts observe it and infer statistics of the original distribution.
  • Utilities: The framework covers convex information-theoretic utilities, including f-divergences for hypothesis testing and mutual information for information preservation.These utilities quantify statistical discrimination and the information retained in a private view.
  • Main results: Staircase mechanisms contain optimal privatization mechanisms for the considered utilities at every privacy level.The mechanisms form a finite family of extremal points in the space of locally private mechanisms.
  • Main results: The privacy–utility optimization is equivalent to a finite-dimensional linear program, but its 2^|X| variables can make computation expensive.The linear-program outcome is the optimal staircase mechanism.
  • Main results: Binary and randomized response mechanisms are optimal in the high- and low-privacy regimes, respectively, and well approximate the intermediate regime.The paper also studies approximate differential privacy, where its techniques do not directly generalize.

2. Main Results

The paper shows that optimal locally private mechanisms can be restricted to staircase mechanisms and represented through a finite-dimensional linear program. Binary and randomized response mechanisms provide simpler optimal or near-optimal solutions across privacy regimes.

  • 2.2 Combinatorial representation of the staircase mechanisms: The linear program has 2^k variables and therefore becomes computationally difficult as the input alphabet grows.This exponential complexity motivates simpler mechanisms for practical use.
  • 2.2 Combinatorial representation of the staircase mechanisms: Binary and randomized response mechanisms are optimal in the high- and low-privacy regimes, respectively, and well approximate the intermediate regime.These mechanisms are simpler alternatives to solving the exponentially sized linear program.
  • 2.1 Optimality of staircase mechanisms: Staircase mechanisms contain optimal solutions for the paper’s broad class of convex utility maximization problems at every privacy level.The class includes utilities built from sublinear functions, including mutual information, total variation, KL-divergence, and χ2-divergence.
  • 2.1 Optimality of staircase mechanisms: An optimal mechanism needs no more outputs than inputs, and its likelihood ratios take only the extremal values 0 or eε in absolute log scale.This extremal structure defines the staircase mechanism family.
  • 2.2 Combinatorial representation of the staircase mechanisms: The original infinite-dimensional nonlinear optimization is equivalent to a finite-dimensional linear program whose optimal solutions correspond to staircase mechanisms.The representation uses a diagonal scaling matrix Θ applied to the staircase pattern matrix.
  • 2.2 Combinatorial representation of the staircase mechanisms: Every staircase mechanism uses columns proportional to one of exactly 2^k canonical staircase patterns for an input alphabet of size k.The patterns are encoded by a binary staircase pattern matrix with entries in {1, eε}.

3. Hypothesis Testing

The paper studies privatized binary hypothesis testing by maximizing f-divergences between induced marginals under local differential privacy. Staircase mechanisms contain optima, with binary and randomized response mechanisms optimal in high- and low-privacy regimes, respectively.

  • 3.1 Utility for hypothesis testing: The analyst’s testing problem reduces to maximizing the f-divergence between privatized marginals M0 and M1 over ε-locally differentially private mechanisms.KL divergence and total variation are special cases of the f-divergence utility.
  • 3.1 Utility for hypothesis testing: Staircase mechanisms are optimal for f-divergences because the relevant objective is convex in the mechanism, enabling the general staircase optimality result.The result applies to the broad f-divergence class described in the section.
  • 3.2 Optimality of the binary mechanism: For ε ≤ ε∗, the binary mechanism maximizes every f-divergence between induced marginals, where ε∗ depends on P0 and P1 but not on the chosen divergence.This high-privacy optimality is established through statistical dominance and Blackwell’s comparison result.
  • 3.2 Optimality of the binary mechanism: For every ε ≥ 0, the binary mechanism maximizes total variation distance between the induced marginals.Thus binary mechanisms remain exactly optimal for this utility beyond the high-privacy regime.
  • 3.3 Optimality of the randomized response mechanism: For KL divergence, the binary mechanism achieves at least 1/[2(e^ε + 1)^2] of optimum, while randomized response is optimal for sufficiently large ε.For ε ≤ 1, the binary mechanism is within a constant factor; randomized response does not require knowledge of P0 or P1.

4. Information Preservation

The section formulates mutual-information preservation as maximizing information about X in a privatized output Y under local differential privacy. Staircase mechanisms are optimal, while binary and randomized response mechanisms are optimal in high- and low-privacy regimes and approximate the intermediate regime.

  • Mutual information is maximized by choosing a privatization mechanism Q subject to local differential privacy constraints.The problem can also be viewed as minimizing conditional entropy because I(X;Y)=H(X)−H(X|Y).
  • Staircase mechanisms are optimal for the mutual-information privacy-utility problem.Convexity and homogeneity of the relevant function imply that the general staircase-mechanism results apply.
  • Optimality of the binary mechanism: For sufficiently high privacy, a binary mechanism maximizes mutual information for every input distribution P.There exists a positive distribution-dependent ε* such that optimality holds for ε≤ε*; the mechanism uses two outputs.
  • Optimality of randomized response: For sufficiently low privacy, randomized response maximizes mutual information over all ε-locally differentially private mechanisms.The threshold ε* depends on P, but randomized response itself does not depend on P and therefore works when P is unknown.
  • Numerical experiments: 35% of the optimal mutual information is the worst reported performance when the mechanism and privacy regime are mismatched.The comparison concerns binary and randomized response mechanisms across small-ε and large-ε regimes.
  • Numerical experiments: 75% for |X|=6 and 65% for |X|=12 are achieved by choosing the better of binary and randomized response across all tested distributions.The mixed strategy is reported as insensitive to alphabet size and is evaluated over |X|∈{3,4,6,12}.

5. Generalizations to approximate differential privacy

For binary input alphabets, the quaternary mechanism is optimal under (ε,δ)-local differential privacy for every privacy level and every utility obeying the data processing inequality. The proof characterizes privacy through hypothesis-testing error regions and shows that the quaternary region is maximal.

  • The result applies to utilities expressible as U(Q)=Σ_y μ(Q_y) for any sublinear μ, a class containing the paper’s studied utilities.
  • The generalization is limited to binary input alphabets because approximate-privacy constraints do not decompose by output.
  • The quaternary mechanism passes X unchanged with probability δ and applies the binary mechanism with probability 1−δ.
  • For |X|=2, the quaternary mechanism maximizes every utility obeying the data processing inequality over (ε,δ)-locally private mechanisms.
  • (ε,δ)-local differential privacy is equivalent to containment of a mechanism’s hypothesis-testing error region within Rε,δ.
  • The quaternary mechanism dominates every differentially private mechanism, so data-processing utilities satisfy U(Q)≤U(QQT).

6. Discussion

The discussion identifies extensions beyond the paper’s independent, exchangeable, binary-testing setting, including correlated data, robust or m-ary testing, and distortion-based utilities.

  • The paper assumes a broad class of convex utilities and non-collaborating individuals, although its techniques can extend to interactive collaboration.
  • Correlation among data: Correlated observations couple individuals’ utility-maximization problems because one observation reveals information about another.
  • Robust and m-ary hypothesis testing: Robust testing can optimize worst-case f-divergence over two classes of prior distributions rather than a fixed pair.
  • Robust and m-ary hypothesis testing: Private m-ary testing may use average or worst-case pairwise f-divergence when data follow one of m distributions.
  • Non-exchangeable utility functions: Non-exchangeable utilities can incorporate a distortion metric over X∪Y; a cited mechanism is near-optimal for sufficiently large ε.

7. Proof of Theorems 2 and 4

The proof reduces optimization over locally private mechanisms to finite polytopes and their extreme points. This yields an optimal staircase mechanism with at most k outputs for a k-symbol input alphabet.

  • Convex utilities satisfying the zero-column assumption need only be optimized over mechanisms with output alphabet size ℓ≤k.
  • Every locally private mechanism can be represented as Q=SΘ, with Sij∈[1,e^ε] and nonnegative diagonal weights in Θ.
  • The columns of S lie in a cube whose corner points have entries in {1,e^ε}, producing staircase patterns.
  • An optimal linear-program solution has at most k nonzero weights, so deleting zero columns yields a staircase mechanism with at most k columns.
  • The locally private mechanism set is a closed, bounded polytope, and each corner point has at most k nonzero columns.
  • The privacy constraints can be written as linear inequalities for every input pair and output, together with stochasticity constraints.

8. Proofs for Hypothesis Testing

For binary hypothesis testing, the proofs establish optimality of the binary mechanism in the low-privacy regime and randomized response in the high-privacy regime, with a constant-factor intermediate-regime guarantee.

  • The binary mechanism achieves the upper and lower marginal bounds for sufficiently small ε, with a threshold ε* depending on P0 and P1.
  • Hypothesis-testing regions represent the convex hull of achievable miss-detection and false-alarm probabilities under decision rules.
  • The binary mechanism dominates any ε-locally private mechanism in the hypothesis-testing region for sufficiently small ε, implying no larger f-divergence is attainable.
  • The binary mechanism is optimal for total variation distance for all ε.
  • For sufficiently large ε, randomized response achieves the upper bound for KL divergence and is therefore optimal in that regime.
  • The intermediate-regime guarantee is BIN≥1/[2(e^ε+1)^2] OPT.

9. Proofs for Information Preservation

The proofs establish optimality of the binary mechanism for sufficiently low privacy levels and randomized response for sufficiently high privacy levels. They use linear-program duality and properties of the staircase pattern to match upper bounds.

  • Linear-program proof: The staircase linear program has no duality gap because its feasible polytope is closed and bounded.The staircase pattern matrix is the k×2^k matrix from Definition 3.
  • Binary mechanism: The binary mechanism achieves the upper bound and is optimal for all ε ≤ ε∗.The proof constructs a feasible dual solution for sufficiently small ε and matches it with the binary mechanism.
  • Low-privacy bound: For ε ≤ 1, the relevant upper bound is at most 1, using the binary mechanism's utility and the maximization over staircase columns.The bound is expressed through max_j μ_j and the binary utility terms μ(P(T), ε) and μ(P(T^c), ε).
  • Partition structure: When T is the singleton containing the most probable symbol, it maximizes P(A)P(A^c) and also maximizes the corresponding utility over subsets.This is stated as Claim 4 for fixed ε ≤ 1.
  • Randomized response: The randomized response mechanism achieves the upper bound and is optimal for all ε ≥ ε∗.The proof establishes dual feasibility for sufficiently large ε before matching the bound with randomized response.

10. Proof of Proposition 17

The proposition proves that utility mechanisms built from a sublinear function obey the data processing inequality. This follows by applying a stochastic mapping after the original mechanism and using sublinearity and row stochasticity.

  • Data processing inequality: A utility of the form U(Q) = Σ_y μ(Q_y), with μ sublinear, obeys the data processing inequality.The result applies when Q is followed by a stochastic mapping W to produce the final output.
Loading 1407.1338v3…