論文の概要: Scalable Differentially Private Sketches under Continual Observation

• arxiv url: http://arxiv.org/abs/2507.03361v2
• Date: Wed, 16 Jul 2025 09:23:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-17 14:40:09.54692
• Title: Scalable Differentially Private Sketches under Continual Observation
• Title（参考訳）: 連続観察下でのスケーラブルな微分プライベートスケッチ
• Authors: Rayne Holland,
• Abstract要約: Sketchesはデータストリーム分析の基本的なツールであり、近似周波数クエリと重いヒットター検出の両方をサポートする。 連続観察モデルにおいて、新しい微分プライベートスケッチ法であるLazy Sketchを紹介する。 提案手法は,前処理のスループットを最大250倍に向上させ,高速ストリーミングアプリケーションにおいて連続的な観測差分プライバシーを実現する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sketches are a fundamental tool in data stream analytics. They are notable for supporting both approximate frequency queries and heavy hitter detection with bounded trade-offs for error and memory. Importantly, on streams that contain sensitive information, sketches can be easily privatized with the injection of a suitable amount of noise. This process is efficient in the single-release model, where the output is released only at the end of the stream. In this setting, it suffices to add noise to the sketch once. In contrast, in the continual observation model, where the output is released at every time-step, noise needs to be added to the sketch before each release. This creates an additional computational overhead. To address this, we introduce Lazy Sketch, a novel differentially private sketching method, in the continual observation model, that employs lazy updates, perturbing and modifying only a small portion of the sketch at each step. Compared to prior work, we reduce the update complexity by a factor of $O(w)$, where $w$ is the width of the sketch. Experiments demonstrate that our method increases throughput by up to 250x over prior work, making continual observation differential privacy practical for high-speed streaming applications. In addition, for heavy hitter detection, we present a new sketch-based algorithm that leverages lazy updates to achieve a per-update complexity of $O(d \log T/w + \log w)$, for sketches with dimension $d\times w$ and streams of length $T$. This marks a significant improvement over prior approaches in the streaming continual observation model, which require recomputing frequency estimates for every item in the input domain at each time step.
• Abstract（参考訳）: Sketchesはデータストリーム分析の基本的なツールである。 これらは、エラーとメモリのトレードオフによって、近似周波数クエリと重いヒットタ検出の両方をサポートすることで有名である。 重要なことに、センシティブな情報を含むストリームでは、適切な量のノイズを注入することで、スケッチを簡単に民営化することができる。 このプロセスは単一リリースモデルで効率的であり、出力はストリームの最後にのみ解放される。 この設定では、一度スケッチにノイズを加えるだけで十分です。 対照的に、連続的な観察モデルでは、出力が毎回解放されるため、各リリースの前にスケッチにノイズを追加する必要がある。 これにより計算オーバーヘッドが増大する。 これを解決するために,遅延更新,摂動,各ステップにおけるスケッチのごく一部のみを修正した,新しい微分プライベートスケッチ手法であるLazy Sketchを連続観察モデルに導入する。 以前の作業と比較して、更新の複雑さを$O(w)$で減らします。 実験により,本手法は前処理のスループットを最大250倍に向上させ,高速ストリーミングアプリケーションにおいて連続的な観察差分プライバシーの実現を可能にする。 さらに,重み付きヒッタ検出のために,遅延更新を利用する新しいスケッチベースアルゴリズムを提案する。これは,次元が$d\times w$のスケッチに対して,$O(d \log T/w + \log w)$の更新毎の複雑性を実現するためである。 ストリーミング連続観測モデルでは、各タイミングで入力領域の各項目の周波数推定を再計算する必要がある。

関連論文リスト

• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。 実現可能な最小二乗の設定において、新しい最上界を創出する。 我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
  論文  参考訳（メタデータ） (2025-04-06T18:39:45Z)
• Linear-Time User-Level DP-SCO via Robust Statistics [55.350093142673316]
  ユーザレベルの差分プライベート凸最適化(DP-SCO)は、マシンラーニングアプリケーションにおけるユーザのプライバシ保護の重要性から、大きな注目を集めている。 微分プライベート勾配勾配(DP-SGD)に基づくような現在の手法は、しばしば高雑音蓄積と準最適利用に苦しむ。 これらの課題を克服するために、ロバストな統計、特に中央値とトリミング平均を利用する新しい線形時間アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2025-02-13T02:05:45Z)
• Towards Scalable and Deep Graph Neural Networks via Noise Masking [59.058558158296265]
  グラフニューラルネットワーク(GNN)は多くのグラフマイニングタスクで顕著に成功している。 計算とストレージのコストが高いため、大きなグラフにスケールすることは困難です。 既存のモデル単純化作業と互換性のあるプラグアンドプレイモジュールであるノイズマスキング(RMask)を用いたランダムウォークを提案する。
  論文  参考訳（メタデータ） (2024-12-19T07:48:14Z)
• S$^3$Attention: Improving Long Sequence Attention with Smoothed Skeleton Sketching [51.38617149946765]
  本稿ではスムースなスケルトンスケッチに基づくアテンション構造S$3$Attentionを提案する。 S$3$Attentionは、線形複雑性をシーケンス長に保ちながら、ノイズの影響を効果的に最小化する2つのメカニズムを持つ。
  論文  参考訳（メタデータ） (2024-08-16T07:01:46Z)
• DPSW-Sketch: A Differentially Private Sketch Framework for Frequency Estimation over Sliding Windows (Technical Report) [17.975365337852345]
  textscDPSW-Sketchは、カウントミンスケッチに基づいたスライドウィンドウフレームワークである。 我々は、textscDPSW-Sketchが最先端の方法よりもはるかに優れたユーティリティプライバシトレードオフを提供することを示した。
  論文  参考訳（メタデータ） (2024-06-12T07:24:19Z)
• PeFAD: A Parameter-Efficient Federated Framework for Time Series Anomaly Detection [51.20479454379662]
  私たちはaを提案します。 フェデレートされた異常検出フレームワークであるPeFADは、プライバシーの懸念が高まっている。 我々は、4つの実際のデータセットに対して広範な評価を行い、PeFADは既存の最先端ベースラインを最大28.74%上回っている。
  論文  参考訳（メタデータ） (2024-06-04T13:51:08Z)
• Graph Spatiotemporal Process for Multivariate Time Series Anomaly Detection with Missing Values [67.76168547245237]
  本稿では,グラフ時間過程と異常スコアラを用いて異常を検出するGST-Proという新しいフレームワークを提案する。 実験結果から,GST-Pro法は時系列データ中の異常を効果的に検出し,最先端の手法より優れていることがわかった。
  論文  参考訳（メタデータ） (2024-01-11T10:10:16Z)
• TFMQ-DM: Temporal Feature Maintenance Quantization for Diffusion Models [52.454274602380124]
  拡散モデルは非常に時間ステップ$t$に大きく依存し、良好なマルチラウンドデノジングを実現している。 本稿では,時間情報ブロック上に構築した時間的特徴保守量子化(TFMQ)フレームワークを提案する。 先駆的なブロック設計により、時間情報認識再構成(TIAR)と有限集合キャリブレーション(FSC)を考案し、完全な時間的特徴を整列させる。
  論文  参考訳（メタデータ） (2023-11-27T12:59:52Z)
• Differentially Private Statistical Inference through $\beta$-Divergence One Posterior Sampling [2.8544822698499255]
  本稿では,モデルとデータ生成プロセス間の$beta$-divergenceの最小化を目標とした,一般化後部からの後部サンプリング手法を提案する。 これにより、基礎となるモデルの変更を必要とせずに、一般的に適用可能なプライベートな推定が可能になる。 我々は、$beta$D-Bayesが同一のプライバシー保証に対してより正確な推測を行うことを示す。
  論文  参考訳（メタデータ） (2023-07-11T12:00:15Z)
• Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability [22.90127105925077]
  本稿では,大規模分散学習環境における一階法のための新しいスケッチ手法を提案する。 スケッチ手法を適用した後も勾配漏れの問題が残っていることを示す。 その結果,勾配情報にランダムノイズを加えることで,アルゴリズムが微分プライベートになることを厳格に証明した。
  論文  参考訳（メタデータ） (2022-10-15T20:44:15Z)
• Continual and Sliding Window Release for Private Empirical Risk Minimization [7.054093620465401]
  本稿では、最近のデータウインドウのモデルを継続的にリリースする、正規化された経験的リスク最小化アルゴリズムについて述べる。 無限の時間的地平線上でモデルをリリースしても、任意のデータポイントのプライバシコストは、一定の$epsilon$差分プライバシーによって制限される。
  論文  参考訳（メタデータ） (2022-03-07T18:44:16Z)
• Improving \ extit{Tug-of-War} sketch using Control-Variates method [0.12891210250935145]
  我々はモンテカルロ・シミュレーションの分散還元で主に知られている古典的な制御-分散性ラベンベルクの手法を用いる。 本稿では,提案手法の理論的解析を行い,実世界のデータセットと合成実験を補完する。
  論文  参考訳（メタデータ） (2022-03-04T17:01:42Z)
• Oblivious sketching for logistic regression [72.42202783677811]
  本稿では,ロジスティック回帰のための最初のデータ難読スケッチを示す。 私たちのスケッチは速く、シンプルで、実装も簡単です。
  論文  参考訳（メタデータ） (2021-07-14T11:29:26Z)
• ${\ m N{\small ode}S{\small ig}}$: Random Walk Diffusion meets Hashing for Scalable Graph Embeddings [7.025709586759654]
  $rm Nsmall odeSsmall ig$は、バイナリノード表現を計算するスケーラブルな埋め込みモデルである。 $rm N Small odeS Small ig$は、ランダムなウォーク拡散確率を、安定したランダムなプロジェクションハッシュを通じて活用する。
  論文  参考訳（メタデータ） (2020-10-01T09:07:37Z)
• WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement [75.12782480740822]
  We design novel composable sketches for WOR $ell_p$ sample。 私たちのスケッチは、サンプルサイズと直線的にしか成長しないサイズです。 我々の方法は、最初に$p>1$の重要なレギュレーションでWORサンプリングを提供し、最初に$p>0$で署名された更新を処理する。
  論文  参考訳（メタデータ） (2020-07-14T00:19:27Z)
• A One-Pass Private Sketch for Most Machine Learning Tasks [48.17461258268463]
  差別化プライバシ(DP)は、正式な証明可能な保証を通じて、プライバシとユーティリティのトレードオフを説明する魅力的なプライバシ定義である。 本稿では,回帰,分類,密度推定など,多数の機械学習タスクをサポートするプライベートスケッチを提案する。 このスケッチは,局所性に敏感なハッシュをインデックス化して,効率的なワンパスアルゴリズムで構築したランダムな一致テーブルで構成されている。
  論文  参考訳（メタデータ） (2020-06-16T17:47:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。