0
$\begingroup$

I stumbled upon a paper that proposes local DP around this argument:

  • A user $u_i$ generates a sequence $s_{i}$ of observations at certain timestamps:

$$ s = ((t_1, x_1), (t_2, x_2), \dots, (t_n, x_n)) $$

  • The authors apply $(\varepsilon/n, 0)$-DP to each sequence by adding Laplacian noise
  • As widely known, Laplacian must be of scale $b = \frac{\Delta f}{ \text{budget}}$

The authors propose budget of $\varepsilon / n$, which is IMO correct. But they also define $\Delta f$, aka the sensitivity of the query, as simply the range of any value at any timestamp, $\text{max}(x) - \text{min}(x)$.

I'm not convinced that this is the true sensitivity. To my understanding, the query output is (ignoring the timestamps) not a single value $\mathbb{R}$ but rather the vector of outputs $\mathbb{R}^n$, so per definition of sensitivity $\ell_1$-sensitivity of a function $f : \mathbb{N}^{|\mathcal{X}|} \rightarrow \mathbb{R}^k$:

$$ \Delta f = \max_{x, y \in \mathbb{N}; \| x - y\|_1 = 1} \| f(x) - f(y) \|_1 $$

and properly computing the $\ell_1$ norm as $\| x - y\|_1 = \sum_{i = 1}^{k} | x_i - y_i |$, the sensitivity should be

$$(\text{max}(x) - \text{min}(x))^n$$

Is my reasoning correct (and the paper's DP potentially wrong), or am I missing something? (I don't reveal the paper on purpose.)


Update: Claryfing context of the time series.

The health data stream each user is represented as a sequence $s = ((t_1, x_1), (t_2, x_2), \dots, (t_n, x_n))$

Here, $(t_d, x_d)$ represents the $d$-th point in the stream where $x_d$ denotes the value measured by the wearable health device at timestamp $t_d$.

We further assume that $x_d$, which is measured by the specific sensor in a wearable health device, is within the predefined range $[x_{min}, x_{max}]$.

Their particular use-case is collecting heart rate ($x$) over time ($t$).

$\endgroup$
1
$\begingroup$

I think you should explain what is $x_i$ in this time series. I would recommend linking the paper. I think without a strong context we could answer wrongly because maybe you could have understood something wrong as it has happened to me sometimes. Some points:

  1. Query output could be $\mathbb{R}$ or $\mathbb{R}^n$, depends what kind of query you are defining and using.

  2. You are right, I suspect they are defining a global sensitivity because maybe is easier to compute. But this depends on the kind of query they are defining on the paper, is a linear query, an only-one query or a non-linear query

$\endgroup$
1
  • $\begingroup$ Thanks, I've updated the question, see above. Here's the paper's DOI: 10.1371/journal.pone.0207639 $\endgroup$ – John Doe Jan 25 at 12:38
0
$\begingroup$

I don't like answering my questions but it seems I misunderstood it and the authors are indeed correct.

Our query wants to obtain $N$ measurements from the database (database of size one but that's not relevant) with overall sensitivity budget $\varepsilon$. We can also split the single query into $N$ independent queries (more on the dependency below), where each query simply asks "What is the value at point $n$". Each of these $N$ queries has much smaller budget $\frac{\varepsilon}{N}$ which satisfies, by query composition, the overall budget $\varepsilon$.

Now each "small" $n$-th query has to satisfy $(\frac{\varepsilon}{N}, 0)$-DP, for which we need a mechanism and the sensitivity of this "small" query. In our case, the sensitivity is the range of values at point $n$, and the mechanism is Laplace as usual.

Regarding dependency between points $x_n$ and $x_{n+1}$. If we knew they are dependent, for example $x_{n+1}$ is simply $2 \cdot {x_n}$, we would only need to allocate the privacy budget $\frac{2 \varepsilon}{N}$ to $x_n$ and $0$ to $x_{n + 1}$. So the mechanism needs to randomize only $x_n$. But we pretend to have no knowledge whatsoever, i.e. the dependency of queries $n$ and $n + 1$, and expect the worst case by protecting each query independently. So even if $x_n$ and $x_{n+1}$ are 100% correlated, we add noise to each of them independently.

(I think a helpful visualization are two points in $\mathbb{R}^2$ and adding multivariate gaussian to each of them; correlated and uncorrelated, and look at the bounds of these two distribution in any point from the possible range)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.