論文の概要: Count on Your Elders: Laplace vs Gaussian Noise
- arxiv url: http://arxiv.org/abs/2408.07021v2
- Date: Tue, 24 Sep 2024 13:15:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-09-26 02:42:23.993043
- Title: Count on Your Elders: Laplace vs Gaussian Noise
- Title(参考訳): 高齢者のカウント:ラプラス対ガウスノイズ
- Authors: Joel Daniel Andersson, Rasmus Pagh, Sahel Torkamani,
- Abstract要約: 多くの環境では、ラプラスノイズはガウスノイズよりも好まれるかもしれないと我々は主張する。
ガウス機構によって付加される雑音は、常に同値な分散のラプラスノイズに置き換えることができることを示す。
- 参考スコア(独自算出の注目度): 10.428888893980739
- License:
- Abstract: In recent years, Gaussian noise has become a popular tool in differentially private algorithms, often replacing Laplace noise which dominated the early literature on differential privacy. Gaussian noise is the standard approach to $\textit{approximate}$ differential privacy, often resulting in much higher utility than traditional (pure) differential privacy mechanisms. In this paper we argue that Laplace noise may in fact be preferable to Gaussian noise in many settings, in particular when we seek to achieve $(\varepsilon,\delta)$-differential privacy for small values of $\delta$. We consider two scenarios: First, we consider the problem of counting under continual observation and present a new generalization of the binary tree mechanism that uses a $k$-ary number system with $\textit{negative digits}$ to improve the privacy-accuracy trade-off. Our mechanism uses Laplace noise and improves the mean squared error over all ``optimal'' $(\varepsilon,\delta)$-differentially private factorization mechanisms based on Gaussian noise whenever $\delta$ is sufficiently small. Specifically, using $k=19$ we get an asymptotic improvement over the bound given in the work by Henzinger, Upadhyay and Upadhyay (SODA 2023) when $\delta = O(T^{-0.92})$. Second, we show that the noise added by the Gaussian mechanism can always be replaced by Laplace noise of comparable variance for the same $(\epsilon, \delta)$ privacy guarantee, and in fact for sufficiently small $\delta$ the variance of the Laplace noise becomes strictly better. This challenges the conventional wisdom that Gaussian noise should be used for high-dimensional noise.
- Abstract(参考訳): 近年、ガウスノイズは、微分プライバシに関する初期の文献を支配したラプラスノイズに置き換わって、微分プライベートアルゴリズムにおいて人気のあるツールとなっている。
ガウスノイズは、$\textit{approximate}$差分プライバシーの標準的なアプローチであり、多くの場合、従来の(純粋な)差分プライバシーメカニズムよりもはるかに高い実用性をもたらす。
この論文では、ラプラスノイズはガウスノイズよりも多くの設定で好まれる可能性があり、特に$(\varepsilon,\delta)$-differential privacy for small values of $\delta$を達成しようとする場合について論じる。
まず、連続観察下でのカウントの問題について考察し、プライバシーと精度のトレードオフを改善するために$\textit{ negative digits}$で$k$-ary数システムを使用するバイナリツリー機構の新たな一般化を提案する。
我々のメカニズムはLaplaceノイズを使用し、すべての ``optimal'' $(\varepsilon,\delta)$-differentially private factorization mechanism に対して平均2乗誤差を改善する。
具体的には、$k=19$ を用いて、$\delta = O(T^{-0.92})$ のとき、ヘンジンガー、ウパディー、そして Upadhyay (SODA 2023) によって与えられる境界に対する漸近的な改善が得られる。
第二に、ガウス機構によって付加されるノイズは、常に同じ$(\epsilon, \delta)$プライバシー保証に対して同等の分散のLaplaceノイズに置き換えることができる。
これはガウスノイズが高次元雑音に使用されるという従来の知恵に挑戦する。
関連論文リスト
- On Computing Pairwise Statistics with Local Differential Privacy [55.81991984375959]
例えば$binomn2-1 sum_i ne j f(x_i, x_j)$, $x_i$ は$i$thユーザへの入力を表し、ローカルモデルでは差分プライバシ(DP)である。
この定式化は、Kendallの$tau$ coefficient、Area Under Curve、Giniの平均差、Giniのエントロピーなどの重要なメトリクスをキャプチャする。
論文 参考訳(メタデータ) (2024-06-24T04:06:09Z) - Continual Counting with Gradual Privacy Expiration [15.87191465142231]
提案アルゴリズムは,大規模なプライバシー有効期限関数に対して,O(log(T)/epsilon)$の加算誤差を実現する。
我々の経験的評価は、自然ベースラインアルゴリズムよりも大きな値の$d$に対する経験的プライバシ損失が著しく小さく、徐々に増加するプライバシー損失を達成していることを示している。
論文 参考訳(メタデータ) (2024-06-06T07:20:16Z) - Profile Reconstruction from Private Sketches [13.929335175122265]
$mathcalD$から$n$のアイテムの多重集合が与えられたとき、強調される再構成問題は、$t = 0, 1, dots, n$ に対して、$mathcalD$ のアイテムの分数 $vecf[t]$ を正確に $tfty 倍と見積もることである。
分散空間制約付き環境での個人プロファイル推定について検討し,マルチセットの更新可能なプライベートスケッチを維持したいと考える。
LPベースの手法の高速化方法を示します
論文 参考訳(メタデータ) (2024-06-03T09:51:28Z) - Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation [56.403488578703865]
我々は$ell$ Sensitivities を $ell$ Sensitivities で拡張することにより、最適な線形 $tilde O(varepsilon-2mu2 d)$ サンプリング複雑性のより良い境界が得られることを示した。
また、ロジスティック回帰のために、$tilde O(varepsilon-2mu2 d)$ sensitivity sample bound を得る。
論文 参考訳(メタデータ) (2024-06-01T07:03:40Z) - Scaling Up Differentially Private LASSO Regularized Logistic Regression
via Faster Frank-Wolfe Iterations [51.14495595270775]
我々は,Frank-Wolfeアルゴリズムを$L_1$のペナル化線形回帰に適応させ,スパース入力を認識し,有効利用する。
この方法では,プライバシパラメータ$epsilon$の値とデータセットの分散度に応じて,最大2,200times$の係数でランタイムを削減できることを示す。
論文 参考訳(メタデータ) (2023-10-30T19:52:43Z) - Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。
第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
論文 参考訳(メタデータ) (2021-07-31T22:23:39Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳(メタデータ) (2021-03-02T06:53:44Z) - On Avoiding the Union Bound When Answering Multiple Differentially
Private Queries [49.453751858361265]
このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。
一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
論文 参考訳(メタデータ) (2020-12-16T17:58:45Z) - A bounded-noise mechanism for differential privacy [3.9596068699962323]
ベクトル $vecx(i) の平均 $frac1nsum_i=1n vecx(i)$ を [0,1]k$ で出力し、任意の $vecx(i)$ に対してプライバシーを保持します。
我々は、ほとんどの値$delta$に対して最適な$ell_infty$エラーを持つ$(epsilon,delta)$-privateメカニズムを示す。
論文 参考訳(メタデータ) (2020-12-07T16:03:21Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳(メタデータ) (2020-09-21T04:13:34Z) - Differentially private $k$-means clustering via exponential mechanism
and max cover [6.736814259597673]
我々は、$k$-meansクラスタリング問題に対して、新しい$(epsilon_p, delta_p)$-differentially privateアルゴリズムを導入する。
論文 参考訳(メタデータ) (2020-09-02T17:52:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。