Privacy Amplification by Decentralization
motivation：平衡隱私保護和實用性，當用戶很多，中心DP有瓶頸。
methods：LDP+relaxation==》Network DP，local view（local memory and messages received）
experiments：求和，離散直方圖，梯度優化
conclusion：對比LDP，隱私收益O（1/根號n）；避免用戶共謀，在完全圖中在LDP下，與相同算法比較提出的算法隱私放大結果O（1/根號n的1/4）
Abstract
1.在LDP中提出了一個relaxation，在圖結構中沿這邊去交換信息，這種relaxation稱為network DP。
2.在求和計算，離散直方圖計算，隨機梯度下降方法優化做實驗。
3.we propose simple algorithms on ring and complete topologies.?
1 Introduction
1.每個user保持自己的數據，并且和中心只分享結果。
問題：中心有瓶頸，當參與方很大的時候
LDP背景：each participant (user) does not trust anyone and assumes that an?adversary may observe everything that she/he shares。問題：utility great loss。Best possible error under LDP is a factor?√n?larger?than in the centralized model of DP
2.amplify methods：shuffling，subsampling，iteration。這些方法很難應用在聯邦/去中心化設置中: the former requires that the identity of the subsampled participants remain secret, while the?latter assumes that only the final model is revealed。
1.2 貢獻
1.提出的放松LDP只可以觀察臨近的數據。Network DP也可以解釋用戶之間碰撞。
2.對于不同任務，提出了simple algorithms，相比于LDP，隱私收益為O(1/√n) 。
3.環圖對于用戶共謀不夠robust，所以提出了完全圖（complete graph）。對于求和問題提出了算法，相比于LDP放大結果為
4.對于隨機梯度下降優化中，提出了decentralized SGD algorithm。在某些情況下，隱私放大為?nearly matching the utility of?centralized private SGD。
5.有趣的是，上述算法可以容忍恒定數量的碰撞，但代價是減少了隱私放大效果。
2.1 Network Differential Privacy
1.
?對于圖的差分隱私之間的關系是弱于本地差分隱私的，但是提供了更好的隱私保障。但是前者保護的是整個數據集的數據，所以說提供了更好的隱私保障。
?A是去中心算法，兩個D就是相鄰數據集。提出了一個滿足（epsilon ,delta）network DP。NetworkDP是被認為講操作O和算法A結合起來的一種分析，主要就是希望結合起來的隱私要比單獨的A要好（與DP比）。
In other words，applying Ov amplifies the privacy guarantees of A.
但是又考慮到用戶之間的勾結，根據定義1，假設一個一個upper bound上界c，代表用戶可能串通的數量。在這種setting下，希望保護聚集的信息Ov'
2.2 Decentralized Computation on a Walk
T 代表token；X是用戶u的局部損失函數在τ處的(隨機)梯度；
3 Walking on a Ring
3.1在有向環圖上的真實求和
邊E從第一個用戶u開始walk，范圍是u到n-1。Token從用戶1開始經過k次。背景：環是公開的。在LDP中，在發送數據給中心之前，需要給每一個single contribution添加隨機擾動（標準差standard deviation）。所以在這個求和問題中，也是考慮了一個抽象機制Perturb(x;?σ) 去添加噪聲（高斯機制或者拉普拉斯）Let?σloc?be the standard?deviation of the noise required so that Perturb(·;?σloc)?satisfifies?(ε, δ)-LDP。添加的噪聲的標準差是滿足?(ε, δ)-LDP的。標準差每n-1次添加一次。
?LDP的標準差是，因此算法1提供了O(1/√n)?reduction in error，就等同于O(1/√n)?gain in?ε。Algorithm 1 achieves the same privacy-utility trade-off as a?trusted?aggregator 。
注意：算法1假設用戶之間是不共謀的。
輸出的其實是對于真實值的一個分布，并不是真實數值。
假設用高斯噪聲，添加標準差為?
全部添加的噪聲為，這就和算法1有一樣的utility。
3.2 離散直方圖計算
并不是環直方圖，是用戶之間的關系可以看作是一個ring，本質上還是單值的頻數估計。
目標：計算
?在LDP中，classic的方法就是L-ary randomized response（Kairouz, P., Oh, S., and Viswanath, P. (2014). Extremal mechanisms for local differential privacy. In?NIPS.）用戶以概率為1-y提交真是值，y是均勻隨機值，使用RR(y)作為隨機擾動。初始化：token用足夠的隨機元素去隱藏第一個貢獻，包含著部分的直方圖，等價于shuffling。
為了簡單地表示，定理2依賴于(Amplifification by?Shufflfling: From Local to Central Differential Privacy via Anonymity.?)，它有一個簡單的封閉形式。
3.3 Discussion
局限：1.對于用戶共謀算法不夠強壯，在算法1假設是不共謀的。如果兩個用戶串通冰鞋share 他們的信息，算法就不滿足DP了。即使加了noise，也沒有保護了。當一個用戶在兩個共謀節點之間，他的隱私保障就會degrade。對于直方圖也有類似推理。
2.固定環拓撲不適合擴展到梯度下降，所以準備用iteration進行隱私放大。在這種放大方案中，對給定用戶（數據點）的隱私保證隨著其之后的梯度步數的增加而增加。因此，在固定環中，用戶u相對于另一個用戶v的隱私取決于它們在環中的相對位置(例如，當v在u之后時，不會有隱私放大)。這些限制促使我們考慮在一個完整圖（complete graph）上的隨機walk。
4 Walking on a Complete Graph
換句話說，在每一步中，token都被發送給在V中均勻隨機選擇的用戶。我們考慮固定長度的隨機行走T > 0，因此給定用戶貢獻的次數本身是隨機的。
4.1 真實求和
用戶u接受第k次的token并且用進行更新，與之前ring中的一樣，也是滿足LDP。在LDP下，對比了相同的算法，并且得到隱私放大是
求和任務本質：隨機選取用戶，通過擾動之后疊加。
which relies on?the intermediate aggregations of values between two visits of the token to a given?user?and?the secrecy of the path of the token.
?
我們fix了用戶v，并且量化了在token訪問的時候，用戶u有多少私人數據泄漏給用戶v。對v的訪問次數遵循二項式定律我們可以用Nv,以（無偏性：估計參數的期望為他的真實值）的概率bound住（采用切比雪夫）。在兩次訪問v之間，行走的步數遵循參數1-1/n的幾何定律。我們區分小于根號n/2的小循環和較大的循環。利用霍夫丁不等式，通過我們bound的了小循環的數量，而且對于每一個小循環的隱私損失最多為。對于較大的循環，the contribution of?u?is aggregated with at least?√?n/2?others,?leading to a privacy loss of at most√2ε/n1/4?. 因為循環對于用戶v是保密的，所以可以看作是在n-1個選擇中替換根號n/2個用戶用作下采樣（subsampling）。用采樣方法去bound隱私損失。
4.2離散直方圖計算?
4.3使用隨機梯度下降做優化 （不看）
5 Experiments
理論界限的比較。我們數值計算了定理3對于實求和任務(算法3)的理論邊界，并將其與局部DP進行了比較。回想一下，用戶貢獻的數量是隨機的(期望值為T /n)。因此，為了提供網絡DP和本地DP之間的公平比較，我們推導了一個類似定理3的本地DP，我們使用相同的Chernoff界來控制用戶貢獻的數量，并使用高級合成來衡量總的隱私損失。此外，為了隔離貢獻數量的影響(這在網絡DP和本地DP中是相同的)，我們還報告了在假設每個用戶貢獻固定次數T /n下得到的邊界。圖1a繪制了變化n的邊界的值。我們看到，當n > 100時，我們的理論結果提供了與局部DP相比的增益，并且這些增益隨著n的增加變得越來越顯著。我們注意到，在每個用戶貢獻的固定數量下獲得的曲線也表明，在邊界內更好地控制Nv可以使我們的放大結果明顯更緊湊。?
經驗行為的差距。我們的形式分析包括控制用戶貢獻的數量，以及使用集中不等式控制周期的大小，這導致了一些近似。然而，在實際部署中，可以使用這些數量的實際值來計算隱私損失。因此，我們研究了我們的理論隱私保障和通過運行隨機walk的模擬可以在實踐中獲得的差距。具體來說，我們對大小為T = 100n的隨機walk進行采樣。然后，對每一對用戶，根據實際行走的特點和高級組合機制計算隱私損失。我們在10次隨機漫步中重復這個實驗，然后我們可以報告在所有用戶對和所有隨機運行中觀察到的平均、最好和最壞的隱私損失。圖1b報告了基于高斯機制的真實求和情況下的經驗結果，其中隱私以因子√m增長，其中m為元素聚集在一起的數量(即，我們觀察到，網絡DP實現的增益在實踐中明顯強于我們的理論邊界保證(見圖1a)。特別是，即使對于較小的n，增益也是顯著的。這些結果再次表明，在我們的分析中還有改進的空間，例如訴諸于更好的集中界限。
我們對離散直方圖計算進行了類似的實驗，這些實驗證實，通過去中心化來擴大隱私的經驗收益對于這項任務也很重要，參見附錄F。
總結
以上是生活随笔為你收集整理的Privacy Amplification by Decentralization的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ERP系统介绍
- 下一篇： Privacy Definitions