論文の概要: DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding Windows (Technical Report)
- arxiv url: http://arxiv.org/abs/2406.07953v1
- Date: Wed, 12 Jun 2024 07:24:19 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-13 18:05:32.495809
- Title: DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding Windows (Technical Report)
- Title（参考訳）: DPSW-Sketch:スライディングウィンドウ上での周波数推定のための微分プライベートスケッチフレームワーク(技術的報告)
- Authors: Yiping Wang, Yanhao Wang, Cen Chen,
- Abstract要約: textscDPSW-Sketchは、カウントミンスケッチに基づいたスライドウィンドウフレームワークである。
我々は、textscDPSW-Sketchが最先端の方法よりもはるかに優れたユーティリティプライバシトレードオフを提供することを示した。
- 参考スコア（独自算出の注目度）: 17.975365337852345
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The sliding window model of computation captures scenarios in which data are continually arriving in the form of a stream, and only the most recent $w$ items are used for analysis. In this setting, an algorithm needs to accurately track some desired statistics over the sliding window using a small space. When data streams contain sensitive information about individuals, the algorithm is also urgently needed to provide a provable guarantee of privacy. In this paper, we focus on the two fundamental problems of privately (1) estimating the frequency of an arbitrary item and (2) identifying the most frequent items (i.e., \emph{heavy hitters}), in the sliding window model. We propose \textsc{DPSW-Sketch}, a sliding window framework based on the count-min sketch that not only satisfies differential privacy over the stream but also approximates the results for frequency and heavy-hitter queries within bounded errors in sublinear time and space w.r.t.~$w$. Extensive experiments on five real-world and synthetic datasets show that \textsc{DPSW-Sketch} provides significantly better utility-privacy trade-offs than state-of-the-art methods.
- Abstract（参考訳）: 計算のスライディングウィンドウモデルは、データがストリームの形式で継続的に到着するシナリオをキャプチャし、分析に使用されるのは最新の$w$アイテムのみである。
この設定では、小さな空間を用いてスライディングウィンドウ上で所望の統計を正確に追跡する必要がある。
データストリームが個人に関する機密情報を含んでいる場合、このアルゴリズムは、証明可能なプライバシー保証を提供するために緊急に必要である。
本稿では,(1)任意の項目の頻度を推定し,(2)最も頻繁な項目(例えば \emph{heavy Hitters} )をスライディングウィンドウモデルで同定する,という2つの基本的な問題に焦点をあてる。
我々は,ストリーム上の差分プライバシーを満足するだけでなく,サブ線形時間と空間w.r.t.~$w$の有界エラーにおける周波数および重ヒッタクエリの結果を近似する,カウントミンスケッチに基づくスライディングウィンドウフレームワークである‘textsc{DPSW-Sketch} を提案する。
5つの実世界および合成データセットに対する大規模な実験により、 \textsc{DPSW-Sketch} は最先端の手法よりもはるかに優れたユーティリティプライバシトレードオフを提供することが示された。
関連論文リスト
- Private Federated Frequency Estimation: Adapting to the Hardness of the
Instance [40.518740805553634]
フェデレート周波数推定(FFE)では、複数のクライアントが協力して、集合データの周波数を推定する。
より実用的なマルチラウンドFEE設定の下では、カウントスケッチの単純な適応は厳密に準最適であることを示す。
そこで本研究では,より高精度なハイブリッドスケッチアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-15T17:30:03Z) - On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
差分プライバシーと適応データ分析の2つの関連分野の空間複雑性について検討する。
差分プライバシーで効率的に解くために指数関数的に多くの空間を必要とする問題Pが存在することを示す。
アダプティブデータ分析の研究の行は、アダプティブクエリのシーケンスに応答するのに必要なサンプルの数を理解することに焦点を当てている。
論文 参考訳（メタデータ） (2023-02-11T14:45:31Z) - Normalized/Clipped SGD with Perturbation for Differentially Private
Non-Convex Optimization [94.06564567766475]
DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。
DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
論文 参考訳（メタデータ） (2022-06-27T03:45:02Z) - Continual and Sliding Window Release for Private Empirical Risk
Minimization [7.054093620465401]
本稿では、最近のデータウインドウのモデルを継続的にリリースする、正規化された経験的リスク最小化アルゴリズムについて述べる。
無限の時間的地平線上でモデルをリリースしても、任意のデータポイントのプライバシコストは、一定の$epsilon$差分プライバシーによって制限される。
論文 参考訳（メタデータ） (2022-03-07T18:44:16Z) - Improved, Deterministic Smoothing for L1 Certified Robustness [119.86676998327864]
分割雑音を伴う非加法的決定論的平滑化法(dssn)を提案する。
一様加法平滑化とは対照的に、ssn認証は無作為なノイズコンポーネントを独立に必要としない。
これは、規範ベースの敵対的脅威モデルに対して決定論的「ランダム化平滑化」を提供する最初の仕事である。
論文 参考訳（メタデータ） (2021-03-17T21:49:53Z) - Learning with User-Level Privacy [61.62978104304273]
ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。
個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。
プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
論文 参考訳（メタデータ） (2021-02-23T18:25:13Z) - Robust and Differentially Private Mean Estimation [40.323756738056616]
異なるプライバシーは、米国国勢調査から商用デバイスで収集されたデータまで、さまざまなアプリケーションで標準要件として浮上しています。
このようなデータベースの数は、複数のソースからのデータからなり、それらすべてが信頼できるわけではない。
これにより、既存のプライベート分析は、腐敗したデータを注入する敵による攻撃に弱い。
論文 参考訳（メタデータ） (2021-02-18T05:02:49Z) - Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy
Amplification by Shuffling [49.43288037509783]
ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。
私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
論文 参考訳（メタデータ） (2020-12-23T17:07:26Z) - A One-Pass Private Sketch for Most Machine Learning Tasks [48.17461258268463]
差別化プライバシ(DP)は、正式な証明可能な保証を通じて、プライバシとユーティリティのトレードオフを説明する魅力的なプライバシ定義である。
本稿では,回帰,分類,密度推定など,多数の機械学習タスクをサポートするプライベートスケッチを提案する。
このスケッチは,局所性に敏感なハッシュをインデックス化して,効率的なワンパスアルゴリズムで構築したランダムな一致テーブルで構成されている。
論文 参考訳（メタデータ） (2020-06-16T17:47:48Z) - Continuous Release of Data Streams under both Centralized and Local
Differential Privacy [30.998501044718548]
差分プライバシ(DP)を満たす実数値データストリームの公開問題について検討する。
最大の課題は、最大値が非常に大きいことだ。
本研究では,実用目標をよく近似する品質関数を備えた指数メカニズムを用いた手法を開発した。
論文 参考訳（メタデータ） (2020-05-24T14:25:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。