論文の概要: Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch
- arxiv url: http://arxiv.org/abs/2301.02457v2
- Date: Tue, 18 Mar 2025 14:02:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-19 14:11:15.032858
- Title: Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch
- Title（参考訳）: Misra-Griesスケッチによるより優れた個人的近似ヒストグラムと重ヒッタ
- Authors: Christian Janos Lebeda, Jakub Tětek,
- Abstract要約: 我々は、Misra-Griesスケッチを$(varepsilon,delta)$-differential privacyの下でリリースするためのより良いメカニズムを示す。
スケッチのサイズに依存しない大きさのノイズを追加する。
この新たなスケッチにノイズを加えるだけでは十分であり、非ストリーミング設定の2倍にも満たない。
- 参考スコア（独自算出の注目度）: 1.2277343096128712
- License:
- Abstract: We consider the problem of computing differentially private approximate histograms and heavy hitters in a stream of elements. In the non-private setting, this is often done using the sketch of Misra and Gries [Science of Computer Programming, 1982]. Chan, Li, Shi, and Xu [PETS 2012] describe a differentially private version of the Misra-Gries sketch, but the amount of noise it adds can be large and scales linearly with the size of the sketch; the more accurate the sketch is, the more noise this approach has to add. We present a better mechanism for releasing a Misra-Gries sketch under $(\varepsilon,\delta)$-differential privacy. It adds noise with magnitude independent of the size of the sketch; in fact, the maximum error coming from the noise is the same as the best known in the private non-streaming setting, up to a constant factor. Our mechanism is simple and likely to be practical. We also give a simple post-processing step of the Misra-Gries sketch that does not increase the worst-case error guarantee. It is sufficient to add noise to this new sketch with less than twice the magnitude of the non-streaming setting. This improves on the previous result for $\varepsilon$-differential privacy where the noise scales linearly to the size of the sketch. Finally, we consider a general setting where users can contribute multiple distinct elements. We present a new sketch with maximum error matching the Misra-Gries sketch. For many parameters in this setting our sketch can be released with less noise under $(\varepsilon, \delta)$-differential privacy.
- Abstract（参考訳）: 我々は、要素列内の偏微分プライベートなヒストグラムと重いヒッタの計算問題を考察する。
プライベートでない環境では、これはしばしばMisraとGriesのスケッチ(Science of Computer Programming, 1982)を使って行われます。
Chan, Li, Shi, and Xu (PETS 2012)は、Misra-Griesスケッチの微分プライベートバージョンを記述しているが、ノイズの量が大きくなり、スケッチのサイズと線形にスケールできる。
私たちは、Misra-Griesのスケッチを$(\varepsilon,\delta)$-differential privacyの下でリリースするためのより良いメカニズムを示します。
実際、ノイズから発生する最大のエラーは、プライベートな非ストリーミング設定でよく知られたものと同じであり、一定の要素までもたらされる。
我々の仕組みは単純で実用的である可能性が高い。
Misra-Griesスケッチの単純な後処理ステップも提供します。
この新たなスケッチにノイズを加えるだけでは十分であり、非ストリーミング設定の2倍にも満たない。
これにより、以前の結果を$\varepsilon$-differential privacyで改善し、ノイズはスケッチのサイズに線形にスケールする。
最後に、ユーザが複数の異なる要素をコントリビュートできる一般的な設定について考察する。
我々はMisra-Griesのスケッチと一致する最大誤差を持つ新しいスケッチを提案する。
この設定の多くのパラメータに対して、スケッチは$(\varepsilon, \delta)$-differential privacyの下でより少ないノイズでリリースできます。
関連論文リスト
- The Correlated Gaussian Sparse Histogram Mechanism [1.2277343096128712]
スパースヒストグラムを$(varepsilon, delta)$-differential privacy でリリースする問題について考察する。
我々はLebedaの手法を採用し、非ゼロ数に相関ノイズを加えることで、空間境界を持つ場合にのみノイズの大きさを小さくできることを示す。
論文 参考訳（メタデータ） (2024-12-13T18:51:33Z) - Count on Your Elders: Laplace vs Gaussian Noise [9.546521474972485]
多くの環境では、ラプラスノイズはガウスノイズよりも好まれるかもしれないと我々は主張する。
ガウス機構によって付加される雑音は、常に同値な分散のラプラスノイズに置き換えることができることを示す。
これはガウスノイズが高次元雑音に使用されるという従来の知恵に挑戦する。
論文 参考訳（メタデータ） (2024-08-13T16:36:33Z) - Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。
純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。
本稿では,総和,数,投票の単純な統計量について両問題を解く。
論文 参考訳（メタデータ） (2023-09-27T17:09:36Z) - SketchXAI: A First Look at Explainability for Human Sketches [104.13322289903577]
本稿では,XAI(Explainable Artificial Intelligence)の風景に人間のスケッチを紹介する。
我々は、スケッチは人間中心のデータ形式であり、説明可能性を研究するための自然なインターフェースであると主張している。
我々は,ストロークの本質的な特性(形状,位置,順序)に対応するスケッチエンコーダを設計する。
論文 参考訳（メタデータ） (2023-04-23T20:28:38Z) - Picture that Sketch: Photorealistic Image Generation from Abstract
Sketches [109.69076457732632]
この論文は、あなたや私のような訓練を受けていないアマチュアの抽象的で変形した普通のスケッチから、それをフォトリアリスティックなイメージに変えます。
まず、エッジマップのようなスケッチを指示するのではなく、抽象的なフリーハンドな人間のスケッチで作業することを目指しています。
そうすることで、スケッチから写真までのパイプラインを民主化し、スケッチがどれだけよいかに関わらず、スケッチを"写真化"します。
論文 参考訳（メタデータ） (2023-03-20T14:49:03Z) - Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
個人的連続和問題(対数問題)について検討する。
並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
論文 参考訳（メタデータ） (2023-01-29T20:42:54Z) - Pre-trained Perceptual Features Improve Differentially Private Image
Generation [8.659595986100738]
差分降下勾配(DP-SGD)を用いた中等度生成モデルの訓練も困難である。
私たちは、情報のある公開データセット上に適切な、関連する表現を構築し、その表現でプライベートデータをモデル化することを学びます。
私たちの研究は、プライベートと非プライベートの深層生成モデルの間のギャップを減らすための、シンプルで強力な基盤を導入しています。
論文 参考訳（メタデータ） (2022-05-25T16:46:01Z) - Differential privacy for symmetric log-concave mechanisms [0.0]
データベースクエリ結果にランダムノイズを加えることは、プライバシを達成するための重要なツールである。
我々は、すべての対称および対数凹形ノイズ密度に対して、$(epsilon, delta)$-differential privacyに対して十分かつ必要な条件を提供する。
論文 参考訳（メタデータ） (2022-02-23T10:20:29Z) - Learning-Augmented Sketches for Hessians [54.97773807211337]
第二次手法の文脈でヘッセンの学習スケッチを設計する方法を紹介します。
学習したスケッチは,「学習されていない」スケッチと比較して,重要な問題に対する近似精度が向上することを示す。
論文 参考訳（メタデータ） (2021-02-24T14:50:59Z) - A One-Pass Private Sketch for Most Machine Learning Tasks [48.17461258268463]
差別化プライバシ(DP)は、正式な証明可能な保証を通じて、プライバシとユーティリティのトレードオフを説明する魅力的なプライバシ定義である。
本稿では,回帰,分類,密度推定など,多数の機械学習タスクをサポートするプライベートスケッチを提案する。
このスケッチは,局所性に敏感なハッシュをインデックス化して,効率的なワンパスアルゴリズムで構築したランダムな一致テーブルで構成されている。
論文 参考訳（メタデータ） (2020-06-16T17:47:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。