論文の概要: Anonymized Histograms in Intermediate Privacy Models

• arxiv url: http://arxiv.org/abs/2210.15178v1
• Date: Thu, 27 Oct 2022 05:11:00 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-28 16:08:05.548545
• Title: Anonymized Histograms in Intermediate Privacy Models
• Title（参考訳）: 中間プライバシーモデルにおける匿名ヒストグラム
• Authors: Badih Ghazi and Pritish Kamath and Ravi Kumar and Pasin Manurangsi
• Abstract要約: 我々は,シャッフルDPおよびパンプライベートモデルにおいて,$tildeO_varepsilon(sqrtn)$とほぼ一致する誤差を保証するアルゴリズムを提案する。 我々のアルゴリズムは非常に単純で、離散的なラプラスノイズヒストグラムを後処理するだけである。
• 参考スコア（独自算出の注目度）: 54.32252900997422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of privately computing the anonymized histogram (a.k.a. unattributed histogram), which is defined as the histogram without item labels. Previous works have provided algorithms with $\ell_1$- and $\ell_2^2$-errors of $O_\varepsilon(\sqrt{n})$ in the central model of differential privacy (DP). In this work, we provide an algorithm with a nearly matching error guarantee of $\tilde{O}_\varepsilon(\sqrt{n})$ in the shuffle DP and pan-private models. Our algorithm is very simple: it just post-processes the discrete Laplace-noised histogram! Using this algorithm as a subroutine, we show applications in privately estimating symmetric properties of distributions such as entropy, support coverage, and support size.
• Abstract（参考訳）: 項目ラベルのないヒストグラムとして定義される匿名ヒストグラム(別名、非分散ヒストグラム)をプライベートに計算する問題について検討する。 以前は$\ell_1$-と$\ell_2^2$-errors of $O_\varepsilon(\sqrt{n})$というアルゴリズムを差分プライバシー(DP)の中心モデルで提供していた。 本研究では,シャッフルDPモデルとパンプライベートモデルにおいて,ほぼ一致した誤差保証を$\tilde{O}_\varepsilon(\sqrt{n})$とするアルゴリズムを提案する。 アルゴリズムは非常に単純で、離散ラプラスのヒストグラムを後処理するだけです! このアルゴリズムをサブルーチンとして使用し,エントロピーやサポートカバレッジ,サポートサイズといった分布の対称特性をプライベートに推定するアプリケーションを示す。

関連論文リスト

• 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)
• Transfer Learning for Latent Variable Network Models [18.31057192626801]
  潜在変数ネットワークモデルにおける推定のための伝達学習について検討する。 潜伏変数が共有されている場合、エラーの消滅が可能であることを示す。 我々のアルゴリズムは、$o(1)$エラーを達成し、ソースやターゲットネットワーク上でパラメトリック形式を仮定しない。
  論文  参考訳（メタデータ） (2024-06-05T16:33:30Z)
• Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model [38.66115499136791]
  局所微分プライバシー(LDP)モデルにおける疎線形回帰の問題を再考する。 そこで本研究では,この問題の第一種である革新的NLDPアルゴリズムを提案する。 その結果, 疎線形回帰問題における非私的ケース, 中央DPモデル, 局所DPモデルとの基本的差異が明らかとなった。
  論文  参考訳（メタデータ） (2023-10-11T10:34:52Z)
• PLAN: Variance-Aware Private Mean Estimation [12.452663855242344]
  差分的にプライベートな平均推定は、データ分析と機械学習のためのプライバシ保護アルゴリズムの重要な構成要素である。 ベクトル $boldsymbolsigma$ のスキューを利用する方法を示し、$ell$エラーで(ゼロ桁の)微分プライベート平均推定値を得る。 PLANの有効性を検証するため,合成データと実世界のデータの両方で精度を実証的に評価した。
  論文  参考訳（メタデータ） (2023-06-14T21:04:50Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Near-Optimal Bounds for Testing Histogram Distributions [35.18069719489173]
  ヒストグラム検査問題はサンプル複雑性$widetilde Theta (sqrtnk / varepsilon + k / varepsilon2 + sqrtn / varepsilon2)$であることを示す。
  論文  参考訳（メタデータ） (2022-07-14T01:24:01Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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