差分隱私下時間序列的查詢敏感性
我偶然發現了一篇圍繞這個論點提出本地 DP 的論文：
- 一個使用者 $ u_i $ 生成一個序列 $ s_{i} $ 在某些時間戳的觀察：
$$ s = ((t_1, x_1), (t_2, x_2), \dots, (t_n, x_n)) $$
- 作者申請 $ (\varepsilon/n, 0) $ -DP 通過添加拉普拉斯雜訊到每個序列
- 眾所周知，拉普拉斯運算元必須具有規模 $ b = \frac{\Delta f}{ \text{budget}} $
作者提出預算 $ \varepsilon / n $ ，這是 IMO 正確的。但他們也定義 $ \Delta f $ ，也就是查詢的敏感性，就像任何時間戳的任何值的範圍一樣， $ \text{max}(x) - \text{min}(x) $ .
我不相信這是真正的敏感性。據我了解，查詢輸出（忽略時間戳）不是單個值 $ \mathbb{R} $ 而是輸出向量 $ \mathbb{R}^n $ ，所以根據靈敏度的定義 $ \ell_1 $ - 函式的敏感性 $ 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 $$
並正確計算 $ \ell_1 $ 規範為 $ | x - y|1 = \sum{i = 1}^{k} | x_i - y_i | $ , 靈敏度應該是
$$ (\text{max}(x) - \text{min}(x))^n $$
我的推理是否正確（論文的 DP 可能是錯誤的），還是我遺漏了什麼？（我不是故意透露這篇論文的。）
更新：澄清時間序列的上下文。
每個使用者的健康數據流表示為一個序列 $ s = ((t_1, x_1), (t_2, x_2), \dots, (t_n, x_n)) $
這裡， $ (t_d, x_d) $ 代表 $ d $ - 流中的第一個點 $ x_d $ 表示可穿戴健康設備在時間戳測量的值 $ t_d $ .
我們進一步假設 $ x_d $ ，由可穿戴健康設備中的特定感測器測量，在預定義的範圍內 $ [x_{min}, x_{max}] $ .
他們的特殊案例是收集心率（ $ x $ ） 隨著時間的推移 （ $ t $ ).
我不喜歡回答我的問題，但似乎我誤解了它，作者確實是正確的。
我們的查詢想要獲得 $ N $ 來自數據庫（大小為 1 的數據庫，但不相關）的測量值與總體靈敏度預算 $ \varepsilon $ . 我們還可以將單個查詢拆分為 $ N $ 獨立查詢（更多關於下面的依賴），其中每個查詢只是詢問“點的值是多少 $ n $ “。這些中的每一個 $ N $ 查詢的預算要小得多 $ \frac{\varepsilon}{N} $ 通過查詢組成滿足總體預算 $ \varepsilon $ .
現在每個“小” $ n $ -th 查詢必須滿足 $ (\frac{\varepsilon}{N}, 0) $ -DP，為此我們需要一種機制和這個“小”查詢的敏感性。在我們的例子中，靈敏度是點的值的範圍 $ n $ , 機制和往常一樣是拉普拉斯。
關於點之間的依賴關係 $ x_n $ 和 $ x_{n+1} $ . 例如，如果我們知道他們是依賴的 $ x_{n+1} $ 簡直就是 $ 2 \cdot {x_n} $ ，我們只需要分配隱私預算 $ \frac{2 \varepsilon}{N} $ 至 $ x_n $ 和 $ 0 $ 至 $ x_{n + 1} $ . 所以機制只需要隨機化 $ x_n $ . 但是我們假裝沒有任何知識，即查詢的依賴性 $ n $ 和 $ n + 1 $ ，並通過獨立保護每個查詢來預期最壞的情況。所以即使 $ x_n $ 和 $ x_{n+1} $ 是 100% 相關的，我們獨立地向它們中的每一個添加雜訊。
（我認為一個有用的視覺化是兩點 $ \mathbb{R}^2 $ 並向它們中的每一個添加多元高斯；相關和不相關，並查看這兩個分佈在可能範圍內任意點的邊界）
我認為你應該解釋什麼是 $ x_i $ 在這個時間序列中。我建議連結論文。我認為如果沒有強有力的背景，我們可能會錯誤地回答，因為也許你可能理解錯誤，因為它有時發生在我身上。幾點：
- 查詢輸出可能是 $ \mathbb{R} $ 或者 $ \mathbb{R}^n $ ，取決於您定義和使用的查詢類型。
- 你是對的，我懷疑他們正在定義全域敏感性，因為可能更容易計算。但這取決於他們在論文中定義的查詢類型，是線性查詢、唯一一個查詢還是非線性查詢