論文の概要: Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling
- arxiv url: http://arxiv.org/abs/2012.12803v2
- Date: Fri, 25 Dec 2020 06:55:45 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-25 18:15:57.151503
- Title: Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling
- Title（参考訳）: クローンの中に座る:シャッフルによるプライバシーの増幅をシンプルかつほぼ最適に分析する
- Authors: Vitaly Feldman, Audra McMillan, Kunal Talwar
- Abstract要約: ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
- 参考スコア（独自算出の注目度）: 49.43288037509783
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent work of Erlingsson, Feldman, Mironov, Raghunathan, Talwar, and
Thakurta [EFMRTT19] demonstrates that random shuffling amplifies differential
privacy guarantees of locally randomized data. Such amplification implies
substantially stronger privacy guarantees for systems in which data is
contributed anonymously [BEMMRLRKTS17] and has lead to significant interest in
the shuffle model of privacy [CSUZZ19,EFMRTT19].
We show that random shuffling of $n$ data records that are input to
$\varepsilon_0$-differentially private local randomizers results in an
$(O((1-e^{-\varepsilon_0})\sqrt{\frac{e^{\varepsilon_0}\log(1/\delta)}{n}}),
\delta)$-differentially private algorithm. This significantly improves over
previous work and achieves the asymptotically optimal dependence in
$\varepsilon_0$. Our result is based on a new approach that is simpler than
previous work and extends to approximate differential privacy with nearly the
same guarantees. Our work also yields an empirical method to derive tighter
bounds the resulting $\varepsilon$ and we show that it gets to within a small
constant factor of the optimal bound. As a direct corollary of our analysis, we
derive a simple and asymptotically optimal algorithm for discrete distribution
estimation in the shuffle model of privacy. We also observe that our result
implies the first asymptotically optimal privacy analysis of noisy stochastic
gradient descent that applies to sampling without replacement.
- Abstract（参考訳）: Erlingsson, Feldman, Mironov, Raghunathan, Talwar, Thakurta[EFMRTT19]の最近の研究は、ランダムシャッフルが局所的にランダム化されたデータの差分プライバシー保証を増幅することを示した。
このような増幅は、データが匿名で寄付されるシステム(bemmrlrkts17])のプライバシー保証が大幅に強化され、シャッフルプライバシモデル(csuzz19,efmrtt19)に大きな関心を寄せている。
我々は、$\varepsilon_0$-differentially private local randomizersに入力された$n$のデータレコードをランダムにシャッフルすると、$(O((1-e^{-\varepsilon_0})\sqrt{\frac{e^{\varepsilon_0}\log(1/\delta)}{n}}),$-differentially private algorithmが生成されることを示す。
これは以前の作業よりも大幅に改善され、$\varepsilon_0$の漸近的最適依存を達成する。
我々の結果は、従来の作業よりもシンプルで、ほぼ同じ保証で近似的な差分プライバシーにまで拡張された新しいアプローチに基づいている。
我々の研究はまた、得られる$\varepsilon$ のより厳密な境界を導出する経験的方法を与え、それが最適境界の小さな定数係数の範囲内になることを示す。
分析の直接系として,プライバシのシャッフルモデルにおける離散分布推定のための単純かつ漸近的最適アルゴリズムを導出する。
また,この結果から,非置換サンプリングに適用できる雑音の確率的勾配降下の非漸近的最適プライバシー解析が示唆された。
関連論文リスト
- A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility [4.7712438974100255]
パーソナライズされたプライバシパラメータで$(epsilon_i,delta_i)$-PLDP設定をシャッフルする方法を示す。
shuffled $(epsilon_i,delta_i)$-PLDP process approximately saves $mu$-Gaussian Differential Privacy with mu = sqrtfrac2sum_i=1n frac1-delta_i1+eepsilon_i-max_ifrac1-delta_i1+e
論文 参考訳（メタデータ） (2023-12-22T02:31:46Z) - Smooth Anonymity for Sparse Graphs [69.1048938123063]
しかし、スパースデータセットを共有するという点では、差分プライバシーがプライバシのゴールドスタンダードとして浮上している。
本研究では、スムーズな$k$匿名性(スムーズな$k$匿名性)と、スムーズな$k$匿名性(スムーズな$k$匿名性)を提供する単純な大規模アルゴリズムを設計する。
論文 参考訳（メタデータ） (2022-07-13T17:09:25Z) - Normalized/Clipped SGD with Perturbation for Differentially Private
Non-Convex Optimization [94.06564567766475]
DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。
DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
論文 参考訳（メタデータ） (2022-06-27T03:45:02Z) - Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
DP-SGDで訓練されたモデルをリリースする際の個々の事例に対するプライバシー保証を特徴付ける。
ほとんどの例では、最悪のケースよりも強力なプライバシー保証を享受しています。
これは、モデルユーティリティの観点からは守られないグループが同時に、より弱いプライバシー保証を経験することを意味する。
論文 参考訳（メタデータ） (2022-06-06T13:49:37Z) - Optimal Algorithms for Mean Estimation under Local Differential Privacy [55.32262879188817]
そこで本研究では,PrivUnitが局所的プライベートな乱数化器群間の最適分散を実現することを示す。
また,ガウス分布に基づくPrivUnitの新たな変種も開発しており,数学的解析に適しており,同じ最適性保証を享受できる。
論文 参考訳（メタデータ） (2022-05-05T06:43:46Z) - Differentially Private Learning Needs Hidden State (Or Much Faster
Convergence) [9.429448411561541]
差分的にプライベートな学習は、厳密な拘束力を持って、隠れた状態のプライバシ分析や、高速な収束を必要とすることを示す。
私たちの収束するプライバシー分析は、差異のあるプライベートな学習が、厳密な拘束力を持って、隠れた状態のプライバシ分析や、高速な収束を必要とすることを示している。
論文 参考訳（メタデータ） (2022-03-10T13:31:08Z) - Uniformity Testing in the Shuffle Model: Simpler, Better, Faster [0.0]
均一性テスト(英: Uniformity testing)または独立した観察が均一に分散されているかどうかをテストすることは、分散テストにおける問題である。
本研究では,シャッフルモデルにおける既知の一様性試験アルゴリズムの解析を大幅に単純化する。
論文 参考訳（メタデータ） (2021-08-20T03:43:12Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - BUDS: Balancing Utility and Differential Privacy by Shuffling [3.618133010429131]
シャッフルやtextitBUDS によるユーティリティと差分プライバシーのバランスをとることは、クラウドソースの統計データベースへのアプローチである。
損失推定法とリスク最小化法を併用したワンホット符号化と反復シャッフル法により,新しいアルゴリズムを提案する。
バランスのとれたユーティリティとプライバシの実証テストの間、BUDSは$epsilon = 0.02$を生成します。
論文 参考訳（メタデータ） (2020-06-07T11:39:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。