論文の概要: On Distributed Differential Privacy and Counting Distinct Elements
- arxiv url: http://arxiv.org/abs/2009.09604v1
- Date: Mon, 21 Sep 2020 04:13:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-16 04:32:06.039097
- Title: On Distributed Differential Privacy and Counting Distinct Elements
- Title（参考訳）: 分散微分プライバシーと個別要素のカウントについて
- Authors: Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi
- Abstract要約: 我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
- 参考スコア（独自算出の注目度）: 52.701425652208734
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the setup where each of $n$ users holds an element from a discrete
set, and the goal is to count the number of distinct elements across all users,
under the constraint of $(\epsilon, \delta)$-differentially privacy:
- In the non-interactive local setting, we prove that the additive error of
any protocol is $\Omega(n)$ for any constant $\epsilon$ and for any $\delta$
inverse polynomial in $n$.
- In the single-message shuffle setting, we prove a lower bound of
$\Omega(n)$ on the error for any constant $\epsilon$ and for some $\delta$
inverse quasi-polynomial in $n$. We do so by building on the moment-matching
method from the literature on distribution estimation.
- In the multi-message shuffle setting, we give a protocol with at most one
message per user in expectation and with an error of $\tilde{O}(\sqrt(n))$ for
any constant $\epsilon$ and for any $\delta$ inverse polynomial in $n$. Our
protocol is also robustly shuffle private, and our error of $\sqrt(n)$ matches
a known lower bound for such protocols.
Our proof technique relies on a new notion, that we call dominated protocols,
and which can also be used to obtain the first non-trivial lower bounds against
multi-message shuffle protocols for the well-studied problems of selection and
learning parity.
Our first lower bound for estimating the number of distinct elements provides
the first $\omega(\sqrt(n))$ separation between global sensitivity and error in
local differential privacy, thus answering an open question of Vadhan (2017).
We also provide a simple construction that gives $\tilde{\Omega}(n)$ separation
between global sensitivity and error in two-party differential privacy, thereby
answering an open question of McGregor et al. (2011).
- Abstract（参考訳）: 我々は、n$ ユーザの各要素が離散集合の要素を持ち、そのゴールは $(\epsilon, \delta)$-differentially privacy という制約の下で、全ユーザにわたって異なる要素の数を数えることである: - 非対話的な局所的な設定では、任意のプロトコルの加算誤差が任意の定数 $\epsilon$ に対して$\omega(n)$であることと、任意の $\delta$ 逆多項式に対して$n$ であることを証明する。
- シングルメッセージシャッフル設定では、任意の定数$\epsilon$に対するエラーに対して$\Omega(n)$の低い境界を証明し、ある$\delta$ inverse quasi-polynomial in $n$に対して。
我々は,分布推定に関する文献からモーメントマッチング法を構築した。
- マルチメッセージシャッフル設定では、期待して1ユーザ当たり少なくとも1つのメッセージと、任意の定数$\epsilon$と$n$の$\delta$逆多項式に対して$\tilde{O}(\sqrt(n))$のエラーを持つプロトコルを提供します。
我々のプロトコルは、厳密にシャッフルされ、そのエラー$\sqrt(n)$は、そのようなプロトコルの既知の下限と一致する。
私たちの証明テクニックは、支配的なプロトコルと呼ばれる新しい概念に依存しており、選択と学習のパリティのよく研究された問題に対するマルチメッセージシャッフルプロトコルに対する最初の非自明な下限を得るのにも利用できる。
異なる要素の数を推定するための最初の下限は、グローバルな感度と局所的な差分プライバシーにおけるエラーを分離する最初の$\omega(\sqrt(n))$である。
また,二者差動プライバシにおけるグローバル感度と誤差の分離を$\tilde{\omega}(n)$ とすることで,mcgregor et al. (2011) の疑問に答える簡単な構成を提供する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Asynchronous Approximate Agreement with Quadratic Communication [23.27199615640474]
非同期ネットワークは$n$のメッセージ送信パーティで、そのうちの最大$t$はビザンチンです。
本研究では,入力の凸内積にほぼ等しい出力が得られるような近似一致について検討する。
これは、信頼できるブロードキャスト毎に$Theta(n2)$メッセージ、またはイテレーション毎に$Theta(n3)$メッセージを取る。
論文 参考訳（メタデータ） (2024-08-10T09:03:06Z) - Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。
我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
論文 参考訳（メタデータ） (2024-04-16T00:56:36Z) - Differentially Private Approximate Pattern Matching [0.0]
我々は差分プライバシー下での$k$-approximateパターンマッチング問題を考察する。
目的は、与えられた文字列のalimate variantsを報告またはカウントすることであり、これは、最大$k$のハミング距離を持つ$S$からパターン$P$までである。
1)$epsilon$-differentially private algorithm with a additive error of $O(epsilon-1log n)$ and no multiplicative error for the existence variant; 2) $epsilon$-differentially private algorithm with an additive error $O(epsilon-1)
論文 参考訳（メタデータ） (2023-11-13T15:53:45Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Tight Bounds for the Randomized and Quantum Communication Complexities
of Equality with Small Error [1.6522364074260811]
誤差が小さいEquality関数のランダム化および量子化通信複雑性を$epsilon$で調べる。
任意の$log(n/epsilon)-log(sqrtn/epsilon)+3$プロトコルが少なくとも$log(n/epsilon)-log(sqrtn/epsilon)-O(1)$ qubitsを通信することを示す。
論文 参考訳（メタデータ） (2021-07-25T13:52:42Z) - On Avoiding the Union Bound When Answering Multiple Differentially
Private Queries [49.453751858361265]
このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。
一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
論文 参考訳（メタデータ） (2020-12-16T17:58:45Z) - 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) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。