PaperlayerView exact revision on arXiv

Source-linked AI summary

From the Information Bottleneck to the Privacy Funnel

Ali Makhdoumi, Salman Salamatian, Nadia Fawaz, Muriel Medard

arXiv:1402.1774v5cs.IT

TL;DR

The paper addresses how users can disclose data correlated with private information while retaining utility and limiting inference leakage. It models the trade-off with log-loss, reducing privacy and utility to mutual-information quantities, and develops a locally optimal greedy Privacy Funnel algorithm connected to Information Bottleneck. The approach is evaluated on the US census dataset.

  • Problem

    Users need to disclose useful data correlated with private data while limiting an analyst’s ability to infer what they wish to keep private.

  • Method

    The paper applies log-loss within a probabilistic privacy-mapping framework, casts the trade-off as Privacy Funnel optimization, and derives a greedy algorithm using its Information Bottleneck connection.

  • Results

    Under log-loss, privacy leakage is I(S; Y), utility is mutual information between non-private and disclosed data, and the greedy algorithm is locally optimal.

  • Takeaways & Limitations

    The framework provides a mutual-information formulation for privacy-utility design and evaluates the resulting greedy mapping procedure on US census data.

Abstract

from arXiv · show

We focus on the privacy-utility trade-off encountered by users who wish to disclose some information to an analyst, that is correlated with their private data, in the hope of receiving some utility. We rely on a general privacy statistical inference framework, under which data is transformed before it is disclosed, according to a probabilistic privacy mapping. We show that when the log-loss is introduced in this framework in both the privacy metric and the distortion metric, the privacy leakage and the utility constraint can be reduced to the mutual information between private data and disclosed data, and between non-private data and disclosed data respectively. We justify the relevance and generality of the privacy metric under the log-loss by proving that the inference threat under any bounded cost function can be upper-bounded by an explicit function of the mutual information between private data and disclosed data. We then show that the privacy-utility tradeoff under the log-loss can be cast as the non-convex Privacy Funnel optimization, and we leverage its connection to the Information Bottleneck, to provide a greedy algorithm that is locally optimal. We evaluate its performance on the US census dataset.

I. INTRODUCTION

The paper studies how to disclose data correlated with private information while balancing utility against inference risk. Under log-loss, this trade-off becomes mutual-information optimization and motivates a locally optimal greedy Privacy Funnel algorithm connected to Information Bottleneck.

  • I. INTRODUCTION: Users transform non-private data probabilistically before disclosure to preserve utility while limiting leakage about correlated private data.The analyst may legitimately use disclosed data for utility but can also exploit it to infer private data.
  • I. INTRODUCTION: Log-loss reduces privacy leakage to I(S; Y) and utility to mutual information between non-private and disclosed data.This formulation links the privacy-utility problem to the Privacy Funnel optimization.
  • I. INTRODUCTION: The paper proves that inference threat under any bounded cost function is upper-bounded by an explicit function of mutual information between private and disclosed data.This result supports the relevance and generality of the log-loss privacy metric.
  • I. INTRODUCTION: Because the Privacy Funnel is non-convex, the paper develops a locally optimal greedy algorithm by leveraging its connection to Information Bottleneck methods.The paper evaluates the algorithm on real-world data, including the US census dataset.

B. Privacy Metric

The privacy metric models an analyst who improves beliefs about private data after observing disclosed data. Its inference-cost gain measures how much observing the disclosure improves expected inference quality.

  • B. Privacy Metric: The analyst selects a prior belief over private data and revises it after observing the disclosed variable Y.This framework represents adversarial statistical inference, including estimates such as MAP inference.
  • B. Privacy Metric: The inference-cost gain ΔC equals the initial minimum average inference cost minus the expected minimum cost after observing Y.The metric compares inference before disclosure with inference conditioned on each observed value.
  • B. Privacy Metric: The privacy mapping should minimize ΔC by keeping post-observation inference costs close to the initial cost without observing Y.Lower cost gain means the disclosure provides less improvement to the analyst’s inference of private data.

C. Accuracy Metric

The accuracy requirement constrains the expected distortion between original non-private data X and transformed data Y. Because distortion is linear in the probabilistic mapping, the utility constraint is linear.

  • C. Accuracy Metric: Utility is modeled by an average distortion constraint E[d(X, Y)] ≤ D for a distortion measure d and level D.The distortion measure depends on X and Y, not on their statistical properties.
  • C. Accuracy Metric: The average distortion is linear in the privacy mapping P_Y|X, making the distortion constraint linear in P_Y|X.This linearity follows from treating d as a fixed function of X and Y.
  • C. Accuracy Metric: For a given distortion level D, the optimal privacy mapping is obtained by solving the corresponding constrained optimization.The optimization minimizes privacy leakage subject to the accuracy requirement.

III. THE PRIVACY FUNNEL METHOD

Under log-loss, privacy leakage is mutual information I(S; Y), and this metric controls inference threats for any bounded cost function. The resulting framework motivates the Privacy Funnel formulation.

  • Privacy Funnel method: The paper uses log-loss in both privacy and distortion metrics to characterize the privacy-utility trade-off through the Privacy Funnel.The section also relates this formulation to the Information Bottleneck method.
  • Privacy metric under log-loss: Under log-loss, average inference cost gain equals mutual information I(S; Y).The result follows because prior and posterior optimal log-loss costs are H(S) and H(S|Y), respectively.
  • Privacy metric under log-loss: For any bounded cost function, inference cost gain is upper-bounded by an explicit function of I(S; Y).Thus, controlling mutual information under log-loss also controls privacy threats under other bounded cost functions.

B. Accuracy metric under log-loss

With log-loss distortion, the average distortion is conditional entropy H(X|Y), so the utility constraint becomes a mutual-information disclosure constraint.

  • Accuracy metric under log-loss: Log-loss distortion d(x, y) = −log P(X = x|Y = y) has average distortion H(X|Y).The mapping P_Y|X is designed to minimize this conditional entropy.
  • Accuracy metric under log-loss: For fixed H(X), the constraint H(X|Y) ≤ D is equivalent to I(X; Y) ≥ R, where R = H(X) − D.Disclosure is defined as mutual information between X and Y under S → X → Y.

C. Privacy-Disclosure Trade-off

The Privacy Funnel designs a randomized mapping that preserves information about public data X while limiting information about private data S. For a required disclosure level, it minimizes I(S; Y).

  • Privacy-Disclosure Trade-off: The randomized mapping P_Y|X produces Y that is informative about X but uninformative about private S.The mapping balances disclosure utility against collateral privacy loss.
  • Privacy-Disclosure Trade-off: The Privacy Funnel selects a mapping maximizing disclosure I(X; Y) subject to minimizing private information I(S; Y).Its formulation represents the privacy-disclosure trade-off directly.
  • Privacy-Disclosure Trade-off: For disclosure level R, the Privacy Funnel minimizes I(S; Y) among mappings satisfying I(X; Y) ≥ R.The objective is convex in the mapping, but the reverse-information constraint makes the optimization non-convex.

D. Connection to the Information Bottleneck Method

The Privacy Funnel and Information Bottleneck optimize opposite information trade-offs: the former preserves X while hiding S, whereas the latter preserves S while compressing X. This connection motivates adapting Information Bottleneck algorithms, including a greedy method for the Privacy Funnel.

  • Connection to the Information Bottleneck Method: Information Bottleneck compresses X while preserving information about correlated S, minimizing I(X; Y) subject to retaining information about S.It generalizes rate-distortion by trading compression length against preserved accuracy.
  • Connection to the Information Bottleneck Method: Privacy Funnel reverses this objective by making I(S; Y) small and I(X; Y) large.Thus, the two methods have structurally opposite optimization goals.
  • Connection to the Information Bottleneck Method: The Information Bottleneck alternating algorithm may converge to either a local minimum or maximum, without guaranteeing which one.The paper therefore develops a greedy algorithm guaranteed to converge to a Privacy Funnel solution.

IV. ALGORITHM FOR THE PRIVACY FUNNEL

Because the Privacy Funnel is non-convex, the paper introduces a greedy algorithm and evaluates it on real-world data.

  • The greedy algorithm approximately solves the non-convex Privacy Funnel optimization.The algorithm is introduced after establishing that the optimization is not convex.
  • It starts from an identity privacy mapping and iteratively merges output symbols while maintaining the utility constraint I(X; Y ) ≥ R.At each iteration, two symbols are selected, merged, and the conditional mapping is updated.
  • The algorithm is evaluated on real-world data.

A. Greedy Algorithm

The greedy procedure begins with Y = X and reduces privacy leakage by merging output symbols while preserving a required mutual-information utility level. It is locally optimal at each step but not guaranteed to be globally optimal.

  • The procedure initializes Y = X, then merges output symbols to reduce I(S; Y ) while retaining I(X; Y ) ≥ R.Merging replaces p(yi|x) and p(yj|x) with their sum for every x.
  • Each merge combines two columns of the conditional-probability matrix, producing a mapping whose entries determine the resulting output assignment.The algorithm starts with an identity matrix and repeatedly deletes two columns before adding their sum.
  • After merging yi and yj, mutual-information differences can be written as conditional-entropy differences before and after the merge.The proof expresses both I(S; Y ) − I(S; Y i−j) and I(X; Y ) − I(X; Y i−j) through conditional entropies.
  • The greedy choice minimizes I(S; Y ) locally at every step, but it has no guarantee of finding the globally optimal privacy mapping.
  • A complementary greedy information-bottleneck algorithm seeks a local maximum of I(S; Y ) for a given I(X; Y ) = R.Together, the two algorithms approximately characterize the range between local minimum and maximum values.

B. Data Set

The evaluation uses the US 1994 Census dataset to study mappings that preserve information about released attributes while protecting selected private attributes.

  • The US 1994 Census dataset contains demographic features and a binary income category for a sample of the US population from 1994.Features include age, work-class, education, gender, and native country.
  • The private attributes are S = (age, income level), while the released attributes are X = (age, gender, education level).
  • Figure 1 plots the maximum and minimum I(S; Y ) values for each I(X; Y ) value.

C. Numerical Results

On the Census data, the paper compares minimum and maximum privacy leakage at each utility level, and frames the overall contribution as a locally optimal greedy approach to the Privacy Funnel.

  • The bottom curve gives the minimum I(S; Y ) for each I(X; Y ), while the top curve gives the maximum using the two greedy algorithms.The area between the curves represents pairs achievable by the considered mappings, though the algorithms are sub-optimal.
  • The privacy mapping is designed to lie on the bottom curve rather than the top curve for a given utility requirement.A negligent mapping may instead produce the higher privacy leakage shown by the top curve.
  • The paper casts the log-loss privacy-utility trade-off as the non-convex Privacy Funnel and evaluates a locally optimal greedy algorithm on the US Census dataset.
Loading 1402.1774v5…