論文の概要: Count on Your Elders: Laplace vs Gaussian Noise

• arxiv url: http://arxiv.org/abs/2408.07021v3
• Date: Mon, 18 Nov 2024 15:40:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-19 14:26:02.940477
• Title: Count on Your Elders: Laplace vs Gaussian Noise
• Title（参考訳）: 高齢者のカウント:ラプラス対ガウスノイズ
• Authors: Joel Daniel Andersson, Rasmus Pagh, Teresa Anna Steiner, Sahel Torkamani,
• Abstract要約: 多くの環境では、ラプラスノイズはガウスノイズよりも好まれるかもしれないと我々は主張する。 ガウス機構によって付加される雑音は、常に同値な分散のラプラスノイズに置き換えることができることを示す。 これはガウスノイズが高次元雑音に使用されるという従来の知恵に挑戦する。
• 参考スコア（独自算出の注目度）: 9.546521474972485
• 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. 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 for $(\varepsilon,\delta)$-differential privacy when $\delta$ is small. 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 whenever $\delta$ is sufficiently small it improves the mean squared error over the best possible $(\varepsilon,\delta)$-differentially private factorization mechanisms based on Gaussian noise. 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)$-differential 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. Finally, we study whether counting under continual observation may be easier in an average-case sense. We show that, under pure differential privacy, the expected worst-case error for a random input must be $\Omega(\log(T)/\varepsilon)$, matching the known lower bound for worst-case inputs.
• Abstract（参考訳）: 近年、ガウスノイズは微分プライベートアルゴリズムにおいて一般的な道具となり、初期の文献を支配したラプラスノイズに取って代わることが多い。 ガウスノイズは、$\textit{approximate}$差分プライバシーの標準的なアプローチであり、多くの場合、従来の(純粋な)差分プライバシーメカニズムよりもはるかに高い実用性をもたらす。 本稿では,特に$(\varepsilon,\delta)$-differential privacy if $\delta$ is small。 まず、連続観察下でのカウントの問題について考察し、プライバシーと精度のトレードオフを改善するために$\textit{ negative digits}$で$k$-ary数システムを使用するバイナリツリー機構の新たな一般化を提案する。 我々のメカニズムはLaplaceノイズを使用し、$\delta$が十分小さいときは常に、ガウスノイズに基づく$(\varepsilon,\delta)$-差分分解機構よりも平均2乗誤差を改善する。 具体的には、$k=19$ を用いて、$\delta = O(T^{-0.92})$ のとき、ヘンジンガー、ウパディー、そして Upadhyay (SODA 2023) によって与えられる境界に対する漸近的な改善が得られる。 第二に、ガウス機構によって加えられたノイズは、常に同じ$(\epsilon, \delta)$-differential privacy guaranteeに対して同等の分散のLaplaceノイズに置き換えることができる。 これはガウス雑音が高次元雑音に使用されるという従来の知恵に挑戦する。 最後に, 連続観測下でのカウントが, 平均的なケースで容易に行えるかを検討した。 純粋な差分プライバシーの下では、ランダムな入力の最悪のエラーは$\Omega(\log(T)/\varepsilon)$でなければならない。

関連論文リスト

• Better Gaussian Mechanism using Correlated Noise [1.450405446885067]
  分散を$(sqrtd + 1)/4$にスケールしたガウス変数として分布するランダム変数を追加することで、独立雑音サンプルの分散を$(d + sqrtd)/4$でのみスケールできることを示す。 私たちのメカニズムの中心的な考え方はシンプルで、そのテクニックは柔軟です。
  論文  参考訳（メタデータ） (2024-08-13T12:31:03Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  プライベート平均推定に対する古典的なアプローチは、真の平均を計算し、バイアスのないがおそらく相関のあるガウスノイズを加えることである。 すべての入力データセットに対して、集中的な差分プライバシーを満たす非バイアス平均推定器が、少なくとも多くのエラーをもたらすことを示す。
  論文  参考訳（メタデータ） (2023-01-31T18:47:42Z)
• Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
  個人的連続和問題(対数問題)について検討する。 並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
  論文  参考訳（メタデータ） (2023-01-29T20:42:54Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Differential privacy for symmetric log-concave mechanisms [0.0]
  データベースクエリ結果にランダムノイズを加えることは、プライバシを達成するための重要なツールである。 我々は、すべての対称および対数凹形ノイズ密度に対して、$(epsilon, delta)$-differential privacyに対して十分かつ必要な条件を提供する。
  論文  参考訳（メタデータ） (2022-02-23T10:20:29Z)
• Infinitely Divisible Noise in the Low Privacy Regime [9.39772079241093]
  ユーザ間でデータを分散し、共有しないフェデレーション学習は、プライバシ保護機械学習に対する一般的なアプローチとして現れている。 実数値データに対して、最初の可除な無限ノイズ分布を提示し、$varepsilon$-differential privacyを実現する。
  論文  参考訳（メタデータ） (2021-10-13T08:16:43Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。