Dwork Roth 2014 - Sparse Vector Technique

Summary

When a long (possibly adaptive) stream of sensitivity-1 queries must be monitored but only a few exceed a public threshold $T$, the sparse vector technique answers “above/below” at privacy cost that depends only on the number $c$ of above-threshold queries, not the stream length. AboveThreshold (halts after one hit) is $(\epsilon ,0)$-DP with noisy threshold $\mathrm{Lap}(2/\epsilon )$ and per-query noise $\mathrm{Lap}(4/\epsilon )$; Sparse restarts it $c$ times, using composition; NumericSparse also releases noisy values. Accuracy is $O(c(\ln k+\ln (c/\beta ))/\epsilon )$ for $\delta =0$, matching Laplace answers to the $c$ big queries up to a $\log k$ factor.

Overview

Independent perturbation of $m$ queries makes privacy degrade proportionally to $m$ (or $\sqrt{m}$ with advanced composition). If we only care about which queries lie above a threshold, we can “discard the numeric answer to queries that lie significantly below the threshold, and merely report that they do indeed lie below”. The technique is simple (add noise, report whether the noisy value exceeds the threshold) and “our emphasis is on the analysis, showing that privacy degrades only with the number of queries which actually lie above the threshold”. It is an online mechanism; the non-interactive analogue is to iterate Report Noisy Max or the exponential mechanism.

Setting. $m$ sensitivity-1 queries (possibly adaptive), one public threshold $T$ (per-query thresholds change nothing), a small number $c$ of expected above-threshold queries. The algorithm works with a noisy threshold $\hat{T}$; $T$ is public but $\hat{T}$ is not.

Main Content

Algorithm 1 - AboveThreshold $(D,\{f_i\},T,\epsilon )$ (p. 57)

T_hat = T + Lap(2/eps)
for each query i:
    nu_i = Lap(4/eps)
    if f_i(D) + nu_i >= T_hat:  output a_i = TOP; halt
    else:                       output a_i = BOTTOM

Input: private database $D$, adaptively chosen stream of sensitivity-1 queries $f_1,\dots$, threshold $T$. Output: stream of responses.

Theorem 3.23 (p. 57)

AboveThreshold is $(\epsilon ,0)$-differentially private, no matter how long the stream is.

Proof (pp. 57-58)

Fix neighbours $D,D^{\prime }$. Let $A,A^{\prime }$ be the outputs on $D,D^{\prime }$; an output has the form $a\in \{\top ,\perp {\}}^k$ with $a_i=\perp$ for $i<k$ and $a_k=\top$. Internal randomness: the noisy threshold $\hat{T}$ and perturbations $\{{\nu }_i\}$. Fix ${\nu }_1,\dots ,{\nu }_{k-1}$ and take probabilities over ${\nu }_k$ and $\hat{T}$. Let $g(D)={\max }_{i<k}(f_i(D)+{\nu }_i)$, now deterministic. Then

$$\mathrm{Pr}[A=a]=\underset{\hat{T},{\nu }_k}{\mathrm{Pr}}[\hat{T}>g(D)\text{and}{f}_k(D)+{\nu }_k\ge \hat{T}]=\mathrm{Pr}[\hat{T}\in (g(D),f_k(D)+{\nu }_k]]=\iint \mathrm{Pr}[{\nu }_k=v]\mathrm{Pr}[\hat{T}=t]1[t\in (g(D),f_k(D)+v]]dvdt.$$

Change variables $\hat{v}=v+g(D)-g(D^{\prime })+f_k(D^{\prime })-f_k(D)$ and $\hat{t}=t+g(D)-g(D^{\prime })$. Since each $f_i$ is 1-sensitive, so is $g$, hence $|\hat{v}-v|\le 2$ and $|\hat{t}-t|\le 1$. Under this shift the indicator maps to the same event on $D^{\prime }$: $t\in (g(D^{\prime }),f_k(D^{\prime })+v]$. Because the Laplace densities have scales $4/\epsilon$ and $2/\epsilon$, shifting ${\nu }_k$ by at most $2$ costs a factor $\exp (\epsilon /2)$ and shifting $\hat{T}$ by at most $1$ costs $\exp (\epsilon /2)$. Therefore $\mathrm{Pr}[A=a]\le \exp (\epsilon /2)\exp (\epsilon /2)\mathrm{Pr}[A^{\prime }=a]=e^{\epsilon }\mathrm{Pr}[A^{\prime }=a]$. (Proof due to Salil Vadhan.)

Definition 3.9 - $(\alpha ,\beta )$-accuracy (pp. 58-59)

A stream-answering algorithm outputting $a_1,\cdots \in \{\top ,\perp {\}}^{\ast }$ for queries $f_1,\dots ,f_k$ is $(\alpha ,\beta )$-accurate w.r.t. threshold $T$ if, except with probability at most $\beta$, it does not halt before $f_k$ and for all $a_i=\top$: $f_i(D)\ge T-\alpha$ and for all $a_i=\perp$: $f_i(D)\le T+\alpha$.

What can go wrong: $\hat{T}$ may be far from $T$; a small count may get large noise and be reported above; a large count may get negative noise and be reported below. Each happens with probability exponentially small in $\alpha$, so $\alpha /2$ is allocated to threshold error and $\alpha /2$ to query noise.

Theorem 3.24 (p. 59)

For any sequence of $k$ queries $f_1,\dots ,f_k$ with $|\{i<k:f_i(D)\ge T-\alpha \}|=0$ (the only query near or above the threshold is possibly the last), AboveThreshold$(D,\{f_i\},T,\epsilon )$ is $(\alpha ,\beta )$-accurate for

$$\alpha =\frac{8(\ln k+\ln (2/\beta ))}{\epsilon }.$$

Proof (pp. 59-60)

It suffices to show that except with probability $\beta$: ${\max }_i|{\nu }_i|+|T-\hat{T}|\le \alpha$. Then for $a_i=\top$: $f_i(D)+{\nu }_i\ge \hat{T}\ge T-|T-\hat{T}|$, so $f_i(D)\ge T-|T-\hat{T}|-|{\nu }_i|\ge T-\alpha$; for $a_i=\perp$: $f_i(D)<\hat{T}\le T+|T-\hat{T}|+|{\nu }_i|\le T+\alpha$; and for $i<k$ with $f_i(D)<T-\alpha <T-|{\nu }_i|-|T-\hat{T}|$, $f_i(D)+{\nu }_i\le \hat{T}$ so $a_i=\perp$ and the algorithm does not halt early. With $\mathrm{Pr}[|Y|\ge tb]=e^{-t}$: $\mathrm{Pr}[|T-\hat{T}|\ge \alpha /2]=\exp (-\alpha \epsilon /4)\le \beta /2$ requires $\alpha \ge 4\ln (2/\beta )/\epsilon$; and by a union bound $\mathrm{Pr}[{\max }_i|{\nu }_i|\ge \alpha /2]\le k\exp (-\alpha \epsilon /8)\le \beta /2$ requires $\alpha \ge 8(\ln k+\ln (2/\beta ))/\epsilon$. The second dominates.

Multiple above-threshold queries: Sparse

Algorithm 2 - Sparse $(D,\{f_i\},T,c,\epsilon ,\delta )$ (p. 61)

if delta == 0:  sigma = 2c/eps
else:           sigma = sqrt(32 c ln(1/delta)) / eps
T_hat_0 = T + Lap(sigma);  count = 0
for each query i:
    nu_i = Lap(2*sigma)
    if f_i(D) + nu_i >= T_hat_count:
        output TOP; count += 1; T_hat_count = T + Lap(sigma)
    else: output BOTTOM
    if count >= c: halt

Theorem 3.25 (pp. 60-61)

Sparse is $(\epsilon ,\delta )$-differentially private.

Proof (pp. 60-61)

Sparse is exactly equivalent to running AboveThreshold$(D,\{f_i\},T,{\epsilon }^{\prime })$ on the stream, restarting it on the remaining stream each time it halts, $c$ times in total, with ${\epsilon }^{\prime }=\epsilon /c$ if $\delta =0$ and ${\epsilon }^{\prime }=\epsilon /\sqrt{8c\ln (1/\delta )}$ otherwise. (Check: AboveThreshold’s noisy-threshold scale $2/{\epsilon }^{\prime }$ equals $2c/\epsilon =\sigma$ in the first case and $2\sqrt{8c\ln (1/\delta )}/\epsilon =\sqrt{32c\ln (1/\delta )}/\epsilon =\sigma$ in the second.) Each run is $({\epsilon }^{\prime },0)$-DP by Thm. 3.23. By basic composition $c$ runs with ${\epsilon }^{\prime }=\epsilon /c$ are $(\epsilon ,0)$-DP; by advanced composition (Thm. 3.20) $c$ runs with ${\epsilon }^{\prime }=\epsilon /\sqrt{8c\ln (1/\delta )}$ are $(\epsilon ,\delta )$-DP.

Theorem 3.26 (p. 62)

For any $k$ queries with $L(T)\equiv |\{i:f_i(D)\ge T-\alpha \}|\le c$, Sparse is $(\alpha ,\beta )$-accurate for

$$\alpha =\frac{(\ln k+\ln \frac{2c}{\beta })\sqrt{512c\ln \frac{1}{\delta }}}{\epsilon }(\delta >0),\alpha =\frac{8c(\ln k+\ln \frac{2c}{\beta })}{\epsilon }(\delta =0).$$

Proof (p. 62). Sparse consists of $c$ calls of AboveThreshold; if each call is $(\alpha ,\beta /c)$-accurate then Sparse is $(\alpha ,\beta )$-accurate. Apply Thm. 3.24 with $\beta /c$ and ${\epsilon }^{\prime }$ equal to $\epsilon /\sqrt{8c\ln (1/\delta )}$ or $\epsilon /c$.

Releasing the values: NumericSparse

Algorithm 3 - NumericSparse $(D,\{f_i\},T,c,\epsilon ,\delta )$ (p. 63)

Like Sparse, but when a query is above threshold it outputs $a_i=f_i(D)+{\upsilon }_i$ with ${\upsilon }_i\sim \mathrm{Lap}(\sigma ({\epsilon }_2))$, where the budget is split as: if $\delta =0$, ${\epsilon }_1=\frac{8}{9}\epsilon$, ${\epsilon }_2=\frac{2}{9}\epsilon$; else ${\epsilon }_1=\frac{\sqrt{512}}{\sqrt{512}+1}\epsilon$, ${\epsilon }_2=\frac{2}{\sqrt{512}+1}\epsilon$; and $\sigma (\epsilon )=\frac{2c}{\epsilon }$ if $\delta =0$, else $\sigma (\epsilon )=\frac{\sqrt{32c\ln (2/\delta )}}{\epsilon }$. Thresholds and per-query noise use $\sigma ({\epsilon }_1)$ (noisy threshold $\mathrm{Lap}(\sigma ({\epsilon }_1))$, query noise $\mathrm{Lap}(2\sigma ({\epsilon }_1))$). Outputs $\perp$ otherwise.

Theorem 3.27 (p. 62)

NumericSparse is $(\epsilon ,\delta )$-differentially private.

Proof (p. 62). If $\delta =0$, NumericSparse is the adaptive composition of Sparse$(D,\{f_i\},T,c,\frac{8}{9}\epsilon ,0)$ with the Laplace mechanism at privacy parameters $(\frac{1}{9}\epsilon ,0)$ (answering the $c$ released values, noise scale $9c/\epsilon =\sigma ({\epsilon }_2)$). If $\delta >0$ it is the composition of Sparse$(D,\{f_i\},T,c,\frac{\sqrt{512}}{\sqrt{512}+1}\epsilon ,\delta /2)$ with the Laplace mechanism at $(\frac{1}{\sqrt{512}+1}\epsilon ,\delta /2)$. Privacy follows by simple composition.

Definition 3.10 - Numeric accuracy (p. 63)

For answers in $(\mathbb{R}\cup \{\perp \}{)}^{\ast }$: $(\alpha ,\beta )$-accurate w.r.t. $T$ if, except with probability at most $\beta$, the algorithm does not halt before $f_k$, for all $a_i\in \mathbb{R}$: $|f_i(D)-a_i|\le \alpha$, and for all $a_i=\perp$: $f_i(D)\le T+\alpha$.

Theorem 3.28 (pp. 63-64)

For any $k$ queries with $L(T)\equiv |\{i:f_i(D)\ge T-\alpha \}|\le c$, NumericSparse is $(\alpha ,\beta )$-accurate for

$$\alpha =\frac{(\ln k+\ln \frac{4c}{\beta })\sqrt{c\ln \frac{2}{\delta }}(\sqrt{512}+1)}{\epsilon }(\delta >0),\alpha =\frac{9c(\ln k+\ln \frac{4c}{\beta })}{\epsilon }(\delta =0).$$

Proof (p. 64). Two conditions: (i) for $a_i=\perp$, $f_i(D)\le T+\alpha$, holding with probability $1-\beta /2$ by the accuracy of Sparse; (ii) for $a_i\in \mathbb{R}$, $|f_i(D)-a_i|\le \alpha$, holding with probability $1-\beta /2$ by the accuracy of the Laplace mechanism.

Take-away (p. 64)

If at most $c$ of a stream of queries have answers above $T-\alpha$, those above the threshold can be answered up to error $\alpha$. This accuracy equals, up to constants and a $\log k$ factor, what one would get if the identities of the large queries were known in advance and answered by the Laplace mechanism: the technique “fish[es] out the identities of these large queries almost ‘for free’, paying only logarithmically for the irrelevant queries”. The same guarantee could come from finding them with the exponential mechanism then answering with Laplace, but SVT is trivial to run and allows adaptively chosen queries.

Bibliographic notes (Sec. 3.7, pp. 64-65). Randomized response: Warner (1965). Laplace mechanism: Dwork et al. Exponential mechanism: McSherry and Talwar. Simple composition claimed in Dwork et al. [21], proof in Appendix B due to Dwork and Lei (McSherry and Mironov obtained a similar proof). Sections 3.5.1-3.5.2 are taken almost verbatim from Dwork, Rothblum, Vadhan; prior “evolution of confidence” arguments (Dinur, Dwork, Nissim) showed $\sqrt{k}$ deterioration for specific mechanisms. Near-tightness of composition without coordinated noise: Dwork, Naor, Vadhan. SVT abstracts a technique of Dwork-Naor-Reingold-Rothblum-Vadhan (indicator vectors in the proof of their Lemma 4.4) and found wide use (Roth-Roughgarden; Dwork-Naor-Pitassi-Rothblum; Hardt-Rothblum); the proof of Thm. 3.23 is due to Salil Vadhan.

Examples

Monitoring 1000 metrics, one anomaly (own simulation). $k=1000$ sensitivity-1 queries with true value 0 except query 700 with value 200; threshold $T=100$; $\epsilon =1$. Theorem 3.24 with $\beta =0.05$ gives $\alpha =8(\ln 1000+\ln 40)/1\approx 84.8$. The theorem’s condition holds because every query except the last has value $0<T-\alpha =15.2$. In 2000 runs AboveThreshold halted at query 700 every time, with no early false alarm and no miss. With $c=3$ anomalies at queries 100, 400, 800 (value 300, $T=150$, $\epsilon =2$, $\delta =0$), Sparse returned $\top$ at exactly $[100,400,800]$ and halted after the third; $\alpha =8\cdot 3(\ln 1000+\ln (6/0.05))/2\approx 140.3$.

import numpy as np, math
rng = np.random.default_rng(0)
 
def above_threshold(values, T, eps, rng=rng):
    """Alg. 1. Returns index of first above-threshold query (or None)."""
    T_hat = T + rng.laplace(0, 2 / eps)
    for i, v in enumerate(values):
        if v + rng.laplace(0, 4 / eps) >= T_hat:
            return i
    return None
 
def sparse(values, T, c, eps, delta=0.0, rng=rng):
    """Alg. 2. Returns list of booleans (True = above threshold) until c hits."""
    sigma = 2 * c / eps if delta == 0 else math.sqrt(32 * c * math.log(1 / delta)) / eps
    T_hat, count, out = T + rng.laplace(0, sigma), 0, []
    for v in values:
        if v + rng.laplace(0, 2 * sigma) >= T_hat:
            out.append(True); count += 1; T_hat = T + rng.laplace(0, sigma)
        else:
            out.append(False)
        if count >= c:
            break
    return out
 
values = np.zeros(1000); hits = [100, 400, 800]; values[hits] = 300
print([i for i, b in enumerate(sparse(values, 150, 3, 2.0)) if b])   # [100, 400, 800]

Connections

• Marketing measurement. Many measurement systems continuously monitor large panels of metrics (conversion rate by geo, spend pacing, brand lift by creative) and act only when one crosses a threshold. SVT is the DP analogue: the stream of “all clear” answers is free, and privacy is spent only when an alert fires. Practical caveat: the noisy threshold $\hat{T}$ is reused until a hit, so the false-alarm rate depends on the shared noise; choose $T$ with margin $\alpha$ and use $\epsilon$ per alert.
• Compare multiple testing: monitoring $k$ metrics inflates false alarms by a $\ln k$ factor in $\alpha$, exactly like a Bonferroni-type correction (Multiple Testing Corrections).

See Also

• Dwork Roth 2014 - Report Noisy Max and the Exponential Mechanism
• Dwork Roth 2014 - Advanced Composition and the Gaussian Mechanism
• Dwork Roth 2014 - Laplace Mechanism