論文の概要: The Correlated Gaussian Sparse Histogram Mechanism
- arxiv url: http://arxiv.org/abs/2412.10357v1
- Date: Fri, 13 Dec 2024 18:51:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-16 15:03:08.873994
- Title: The Correlated Gaussian Sparse Histogram Mechanism
- Title（参考訳）: ガウススパースヒストグラムの関連性
- Authors: Christian Janos Lebeda, Lukas Retschmeier,
- Abstract要約: スパースヒストグラムを$(varepsilon, delta)$-differential privacy でリリースする問題について考察する。
我々はLebedaの手法を採用し、非ゼロ数に相関ノイズを加えることで、空間境界を持つ場合にのみノイズの大きさを小さくできることを示す。
- 参考スコア（独自算出の注目度）: 1.2277343096128712
- License:
- Abstract: We consider the problem of releasing a sparse histogram under $(\varepsilon, \delta)$-differential privacy. The stability histogram independently adds noise from a Laplace or Gaussian distribution to the non-zero entries and removes those noisy counts below a threshold. Thereby, the introduction of new non-zero values between neighboring histograms is only revealed with probability at most $\delta$, and typically, the value of the threshold dominates the error of the mechanism. We consider the variant of the stability histogram with Gaussian noise. Recent works ([Joseph and Yu, COLT '24] and [Lebeda, SOSA '25]) reduced the error for private histograms using correlated Gaussian noise. However, these techniques can not be directly applied in the very sparse setting. Instead, we adopt Lebeda's technique and show that adding correlated noise to the non-zero counts only allows us to reduce the magnitude of noise when we have a sparsity bound. This, in turn, allows us to use a lower threshold by up to a factor of $1/2$ compared to the non-correlated noise mechanism. We then extend our mechanism to a setting without a known bound on sparsity. Additionally, we show that correlated noise can give a similar improvement for the more practical discrete Gaussian mechanism.
- Abstract（参考訳）: スパースヒストグラムを$(\varepsilon, \delta)$-differential privacyの下でリリースする問題を考える。
安定性ヒストグラムは独立に非零成分にラプラス分布やガウス分布からノイズを加え、閾値以下のノイズ数を取り除く。
これにより、隣り合うヒストグラム間の新しいゼロでない値の導入は、最大$\delta$の確率でのみ明らかとなり、通常、閾値の値はメカニズムの誤差を支配する。
ガウス雑音による安定性ヒストグラムの変種を考察する。
最近の研究 (Joseph and Yu, COLT '24] と (Lebeda, SOSA '25]) は, 相関ガウス雑音を用いた私的ヒストグラムの誤差を低減した。
しかし、これらのテクニックは、非常にスパースな設定では直接適用できない。
代わりに、Lebedaの手法を採用し、非ゼロ数に相関ノイズを加えることで、空間境界を持つときのみノイズの大きさを小さくできることを示す。
これにより、非相関ノイズ機構と比較して最大1/2ドル以下の閾値を使用できる。
次に、スパーシリティに縛られることなく、我々のメカニズムを設定に拡張する。
さらに、相関雑音はより実用的な離散ガウス機構に類似した改善をもたらすことを示した。
関連論文リスト
- Count on Your Elders: Laplace vs Gaussian Noise [9.546521474972485]
多くの環境では、ラプラスノイズはガウスノイズよりも好まれるかもしれないと我々は主張する。
ガウス機構によって付加される雑音は、常に同値な分散のラプラスノイズに置き換えることができることを示す。
これはガウスノイズが高次元雑音に使用されるという従来の知恵に挑戦する。
論文 参考訳（メタデータ） (2024-08-13T16:36:33Z) - Better Gaussian Mechanism using Correlated Noise [1.450405446885067]
分散を$(sqrtd + 1)/4$にスケールしたガウス変数として分布するランダム変数を追加することで、独立雑音サンプルの分散を$(d + sqrtd)/4$でのみスケールできることを示す。
私たちのメカニズムの中心的な考え方はシンプルで、そのテクニックは柔軟です。
論文 参考訳（メタデータ） (2024-08-13T12:31:03Z) - Revisiting Convergence of AdaGrad with Relaxed Assumptions [4.189643331553922]
問題に対する AdaGrad の収束と運動量(特別の場合として AdaGrad をカバー)を再考する。
このモデルは、多くの実用的な応用において、サブソースを含む広い範囲のノイズを含む。
論文 参考訳（メタデータ） (2024-02-21T13:24:14Z) - 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) - Anonymized Histograms in Intermediate Privacy Models [54.32252900997422]
我々は,シャッフルDPおよびパンプライベートモデルにおいて,$tildeO_varepsilon(sqrtn)$とほぼ一致する誤差を保証するアルゴリズムを提案する。
我々のアルゴリズムは非常に単純で、離散的なラプラスノイズヒストグラムを後処理するだけである。
論文 参考訳（メタデータ） (2022-10-27T05:11:00Z) - Differential privacy for symmetric log-concave mechanisms [0.0]
データベースクエリ結果にランダムノイズを加えることは、プライバシを達成するための重要なツールである。
我々は、すべての対称および対数凹形ノイズ密度に対して、$(epsilon, delta)$-differential privacyに対して十分かつ必要な条件を提供する。
論文 参考訳（メタデータ） (2022-02-23T10:20:29Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Fast Dimension Independent Private AdaGrad on Publicly Estimated
Subspaces [24.52697154861819]
AdaGradは、従来のAdaGradに匹敵する後悔と、ノイズによるよく制御された用語を達成していることを示す。
我々は制約付きおよび制約なしの最小化において一般凸関数で操作する。
論文 参考訳（メタデータ） (2020-08-14T20:46:38Z) - Shape Matters: Understanding the Implicit Bias of the Noise Covariance [76.54300276636982]
勾配降下のノイズはパラメータ化モデルに対するトレーニングにおいて重要な暗黙の正則化効果をもたらす。
ミニバッチやラベルの摂動によって引き起こされるパラメータ依存ノイズはガウスノイズよりもはるかに効果的であることを示す。
分析の結果,パラメータ依存ノイズは局所最小値に偏りを生じさせるが,球状ガウス雑音は生じないことがわかった。
論文 参考訳（メタデータ） (2020-06-15T18:31:02Z) - Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles [65.9694455739978]
特徴不確実性の下での文脈線形帯域問題について検討する。
本分析により, 最適仮説は, 雑音特性に応じて, 基礎となる実現可能性関数から著しく逸脱しうることが明らかとなった。
これは、古典的アプローチが非自明な後悔境界を保証できないことを意味する。
論文 参考訳（メタデータ） (2017-03-03T21:39:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。