論文の概要: Differentially Private Set Union
- arxiv url: http://arxiv.org/abs/2002.09745v2
- Date: Wed, 6 Apr 2022 23:04:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-29 19:11:19.589668
- Title: Differentially Private Set Union
- Title（参考訳）: Differentially Private Set Union
- Authors: Sivakanth Gopi, Pankaj Gulhane, Janardhan Kulkarni, Judy Hanwen Shen,
Milad Shokouhi and Sergey Yekhanin
- Abstract要約: 差分プライバシーのグローバルモデルにおけるセットユニオンの基本動作について検討する。
この問題では、無限の大きさのアイテムが$U$で、データベースが$D$である。
我々は、$S のサブセットである cup_i W_i$ を出力する(epsilon$,$delta$)-微分プライベートなアルゴリズムを望んでいる。
- 参考スコア（独自算出の注目度）: 23.001440922454407
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the basic operation of set union in the global model of differential
privacy. In this problem, we are given a universe $U$ of items, possibly of
infinite size, and a database $D$ of users. Each user $i$ contributes a subset
$W_i \subseteq U$ of items. We want an ($\epsilon$,$\delta$)-differentially
private algorithm which outputs a subset $S \subset \cup_i W_i$ such that the
size of $S$ is as large as possible. The problem arises in countless real world
applications; it is particularly ubiquitous in natural language processing
(NLP) applications as vocabulary extraction. For example, discovering words,
sentences, $n$-grams etc., from private text data belonging to users is an
instance of the set union problem.
Known algorithms for this problem proceed by collecting a subset of items
from each user, taking the union of such subsets, and disclosing the items
whose noisy counts fall above a certain threshold. Crucially, in the above
process, the contribution of each individual user is always independent of the
items held by other users, resulting in a wasteful aggregation process, where
some item counts happen to be way above the threshold. We deviate from the
above paradigm by allowing users to contribute their items in a
$\textit{dependent fashion}$, guided by a $\textit{policy}$. In this new
setting ensuring privacy is significantly delicate. We prove that any policy
which has certain $\textit{contractive}$ properties would result in a
differentially private algorithm. We design two new algorithms, one using
Laplace noise and other Gaussian noise, as specific instances of policies
satisfying the contractive properties. Our experiments show that the new
algorithms significantly outperform previously known mechanisms for the
problem.
- Abstract（参考訳）: 差分プライバシーのグローバルモデルにおけるセットユニオンの基本動作について検討する。
この問題では、無限の大きさのアイテムが$U$で、データベースが$D$である。
各ユーザ$i$は、サブセット$W_i \subseteq U$のアイテムをコントリビュートする。
私たちは、$s$のサイズが可能な限り大きいように、サブセット$s \subset \cup_i w_i$を出力する($\epsilon$,$\delta$)-微分的プライベートアルゴリズムが欲しいです。
特に自然言語処理(nlp)アプリケーションにおいて語彙抽出としてユビキタスである。
例えば、ユーザーに属するプライベートテキストデータから単語、文、$n$-grams等を発見することは、セットユニオン問題の一例である。
この問題の既知のアルゴリズムは、各ユーザからアイテムのサブセットを収集し、それらのサブセットの結合を取り、ノイズが一定のしきい値を超えているアイテムを開示する。
重要なことに、上記のプロセスでは、個々のユーザのコントリビューションは、常に他のユーザの保持するアイテムとは独立しており、結果として無駄な集約プロセスが発生します。
上記のパラダイムから逸脱し、ユーザが$\textit{dependent fashion}$でアイテムをコントリビュートできるようにし、$\textit{policy}$でガイドします。
この新しい設定では、プライバシーは極めてデリケートだ。
特定の$\textit{contractive}$プロパティを持つ任意のポリシーが、微分プライベートアルゴリズムをもたらすことを証明します。
制約特性を満たすポリシーの具体例として,ラプラスノイズとガウス雑音を用いた2つの新しいアルゴリズムを設計した。
実験の結果, このアルゴリズムは, 既知のメカニズムを著しく上回っていることがわかった。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。
近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。
ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
論文 参考訳（メタデータ） (2023-09-21T21:51:55Z) - Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - A bounded-noise mechanism for differential privacy [3.9596068699962323]
ベクトル $vecx(i) の平均 $frac1nsum_i=1n vecx(i)$ を [0,1]k$ で出力し、任意の $vecx(i)$ に対してプライバシーを保持します。
我々は、ほとんどの値$delta$に対して最適な$ell_infty$エラーを持つ$(epsilon,delta)$-privateメカニズムを示す。
論文 参考訳（メタデータ） (2020-12-07T16:03:21Z) - The Sparse Vector Technique, Revisited [67.57692396665915]
我々は、微分プライバシーの文献において最も基礎的で広く適用可能なテクニックの1つを再考する。
この単純なアルゴリズムは、データベース上のあるクエリの値が、私たちが期待している値に近いかどうかをプライベートにテストします。
一つの個人が過剰なクエリの回答に寄与しない限り、クエリのテストを継続できる代替の、等しくシンプルなアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-02T10:50:52Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳（メタデータ） (2020-09-21T04:13:34Z) - Learning discrete distributions: user vs item-level privacy [47.05234904407048]
近年,フェデレート学習のような実践的なアプリケーションでは,単一ユーザのすべての項目に対するプライバシ保護が求められている。
ユーザレベルの差分プライバシーを持つシンボルを$k$で学習する際の基本的な問題について検討する。
ユーザ数が$tildemathcalO(k/(malpha2) + k/sqrtmepsilonalpha)$とスケールする仕組みを提案する。
論文 参考訳（メタデータ） (2020-07-27T16:15:14Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。