論文の概要: Accelerating Private Heavy Hitter Detection on Continual Observation Streams

• arxiv url: http://arxiv.org/abs/2507.03361v1
• Date: Fri, 04 Jul 2025 07:49:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-08 15:46:34.704204
• Title: Accelerating Private Heavy Hitter Detection on Continual Observation Streams
• Title（参考訳）: 連続観測ストリームにおけるプライベートヘビーヒッタ検出の高速化
• Authors: Rayne Holland,
• Abstract要約: 遅延更新に基づく新たな微分プライベートスケッチ技術を導入し、各ステップで出力スケッチの小さな回転部分のみを摂動・更新する。 実験の結果、スループットが250ドル向上し、リアルタイム、連続観察、アプリケーションに差分プライバシーをより実用的なものにしている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Differentially private frequency estimation and heavy hitter detection are core problems in the private analysis of data streams. Two models are typically considered: the one-pass model, which outputs results only at the end of the stream, and the continual observation model, which requires releasing private summaries at every time step. While the one-pass model allows more efficient solutions, continual observation better reflects scenarios where timely and ongoing insights are critical. In the one-pass setting, sketches have proven to be an effective tool for differentially private frequency analysis, as they can be privatized by a single injection of calibrated noise. In contrast, existing methods in the continual observation model add fresh noise to the entire sketch at every step, incurring high computational costs. This challenge is particularly acute for heavy hitter detection, where current approaches often require querying every item in the universe at each step, resulting in untenable per-update costs for large domains. To overcome these limitations, we introduce a new differentially private sketching technique based on lazy updates, which perturbs and updates only a small, rotating part of the output sketch at each time step. This significantly reduces computational overhead while maintaining strong privacy and utility guarantees. In comparison to prior art, for frequency estimation, our method improves the update time by a factor of $O(w)$ for sketches of dimension $d \times w$; for heavy hitter detection, it reduces per-update complexity from $\Omega(|U|)$ to $O(d \log w)$, where $U$ is the input domain. Experiments show a increase in throughput by a factor of~$250$, making differential privacy more practical for real-time, continual observation, applications.
• Abstract（参考訳）: データストリームのプライベート分析において、異なるプライベート周波数推定と重ヒッタ検出が中核的な問題である。 ストリームの最後にのみ結果を出力するワンパスモデルと、各ステップでプライベートなサマリーを解放する必要がある連続的な観測モデルである。 ワンパスモデルはより効率的なソリューションを可能にするが、継続的な観察は、時間的および進行中の洞察が重要となるシナリオをよりよく反映する。 ワンパス設定では、スケッチはキャリブレーションノイズの単一注入により民営化できるため、差分プライベート周波数解析に有効なツールであることが証明されている。 対照的に、継続観測モデルの既存の手法は、すべてのステップでスケッチ全体に新しいノイズを与え、高い計算コストを発生させる。 現在のアプローチでは、各ステップで宇宙のすべてのアイテムを問い合わせる必要があり、その結果、大きなドメインの更新コストが不必要になる。 これらの制限を克服するために、遅延更新に基づく新たな微分プライベートスケッチ技術を導入し、各ステップで出力スケッチの小さな回転部分のみを摂動、更新する。 これにより、強力なプライバシとユーティリティ保証を維持しながら、計算オーバーヘッドを大幅に削減できる。 先行技術と比較して、周波数推定では、本手法は、次元$d \times w$のスケッチに対して$O(w)$で更新時間を改善し、重いヒットター検出では、更新時の複雑さを$Omega(|U|)$から$O(d \log w)$に減らし、$U$は入力ドメインである。 実験の結果、スループットは250ドル程度に向上し、リアルタイム、連続観察、アプリケーションに差分プライバシーをより実用的なものにしている。

関連論文リスト

• 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)

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

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