論文の概要: 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つのアプローチは、各ユーザのヒストグラムへの貢献を束縛(あるいは制限)することである。 しかし、ユーザーが少額の貢献に制限された場合、かなりの量のデータが破棄される。 本研究では,境界領域と非境界領域の両方において,ヒストグラム推定に最適なユーザ貢献度を選択するアルゴリズムを提案する。 ドメインのサイズが制限されている場合は、後から見て最善の貢献に対してほぼ近似を達成するユーザ貢献バウンディング戦略を提案する。 本研究では,非有界領域ヒストグラム推定法として,最適寄与度に対する対数近似アルゴリズムを提案する。 この結果は、データに対する分布の仮定なしに成り立つ。 実データと合成データの両方における実験は、理論的な知見を検証し、アルゴリズムの有効性を実証する。 また,境界ユーザの貢献によって引き起こされるクリップングバイアスは,独立した関心を持つような軽度分布仮定の下で低減できることを示した。

関連論文リスト

• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  ユーザレベルの差分プライベート凸最適化(DP-SCO)は、マシンラーニングアプリケーションにおけるユーザのプライバシ保護の重要性から、大きな注目を集めている。 微分プライベート勾配勾配(DP-SGD)に基づくような現在の手法は、しばしば高雑音蓄積と準最適利用に苦しむ。 これらの課題を克服するために、ロバストな統計、特に中央値とトリミング平均を利用する新しい線形時間アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-02-13T02:05:45Z)
• Scalable Private Partition Selection via Adaptive Weighting [66.09199304818928]
  プライベート・セット・ユニオンでは、ユーザーは非有界宇宙からのアイテムのサブセットを保持する。 目標は、ユーザレベルの差分プライバシーを維持しながら、ユーザセットの統一から可能な限り多くのアイテムを出力することである。 そこで本研究では,プライバシに必要なしきい値よりもはるかに重い項目からより少ない項目へ適応的に重みを還元するアルゴリズムであるMaximumDegree (MAD)を提案する。
  論文  参考訳（メタデータ） (2025-02-13T01:27:11Z)
• 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)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)

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

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