論文の概要: Algorithms for bounding contribution for histogram estimation under user-level privacy

• arxiv url: http://arxiv.org/abs/2206.03008v2
• Date: Fri, 30 Jun 2023 14:21:27 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-03 16:00:17.922342
• Title: Algorithms for bounding contribution for histogram estimation under user-level privacy
• Title（参考訳）: ユーザレベルのプライバシに基づくヒストグラム推定のためのバウンディングコントリビューションアルゴリズム
• Authors: Yuhan Liu, Ananda Theertha Suresh, Wennan Zhu, Peter Kairouz, Marco Gruteser
• Abstract要約: ユーザレベルの差分プライバシー下でのヒストグラム推定の問題点について検討する。 目標は、単一のユーザのすべてのエントリのプライバシを維持することだ。 ヒストグラム推定のための最適なユーザコントリビューションを選択するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 37.406400590568644
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of histogram estimation under user-level differential privacy, where the goal is to preserve the privacy of all entries of any single user. We consider the heterogeneous scenario where the quantity of data can be different for each user. In this scenario, the amount of noise injected into the histogram to obtain differential privacy is proportional to the maximum user contribution, which can be amplified by few outliers. One approach to circumvent this would be to bound (or limit) the contribution of each user to the histogram. However, if users are limited to small contributions, a significant amount of data will be discarded. In this work, we propose algorithms to choose the best user contribution bound for histogram estimation under both bounded and unbounded domain settings. When the size of the domain is bounded, we propose a user contribution bounding strategy that almost achieves a two-approximation with respect to the best contribution bound in hindsight. For unbounded domain histogram estimation, we propose an algorithm that is logarithmic-approximation with respect to the best contribution bound in hindsight. This result holds without any distribution assumptions on the data. Experiments on both real and synthetic datasets verify our theoretical findings and demonstrate the effectiveness of our algorithms. We also show that clipping bias introduced by bounding user contribution may be reduced under mild distribution assumptions, which can be of independent interest.
• Abstract（参考訳）: ユーザレベルの差分プライバシに基づくヒストグラム推定の問題について検討し,その目的は,ユーザのすべてのエントリのプライバシを維持することである。 ユーザ毎にデータの量が異なる異種シナリオを考察する。 このシナリオでは、差分プライバシーを得るためにヒストグラムに注入されるノイズの量は最大ユーザの貢献に比例する。 これを回避する1つのアプローチは、各ユーザのヒストグラムへの貢献を束縛(あるいは制限)することである。 しかし、ユーザーが少額の貢献に制限された場合、かなりの量のデータが破棄される。 本研究では,境界領域と非境界領域の両方において,ヒストグラム推定に最適なユーザ貢献度を選択するアルゴリズムを提案する。 ドメインのサイズが制限されている場合は、後から見て最善の貢献に対してほぼ近似を達成するユーザ貢献バウンディング戦略を提案する。 本研究では,非有界領域ヒストグラム推定法として,最適寄与度に対する対数近似アルゴリズムを提案する。 この結果は、データに対する分布の仮定なしに成り立つ。 実データと合成データの両方における実験は、理論的な知見を検証し、アルゴリズムの有効性を実証する。 また,境界ユーザの貢献によって引き起こされるクリップングバイアスは,独立した関心を持つような軽度分布仮定の下で低減できることを示した。

関連論文リスト

• A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility [4.7712438974100255]
  パーソナライズされたプライバシパラメータで$(epsilon_i,delta_i)$-PLDP設定をシャッフルする方法を示す。 shuffled $(epsilon_i,delta_i)$-PLDP process approximately saves $mu$-Gaussian Differential Privacy with mu = sqrtfrac2sum_i=1n frac1-delta_i1+eepsilon_i-max_ifrac1-delta_i1+e
  論文  参考訳（メタデータ） (2023-12-22T02:31:46Z)
• User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
  サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。 近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。 ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
  論文  参考訳（メタデータ） (2023-09-21T21:51:55Z)
• A Unifying Privacy Analysis Framework for Unknown Domain Algorithms in Differential Privacy [1.5773159234875098]
  我々は、未知のドメイン上でヒストグラムをリリースするための、既存の微分プライベートアルゴリズムのいくつかを再検討する。 未知の領域でヒストグラムをリリースする主な実用的利点は、アルゴリズムが欠落したラベルを埋める必要がないことである。 いくつかの既存アルゴリズムのプライバシー分析のための統一的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-09-17T05:47:33Z)
• Mean Estimation with User-level Privacy under Data Heterogeneity [54.07947274508013]
  異なるユーザーは、非常に多くの異なるデータポイントを持っているかもしれない。 すべてのユーザが同じディストリビューションからサンプルを採取していると仮定することはできない。 本研究では,データの分布と量の両方でユーザデータが異なる異質なユーザデータの単純なモデルを提案する。
  論文  参考訳（メタデータ） (2023-07-28T23:02:39Z)
• Unbounded Differentially Private Quantile and Maximum Estimation [2.855485723554975]
  単純な$textttAboveThreshold$の呼び出しは、最高の量子化に対してより正確でロバストな見積もりを提供する。 我々は、textttAboveThreshold$を改良することで、広く使われているスパースベクトルテクニックのプライバシー保証を改善することができることを示す。
  論文  参考訳（メタデータ） (2023-05-02T03:23:07Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。 我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
  論文  参考訳（メタデータ） (2022-05-28T15:37:03Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)

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

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