論文の概要: Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation
- arxiv url: http://arxiv.org/abs/2306.06723v3
- Date: Wed, 10 Jul 2024 19:18:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-13 00:07:09.737134
- Title: Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation
- Title（参考訳）: 連続観測下での差分プライバシーを持つ旋律モデルにおける固有要素の計数
- Authors: Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith,
- Abstract要約: 挿入や削除を処理するすべての異なるプライベートなメカニズムは、比較的弱いイベントレベルのプライバシ定義の下でも、最低でもT1/4$の付加エラーがあることを示す。
最大フリップパンシー$w$を持つすべてのターンタイルストリームに対して、$O(sqrtw cdot polylog T)$加法誤差で異なる要素の数を連続的に出力するアイテムレベル微分プライベート機構を提案する。
- 参考スコア（独自算出の注目度）: 3.9476868147424162
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Privacy is a central challenge for systems that learn from sensitive data sets, especially when a system's outputs must be continuously updated to reflect changing data. We consider the achievable error for differentially private continual release of a basic statistic - the number of distinct items - in a stream where items may be both inserted and deleted (the turnstile model). With only insertions, existing algorithms have additive error just polylogarithmic in the length of the stream $T$. We uncover a much richer landscape in the turnstile model, even without considering memory restrictions. We show that every differentially private mechanism that handles insertions and deletions has worst-case additive error at least $T^{1/4}$ even under a relatively weak, event-level privacy definition. Then, we identify a parameter of the input stream, its maximum flippancy, that is low for natural data streams and for which we give tight parameterized error guarantees. Specifically, the maximum flippancy is the largest number of times that the contribution of a single item to the distinct elements count changes over the course of the stream. We present an item-level differentially private mechanism that, for all turnstile streams with maximum flippancy $w$, continually outputs the number of distinct elements with an $O(\sqrt{w} \cdot poly\log T)$ additive error, without requiring prior knowledge of $w$. We prove that this is the best achievable error bound that depends only on $w$, for a large range of values of $w$. When $w$ is small, the error of our mechanism is similar to the polylogarithmic in $T$ error in the insertion-only setting, bypassing the hardness in the turnstile model.
- Abstract（参考訳）: プライバシは、センシティブなデータセットから学ぶシステムにとって、特に変化するデータを反映するためにシステムのアウトプットを継続的に更新する必要がある場合において、中心的な課題である。
我々は、アイテムの挿入と削除の両方が可能なストリーム(ターンタイルモデル)において、基本統計量(異なるアイテムの数)を微分的にプライベートにリリースする際の達成可能なエラーについて検討する。
挿入のみの場合、既存のアルゴリズムはストリームの長さが$T$の付加誤差を持つ。
メモリ制限を考慮せずにターンタイルモデルで、はるかにリッチなランドスケープを発見しました。
挿入や削除を処理するすべての微分プライベートなメカニズムは、比較的弱いイベントレベルのプライバシ定義の下でも、最悪の追加エラーを少なくとも$T^{1/4}$で発生します。
そして,入力ストリームのパラメータ,最大浮動小数点数,自然データストリームの低いパラメータを同定し,パラメータ化誤差を厳格に保証する。
具体的には、最大フリップパシーは、異なる要素に対する1つのアイテムの寄与がストリームの途中で変化を計上する最大の回数である。
最大フリップパンシー$w$を持つすべてのターンタイルストリームに対して、$O(\sqrt{w} \cdot poly\log T)$加法誤差を$w$の事前知識を必要とせずに連続的に出力するアイテムレベルの差分プライベートメカニズムを提案する。
これは、$w$の広い範囲の値に対して、$w$のみに依存する最も達成可能なエラー境界であることを示す。
w$ が小さい場合、我々の機構の誤差は挿入のみの設定における$T$ の誤差と類似しており、ターンタイルモデルの硬さを回避している。
関連論文リスト
- Rate-reliability functions for deterministic identification [49.126395046088014]
正の指数に対して線形スケーリングが復元され、信頼指数の関数であるレートが復元される。
製品入力制限付き古典量子チャネルや量子チャネルに結果を拡張します。
論文 参考訳（メタデータ） (2025-02-04T15:09:14Z) - Privately Counting Partially Ordered Data [50.98561191019676]
各データポイントが部分順序を満たす$d$ビットからなる場合、差分プライベートカウントを考える。
私たちの主な技術的貢献は問題固有の$K$-normメカニズムで、時間内に$O(d2)$を実行します。
論文 参考訳（メタデータ） (2024-10-09T13:43:35Z) - Private Counting of Distinct Elements in the Turnstile Model and Extensions [2.5200018924833327]
スパースベクトル法に基づく非常に単純なアルゴリズムは、アイテムレベルの$(epsilon,delta)$-differential privacyに対して厳密な加算誤差を実現する。
2つ目の結果は、大規模なアルゴリズムでは、アイテムレベルの差分プライバシからイベントレベルの差分プライバシまでのバウンドが低いことを示すバウンドである。
論文 参考訳（メタデータ） (2024-08-21T14:06:22Z) - On Differentially Private U Statistics [25.683071759227293]
局所的なH'ajekプロジェクションを用いて、データの異なる部分集合を再重み付けする新しいしきい値に基づくアプローチを提案する。
これは、非退化U統計に対してほぼ最適なプライベート誤差をもたらし、退化U統計に対してほぼ最適であることを示す強い指標となる。
論文 参考訳（メタデータ） (2024-07-06T03:27:14Z) - Almost Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy [36.04370583654189]
クリッピング機構が$O(max_i x_i cdot loglog U /varepsilon)$のインスタンス最適誤差を実現する方法を示す。
また、この手法を高次元和推定問題とスパースベクトルアグリゲーションに拡張する。
論文 参考訳（メタデータ） (2024-03-15T09:04:00Z) - Provably Efficient High-Dimensional Bandit Learning with Batched
Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。
具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。
我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文 参考訳（メタデータ） (2023-11-22T06:06:54Z) - Differentially Private Clustering in Data Streams [65.78882209673885]
オフラインのDPコアセットやクラスタリングアルゴリズムをブラックボックスとしてのみ必要とする,差分プライベートなストリーミングクラスタリングフレームワークを提案する。
我々のフレームワークはまた、連続的なリリース設定の下で微分プライベートであり、すなわち、全てのタイムスタンプにおけるアルゴリズムの出力の和は常に微分プライベートである。
論文 参考訳（メタデータ） (2023-07-14T16:11:22Z) - Differential Privacy for Clustering Under Continual Observation [5.220940151628734]
我々は、点の挿入と削除の両方を行う$mathbbRd$のデータセットをプライベートにクラスタリングする問題を考える。
連続観測において、$k$-meansの目的に対して、$varepsilon$-differentially private clustering 機構を提供する。
論文 参考訳（メタデータ） (2023-07-07T07:23:56Z) - Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
個人的連続和問題(対数問題)について検討する。
並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
論文 参考訳（メタデータ） (2023-01-29T20:42:54Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳（メタデータ） (2020-09-21T04:13:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。