Dong Roth Su 2022 - Trade-off Functions and f-DP

Summary

DP is recast as a hypothesis test between neighboring datasets $S,S^{\prime }$. The trade-off function $T(P,Q)$ is the minimal type II error achievable at each type I level. A mechanism is $f$-DP if $T(M(S),M(S^{\prime }))\ge f$ for all neighbors. $(\epsilon ,\delta )$-DP is exactly $f_{\epsilon ,\delta }$-DP, a piecewise-linear function; every symmetric trade-off function is a valid privacy parameter.

Overview

The paper’s starting observation (credited to Wasserman-Zhou and Kairouz-Oh-Viswanath): DP is most naturally defined through the attacker’s hypothesis testing problem

$$H_0:\text{the underlying dataset is }S\text{vs}{H}_1:\text{the underlying dataset is }{S}^{\prime }.$$

Rejecting $H_0$ corresponds to detecting the absence of Alice (the one individual in $S$ but not $S^{\prime }$). For an $(\epsilon ,\delta )$-DP mechanism, any test at significance level $\alpha$ has power at most $e^{\epsilon }\alpha +\delta$, only slightly above $\alpha$ for small $\epsilon ,\delta$, so every test is essentially powerless.

Main Content

Notation. A dataset $S=(x_1,\dots ,x_n)$, $x_i\in \mathcal{X}$. Datasets $S,S^{\prime }$ are neighbors if they differ in exactly one record (replace-one adjacency). A mechanism $M$ is a randomized algorithm releasing $M(S)$. Let $P,Q$ be the distributions of $M(S),M(S^{\prime })$.

A rejection rule $0\le \varphi \le 1$ has type I error ${\alpha }_{\varphi }={\mathbb{E}}_P[\varphi ]$ and type II error ${\beta }_{\varphi }=1-{\mathbb{E}}_Q[\varphi ]$. These satisfy ${\alpha }_{\varphi }+{\beta }_{\varphi }\ge 1-\text{TV}(P,Q)$ (Eq. 3), a rough constraint that the trade-off function refines.

Definition 2.1 (trade-off function)

For distributions $P,Q$ on the same space, $T(P,Q):[0,1]\to [0,1]$,

$$T(P,Q)(\alpha )=\inf \{{\beta }_{\varphi }:{\alpha }_{\varphi }\le \alpha \},$$

the infimum over all measurable rejection rules. By the Neyman-Pearson lemma (Theorem A.1) the minimum is attained by the likelihood ratio test. The greater $T(P,Q)$, the harder it is to distinguish $P$ from $Q$.

Proposition 2.2 (characterization)

A function $f:[0,1]\to [0,1]$ is a trade-off function if and only if $f$ is convex, continuous, non-increasing, and $f(x)\le 1-x$ for $x\in [0,1]$.

Consequence: $\max \{f,g\}$ is a trade-off function if $f,g$ are. Convexity implies continuity on $(0,1)$; $f(\alpha )\ge 0$ and $f\le 1-\alpha$ give continuity at 1, so the continuity condition matters only at $x=0$.

Definition 2.3 ( $f$-differential privacy)

Let $f$ be a trade-off function. A mechanism $M$ is $f$-DP if $T(M(S),M(S^{\prime }))\ge f$ for all neighboring datasets $S,S^{\prime }$. Equivalently, distinguishing any two neighbors from the output is at least as difficult as distinguishing $P$ from $Q$ from one draw, where $f=T(P,Q)$.

The definition is parameterized by a function rather than a pair of reals, avoiding premature summarization. Because neighboring is symmetric, $f$-DP also requires $T(M(S^{\prime }),M(S))\ge f$.

Proposition 2.4 (symmetrization)

If $M$ is $f$-DP then $M$ is $f^S$-DP with $f^S=\max \{f,f^{-1}\}$, where the (left-continuous) inverse is $f^{-1}(\alpha )=\inf \{t\in [0,1]:f(t)\le \alpha \}$. Writing $f=T(P,Q)$, $f^{-1}=T(Q,P)$, so $f^S$ is a symmetric trade-off function ($f^S=(f^S{)}^{-1}$) and $f^S\ge f$. Henceforth trade-off functions are assumed symmetric.

The $(\epsilon ,\delta )$ trade-off function

$$f_{\epsilon ,\delta }(\alpha )=\max \{0,1-\delta -e^{\epsilon }\alpha ,e^{-\epsilon }(1-\delta -\alpha )\},0\le \alpha \le 1.$$

It is piecewise linear with intercept $1-\delta$, slopes $-e^{\pm \epsilon }$ and is symmetric about $y=x$ (Figure 3, left).

Proposition 2.5 (Wasserman-Zhou)

A mechanism is $(\epsilon ,\delta )$-DP if and only if it is $f_{\epsilon ,\delta }$-DP.

So $f$-DP generalizes $(\epsilon ,\delta )$-DP, which is a special case that uses only two parameters out of the whole function.

Examples

Reading $f_{\epsilon ,\delta }$ at a specific level

Setup: $\epsilon =1,\delta =0$ (pure 1-DP), test level $\alpha =0.05$. Solution: $f_{1,0}(0.05)=\max \{0,1-e\cdot 0.05,e^{-1}(0.95)\}=\max \{0,0.864,0.349\}=0.864$. So type II error $\ge 0.864$ and power $\le 1-0.864=0.136=e^1\cdot 0.05$. Interpretation: this is exactly the “power at most $e^{\epsilon }\alpha +\delta$” statement of Section 1. Recomputed.

Graphical reading of Figure 2

The paper plots three trade-off curves $T(M(S),M(S^{\prime }))$ against $f$; only the dashed curve that lies above $f$ everywhere satisfies $f$-DP. A mechanism whose trade-off curve crosses below $f$ at any $\alpha$ fails, even if it is above $f$ elsewhere: $f$-DP is a pointwise constraint on the whole curve.

Connections

• GDP is the one-parameter family of trade-off functions of unit-variance Gaussians: Dong Roth Su 2022 - Gaussian Differential Privacy Definition and Gaussian Mechanism.
• $f$-DP and Renyi DP: Renyi DP measures indistinguishability by a divergence (Mironov 2017 - Renyi Divergence and the RDP Definition); the exact relation is in Dong Roth Su 2022 - Divergence Conversion, Discussion and Limitations.
• Type I and II error vocabulary: Power Analysis and Sample Size.
• Marketing reading: the testing interpretation translates “attacker power at level $\alpha$” into plain language for non-technical stakeholders, e.g. “an adversary who wants to confirm a person was in a conversion cohort can be right at most so often”; see Dong Roth Su 2022 - Divergence Conversion, Discussion and Limitations.

See Also

• Dong Roth Su 2022 - Gaussian Differential Privacy - Overview
• Dong Roth Su 2022 - Post-Processing, Blackwell, Primal-Dual and Group Privacy
• Wasserman Zhou 2010 - Differential Privacy as a Hypothesis-Testing Constraint — the original hypothesis-testing characterization that Proposition 2.5 adapts.