論文の概要: The Sparse Vector Technique, Revisited
- arxiv url: http://arxiv.org/abs/2010.00917v2
- Date: Mon, 16 Nov 2020 14:15:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-12 01:14:53.944607
- Title: The Sparse Vector Technique, Revisited
- Title（参考訳）: スパースベクトル法 再訪しました
- Authors: Haim Kaplan, Yishay Mansour, Uri Stemmer
- Abstract要約: 我々は、微分プライバシーの文献において最も基礎的で広く適用可能なテクニックの1つを再考する。
この単純なアルゴリズムは、データベース上のあるクエリの値が、私たちが期待している値に近いかどうかをプライベートにテストします。
一つの個人が過剰なクエリの回答に寄与しない限り、クエリのテストを継続できる代替の、等しくシンプルなアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 67.57692396665915
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit one of the most basic and widely applicable techniques in the
literature of differential privacy - the sparse vector technique [Dwork et al.,
STOC 2009]. This simple algorithm privately tests whether the value of a given
query on a database is close to what we expect it to be. It allows to ask an
unbounded number of queries as long as the answer is close to what we expect,
and halts following the first query for which this is not the case.
We suggest an alternative, equally simple, algorithm that can continue
testing queries as long as any single individual does not contribute to the
answer of too many queries whose answer deviates substantially form what we
expect. Our analysis is subtle and some of its ingredients may be more widely
applicable. In some cases our new algorithm allows to privately extract much
more information from the database than the original.
We demonstrate this by applying our algorithm to the shifting heavy-hitters
problem: On every time step, each of $n$ users gets a new input, and the task
is to privately identify all the current heavy-hitters. That is, on time step
$i$, the goal is to identify all data elements $x$ such that many of the users
have $x$ as their current input. We present an algorithm for this problem with
improved error guarantees over what can be obtained using existing techniques.
Specifically, the error of our algorithm depends on the maximal number of times
that a single user holds a heavy-hitter as input, rather than the total number
of times in which a heavy-hitter exists.
- Abstract（参考訳）: 我々は、微分プライバシーの文献において最も基礎的で広く適用可能なテクニックの1つ、スパースベクトル技術 [Dwork et al., STOC 2009]を再考する。
この単純なアルゴリズムは、データベース上の与えられたクエリの値が、私たちが期待する値に近いかどうかをプライベートにテストします。
答えが期待に近づいている限り、無制限のクエリを問うことができ、これがそうでない最初のクエリの後に停止する。
我々は、ある個人が、我々が期待するものを実質的に逸脱しているクエリの回答に寄与しない限り、クエリを引き続きテストできる、同等にシンプルなアルゴリズムを提案する。
我々の分析は微妙であり、その成分のいくつかはより広く適用できる可能性がある。
場合によっては、我々の新しいアルゴリズムは、データベースからオリジナルよりもずっと多くの情報をプライベートに抽出することができる。
私たちは、アルゴリズムをシフトするヘビーヒット問題に適用することで、これを実証する: ステップ毎に、$n$のユーザがそれぞれ新しい入力を受け取り、タスクは、現在のヘビーヒットをすべてプライベートに識別する。
つまり、ステップ$i$の時点では、現在の入力として多くのユーザが$x$を持つように、すべてのデータ要素を$x$で識別することが目標だ。
そこで本研究では,既存の手法で得られる誤りの保証を改善するアルゴリズムを提案する。
具体的には,本アルゴリズムの誤差は,単一ユーザが重ヒッタを入力として保持する最大回数に依存するが,重ヒッタが存在する総回数には依存しない。
関連論文リスト
- The Limits of Assumption-free Tests for Algorithm Performance [6.7171902258864655]
与えられたモデリングタスクにおいてアルゴリズムはどの程度うまく機能し、どのアルゴリズムが最善を尽くすか?
一方、特定のトレーニングデータセットに対して$A$を実行して生成された特定の適合モデルが$n$であるのか?
論文 参考訳（メタデータ） (2024-02-12T03:19:30Z) - Auditable Algorithms for Approximate Model Counting [31.609554468870382]
我々は、$Sigma3P$ oracleを呼び出す新しい決定論的近似カウントアルゴリズムを開発したが、より少ない変数で$SigmaP$ oracleを使用して認証することができる。
これは、監査の複雑さが近似カウントの複雑さのためにどのように交換できるかを初めて示す。
論文 参考訳（メタデータ） (2023-12-19T17:47:18Z) - User-Level Differential Privacy With Few Examples Per User [73.81862394073308]
サンプルスカース方式では,各ユーザが少数のサンプルしか持たないため,以下の結果が得られる。
近似DPについては,任意の項目レベルDPアルゴリズムをユーザレベルDPアルゴリズムに汎用変換する。
ユーザレベル設定に指数的機構(McSherry, Talwar FOCS 2007)を適用するための簡単な手法を提案する。
論文 参考訳（メタデータ） (2023-09-21T21:51:55Z) - Unbounded Differentially Private Quantile and Maximum Estimation [2.855485723554975]
単純な$textttAboveThreshold$の呼び出しは、最高の量子化に対してより正確でロバストな見積もりを提供する。
我々は、textttAboveThreshold$を改良することで、広く使われているスパースベクトルテクニックのプライバシー保証を改善することができることを示す。
論文 参考訳（メタデータ） (2023-05-02T03:23:07Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - Memory Bounds for the Experts Problem [53.67419690563877]
専門家のアドバイスによるオンライン学習は、逐次予測の根本的な問題である。
目標は、予測を処理し、最小コストで予測を行うことです。
アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。
論文 参考訳（メタデータ） (2022-04-21T01:22:18Z) - 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) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Quick Streaming Algorithms for Maximization of Monotone Submodular
Functions in Linear Time [16.346069386394703]
単調な部分モジュラー(submodular)の問題を、濃度制約に従えば$n$の基底集合上で考える。
線形時間複雑性を持つ最初の決定論的アルゴリズムを導入し,これらのアルゴリズムはストリーミングアルゴリズムである。
我々のシングルパスアルゴリズムは任意の$c ge 1$に対して$lceil n / c rceil + c$ oracle クエリの定数比を得る。
論文 参考訳（メタデータ） (2020-09-10T16:35:54Z) - Differentially Private Set Union [23.001440922454407]
差分プライバシーのグローバルモデルにおけるセットユニオンの基本動作について検討する。
この問題では、無限の大きさのアイテムが$U$で、データベースが$D$である。
我々は、$S のサブセットである cup_i W_i$ を出力する(epsilon$,$delta$)-微分プライベートなアルゴリズムを望んでいる。
論文 参考訳（メタデータ） (2020-02-22T18:33:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。